Maximum flow through a network has many applications, both to practical situations and to theoretical results in graph theory. Students can generally understand the concept of maximum flow, however algorithms for finding maximum flow are based on theoretical results dealing with minimum cuts and augmenting paths.

This module allows students the ability to move through a network to apply the max-flow algorithm, i.e., find augmenting paths, use the path to modify the flow and see the effect of that change. Students will also be able to interactively choose cut sets so that they can see the relationship of cuts to the maximum flow algorithm.

The virtual environment for PC/UNIX platforms was developed with the assistance of Sense8 VR libraries. Users can either augment flow by clicking on vertices to extend paths, or they can test out their ability to find minimum cuts, or they can see the algorithm in action. The web version is an ActiveX plugin. Principal programmer: Alok Shrestha.

screen view of algorithm

Prinicpal Participants:

  Kathy McKeon: Associate Professor of Mathematics

  Elizabeth Kaechele: Studio Art

  Alok Shrestho: Computer Science and Math

Courses where module will be used: