**Add Node**: Mouse click in an empty space.**Add Arc**: Mouse click on a node, drag the mouse, and release on another node.**Move Node**: Hold down the SHIFT key when mouse click on a node, and drag.**Delete Node**: Click on a node. The node is painted in red. To delete the node, hit the DELETE key.**Edit Node**: Click on a node. The node is painted in red. To edit the node, hit the letter e key.**Delete Arc**: Do as if adding the arc. The arc is painted in red. To delete the arc, hit the DELETE key.**Edit Arc**: Do as if adding the arc. The arc is painted in red. To edit the arc, hit the letter e key.**Zoom In**: Drag the mouse to the desired region to zoom in on.**Zoom Out**: Press the ESCAPE key.

Manual Graph Editing:

**File****Show Hide Cap**show or hide the arc capacities: Resets the graph by clearing all the nodes and arcs.*Clear Graph*: Exits the applet window.*Exit***Generation**: Various graph node/arc generation algorithms. Length of an arc is always the Euclidean distance between its extremities in the 10000x10000 grid. Graph construction only applies on the nodes that are displayed in the applet window. The capacity of random value between 1 and 5 is assigned to each created arc.: Generates a complete graph.*Kn*: Adds an arc between every pair of nodes with a given probability.*Random Gn,p*: Considers every pair of nodes and adds an arc between them if their distance is less than some threshold.*Geometric*: Creates a Delaunay traingulation of the nodes.*Triangulation**Note: This construction is rather slow!!*: Creates a given number of nodes to the grid. The nodes have a random location in the 10,000x10.000 grid. The graph is reset.*Create Nodes***Maximum Flow Heuristics**: The maximum flow algorithm generates a flow of maximum value from a node called the source to a node called the sink. The flow in each arc is limited to the arc capacity. We use the famous max flow algorithm, called the augmenting path algorithm. At each iteration, the algorithm attempts to find a path from the source to the sink in the residual graph. The capacity of an arc in the residual graph is the original arc capacity minus the flow assigned to this arc in previous iterations. If a path from source to sink is found, a flow of maximum possible value is sent through the path. The algorithm stops when no more such augmenting path can be found.- Select "Maximum Flow" or "Maximum Flow in slow motion" from the Heuristic menu
- First select the source and then the sink by clicking on them.
- In red the edges saturated by the maximum flow
- In blue the edges with some flow but not saturated
- In blue the nodes of the source set (reachable from the source in the
last residual graph).

Remark: Only if "slow motion" was selected.

Menus:

The slow motion of the algorithm exhibits the augmenting paths one by one.

**In order to run the maxflow algorithm**

**At the end, the algorithm displays**

Back to the Graph Algorithms Applet