Quick Directions

Manual Graph Editing:



• 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.

Menus:



• File
• Show Hide Cap show or hide the arc capacities
• Clear Graph: Resets the graph by clearing all the nodes and arcs.
• Exit: Exits the applet window.




• 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.
• Kn: Generates a complete graph.
• Random Gn,p: Adds an arc between every pair of nodes with a given probability.
• Geometric: Considers every pair of nodes and adds an arc between them if their distance is less than some threshold.
• Triangulation: Creates a Delaunay traingulation of the nodes. Note: This construction is rather slow!!
• Create Nodes: 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.
• 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.

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

In order to run the maxflow algorithm

1. Select "Maximum Flow" or "Maximum Flow in slow motion" from the Heuristic menu
2. First select the source and then the sink by clicking on them.

At the end, the algorithm displays

• 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.

---

Back to the Graph Algorithms Applet