alpar@21
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
alpar@21
|
2 |
*
|
alpar@21
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
alpar@21
|
4 |
*
|
kpeter@32
|
5 |
* Copyright (C) 2003-2010
|
alpar@21
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@21
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@21
|
8 |
*
|
alpar@21
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@21
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@21
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@21
|
12 |
*
|
alpar@21
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@21
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@21
|
15 |
* purpose.
|
alpar@21
|
16 |
*
|
alpar@21
|
17 |
*/
|
alpar@21
|
18 |
|
alpar@21
|
19 |
namespace lemon {
|
alpar@21
|
20 |
/**
|
kpeter@26
|
21 |
[PAGE]sec_basics[PAGE] Basic Concepts
|
alpar@21
|
22 |
|
kpeter@27
|
23 |
Throughout the tutorial we are working with the \ref lemon namespace.
|
kpeter@27
|
24 |
To save a lot of typing, we assume that a
|
alpar@21
|
25 |
|
alpar@21
|
26 |
\code
|
alpar@21
|
27 |
using namespace lemon;
|
alpar@21
|
28 |
\endcode
|
alpar@21
|
29 |
|
alpar@21
|
30 |
directive is added to the code at the beginning.
|
alpar@21
|
31 |
|
kpeter@26
|
32 |
[SEC]sec_digraphs[SEC] Directed Graphs
|
alpar@21
|
33 |
|
kpeter@37
|
34 |
The core features of LEMON are the data structures, algorithms and auxiliary
|
kpeter@37
|
35 |
tools that make it possible to represent graphs and working with them easily
|
kpeter@37
|
36 |
and efficiently.
|
kpeter@27
|
37 |
This section tells you how to work with a directed graph (\e digraph,
|
kpeter@28
|
38 |
for short) in LEMON. Here we use \ref ListDigraph, the most versatile
|
kpeter@28
|
39 |
digraph structure. (The library also provides other digraph types,
|
kpeter@28
|
40 |
see \ref sec_graph_structures "later".)
|
alpar@21
|
41 |
|
kpeter@37
|
42 |
For using \ref ListDigraph, you must include the header file
|
kpeter@37
|
43 |
\ref list_graph.h like this:
|
kpeter@37
|
44 |
|
kpeter@37
|
45 |
\code
|
kpeter@37
|
46 |
#include <lemon/list_graph.h>
|
kpeter@37
|
47 |
\endcode
|
kpeter@37
|
48 |
|
kpeter@37
|
49 |
The default constructor of the class creates an empty digraph.
|
kpeter@37
|
50 |
|
kpeter@37
|
51 |
\code
|
kpeter@37
|
52 |
ListDigraph g;
|
kpeter@37
|
53 |
\endcode
|
kpeter@37
|
54 |
|
kpeter@27
|
55 |
The nodes and the arcs of a graph are identified by two data types called
|
kpeter@27
|
56 |
\ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
|
kpeter@27
|
57 |
"ListDigraph::Arc". You can add new items to the graph using the member
|
kpeter@27
|
58 |
functions \ref ListDigraph::addNode() "addNode()" and
|
kpeter@27
|
59 |
\ref ListDigraph::addArc() "addArc()", like this:
|
alpar@21
|
60 |
|
alpar@21
|
61 |
\code
|
kpeter@37
|
62 |
ListDigraph::Node x = g.addNode();
|
kpeter@37
|
63 |
ListDigraph::Node y = g.addNode();
|
kpeter@37
|
64 |
ListDigraph::Node z = g.addNode();
|
alpar@21
|
65 |
|
kpeter@37
|
66 |
g.addArc(x,y);
|
kpeter@37
|
67 |
g.addArc(y,z);
|
kpeter@37
|
68 |
g.addArc(z,x);
|
alpar@21
|
69 |
\endcode
|
alpar@21
|
70 |
|
alpar@21
|
71 |
Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
|
alpar@21
|
72 |
|
alpar@21
|
73 |
\code
|
kpeter@37
|
74 |
ListDigraph::Arc arc = g.addArc(x,z);
|
kpeter@37
|
75 |
\endcode
|
kpeter@37
|
76 |
|
kpeter@37
|
77 |
Parallel and loop arcs are also supported.
|
kpeter@37
|
78 |
|
kpeter@37
|
79 |
\code
|
kpeter@37
|
80 |
ListDigraph::Arc parallel = g.addArc(x,y);
|
kpeter@37
|
81 |
ListDigraph::Arc loop = g.addArc(x,x);
|
alpar@21
|
82 |
\endcode
|
alpar@21
|
83 |
|
kpeter@27
|
84 |
\note Using ListDigraph, you can also remove nodes or arcs with the
|
kpeter@28
|
85 |
\ref ListDigraph::erase() "erase()" function. Moreover, this class provides
|
kpeter@28
|
86 |
several other operations, see its \ref ListDigraph "documentation" for more
|
kpeter@28
|
87 |
information.
|
kpeter@27
|
88 |
However, not all graph structures support the addition and deletion
|
kpeter@28
|
89 |
of graph items (see \ref sec_graph_concepts).
|
alpar@21
|
90 |
|
kpeter@27
|
91 |
Two important member functions of the directed graphs are
|
alpar@21
|
92 |
\ref concepts::Digraph::source() "source()"
|
alpar@21
|
93 |
and \ref concepts::Digraph::target() "target()".
|
kpeter@37
|
94 |
They give back the two end nodes of an arc (as \c Node objects).
|
alpar@21
|
95 |
|
alpar@21
|
96 |
\code
|
kpeter@37
|
97 |
if (g.source(loop) == g.target(loop))
|
alpar@21
|
98 |
std::cout << "This is a loop arc" << std::endl;
|
alpar@21
|
99 |
\endcode
|
alpar@21
|
100 |
|
kpeter@37
|
101 |
Each graph item has a non-negative integer identifier, which can be obtained
|
kpeter@37
|
102 |
using the \ref concepts::Digraph::id() "id()" function of the graph structure.
|
kpeter@37
|
103 |
These identifiers are unique with respect to a certain item type in a graph,
|
kpeter@37
|
104 |
but a node and an arc may have the same id.
|
kpeter@27
|
105 |
|
kpeter@27
|
106 |
\code
|
kpeter@27
|
107 |
std::cout << "Arc " << g.id(arc) << " goes from node "
|
kpeter@27
|
108 |
<< g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
|
kpeter@27
|
109 |
\endcode
|
kpeter@27
|
110 |
|
kpeter@27
|
111 |
\note In fact, the \c Node and \c Arc types are typically simple wrapper
|
kpeter@27
|
112 |
classes for a single \c int value, which is the identifier of the item.
|
kpeter@27
|
113 |
|
kpeter@26
|
114 |
|
kpeter@26
|
115 |
[SEC]sec_digraph_it[SEC] Iterators
|
alpar@21
|
116 |
|
kpeter@27
|
117 |
Let us assume you want to list the elements of the graph. For this purpose,
|
kpeter@37
|
118 |
the graph structures provide several \e iterators. For example, the following
|
kpeter@27
|
119 |
code will count the number of nodes in a graph.
|
alpar@21
|
120 |
|
alpar@21
|
121 |
\code
|
alpar@21
|
122 |
int cnt = 0;
|
kpeter@27
|
123 |
for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
|
alpar@21
|
124 |
cnt++;
|
alpar@21
|
125 |
std::cout << "Number of nodes: " << cnt << std::endl;
|
alpar@21
|
126 |
\endcode
|
alpar@21
|
127 |
|
kpeter@37
|
128 |
\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
|
kpeter@37
|
129 |
is an iterator class that lists the nodes.
|
kpeter@37
|
130 |
The name of an iterator type starts with a name that refers to
|
kpeter@37
|
131 |
the iterated objects and ends with 'It'.
|
kpeter@37
|
132 |
|
kpeter@37
|
133 |
Using \ref concepts::Digraph::NodeIt "NodeIt", you must give
|
kpeter@37
|
134 |
the graph object to the constructor and the iterator will be set
|
alpar@21
|
135 |
to the first node. The next node is obtained by the prefix ++
|
kpeter@27
|
136 |
operator. If there are no more nodes in the graph, the iterator will
|
kpeter@37
|
137 |
be set to \ref INVALID, which is exploited in the stop condition of
|
kpeter@37
|
138 |
the loop.
|
alpar@21
|
139 |
|
kpeter@37
|
140 |
\note \ref INVALID is a constant in the \ref lemon namespace, which converts to
|
kpeter@37
|
141 |
and compares with each and every iterator and graph item type.
|
kpeter@37
|
142 |
Thus, you can even assign \ref INVALID to a \c Node or \c Arc object.
|
alpar@21
|
143 |
|
kpeter@37
|
144 |
The iterators convert to the corresponding item types.
|
kpeter@37
|
145 |
For example, the identifiers of the nodes can be printed like this.
|
kpeter@37
|
146 |
|
kpeter@37
|
147 |
\code
|
kpeter@37
|
148 |
for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
|
kpeter@37
|
149 |
std::cout << g.id(n) << std::endl;
|
kpeter@37
|
150 |
\endcode
|
kpeter@37
|
151 |
|
kpeter@37
|
152 |
As an other example, the following code adds a full graph to the
|
kpeter@37
|
153 |
existing nodes.
|
alpar@21
|
154 |
|
alpar@21
|
155 |
\code
|
kpeter@27
|
156 |
for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
|
kpeter@27
|
157 |
for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
|
kpeter@27
|
158 |
if (u != v) g.addArc(u, v);
|
alpar@21
|
159 |
\endcode
|
alpar@21
|
160 |
|
kpeter@27
|
161 |
\note Contrary to the iterators in the C++ Standard Template Library (STL),
|
kpeter@27
|
162 |
LEMON iterators are convertible to the corresponding
|
kpeter@32
|
163 |
item types without having to use \c %operator*(). This is not confusing,
|
kpeter@32
|
164 |
since the program context always indicates whether we refer to the iterator
|
kpeter@32
|
165 |
or to the graph item (they do not have conflicting functionalities).
|
kpeter@27
|
166 |
|
kpeter@27
|
167 |
The graph items are also ordered by the 'less than' operator (with respect to
|
kpeter@27
|
168 |
their integer identifiers). For example, this code will add only one of the
|
kpeter@27
|
169 |
opposite arcs.
|
alpar@21
|
170 |
|
alpar@21
|
171 |
\code
|
kpeter@27
|
172 |
for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
|
kpeter@27
|
173 |
for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
|
kpeter@27
|
174 |
if (u < v) g.addArc(u, v);
|
alpar@21
|
175 |
\endcode
|
alpar@21
|
176 |
|
kpeter@27
|
177 |
\warning The order in which the iterators visit the items is
|
alpar@21
|
178 |
undefined. The only thing you may assume that they will list the items
|
alpar@21
|
179 |
in the same order until the graph is not changed.
|
alpar@21
|
180 |
|
alpar@21
|
181 |
Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
|
alpar@21
|
182 |
lists the arcs. Its usage is the same as of
|
alpar@21
|
183 |
\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
|
alpar@21
|
184 |
|
alpar@21
|
185 |
\code
|
alpar@21
|
186 |
int cnt = 0;
|
kpeter@27
|
187 |
for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
|
alpar@21
|
188 |
cnt++;
|
alpar@21
|
189 |
std::cout << "Number of arcs: " << cnt << std::endl;
|
alpar@21
|
190 |
\endcode
|
alpar@21
|
191 |
|
alpar@21
|
192 |
Finally, you can also list the arcs starting from or arriving at a
|
kpeter@32
|
193 |
certain node with
|
alpar@21
|
194 |
\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
|
alpar@21
|
195 |
and
|
alpar@21
|
196 |
\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
|
kpeter@27
|
197 |
Their usage is the same, but you must also give the node to the constructor.
|
alpar@21
|
198 |
|
alpar@21
|
199 |
\code
|
alpar@21
|
200 |
int cnt = 0;
|
kpeter@37
|
201 |
for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a)
|
alpar@21
|
202 |
cnt++;
|
kpeter@37
|
203 |
std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl;
|
alpar@21
|
204 |
\endcode
|
alpar@21
|
205 |
|
kpeter@37
|
206 |
\note LEMON provides functions for counting the nodes and arcs of a digraph:
|
kpeter@37
|
207 |
\ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs().
|
kpeter@37
|
208 |
Using them is not just simpler than the above loops, but they could be much
|
kpeter@37
|
209 |
faster, since several graph types support constant time item counting.
|
kpeter@37
|
210 |
|
kpeter@26
|
211 |
|
kpeter@26
|
212 |
[SEC]sec_digraph_maps[SEC] Maps
|
alpar@21
|
213 |
|
kpeter@27
|
214 |
The concept of "maps" is another fundamental part of LEMON. They allow assigning
|
kpeter@27
|
215 |
values of any type to the nodes or arcs of a graph. The standard maps
|
alpar@21
|
216 |
provided by the graph structures have a couple of nice properties.
|
alpar@21
|
217 |
|
kpeter@27
|
218 |
- \e Fast. Accessing (reading/writing) the values is as fast as a
|
kpeter@27
|
219 |
simple vector reading/writing.
|
alpar@21
|
220 |
- \e Dynamic. Whenever you need, you
|
alpar@21
|
221 |
can allocate new maps in your code, just as a local variable. So when you
|
alpar@21
|
222 |
leave its scope, it will be de-allocated automatically.
|
alpar@21
|
223 |
- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
|
alpar@21
|
224 |
existing maps will automatically expanded and the new slots will be
|
alpar@21
|
225 |
initialized. On the removal of an item, the corresponding values in the maps
|
alpar@21
|
226 |
are properly destructed.
|
kpeter@37
|
227 |
|
kpeter@37
|
228 |
By principle, the graph classes represent only the pure structure of
|
kpeter@37
|
229 |
the graph (i.e. the nodes and arcs and their connections).
|
kpeter@37
|
230 |
All data that are assigned to the items of the graph (e.g. node labels,
|
kpeter@37
|
231 |
arc costs or capacities) must be stored separately using maps.
|
alpar@21
|
232 |
|
kpeter@27
|
233 |
\note These maps must not be confused with \c std::map, since they provide
|
kpeter@37
|
234 |
O(1) time access to the elements instead of O(log n).
|
kpeter@27
|
235 |
|
alpar@21
|
236 |
So, if you want to assign \c int values to each node, you have to allocate a
|
kpeter@27
|
237 |
\ref concepts::Digraph::NodeMap "NodeMap<int>".
|
alpar@21
|
238 |
|
alpar@21
|
239 |
\code
|
alpar@21
|
240 |
ListDigraph::NodeMap<int> map(g);
|
alpar@21
|
241 |
\endcode
|
alpar@21
|
242 |
|
alpar@21
|
243 |
As you see, the graph you want to assign a map is given to the
|
alpar@21
|
244 |
constructor. Then you can access its element as if it were a vector.
|
alpar@21
|
245 |
|
alpar@21
|
246 |
\code
|
kpeter@37
|
247 |
map[x] = 2;
|
kpeter@37
|
248 |
map[y] = 3;
|
kpeter@37
|
249 |
map[z] = map[x] + map[y];
|
alpar@21
|
250 |
\endcode
|
alpar@21
|
251 |
|
kpeter@37
|
252 |
Any kind of data can be assigned to the graph items (assuming that the type
|
kpeter@37
|
253 |
has a default constructor).
|
kpeter@27
|
254 |
|
kpeter@27
|
255 |
\code
|
kpeter@37
|
256 |
ListDigraph::NodeMap<std::string> name(g);
|
kpeter@37
|
257 |
name[x] = "Node A";
|
kpeter@37
|
258 |
name[y] = "Node B";
|
kpeter@27
|
259 |
\endcode
|
kpeter@27
|
260 |
|
kpeter@37
|
261 |
As a more complex example, let us create a map that assigns \c char labels
|
kpeter@37
|
262 |
to the nodes.
|
alpar@21
|
263 |
|
alpar@21
|
264 |
\code
|
kpeter@37
|
265 |
ListDigraph::NodeMap<char> label(g);
|
kpeter@37
|
266 |
char ch = 'A';
|
kpeter@27
|
267 |
for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
|
kpeter@37
|
268 |
label[n] = ch++;
|
alpar@21
|
269 |
\endcode
|
alpar@21
|
270 |
|
kpeter@27
|
271 |
When you create a map, you can also give an initial value of the elements
|
kpeter@27
|
272 |
as a second parameter. For example, the following code puts the number
|
kpeter@27
|
273 |
of outgoing arcs for each node in a map.
|
alpar@21
|
274 |
|
alpar@21
|
275 |
\code
|
kpeter@27
|
276 |
ListDigraph::NodeMap<int> out_deg(g, 0);
|
kpeter@27
|
277 |
for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
|
alpar@21
|
278 |
out_deg[g.source(a)]++;
|
alpar@21
|
279 |
\endcode
|
alpar@21
|
280 |
|
kpeter@27
|
281 |
\warning The initial value will apply to the currently existing items only. If
|
alpar@21
|
282 |
you add new nodes/arcs to the graph, then the corresponding values in the
|
alpar@21
|
283 |
map will be initialized with the default constructor of the
|
alpar@21
|
284 |
type.
|
alpar@21
|
285 |
|
kpeter@37
|
286 |
|
kpeter@37
|
287 |
[SEC]sec_naming_conv[SEC] Naming Conventions
|
kpeter@37
|
288 |
|
kpeter@37
|
289 |
In LEMON, there are some naming conventions you might already notice
|
kpeter@37
|
290 |
in the above examples.
|
kpeter@37
|
291 |
|
kpeter@37
|
292 |
The name of a source file is written lowercase and the words are separated with
|
kpeter@37
|
293 |
underscores (e.g. \ref list_graph.h). All header files are located in the
|
kpeter@37
|
294 |
\c %lemon subdirectory, so you can include them like this.
|
kpeter@37
|
295 |
|
kpeter@37
|
296 |
\code
|
kpeter@37
|
297 |
#include <lemon/header_file.h>
|
kpeter@37
|
298 |
\endcode
|
kpeter@37
|
299 |
|
kpeter@37
|
300 |
The name of a class or any type looks like the following
|
kpeter@37
|
301 |
(e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node",
|
kpeter@37
|
302 |
\ref concepts::Digraph::NodeIt "NodeIt" etc.).
|
kpeter@37
|
303 |
|
kpeter@37
|
304 |
\code
|
kpeter@37
|
305 |
AllWordsCapitalizedWithoutUnderscores
|
kpeter@37
|
306 |
\endcode
|
kpeter@37
|
307 |
|
kpeter@37
|
308 |
The name of a function looks like the following
|
kpeter@37
|
309 |
(e.g. \ref concepts::Digraph::source() "source()",
|
kpeter@37
|
310 |
\ref concepts::Digraph::source() "target()",
|
kpeter@37
|
311 |
\ref countNodes(), \ref countArcs() etc.).
|
kpeter@37
|
312 |
|
kpeter@37
|
313 |
\code
|
kpeter@37
|
314 |
firstWordLowerCaseRestCapitalizedWithoutUnderscores
|
kpeter@37
|
315 |
\endcode
|
kpeter@37
|
316 |
|
kpeter@37
|
317 |
The names of constants and macros look like the following
|
kpeter@37
|
318 |
(e.g. \ref INVALID).
|
kpeter@37
|
319 |
|
kpeter@37
|
320 |
\code
|
kpeter@37
|
321 |
ALL_UPPER_CASE_WITH_UNDERSCORES
|
kpeter@37
|
322 |
\endcode
|
kpeter@37
|
323 |
|
kpeter@37
|
324 |
For more details, see \ref coding_style.
|
kpeter@37
|
325 |
|
alpar@21
|
326 |
[TRAILER]
|
alpar@21
|
327 |
*/
|
alpar@21
|
328 |
}
|