kpeter@29
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
kpeter@29
|
2 |
*
|
kpeter@29
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
kpeter@29
|
4 |
*
|
kpeter@32
|
5 |
* Copyright (C) 2003-2010
|
kpeter@29
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@29
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@29
|
8 |
*
|
kpeter@29
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@29
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@29
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@29
|
12 |
*
|
kpeter@29
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@29
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@29
|
15 |
* purpose.
|
kpeter@29
|
16 |
*
|
kpeter@29
|
17 |
*/
|
kpeter@29
|
18 |
|
kpeter@29
|
19 |
namespace lemon {
|
kpeter@29
|
20 |
/**
|
kpeter@29
|
21 |
[PAGE]sec_graph_adaptors[PAGE] Graph Adaptors
|
kpeter@29
|
22 |
|
kpeter@39
|
23 |
In typical algorithms and applications related to graphs and networks,
|
kpeter@39
|
24 |
we usually encounter situations in which a specific alteration of a graph
|
kpeter@39
|
25 |
has to be considered.
|
kpeter@39
|
26 |
If some nodes or arcs have to be hidden (maybe temporarily) or the reverse
|
kpeter@39
|
27 |
oriented graph has to be used, then this is the case.
|
kpeter@39
|
28 |
However, actually modifing physical storage of the graph or
|
kpeter@39
|
29 |
making a copy of the graph structure along with the required maps
|
kpeter@39
|
30 |
could be rather expensive (in time or in memory usage) compared to the
|
kpeter@39
|
31 |
operations that should be performed on the altered graph.
|
kpeter@39
|
32 |
In such cases, the LEMON \e graph \e adaptor \e classes could be used.
|
kpeter@29
|
33 |
|
kpeter@39
|
34 |
[SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph
|
kpeter@29
|
35 |
|
kpeter@39
|
36 |
Let us suppose that we have an instance \c g of a directed graph type, say
|
kpeter@39
|
37 |
\ref ListDigraph and an algorithm
|
kpeter@29
|
38 |
\code
|
kpeter@39
|
39 |
template <typename Digraph>
|
kpeter@39
|
40 |
int algorithm(const Digraph&);
|
kpeter@29
|
41 |
\endcode
|
kpeter@39
|
42 |
is needed to run on the reverse oriented digraph.
|
kpeter@39
|
43 |
In this situation, a certain adaptor class
|
kpeter@29
|
44 |
\code
|
kpeter@39
|
45 |
template <typename Digraph>
|
kpeter@39
|
46 |
class ReverseDigraph;
|
kpeter@29
|
47 |
\endcode
|
kpeter@39
|
48 |
can be used.
|
kpeter@39
|
49 |
|
kpeter@39
|
50 |
The graph adaptors are special classes that serve for considering other graph
|
kpeter@39
|
51 |
structures in different ways. They can be used exactly the same as "real"
|
kpeter@39
|
52 |
graphs, i.e. they conform to the \ref graph_concepts "graph concepts", thus all
|
kpeter@39
|
53 |
generic algorithms can be performed on them. However, the adaptor classes
|
kpeter@39
|
54 |
cannot be used alone but only in conjunction with actual graph representations.
|
kpeter@39
|
55 |
They do not alter the physical graph storage, they just give another view of it.
|
kpeter@39
|
56 |
When the methods of the adaptors are called, they use the underlying
|
kpeter@39
|
57 |
graph structures and their operations, thus these classes have only negligible
|
kpeter@39
|
58 |
memory usage and do not perform sophisticated algorithmic actions.
|
kpeter@39
|
59 |
|
kpeter@39
|
60 |
This technique yields convenient tools that help writing compact and elegant
|
kpeter@39
|
61 |
code, and makes it possible to easily implement complex algorithms based on
|
kpeter@39
|
62 |
well tested standard components.
|
kpeter@39
|
63 |
|
kpeter@39
|
64 |
For solving the problem introduced above, we could use the follwing code.
|
kpeter@39
|
65 |
|
kpeter@29
|
66 |
\code
|
kpeter@39
|
67 |
ListDigraph g;
|
kpeter@39
|
68 |
ReverseDigraph<ListDigraph> rg(g);
|
kpeter@39
|
69 |
int result = algorithm(rg);
|
kpeter@29
|
70 |
\endcode
|
kpeter@29
|
71 |
|
kpeter@39
|
72 |
Note that the original digraph \c g remains untouched during the whole
|
kpeter@39
|
73 |
procedure.
|
kpeter@29
|
74 |
|
kpeter@39
|
75 |
LEMON also provides simple "creator functions" for the adaptor
|
kpeter@39
|
76 |
classes to make their usage even simpler.
|
kpeter@39
|
77 |
For example, \ref reverseDigraph() returns an instance of \ref ReverseDigraph,
|
kpeter@39
|
78 |
thus the above code can be written like this.
|
kpeter@29
|
79 |
|
kpeter@29
|
80 |
\code
|
kpeter@39
|
81 |
ListDigraph g;
|
kpeter@39
|
82 |
int result = algorithm(reverseDigraph(g));
|
kpeter@29
|
83 |
\endcode
|
kpeter@39
|
84 |
|
kpeter@39
|
85 |
Another essential feature of the adaptors is that their \c Node and \c Arc
|
kpeter@39
|
86 |
types convert to the original item types.
|
kpeter@39
|
87 |
Therefore, the maps of the original graph can be used in connection with
|
kpeter@39
|
88 |
the adaptor.
|
kpeter@39
|
89 |
|
kpeter@39
|
90 |
In the following code, Dijksta's algorithm is run on the reverse oriented
|
kpeter@39
|
91 |
graph but using the original node and arc maps.
|
kpeter@39
|
92 |
|
kpeter@39
|
93 |
\code
|
kpeter@39
|
94 |
ListDigraph g;
|
kpeter@39
|
95 |
ListDigraph::ArcMap length(g);
|
kpeter@39
|
96 |
ListDigraph::NodeMap dist(g);
|
kpeter@39
|
97 |
|
kpeter@39
|
98 |
ListDigraph::Node s = g.addNode();
|
kpeter@39
|
99 |
// add more nodes and arcs
|
kpeter@39
|
100 |
|
kpeter@39
|
101 |
dijkstra(reverseDigraph(g), length).distMap(dist).run(s);
|
kpeter@39
|
102 |
\endcode
|
kpeter@39
|
103 |
|
kpeter@39
|
104 |
In the above examples, we used \ref ReverseDigraph in such a way that the
|
kpeter@39
|
105 |
underlying digraph was not changed. However, the adaptor class can even be
|
kpeter@39
|
106 |
used for modifying the original graph structure.
|
kpeter@39
|
107 |
It allows adding and deleting arcs or nodes, and these operations are carried
|
kpeter@39
|
108 |
out by calling suitable functions of the underlying digraph (if it supports
|
kpeter@39
|
109 |
them).
|
kpeter@39
|
110 |
|
kpeter@39
|
111 |
For this, \ref ReverseDigraph "ReverseDigraph<GR>" has a constructor of the
|
kpeter@39
|
112 |
following form.
|
kpeter@39
|
113 |
\code
|
kpeter@39
|
114 |
ReverseDigraph(GR& gr);
|
kpeter@39
|
115 |
\endcode
|
kpeter@39
|
116 |
|
kpeter@39
|
117 |
This means that in a situation, when the modification of the original graph
|
kpeter@39
|
118 |
has to be avoided (e.g. it is given as a const reference), then the adaptor
|
kpeter@39
|
119 |
class has to be instantiated with \c GR set to be \c const type
|
kpeter@39
|
120 |
(e.g. <tt>GR = const %ListDigraph</tt>), as in the following example.
|
kpeter@39
|
121 |
|
kpeter@29
|
122 |
\code
|
kpeter@29
|
123 |
int algorithm1(const ListDigraph& g) {
|
kpeter@29
|
124 |
ReverseDigraph<const ListDigraph> rg(g);
|
kpeter@29
|
125 |
return algorithm2(rg);
|
kpeter@29
|
126 |
}
|
kpeter@29
|
127 |
\endcode
|
kpeter@29
|
128 |
|
kpeter@39
|
129 |
\note Modification capabilities are not supported for all adaptors.
|
kpeter@39
|
130 |
E.g. for \ref ResidualDigraph (see \ref sec_other_adaptors "later"),
|
kpeter@39
|
131 |
this makes no sense.
|
kpeter@29
|
132 |
|
kpeter@39
|
133 |
As a more complex example, let us see how \ref ReverseDigraph can be used
|
kpeter@39
|
134 |
together with a graph search algorithm to decide whether a directed graph is
|
kpeter@39
|
135 |
strongly connected or not.
|
kpeter@39
|
136 |
We exploit the fact the a digraph is strongly connected if and only if
|
kpeter@39
|
137 |
for an arbitrarily selected node \c u, each other node is reachable from
|
kpeter@39
|
138 |
\c u (along a directed path) and \c u is reachable from each node.
|
kpeter@39
|
139 |
The latter condition is the same that each node is reachable from \c u
|
kpeter@39
|
140 |
in the reversed digraph.
|
kpeter@29
|
141 |
|
kpeter@29
|
142 |
\code
|
kpeter@39
|
143 |
template <typename Digraph>
|
kpeter@39
|
144 |
bool stronglyConnected(const Digraph& g) {
|
kpeter@39
|
145 |
typedef typename Digraph::NodeIt NodeIt;
|
kpeter@39
|
146 |
NodeIt u(g);
|
kpeter@39
|
147 |
if (u == INVALID) return true;
|
kpeter@39
|
148 |
|
kpeter@39
|
149 |
// Run BFS on the original digraph
|
kpeter@39
|
150 |
Bfs<Digraph> bfs(g);
|
kpeter@39
|
151 |
bfs.run(u);
|
kpeter@39
|
152 |
for (NodeIt n(g); n != INVALID; ++n) {
|
kpeter@39
|
153 |
if (!bfs.reached(n)) return false;
|
kpeter@39
|
154 |
}
|
kpeter@39
|
155 |
|
kpeter@39
|
156 |
// Run BFS on the reverse oriented digraph
|
kpeter@39
|
157 |
typedef ReverseDigraph<const Digraph> RDigraph;
|
kpeter@39
|
158 |
RDigraph rg(g);
|
kpeter@39
|
159 |
Bfs<RDigraph> rbfs(rg);
|
kpeter@39
|
160 |
rbfs.run(u);
|
kpeter@39
|
161 |
for (NodeIt n(g); n != INVALID; ++n) {
|
kpeter@39
|
162 |
if (!rbfs.reached(n)) return false;
|
kpeter@39
|
163 |
}
|
kpeter@39
|
164 |
|
kpeter@39
|
165 |
return true;
|
kpeter@39
|
166 |
}
|
kpeter@29
|
167 |
\endcode
|
kpeter@29
|
168 |
|
kpeter@39
|
169 |
Note that we have to use the adaptor with '<tt>const Digraph</tt>' type, since
|
kpeter@39
|
170 |
\c g is a \c const reference to the original graph structure.
|
kpeter@39
|
171 |
The \ref stronglyConnected() function provided in LEMON has a quite
|
kpeter@39
|
172 |
similar implementation.
|
kpeter@29
|
173 |
|
kpeter@39
|
174 |
|
kpeter@39
|
175 |
[SEC]sec_subgraphs[SEC] Subgraph Adaptorts
|
kpeter@39
|
176 |
|
kpeter@39
|
177 |
Another typical requirement is the use of certain subgraphs of a graph,
|
kpeter@39
|
178 |
or in other words, hiding nodes and/or arcs from a graph.
|
kpeter@39
|
179 |
LEMON provides several convenient adaptors for these purposes.
|
kpeter@45
|
180 |
In the following image, a \ref SubDigraph adaptor is applied to an
|
kpeter@41
|
181 |
underlying digraph structure to obtain a suitable subgraph.
|
kpeter@41
|
182 |
|
kpeter@41
|
183 |
\image html adaptors1.png
|
kpeter@41
|
184 |
\image latex adaptors1.eps "SubDigraph adaptor" width=\textwidth
|
kpeter@39
|
185 |
|
kpeter@39
|
186 |
\ref FilterArcs can be used when some arcs have to be hidden from a digraph.
|
kpeter@39
|
187 |
A \e filter \e map has to be given to the constructor, which assign \c bool
|
kpeter@39
|
188 |
values to the arcs specifying whether they have to be shown or not in the
|
kpeter@39
|
189 |
subgraph structure.
|
kpeter@39
|
190 |
Suppose we have a \ref ListDigraph structure \c g.
|
kpeter@39
|
191 |
Then we can construct a subgraph in which some arcs (\c a1, \c a2 etc.)
|
kpeter@39
|
192 |
are hidden as follows.
|
kpeter@39
|
193 |
|
kpeter@39
|
194 |
\code
|
kpeter@39
|
195 |
ListDigraph::ArcMap filter(g, true);
|
kpeter@39
|
196 |
filter[a1] = false;
|
kpeter@39
|
197 |
filter[a2] = false;
|
kpeter@39
|
198 |
// ...
|
kpeter@39
|
199 |
FilterArcs<ListDigraph> subgraph(g, filter);
|
kpeter@39
|
200 |
\endcode
|
kpeter@39
|
201 |
|
kpeter@39
|
202 |
The following more complex code runs Dijkstra's algorithm on a digraph
|
kpeter@39
|
203 |
that is obtained from another digraph by hiding all arcs having negative
|
kpeter@39
|
204 |
lengths.
|
kpeter@39
|
205 |
|
kpeter@39
|
206 |
\code
|
kpeter@39
|
207 |
ListDigraph::ArcMap<int> length(g);
|
kpeter@39
|
208 |
ListDigraph::NodeMap<int> dist(g);
|
kpeter@39
|
209 |
|
kpeter@39
|
210 |
dijkstra(filterArcs( g, lessMap(length, constMap<ListDigraph::Arc>(0)) ),
|
kpeter@39
|
211 |
length).distMap(dist).run(s);
|
kpeter@39
|
212 |
\endcode
|
kpeter@39
|
213 |
|
kpeter@39
|
214 |
Note the extensive use of map adaptors and creator functions, which makes
|
kpeter@39
|
215 |
the code really compact and elegant.
|
kpeter@39
|
216 |
|
kpeter@39
|
217 |
\note Implicit maps and graphs (e.g. created using functions) can only be
|
kpeter@39
|
218 |
used with the function-type interfaces of the algorithms, since they store
|
kpeter@39
|
219 |
only references for the used structures.
|
kpeter@39
|
220 |
|
kpeter@39
|
221 |
\ref FilterEdges can be used for hiding edges from an undirected graph (like
|
kpeter@39
|
222 |
\ref FilterArcs is used for digraphs). \ref FilterNodes serves for filtering
|
kpeter@39
|
223 |
nodes along with the incident arcs or edges in a directed or undirected graph.
|
kpeter@39
|
224 |
If both arcs/edges and nodes have to be hidden, then you could use
|
kpeter@39
|
225 |
\ref SubDigraph or \ref SubGraph adaptors.
|
kpeter@39
|
226 |
|
kpeter@39
|
227 |
\code
|
kpeter@39
|
228 |
ListGraph ug;
|
kpeter@39
|
229 |
ListGraph::NodeMap<bool> node_filter(ug);
|
kpeter@39
|
230 |
ListGraph::EdgeMap<bool> edge_filter(ug);
|
kpeter@39
|
231 |
|
kpeter@39
|
232 |
SubGraph<ListGraph> sg(ug, node_filter, edge_filter);
|
kpeter@39
|
233 |
\endcode
|
kpeter@39
|
234 |
|
kpeter@39
|
235 |
As you see, we needed two filter maps in this case: one for the nodes and
|
kpeter@39
|
236 |
another for the edges. If a node is hidden, then all of its incident edges
|
kpeter@39
|
237 |
are also considered to be hidden independently of their own filter values.
|
kpeter@39
|
238 |
|
kpeter@39
|
239 |
The subgraph adaptors also make it possible to modify the filter values
|
kpeter@39
|
240 |
even after the construction of the adaptor class, thus the corresponding
|
kpeter@39
|
241 |
graph items can be hidden or shown on the fly.
|
kpeter@39
|
242 |
The adaptors store references to the filter maps, thus the map values can be
|
kpeter@39
|
243 |
set directly and even by using the \c enable(), \c disable() and \c status()
|
kpeter@39
|
244 |
functions.
|
kpeter@39
|
245 |
|
kpeter@39
|
246 |
\code
|
kpeter@39
|
247 |
ListDigraph g;
|
kpeter@39
|
248 |
ListDigraph::Node x = g.addNode();
|
kpeter@39
|
249 |
ListDigraph::Node y = g.addNode();
|
kpeter@39
|
250 |
ListDigraph::Node z = g.addNode();
|
kpeter@39
|
251 |
|
kpeter@39
|
252 |
ListDigraph::NodeMap<bool> filter(g, true);
|
kpeter@39
|
253 |
FilterNodes<ListDigraph> subgraph(g, filter);
|
kpeter@39
|
254 |
std::cout << countNodes(subgraph) << ", ";
|
kpeter@39
|
255 |
|
kpeter@39
|
256 |
filter[x] = false;
|
kpeter@39
|
257 |
std::cout << countNodes(subgraph) << ", ";
|
kpeter@39
|
258 |
|
kpeter@39
|
259 |
subgraph.enable(x);
|
kpeter@39
|
260 |
subgraph.disable(y);
|
kpeter@39
|
261 |
subgraph.status(z, !subgraph.status(z));
|
kpeter@39
|
262 |
std::cout << countNodes(subgraph) << std::endl;
|
kpeter@39
|
263 |
\endcode
|
kpeter@39
|
264 |
|
kpeter@39
|
265 |
The above example prints out this line.
|
kpeter@39
|
266 |
\code
|
kpeter@39
|
267 |
3, 2, 1
|
kpeter@39
|
268 |
\endcode
|
kpeter@39
|
269 |
|
kpeter@39
|
270 |
Similarly to \ref ReverseDigraph, the subgraph adaptors also allow the
|
kpeter@39
|
271 |
modification of the underlying graph structures unless the graph template
|
kpeter@39
|
272 |
parameter is set to be \c const type.
|
kpeter@39
|
273 |
Moreover the item types of the original graphs and the subgraphs are
|
kpeter@39
|
274 |
convertible to each other.
|
kpeter@39
|
275 |
|
kpeter@39
|
276 |
The iterators of the subgraph adaptors use the iterators of the original
|
kpeter@39
|
277 |
graph structures in such a way that each item with \c false filter value
|
kpeter@39
|
278 |
is skipped. If both the node and arc sets are filtered, then the arc iterators
|
kpeter@39
|
279 |
check for each arc the status of its end nodes in addition to its own assigned
|
kpeter@39
|
280 |
filter value. If the arc or one of its end nodes is hidden, then the arc
|
kpeter@39
|
281 |
is left out and the next arc is considered.
|
kpeter@39
|
282 |
(It is the same for edges in undirected graphs.)
|
kpeter@39
|
283 |
Therefore, the iterators of these adaptors are significantly slower than the
|
kpeter@39
|
284 |
original iterators.
|
kpeter@39
|
285 |
|
kpeter@39
|
286 |
Using adaptors, these efficiency aspects should be kept in mind.
|
kpeter@39
|
287 |
For example, if rather complex algorithms have to be performed on a
|
kpeter@39
|
288 |
subgraph (e.g. the nodes and arcs need to be traversed several times),
|
kpeter@39
|
289 |
then it could worth copying the altered graph into an efficient
|
kpeter@39
|
290 |
structure (e.g. \ref StaticDigraph) and run the algorithm on it.
|
kpeter@29
|
291 |
Note that the adaptor classes can also be used for doing this easily,
|
kpeter@29
|
292 |
without having to copy the graph manually, as shown in the following
|
kpeter@29
|
293 |
example.
|
kpeter@29
|
294 |
|
kpeter@29
|
295 |
\code
|
kpeter@29
|
296 |
ListDigraph g;
|
kpeter@29
|
297 |
ListDigraph::NodeMap<bool> filter_map(g);
|
kpeter@29
|
298 |
// construct the graph and fill the filter map
|
kpeter@29
|
299 |
|
kpeter@29
|
300 |
{
|
kpeter@39
|
301 |
StaticDigraph tmp_graph;
|
kpeter@39
|
302 |
ListDigraph::NodeMap<StaticDigraph::Node> node_ref(g);
|
kpeter@39
|
303 |
digraphCopy(filterNodes(g, filter_map), tmp_graph)
|
kpeter@29
|
304 |
.nodeRef(node_ref).run();
|
kpeter@29
|
305 |
|
kpeter@39
|
306 |
// use tmp_graph
|
kpeter@29
|
307 |
}
|
kpeter@29
|
308 |
\endcode
|
kpeter@29
|
309 |
|
kpeter@39
|
310 |
\note Using \ref ReverseDigraph could be as efficient as working with the
|
kpeter@39
|
311 |
original graph, but most of the adaptors cannot be so fast, of course.
|
kpeter@29
|
312 |
|
kpeter@29
|
313 |
|
kpeter@39
|
314 |
[SEC]sec_other_adaptors[SEC] Other Graph Adaptors
|
kpeter@39
|
315 |
|
kpeter@39
|
316 |
Two other practical adaptors are \ref Undirector and \ref Orienter.
|
kpeter@39
|
317 |
\ref Undirector makes an undirected graph from a digraph disregarding the
|
kpeter@39
|
318 |
orientations of the arcs. More precisely, an arc of the original digraph
|
kpeter@39
|
319 |
is considered as an edge (and two arcs, as well) in the adaptor.
|
kpeter@39
|
320 |
\ref Orienter can be used for the reverse alteration, it assigns a certain
|
kpeter@39
|
321 |
orientation to each edge of an undirected graph to form a directed graph.
|
kpeter@39
|
322 |
A \c bool edge map of the underlying graph must be given to the constructor
|
kpeter@39
|
323 |
of the class, which define the direction of the arcs in the created adaptor
|
kpeter@39
|
324 |
(with respect to the inherent orientation of the original edges).
|
kpeter@39
|
325 |
|
kpeter@39
|
326 |
\code
|
kpeter@39
|
327 |
ListGraph graph;
|
kpeter@39
|
328 |
ListGraph::EdgeMap<bool> dir_map(graph, true);
|
kpeter@39
|
329 |
Orienter<ListGraph> directed_graph(graph, dir_map);
|
kpeter@39
|
330 |
\endcode
|
kpeter@39
|
331 |
|
kpeter@41
|
332 |
Sine the adaptor classes conform to the \ref graph_concepts "graph concepts",
|
kpeter@41
|
333 |
we can even apply an adaptor to another one.
|
kpeter@41
|
334 |
The following image illustrates a situation when a \ref SubDigraph and an
|
kpeter@45
|
335 |
\ref Undirector adaptor is applied to a digraph.
|
kpeter@41
|
336 |
|
kpeter@41
|
337 |
\image html adaptors2.png
|
kpeter@41
|
338 |
\image latex adaptors2.eps "Arc disjoint paths" width=\textwidth
|
kpeter@41
|
339 |
|
kpeter@39
|
340 |
LEMON also provides some more complex adaptors, for
|
kpeter@39
|
341 |
instance, \ref SplitNodes, which can be used for splitting each node of a
|
kpeter@39
|
342 |
directed graph into an in-node and an out-node.
|
kpeter@39
|
343 |
Formally, the adaptor replaces each node u in the graph with two nodes,
|
kpeter@39
|
344 |
namely u<sub>in</sub> and u<sub>out</sub>. Each arc (u,v) of the original
|
kpeter@39
|
345 |
graph will correspond to an arc (u<sub>out</sub>,v<sub>in</sub>).
|
kpeter@39
|
346 |
The adaptor also adds an additional bind arc (u<sub>in</sub>,u<sub>out</sub>)
|
kpeter@39
|
347 |
for each node u of the original digraph.
|
kpeter@39
|
348 |
|
kpeter@39
|
349 |
The aim of this class is to assign costs or capacities to the nodes when using
|
kpeter@39
|
350 |
algorithms which would otherwise consider arc costs or capacities only.
|
kpeter@39
|
351 |
For example, let us suppose that we have a digraph \c g with costs assigned to
|
kpeter@39
|
352 |
both the nodes and the arcs. Then Dijkstra's algorithm can be used in
|
kpeter@39
|
353 |
connection with \ref SplitNodes as follows.
|
kpeter@29
|
354 |
|
kpeter@29
|
355 |
\code
|
kpeter@29
|
356 |
typedef SplitNodes<ListDigraph> SplitGraph;
|
kpeter@29
|
357 |
SplitGraph sg(g);
|
kpeter@29
|
358 |
SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap>
|
kpeter@29
|
359 |
combined_cost(node_cost, arc_cost);
|
kpeter@29
|
360 |
SplitGraph::NodeMap<double> dist(sg);
|
kpeter@29
|
361 |
dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u));
|
kpeter@29
|
362 |
\endcode
|
kpeter@29
|
363 |
|
kpeter@39
|
364 |
\note This problem can also be solved using map adaptors to create
|
kpeter@39
|
365 |
an implicit arc map that assigns for each arc the sum of its cost
|
kpeter@39
|
366 |
and the cost of its target node. This map can be used with the original
|
kpeter@39
|
367 |
graph more efficiently than using the above solution.
|
kpeter@29
|
368 |
|
kpeter@39
|
369 |
Another nice application is the problem of finding disjoint paths in
|
kpeter@39
|
370 |
a digraph.
|
kpeter@39
|
371 |
The maximum number of \e edge \e disjoint paths from a source node to
|
kpeter@39
|
372 |
a sink node in a digraph can be easily computed using a maximum flow
|
kpeter@39
|
373 |
algorithm with all arc capacities set to 1.
|
kpeter@40
|
374 |
For example, in the following digraph, four arc disjoint paths can be found
|
kpeter@40
|
375 |
from the node on the left to the node on the right.
|
kpeter@40
|
376 |
|
kpeter@40
|
377 |
\image html splitnodes1.png
|
kpeter@40
|
378 |
\image latex splitnodes1.eps "Arc disjoint paths" width=\textwidth
|
kpeter@40
|
379 |
|
kpeter@39
|
380 |
On the other hand, \e node \e disjoint paths cannot be found directly
|
kpeter@39
|
381 |
using a standard algorithm.
|
kpeter@39
|
382 |
However, \ref SplitNodes adaptor makes it really simple.
|
kpeter@39
|
383 |
If a maximum flow computation is performed on this adaptor, then the
|
kpeter@39
|
384 |
bottleneck of the flow (i.e. the minimum cut) will be formed by bind arcs,
|
kpeter@39
|
385 |
thus the found flow will correspond to the union of some node disjoint
|
kpeter@39
|
386 |
paths in terms of the original digraph.
|
kpeter@40
|
387 |
For example, in the above digraph, there are only three node disjoint paths.
|
kpeter@40
|
388 |
|
kpeter@40
|
389 |
\image html splitnodes2.png
|
kpeter@40
|
390 |
\image latex splitnodes2.eps "Node disjoint paths" width=\textwidth
|
kpeter@39
|
391 |
|
kpeter@39
|
392 |
In flow, circulation and matching problems, the residual network is of
|
kpeter@39
|
393 |
particular importance, which is implemented in \ref ResidualDigraph.
|
kpeter@39
|
394 |
Combining this adaptor with various algorithms, a range of weighted and
|
kpeter@39
|
395 |
cardinality optimization methods can be implemented easily.
|
kpeter@39
|
396 |
|
kpeter@39
|
397 |
To construct a residual network, a digraph structure, a flow map and a
|
kpeter@39
|
398 |
capacity map have to be given to the constructor of the adaptor as shown
|
kpeter@39
|
399 |
in the following code.
|
kpeter@39
|
400 |
|
kpeter@39
|
401 |
\code
|
kpeter@39
|
402 |
ListDigraph g;
|
kpeter@39
|
403 |
ListDigraph::ArcMap<int> flow(g);
|
kpeter@39
|
404 |
ListDigraph::ArcMap<int> capacity(g);
|
kpeter@39
|
405 |
|
kpeter@39
|
406 |
ResidualDigraph<ListDigraph> res_graph(g, capacity, flow);
|
kpeter@39
|
407 |
\endcode
|
kpeter@39
|
408 |
|
kpeter@39
|
409 |
\note In fact, this class is implemented using two other adaptors:
|
kpeter@39
|
410 |
\ref Undirector and \ref FilterArcs.
|
kpeter@29
|
411 |
|
kpeter@29
|
412 |
[TRAILER]
|
kpeter@29
|
413 |
*/
|
kpeter@32
|
414 |
}
|