Graph Algorithms

This chapter gives a summary of the graph algorithms contained in LEDA,
basic graph algorithms for reachability problems, shortest path algorithms,
matching algorithms, flow algorithms, ... .

All graph algorithms are generic, i.e., they accept
instances of any user defined
parameterized graph type *GRAPH*`<`
*vtype*, *etype*`>` as arguments.

All graph algorithms are available by including the
header file `<`LEDA/graph/graph_alg.h`>`. Alternatively, one may include
a more specific header file.

An important subclass of graph algorithms are network algorithms.
The input to most network algorithms is a graph whose edges or nodes
are labeled with numbers, e.g., shortest path algorithms get edge costs,
network flow algorithms get edge capacities, and min cost flow algorithms
get edge capacities and edge costs. We use *NT* to denote the number
type used for the edge and node labels.

Most network algorithms come in three kinds: A templated version in which
*NT* is a template parameter, and reinstantiated and precompiled
versions for the number types
*int* (always) and *double* (except for a small number of functions).
The function name of the templated version
ends in _T. Thus MAX_FLOW_T is the name of the templated version of the max
flow algorithm and MAX_FLOW is the name of the instantiated version.

In order to use the templated version a file `<`LEDA/graph/templates/XXX.h`>`
must be included, e.g., in order to use the templated version of the
maxflow algorithm, one must include `<`LEDA/graph/templates/max_flow.h`>`

Special care should be taken when using network algorithms with a number
type *NT* that can incur rounding error, e.g., the type *double*.
The functions perform correctly if
the arithmetic is exact.
This is the case if all numerical values in the input
are integers (albeit stored as a number of type *NT*),
if none of the intermediate
results exceeds the maximal integer representable by the
number type (2^{52} in the case of *doubles*), and if no round-off errors
occur during the computation. We give more specific information on the
arithmetic demand for each function below.
If the arithmetic incurs rounding error, the computation may fail in
two ways: give a wrong answer or run forever.

- Basic Graph Algorithms ( basic_graph_alg )
- Shortest Path Algorithms ( shortest_path )
- Maximum Flow ( max_flow )
- Min Cost Flow Algorithms ( min_cost_flow )
- Minimum Cut ( min_cut )
- Maximum Cardinality Matchings in Bipartite Graphs ( mcb_matching )
- Bipartite Weighted Matchings and Assignments ( mwb_matching )
- Maximum Cardinality Matchings in General Graphs ( mc_matching )
- General Weighted Matchings ( mw_matching )
- Proof of Optimality.
- Heuristics for Initial Matching Constructions.
- Graph Structure.
- Edge Weight Restrictions.
- Arithmetic Demand.
- Single Tree vs. Multiple Tree Approach:
- Worst-Case Running Time:

- Stable Matching ( stable_matching )
- Minimum Spanning Trees ( min_span )
- Euler Tours ( euler_tour )
- Algorithms for Planar Graphs ( plane_graph_alg )
- Graph Drawing Algorithms ( graph_draw )
- Graph Morphism Algorithms ( graph_morphism )
- Graph Morphism Algorithm Functionality ( graph_morphism_algorithm )