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 |
*
|
alpar@21
|
5 |
* Copyright (C) 2003-2009
|
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@27
|
34 |
This section tells you how to work with a directed graph (\e digraph,
|
kpeter@28
|
35 |
for short) in LEMON. Here we use \ref ListDigraph, the most versatile
|
kpeter@28
|
36 |
digraph structure. (The library also provides other digraph types,
|
kpeter@28
|
37 |
see \ref sec_graph_structures "later".)
|
alpar@21
|
38 |
|
kpeter@27
|
39 |
The nodes and the arcs of a graph are identified by two data types called
|
kpeter@27
|
40 |
\ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
|
kpeter@27
|
41 |
"ListDigraph::Arc". You can add new items to the graph using the member
|
kpeter@27
|
42 |
functions \ref ListDigraph::addNode() "addNode()" and
|
kpeter@27
|
43 |
\ref ListDigraph::addArc() "addArc()", like this:
|
alpar@21
|
44 |
|
alpar@21
|
45 |
\code
|
alpar@21
|
46 |
ListDigraph g;
|
alpar@21
|
47 |
ListDigraph::Node a = g.addNode();
|
alpar@21
|
48 |
ListDigraph::Node b = g.addNode();
|
alpar@21
|
49 |
ListDigraph::Node c = g.addNode();
|
alpar@21
|
50 |
ListDigraph::Node d = g.addNode();
|
alpar@21
|
51 |
|
alpar@21
|
52 |
g.addArc(a,b);
|
alpar@21
|
53 |
g.addArc(b,c);
|
alpar@21
|
54 |
g.addArc(c,d);
|
alpar@21
|
55 |
g.addArc(d,a);
|
alpar@21
|
56 |
\endcode
|
alpar@21
|
57 |
|
alpar@21
|
58 |
Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc:
|
alpar@21
|
59 |
|
alpar@21
|
60 |
\code
|
kpeter@27
|
61 |
ListDigraph::Arc arc = g.addArc(a,c);
|
alpar@21
|
62 |
\endcode
|
alpar@21
|
63 |
|
kpeter@27
|
64 |
\note Using ListDigraph, you can also remove nodes or arcs with the
|
kpeter@28
|
65 |
\ref ListDigraph::erase() "erase()" function. Moreover, this class provides
|
kpeter@28
|
66 |
several other operations, see its \ref ListDigraph "documentation" for more
|
kpeter@28
|
67 |
information.
|
kpeter@27
|
68 |
However, not all graph structures support the addition and deletion
|
kpeter@28
|
69 |
of graph items (see \ref sec_graph_concepts).
|
alpar@21
|
70 |
|
kpeter@27
|
71 |
Two important member functions of the directed graphs are
|
alpar@21
|
72 |
\ref concepts::Digraph::source() "source()"
|
alpar@21
|
73 |
and \ref concepts::Digraph::target() "target()".
|
kpeter@27
|
74 |
They give back the two end nodes of an arc.
|
alpar@21
|
75 |
|
alpar@21
|
76 |
\code
|
kpeter@27
|
77 |
if (g.source(arc) == g.target(arc))
|
alpar@21
|
78 |
std::cout << "This is a loop arc" << std::endl;
|
alpar@21
|
79 |
\endcode
|
alpar@21
|
80 |
|
kpeter@27
|
81 |
Each graph item has a unique integer identifier, which can be obtained using
|
kpeter@27
|
82 |
the \ref concepts::Digraph::id() "id()" function of the graph structure.
|
kpeter@27
|
83 |
|
kpeter@27
|
84 |
\code
|
kpeter@27
|
85 |
std::cout << "Arc " << g.id(arc) << " goes from node "
|
kpeter@27
|
86 |
<< g.id(g.source(arc)) << " to node " << g.id(g.target(arc)) << std::endl;
|
kpeter@27
|
87 |
\endcode
|
kpeter@27
|
88 |
|
kpeter@27
|
89 |
\note In fact, the \c Node and \c Arc types are typically simple wrapper
|
kpeter@27
|
90 |
classes for a single \c int value, which is the identifier of the item.
|
kpeter@27
|
91 |
|
kpeter@26
|
92 |
|
kpeter@26
|
93 |
[SEC]sec_digraph_it[SEC] Iterators
|
alpar@21
|
94 |
|
kpeter@27
|
95 |
Let us assume you want to list the elements of the graph. For this purpose,
|
kpeter@27
|
96 |
the graph structures provide several iterators. For example, the following
|
kpeter@27
|
97 |
code will count the number of nodes in a graph.
|
alpar@21
|
98 |
|
alpar@21
|
99 |
\code
|
alpar@21
|
100 |
int cnt = 0;
|
kpeter@27
|
101 |
for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
|
alpar@21
|
102 |
cnt++;
|
alpar@21
|
103 |
std::cout << "Number of nodes: " << cnt << std::endl;
|
alpar@21
|
104 |
\endcode
|
alpar@21
|
105 |
|
alpar@21
|
106 |
Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt"
|
kpeter@27
|
107 |
is an iterator class that traverses the
|
kpeter@27
|
108 |
nodes. You must give the graph to the constructor and the iterator will be set
|
alpar@21
|
109 |
to the first node. The next node is obtained by the prefix ++
|
kpeter@27
|
110 |
operator. If there are no more nodes in the graph, the iterator will
|
alpar@21
|
111 |
be set to \ref INVALID.
|
alpar@21
|
112 |
|
kpeter@27
|
113 |
\note \ref INVALID is a global constant, which converts to
|
kpeter@27
|
114 |
and compares with each and every iterator in LEMON.
|
alpar@21
|
115 |
|
kpeter@27
|
116 |
The iterators convert to the corresponding item types. For example,
|
alpar@21
|
117 |
to following code will add a full graph to the existing nodes.
|
alpar@21
|
118 |
|
alpar@21
|
119 |
\code
|
kpeter@27
|
120 |
for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
|
kpeter@27
|
121 |
for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
|
kpeter@27
|
122 |
if (u != v) g.addArc(u, v);
|
alpar@21
|
123 |
\endcode
|
alpar@21
|
124 |
|
kpeter@27
|
125 |
\note Contrary to the iterators in the C++ Standard Template Library (STL),
|
kpeter@27
|
126 |
LEMON iterators are convertible to the corresponding
|
kpeter@27
|
127 |
item types without having to use \c %operator*(). This is not confusing, since the
|
kpeter@27
|
128 |
program context always indicates whether we refer to the iterator or to the graph
|
kpeter@27
|
129 |
item (they do not have conflicting functionalities).
|
kpeter@27
|
130 |
|
kpeter@27
|
131 |
The graph items are also ordered by the 'less than' operator (with respect to
|
kpeter@27
|
132 |
their integer identifiers). For example, this code will add only one of the
|
kpeter@27
|
133 |
opposite arcs.
|
alpar@21
|
134 |
|
alpar@21
|
135 |
\code
|
kpeter@27
|
136 |
for (ListDigraph::NodeIt u(g); u != INVALID; ++u)
|
kpeter@27
|
137 |
for (ListDigraph::NodeIt v(g); v != INVALID; ++v)
|
kpeter@27
|
138 |
if (u < v) g.addArc(u, v);
|
alpar@21
|
139 |
\endcode
|
alpar@21
|
140 |
|
kpeter@27
|
141 |
\warning The order in which the iterators visit the items is
|
alpar@21
|
142 |
undefined. The only thing you may assume that they will list the items
|
alpar@21
|
143 |
in the same order until the graph is not changed.
|
alpar@21
|
144 |
|
alpar@21
|
145 |
Similarly, \ref concepts::Digraph::ArcIt "ListDigraph::ArcIt"
|
alpar@21
|
146 |
lists the arcs. Its usage is the same as of
|
alpar@21
|
147 |
\ref concepts::Digraph::NodeIt "ListDigraph::NodeIt".
|
alpar@21
|
148 |
|
alpar@21
|
149 |
\code
|
alpar@21
|
150 |
int cnt = 0;
|
kpeter@27
|
151 |
for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
|
alpar@21
|
152 |
cnt++;
|
alpar@21
|
153 |
std::cout << "Number of arcs: " << cnt << std::endl;
|
alpar@21
|
154 |
\endcode
|
alpar@21
|
155 |
|
alpar@21
|
156 |
Finally, you can also list the arcs starting from or arriving at a
|
alpar@21
|
157 |
certain node with
|
alpar@21
|
158 |
\ref concepts::Digraph::OutArcIt "ListDigraph::OutArcIt"
|
alpar@21
|
159 |
and
|
alpar@21
|
160 |
\ref concepts::Digraph::InArcIt "ListDigraph::InArcIt".
|
kpeter@27
|
161 |
Their usage is the same, but you must also give the node to the constructor.
|
alpar@21
|
162 |
|
alpar@21
|
163 |
\code
|
alpar@21
|
164 |
int cnt = 0;
|
kpeter@27
|
165 |
for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a)
|
alpar@21
|
166 |
cnt++;
|
alpar@21
|
167 |
std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl;
|
alpar@21
|
168 |
\endcode
|
alpar@21
|
169 |
|
kpeter@26
|
170 |
|
kpeter@26
|
171 |
[SEC]sec_digraph_maps[SEC] Maps
|
alpar@21
|
172 |
|
kpeter@27
|
173 |
The concept of "maps" is another fundamental part of LEMON. They allow assigning
|
kpeter@27
|
174 |
values of any type to the nodes or arcs of a graph. The standard maps
|
alpar@21
|
175 |
provided by the graph structures have a couple of nice properties.
|
alpar@21
|
176 |
|
kpeter@27
|
177 |
- \e Fast. Accessing (reading/writing) the values is as fast as a
|
kpeter@27
|
178 |
simple vector reading/writing.
|
alpar@21
|
179 |
- \e Dynamic. Whenever you need, you
|
alpar@21
|
180 |
can allocate new maps in your code, just as a local variable. So when you
|
alpar@21
|
181 |
leave its scope, it will be de-allocated automatically.
|
alpar@21
|
182 |
- \e Automatic. If you add new nodes or arcs to the graph, the storage of the
|
alpar@21
|
183 |
existing maps will automatically expanded and the new slots will be
|
alpar@21
|
184 |
initialized. On the removal of an item, the corresponding values in the maps
|
alpar@21
|
185 |
are properly destructed.
|
alpar@21
|
186 |
|
kpeter@27
|
187 |
\note These maps must not be confused with \c std::map, since they provide
|
kpeter@27
|
188 |
O(1) time acces to the elements instead of O(log n).
|
kpeter@27
|
189 |
|
alpar@21
|
190 |
So, if you want to assign \c int values to each node, you have to allocate a
|
kpeter@27
|
191 |
\ref concepts::Digraph::NodeMap "NodeMap<int>".
|
alpar@21
|
192 |
|
alpar@21
|
193 |
\code
|
alpar@21
|
194 |
ListDigraph::NodeMap<int> map(g);
|
alpar@21
|
195 |
\endcode
|
alpar@21
|
196 |
|
alpar@21
|
197 |
As you see, the graph you want to assign a map is given to the
|
alpar@21
|
198 |
constructor. Then you can access its element as if it were a vector.
|
alpar@21
|
199 |
|
alpar@21
|
200 |
\code
|
kpeter@27
|
201 |
map[a] = 2;
|
kpeter@27
|
202 |
map[b] = 3;
|
kpeter@27
|
203 |
map[c] = map[a] + map[b];
|
alpar@21
|
204 |
\endcode
|
alpar@21
|
205 |
|
kpeter@27
|
206 |
Any kind of data can be assigned to the graph items.
|
kpeter@27
|
207 |
|
kpeter@27
|
208 |
\code
|
kpeter@27
|
209 |
ListDigraph::NodeMap<std::string> label(g);
|
kpeter@27
|
210 |
label[a] = "Node A";
|
kpeter@27
|
211 |
label[b] = "Node B";
|
kpeter@27
|
212 |
\endcode
|
kpeter@27
|
213 |
|
kpeter@27
|
214 |
For a more complex example, let us create a map that assigns a unique
|
alpar@21
|
215 |
integer number to each node.
|
alpar@21
|
216 |
|
alpar@21
|
217 |
\code
|
alpar@21
|
218 |
ListDigraph::NodeMap<int> id(g);
|
kpeter@27
|
219 |
int cnt = 0;
|
kpeter@27
|
220 |
for (ListDigraph::NodeIt n(g); n != INVALID; ++n)
|
kpeter@27
|
221 |
id[n] = cnt++;
|
alpar@21
|
222 |
\endcode
|
alpar@21
|
223 |
|
kpeter@27
|
224 |
When you create a map, you can also give an initial value of the elements
|
kpeter@27
|
225 |
as a second parameter. For example, the following code puts the number
|
kpeter@27
|
226 |
of outgoing arcs for each node in a map.
|
alpar@21
|
227 |
|
alpar@21
|
228 |
\code
|
kpeter@27
|
229 |
ListDigraph::NodeMap<int> out_deg(g, 0);
|
alpar@21
|
230 |
|
kpeter@27
|
231 |
for (ListDigraph::ArcIt a(g); a != INVALID; ++a)
|
alpar@21
|
232 |
out_deg[g.source(a)]++;
|
alpar@21
|
233 |
\endcode
|
alpar@21
|
234 |
|
kpeter@27
|
235 |
\warning The initial value will apply to the currently existing items only. If
|
alpar@21
|
236 |
you add new nodes/arcs to the graph, then the corresponding values in the
|
alpar@21
|
237 |
map will be initialized with the default constructor of the
|
alpar@21
|
238 |
type.
|
alpar@21
|
239 |
|
alpar@21
|
240 |
[TRAILER]
|
alpar@21
|
241 |
*/
|
alpar@21
|
242 |
}
|