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_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/templates/XXX.t > must be included, e.g., in order to use the templated version of the maxflow algorithm, one must include <LEDA/templates/max_flow.t >
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 (252 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.