1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 [PAGE]sec_graph_structures[PAGE] Graph Structures
23 The implementation of combinatorial algorithms heavily relies on
24 efficient graph structures. Diverse applications require the
25 usage of different physical graph storages.
26 Until now, we used two general graph structures, \ref ListDigraph
27 and \ref ListGraph. Apart from these types, LEMON also provides several
28 other classes for handling directed and undirected graphs to meet the
29 diverging requirements of the possible users. In order to save on running
30 time or on memory usage, some structures may fail to support some graph
31 features like node or arc/edge deletion.
32 You are free to use the graph structure that fit your requirements the best,
33 since most graph algorithms and auxiliary data structures can be used
37 [SEC]sec_graph_concepts[SEC] Graph Concepts
39 In LEMON, there are various graph types, which are rather different, but
40 they all conform to the corresponding \ref graph_concepts "graph concept",
41 which defines the common part of the graph interfaces.
42 The \ref concepts::Digraph "Digraph concept" describes the common interface
43 of directed graphs (without any sensible implementation), while
44 the \ref concepts::Graph "Graph concept" describes the undirected graphs.
45 A generic graph algorithm should only exploit the features of the
46 corresponding graph concept so that it could be applied to any graph
47 structure. (Such an algorithm should compile with the
48 \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
49 but it will not run properly, of course.)
51 The graph %concepts define the member classes for the iterators and maps
52 along with some useful basic functions for obtaining the identifiers of
53 the items, the end nodes of the arcs (or edges) and their iterators,
55 An actual graph implementation may have various additional functionalities
56 according to its purpose.
58 Another advantage of this design is that you can write your own graph classes,
60 As long as they provide the interface defined in one of the graph concepts,
61 all the LEMON algorithms and classes will work with them properly.
64 [SEC]sec_digraph_types[SEC] Directed Graph Structures
66 The already used \ref ListDigraph class is the most versatile directed
67 graph structure. As its name suggests, it is based on linked lists,
68 therefore iterating through its nodes and arcs is fast and it is quite
69 flexible. Apart from the general digraph functionalities, it
70 provides operations for adding and removing nodes and arcs, changing
71 the source or target node of an arc, and contracting and splitting nodes
74 \ref SmartDigraph is another general digraph implementation, which is
75 significantly more efficient (both in terms of space and time), but it
76 provides less functionality. For example, nodes and arcs cannot be
79 The \ref StaticDigraph structure is even more optimized for efficiency,
80 but it is completely static. It requires less space in memory and
81 provides faster item iteration than \ref ListDigraph and \ref
82 SmartDigraph, especially using \ref concepts::Digraph::OutArcIt
83 "OutArcIt" iterators, since its arcs are stored in an appropriate order.
84 However, you can neither add nor delete arcs or nodes, the graph
85 has to be built at once and other modifications are not supported.
87 \ref FullDigraph is an efficient implementation of a directed full graph.
88 This structure is also completely static and it needs constant space
92 [SEC]sec_graph_types[SEC] Undirected Graph Structures
94 The general undirected graph classes, \ref ListGraph and \ref SmartGraph
95 have similar implementations as their directed variants.
96 Therefore, \ref SmartGraph is more efficient, but \ref ListGraph provides
98 In addition to these general structures, LEMON also provides special purpose
99 undirected graph types for handling \ref FullGraph "full graphs",
100 \ref GridGraph "grid graphs" and \ref HypercubeGraph "hypercube graphs".