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,
- 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.
- Show Hide Cap show or hide the arc capacities
- Clear Graph: Resets the graph by clearing all the nodes
- 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
- 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
In order to run the maxflow algorithm
- 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.
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