Most graph algorithms do not change the underlying graph, they work on a constant or static graph. A static graph consists of a fixed sequence of nodes and edges. In many cases static graphs are much more efficient (time as well as space efficient) than other graph implementations. LEDA improves the time efficiency of flow algorithms significantly.
What are Static Graphs?
Most graph algorithms do not change the underlying graph, they work on a constant or static graph. A static graph consists of a fixed sequence of nodes and edges. New nodes or edges can be appended only in a construction phase which has to be started by calling G.start_construction() and terminated by G.finish_construction(). After the construction phase both sequences V and E are fixed.
There are different models of static graphs; the class is parameterized by the so called graph category. There are directed graphs, bidirectional graphs, opposite graphs, bidirected graphs and undirected graphs. Currently, the first three are available.
See the manual page for a definition.
Finally static graphs support several efficient ways  efficient compared to using node_arrays, edge_arrays, node_maps, and edge_maps  to associate data with the edges and nodes of the graph.
The manual page explains the details.
Why should you use Static Graphs?
In many cases static graphs are much more efficient (time as well as space efficient) than other graph implementations.
In our experiments, running maxflow algorithms on networks produced by the akgenerator of Cherkassy and Goldberg, we received the following results:
Table of results.
The running time improvement is up to 65% (or even up to 75% if we compare static graphs using static slots with L E D A graphs using external arrays), the space savings are up to 62%.
LEDA 5.1 brings new implementations, the time efficiency of several flow algorithms improved even more.
Samples: Have a look at an example.
Documentation: Read the manual page.
