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 In \ref sec_basics, we have introduced a general digraph structure,
27 \ref ListDigraph. Apart from this class, LEMON 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 Any generic graph algorithm should only exploit the features of the
46 corresponding graph concept. (It should compile with the
47 \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
48 but it will not run properly, of course.)
50 The graph %concepts define the member classes for the iterators and maps
51 along with some useful basic functions for obtaining the identifiers of
52 the items, the end nodes of the arcs (or edges) and their iterators,
54 An actual graph implementation may have various additional functionalities
55 according to its purpose.
58 [SEC]sec_digraph_types[SEC] Digraph Structures
60 The already used \ref ListDigraph class is the most versatile directed
61 graph structure. Apart from the general digraph functionalities, it
62 provides operations for adding and removing nodes and arcs, changing
63 the source or target node of an arc, and contracting and splitting nodes
66 \ref SmartDigraph is another general digraph implementation, which is
67 significantly more efficient (both in terms of space and time), but it
68 provides less functionality. For example, nodes and arcs cannot be
71 \ref FullDigraph is an efficient implementation of a directed full graph.
72 This structure is completely static, so you can neither add nor delete
73 arcs or nodes, and the class needs constant space in memory.
76 [SEC]sec_undir_graphs[SEC] Undirected Graphs
78 LEMON also provides undirected graph structures. For example,
79 \ref ListGraph and \ref SmartGraph are the undirected versions of
80 \ref ListDigraph and \ref SmartDigraph, respectively.
81 They provide similar features to the digraph structures.
83 The \ref concepts::Graph "undirected graphs" also fulfill the concept of
84 \ref concepts::Digraph "directed graphs", in such a way that each
85 undirected \e edge of a graph can also be regarded as two oppositely
86 directed \e arcs. As a result, all directed graph algorithms automatically
87 run on undirected graphs, as well.
89 Undirected graphs provide an \c Edge type for the \e undirected \e edges
90 and an \c Arc type for the \e directed \e arcs. The \c Arc type is
91 convertible to \c Edge (or inherited from it), thus the corresponding
92 edge can always be obtained from an arc.
94 Only nodes and edges can be added to or removed from an undirected
95 graph and the corresponding arcs are added or removed automatically
96 (there are twice as many arcs as edges)
102 ListGraph::Node a = g.addNode();
103 ListGraph::Node b = g.addNode();
104 ListGraph::Node c = g.addNode();
106 ListGraph::Edge e = g.addEdge(a,b);
111 Each edge has an inherent orientation, thus it can be defined whether an
112 arc is forward or backward oriented in an undirected graph with respect
113 to this default oriantation of the represented edge.
114 The direction of an arc can be obtained and set using the functions
115 \ref concepts::Graph::direction() "direction()" and
116 \ref concepts::Graph::direct() "direct()", respectively.
120 ListGraph::Arc a1 = g.direct(e, true); // a1 is the forward arc
121 ListGraph::Arc a2 = g.direct(e, false); // a2 is the backward arc
123 if (a2 == g.oppositeArc(a1))
124 std::cout << "a2 is the opposite of a1" << std::endl;
127 The end nodes of an edge can be obtained using the functions
128 \ref concepts::Graph::source() "u()" and
129 \ref concepts::Graph::target() "v()", while the
130 \ref concepts::Graph::source() "source()" and
131 \ref concepts::Graph::target() "target()" can be used for arcs.
134 std::cout << "Edge " << g.id(e) << " connects node "
135 << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
137 std::cout << "Arc " << g.id(a2) << " goes from node "
138 << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
142 Similarly to the digraphs, the undirected graphs also provide iterators
143 \ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
144 \ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
145 "InArcIt", which can be used the same way.
146 However, they also have iterator classes for edges.
147 \ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
148 \ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
151 For example, the degree of each node can be computed and stored in a node map
155 ListGraph::NodeMap<int> deg(g, 0);
156 for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
157 for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
163 In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
164 and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
165 but with opposite direction. They are convertible to both \c Arc and
166 \c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
167 on these edges, but it is not convertible to \c Arc, only to \c Edge.
169 Apart from the node and arc maps, an undirected graph also defines
170 a template member class for constructing edge maps. These maps can be
171 used in conjunction with both edges and arcs.
175 ListGraph::EdgeMap cost(g);
177 std::cout << cost[e] << std::endl;
178 std::cout << cost[a1] << ", " << cost[a2] << std::endl;
180 ListGraph::ArcMap arc_cost(g);
181 arc_cost[a1] = cost[a1];
182 arc_cost[a2] = 2 * cost[a2];
183 // std::cout << arc_cost[e] << std::endl; // this is not valid
184 std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
187 [SEC]sec_special_graphs[SEC] Special Graph Structures
189 In addition to the general undirected classes \ref ListGraph and
190 \ref SmartGraph, LEMON also provides special purpose graph types for
191 handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and
192 \ref HypercubeGraph "hypercube graphs".
193 They all static structures, i.e. they do not allow distinct item additions
194 or deletions, the graph has to be built at once.