The implementation of combinatorial algorithms heavily relies on efficient graph structures. Diverse applications require the usage of different physical graph storages. Until now, we used two general graph structures,
ListDigraph and
ListGraph. Apart from these types, LEMON also provides several other classes for handling directed and undirected graphs to meet the diverging requirements of the possible users. In order to save on running time or on memory usage, some structures may fail to support some graph features like node or arc/edge deletion. You are free to use the graph structure that fit your requirements the best, since most graph algorithms and auxiliary data structures can be used with any of them.
In LEMON, there are various graph types, which are rather different, but they all conform to the corresponding
graph concept, which defines the common part of the graph interfaces. The
Digraph concept describes the common interface of directed graphs (without any sensible implementation), while the
Graph concept describes the undirected graphs. A generic graph algorithm should only exploit the features of the corresponding graph concept so that it could be applied to any graph structure. (Such an algorithm should compile with the
Digraph or
Graph type, but it will not run properly, of course.)
The graph concepts define the member classes for the iterators and maps along with some useful basic functions for obtaining the identifiers of the items, the end nodes of the arcs (or edges) and their iterators, etc. An actual graph implementation may have various additional functionalities according to its purpose.
Another advantage of this design is that you can write your own graph classes, if you would like to. As long as they provide the interface defined in one of the graph concepts, all the LEMON algorithms and classes will work with them properly.
The already used
ListDigraph class is the most versatile directed graph structure. As its name suggests, it is based on linked lists, therefore iterating through its nodes and arcs is fast and it is quite flexible. Apart from the general digraph functionalities, it provides operations for adding and removing nodes and arcs, changing the source or target node of an arc, and contracting and splitting nodes or arcs.
SmartDigraph is another general digraph implementation, which is significantly more efficient (both in terms of space and time), but it provides less functionality. For example, nodes and arcs cannot be removed from it.
The StaticDigraph structure is even more optimized for efficiency, but it is completely static. It requires less space in memory and provides faster item iteration than ListDigraph and SmartDigraph, especially using OutArcIt iterators, since its arcs are stored in an appropriate order. However, you can neither add nor delete arcs or nodes, the graph has to be built at once and other modifications are not supported.
FullDigraph is an efficient implementation of a directed full graph. This structure is also completely static and it needs constant space in memory.
The general undirected graph classes,
ListGraph and
SmartGraph have similar implementations as their directed variants. Therefore,
SmartGraph is more efficient, but
ListGraph provides more functionality. In addition to these general structures, LEMON also provides special purpose undirected graph types for handling
full graphs,
grid graphs and
hypercube graphs.
<< 7 Maps | Home | 9 Graph Adaptors >>
