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