5.6. What we did not cover

Learning objectives

The class ugraph
The classes node_matrix and node_map2
Static graphs
The classes face_array and face_map
The classes planar_map and PLANAR_MAP
Functions templatized with number types
The gml format

The class ugraph

The class ugraph implements undirected graphs. It is primarily used by LEDA's internal algorithms and should not be used in programs of one's own, just because the interfaces of LEDA's built-in graph algorithms all expect a graph as input.

The classes node_matrix and node_map2

The class node_matrix expands the concept of node_array to two-dimensional index sets. (Both indices are nodes.) It appears, for example, as the type of a parameter of the function ALL_PAIRS_SHORTEST_PATHS() that defines the distance of each node to each other node. Likewise, the class node_map2 expands the concept of the class node_map to two-dimensional index sets.

Static graphs

As of version 4.5 of LEDA, there is a particularly efficient class of its own for static graphs, that is, for graphs that do not change any more after their construction phase. The corresponding manual page contains more information about this graph type.

The classes face_array and face_map

The classes face_array and face_map allow to associate information to the faces of a map.

The classes planar_map and PLANAR_MAP

The class planar_map is useful for managing combinatorial embeddings of planar graphs, as we came to know them in Section 5.2.6.

The class PLANAR_MAP allows to associate additional information to the nodes, edges, and faces of a planar map.

Functions templatized with number types

Many functions from shortest_path.h, max_flow.h, mwb_matching.h, and mw_matching.h are also available in a templatized version in which the number type of the edge information can be specified (and therefore does not necessarily have to be int). By using a number type with a larger definition domain and/or a higher precision, methodically induced rounding errors can be lowered.

The gml format

Beside the standard format for storing graphs (file extension .gw), there is also, by historical reasons, the gml format (file extension .gml).




Imprint-Dataprotection