COIN-OR::LEMON - Graph Library

source: lemon-tutorial/graphs.dox @ 38:236e7061b70d

Last change on this file since 38:236e7061b70d was 38:236e7061b70d, checked in by Peter Kovacs <kpeter@…>, 12 years ago

Extend the graphs section

File size: 8.6 KB
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
19namespace lemon {
21[PAGE]sec_graph_structures[PAGE] Graph Structures
23The implementation of combinatorial algorithms heavily relies on
24efficient graph structures. Diverse applications require the
25usage of different physical graph storages.
26In \ref sec_basics, we have introduced a general digraph structure,
27\ref ListDigraph. Apart from this class, LEMON provides several
28other classes for handling directed and undirected graphs to meet the
29diverging requirements of the possible users. In order to save on running
30time or on memory usage, some structures may fail to support some graph
31features like node or arc/edge deletion.
32You are free to use the graph structure that fit your requirements the best,
33since most graph algorithms and auxiliary data structures can be used
34with any of them.
37[SEC]sec_graph_concepts[SEC] Graph Concepts
39In LEMON, there are various graph types, which are rather different, but
40they all conform to the corresponding \ref graph_concepts "graph concept",
41which defines the common part of the graph interfaces.
42The \ref concepts::Digraph "Digraph concept" describes the common interface
43of directed graphs (without any sensible implementation), while
44the \ref concepts::Graph "Graph concept" describes the undirected graphs.
45A generic graph algorithm should only exploit the features of the
46corresponding graph concept so that it could be applied to any graph
47structure. (Such an algorithm should compile with the
48\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
49but it will not run properly, of course.)
51The graph %concepts define the member classes for the iterators and maps
52along with some useful basic functions for obtaining the identifiers of
53the items, the end nodes of the arcs (or edges) and their iterators,
55An actual graph implementation may have various additional functionalities
56according to its purpose.
58Another advantage of this design is that you can write your own graph classes,
59if you would like to.
60As long as they provide the interface defined in one of the graph concepts,
61all the LEMON algorithms and classes will work with them properly.
64[SEC]sec_digraph_types[SEC] Digraph Structures
66The already used \ref ListDigraph class is the most versatile directed
67graph structure. As its name suggests, it is based on linked lists,
68therefore iterating through its nodes and arcs is fast and it is quite
69flexible. Apart from the general digraph functionalities, it
70provides operations for adding and removing nodes and arcs, changing
71the source or target node of an arc, and contracting and splitting nodes
72or arcs.
74\ref SmartDigraph is another general digraph implementation, which is
75significantly more efficient (both in terms of space and time), but it
76provides less functionality. For example, nodes and arcs cannot be
77removed from it.
79The \ref StaticDigraph structure is even more optimized for efficiency,
80but it is completely static. It requires less space in memory and
81provides faster item iteration than \ref ListDigraph and \ref
82SmartDigraph, especially using \ref concepts::Digraph::OutArcIt
83"OutArcIt" iterators, since its arcs are stored in an appropriate order.
84However, it only provides \ref StaticDigraph::build() "build()" and
85\ref \ref StaticDigraph::clear() "clear()" functions and does not
86support any other modification of the digraph.
88\ref FullDigraph is an efficient implementation of a directed full graph.
89This structure is also completely static, so you can neither add nor delete
90arcs or nodes, moreover, the class needs constant space in memory.
93[SEC]sec_undir_graphs[SEC] Undirected Graphs
95LEMON also provides undirected graph structures. For example,
96\ref ListGraph and \ref SmartGraph are the undirected versions of
97\ref ListDigraph and \ref SmartDigraph, respectively.
98They provide similar features to the digraph structures.
100The \ref concepts::Graph "undirected graphs" also fulfill the concept of
101\ref concepts::Digraph "directed graphs", in such a way that each
102undirected \e edge of a graph can also be regarded as two oppositely
103directed \e arcs. As a result, all directed graph algorithms automatically
104run on undirected graphs, as well.
106Undirected graphs provide an \c Edge type for the \e undirected \e edges
107and an \c Arc type for the \e directed \e arcs. The \c Arc type is
108convertible to \c Edge (or inherited from it), thus the corresponding
109edge can always be obtained from an arc.
111Only nodes and edges can be added to or removed from an undirected
112graph and the corresponding arcs are added or removed automatically
113(there are twice as many arcs as edges)
115For example,
117  ListGraph g;
119  ListGraph::Node a = g.addNode();
120  ListGraph::Node b = g.addNode();
121  ListGraph::Node c = g.addNode();
123  ListGraph::Edge e = g.addEdge(a,b);
124  g.addEdge(b,c);
125  g.addEdge(c,a);
128Each edge has an inherent orientation, thus it can be defined whether an
129arc is forward or backward oriented in an undirected graph with respect
130to this default oriantation of the represented edge.
131The direction of an arc can be obtained and set using the functions
132\ref concepts::Graph::direction() "direction()" and
133\ref concepts::Graph::direct() "direct()", respectively.
135For example,
137  ListGraph::Arc a1 =, true);    // a1 is the forward arc
138  ListGraph::Arc a2 =, false);   // a2 is the backward arc
140  if (a2 == g.oppositeArc(a1))
141    std::cout << "a2 is the opposite of a1" << std::endl;
144The end nodes of an edge can be obtained using the functions
145\ref concepts::Graph::source() "u()" and
146\ref concepts::Graph::target() "v()", while the
147\ref concepts::Graph::source() "source()" and
148\ref concepts::Graph::target() "target()" can be used for arcs.
151  std::cout << "Edge " << << " connects node "
152    << << " and node " << << std::endl;
154  std::cout << "Arc " << << " goes from node "
155    << << " to node " << << std::endl;
159Similarly to the digraphs, the undirected graphs also provide iterators
160\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
161\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
162"InArcIt", which can be used the same way.
163However, they also have iterator classes for edges.
164\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
165\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
166certain node.
168For example, the degree of each node can be computed and stored in a node map
169like this:
172  ListGraph::NodeMap<int> deg(g, 0);
173  for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
174    for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
175      deg[n]++;
176    }
177  }
180In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
181and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
182but with opposite direction. They are convertible to both \c Arc and
183\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
184on these edges, but it is not convertible to \c Arc, only to \c Edge.
186Apart from the node and arc maps, an undirected graph also defines
187a template member class for constructing edge maps. These maps can be
188used in conjunction with both edges and arcs.
190For example,
192  ListGraph::EdgeMap cost(g);
193  cost[e] = 10;
194  std::cout << cost[e] << std::endl;
195  std::cout << cost[a1] << ", " << cost[a2] << std::endl;
197  ListGraph::ArcMap arc_cost(g);
198  arc_cost[a1] = cost[a1];
199  arc_cost[a2] = 2 * cost[a2];
200  // std::cout << arc_cost[e] << std::endl;   // this is not valid
201  std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
204[SEC]sec_special_graphs[SEC] Special Graph Structures
206In addition to the general undirected classes \ref ListGraph and
207\ref SmartGraph, LEMON also provides special purpose graph types for
208handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and
209\ref HypercubeGraph "hypercube graphs".
210They all static structures, i.e. they do not allow distinct item additions
211or deletions, the graph has to be built at once.
Note: See TracBrowser for help on using the repository browser.