Ford Fulkerson
-
addGenerate New Graph
Number of nodes in random graph:
-
file_downloadUpload/Download Graph
Graphs can be stored as json files with the format:
{
"nodes" : [{ "id": 0, "x": -300, "y": 0},
...,{ "id": 4, "x": 300, "y": 0}],
"edges" : [{ "from": 0, "to": 1, "capacity": 2},
...,{ "from": 3, "to": 4, "capacity": 4}]
}
- node coordinates are not required
- node ids must be consecutive
- node 0 is S, and node N is T where N is the number of nodes
For an example, click 'download' for a json representation of the current graph.
-
createDraw New Graph
Follow instructions at top of screen
build residual graph
while(maximum flow has not been found):
search for augmenting path in residual graph from S to T
if augmenting path is found:
for each edge in path:
augment flow along forwards edge
decrement flow along backwards edge
else:
maximum flow has been found: break;
update residual graph
reveal edges in minimum cut
press play to begin.