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_adaptors[PAGE] Graph Adaptors
23 In typical algorithms and applications related to graphs and networks,
24 we usually encounter situations in which a specific alteration of a graph
26 If some nodes or arcs have to be hidden (maybe temporarily) or the reverse
27 oriented graph has to be used, then this is the case.
28 However, actually modifing physical storage of the graph or
29 making a copy of the graph structure along with the required maps
30 could be rather expensive (in time or in memory usage) compared to the
31 operations that should be performed on the altered graph.
32 In such cases, the LEMON \e graph \e adaptor \e classes could be used.
34 [SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph
36 Let us suppose that we have an instance \c g of a directed graph type, say
37 \ref ListDigraph and an algorithm
39 template <typename Digraph>
40 int algorithm(const Digraph&);
42 is needed to run on the reverse oriented digraph.
43 In this situation, a certain adaptor class
45 template <typename Digraph>
50 The graph adaptors are special classes that serve for considering other graph
51 structures in different ways. They can be used exactly the same as "real"
52 graphs, i.e. they conform to the \ref graph_concepts "graph concepts", thus all
53 generic algorithms can be performed on them. However, the adaptor classes
54 cannot be used alone but only in conjunction with actual graph representations.
55 They do not alter the physical graph storage, they just give another view of it.
56 When the methods of the adaptors are called, they use the underlying
57 graph structures and their operations, thus these classes have only negligible
58 memory usage and do not perform sophisticated algorithmic actions.
60 This technique yields convenient tools that help writing compact and elegant
61 code, and makes it possible to easily implement complex algorithms based on
62 well tested standard components.
64 For solving the problem introduced above, we could use the follwing code.
68 ReverseDigraph<ListDigraph> rg(g);
69 int result = algorithm(rg);
72 Note that the original digraph \c g remains untouched during the whole
75 LEMON also provides simple "creator functions" for the adaptor
76 classes to make their usage even simpler.
77 For example, \ref reverseDigraph() returns an instance of \ref ReverseDigraph,
78 thus the above code can be written like this.
82 int result = algorithm(reverseDigraph(g));
85 Another essential feature of the adaptors is that their \c Node and \c Arc
86 types convert to the original item types.
87 Therefore, the maps of the original graph can be used in connection with
90 In the following code, Dijksta's algorithm is run on the reverse oriented
91 graph but using the original node and arc maps.
95 ListDigraph::ArcMap length(g);
96 ListDigraph::NodeMap dist(g);
98 ListDigraph::Node s = g.addNode();
99 // add more nodes and arcs
101 dijkstra(reverseDigraph(g), length).distMap(dist).run(s);
104 In the above examples, we used \ref ReverseDigraph in such a way that the
105 underlying digraph was not changed. However, the adaptor class can even be
106 used for modifying the original graph structure.
107 It allows adding and deleting arcs or nodes, and these operations are carried
108 out by calling suitable functions of the underlying digraph (if it supports
111 For this, \ref ReverseDigraph "ReverseDigraph<GR>" has a constructor of the
114 ReverseDigraph(GR& gr);
117 This means that in a situation, when the modification of the original graph
118 has to be avoided (e.g. it is given as a const reference), then the adaptor
119 class has to be instantiated with \c GR set to be \c const type
120 (e.g. <tt>GR = const %ListDigraph</tt>), as in the following example.
123 int algorithm1(const ListDigraph& g) {
124 ReverseDigraph<const ListDigraph> rg(g);
125 return algorithm2(rg);
129 \note Modification capabilities are not supported for all adaptors.
130 E.g. for \ref ResidualDigraph (see \ref sec_other_adaptors "later"),
133 As a more complex example, let us see how \ref ReverseDigraph can be used
134 together with a graph search algorithm to decide whether a directed graph is
135 strongly connected or not.
136 We exploit the fact the a digraph is strongly connected if and only if
137 for an arbitrarily selected node \c u, each other node is reachable from
138 \c u (along a directed path) and \c u is reachable from each node.
139 The latter condition is the same that each node is reachable from \c u
140 in the reversed digraph.
143 template <typename Digraph>
144 bool stronglyConnected(const Digraph& g) {
145 typedef typename Digraph::NodeIt NodeIt;
147 if (u == INVALID) return true;
149 // Run BFS on the original digraph
152 for (NodeIt n(g); n != INVALID; ++n) {
153 if (!bfs.reached(n)) return false;
156 // Run BFS on the reverse oriented digraph
157 typedef ReverseDigraph<const Digraph> RDigraph;
159 Bfs<RDigraph> rbfs(rg);
161 for (NodeIt n(g); n != INVALID; ++n) {
162 if (!rbfs.reached(n)) return false;
169 Note that we have to use the adaptor with '<tt>const Digraph</tt>' type, since
170 \c g is a \c const reference to the original graph structure.
171 The \ref stronglyConnected() function provided in LEMON has a quite
172 similar implementation.
175 [SEC]sec_subgraphs[SEC] Subgraph Adaptorts
177 Another typical requirement is the use of certain subgraphs of a graph,
178 or in other words, hiding nodes and/or arcs from a graph.
179 LEMON provides several convenient adaptors for these purposes.
180 In the following image, a \ref SubDigraph adaptor is applied to an
181 underlying digraph structure to obtain a suitable subgraph.
183 \image html adaptors1.png
184 \image latex adaptors1.eps "SubDigraph adaptor" width=\textwidth
186 \ref FilterArcs can be used when some arcs have to be hidden from a digraph.
187 A \e filter \e map has to be given to the constructor, which assign \c bool
188 values to the arcs specifying whether they have to be shown or not in the
190 Suppose we have a \ref ListDigraph structure \c g.
191 Then we can construct a subgraph in which some arcs (\c a1, \c a2 etc.)
192 are hidden as follows.
195 ListDigraph::ArcMap filter(g, true);
199 FilterArcs<ListDigraph> subgraph(g, filter);
202 The following more complex code runs Dijkstra's algorithm on a digraph
203 that is obtained from another digraph by hiding all arcs having negative
207 ListDigraph::ArcMap<int> length(g);
208 ListDigraph::NodeMap<int> dist(g);
210 dijkstra(filterArcs( g, lessMap(length, constMap<ListDigraph::Arc>(0)) ),
211 length).distMap(dist).run(s);
214 Note the extensive use of map adaptors and creator functions, which makes
215 the code really compact and elegant.
217 \note Implicit maps and graphs (e.g. created using functions) can only be
218 used with the function-type interfaces of the algorithms, since they store
219 only references for the used structures.
221 \ref FilterEdges can be used for hiding edges from an undirected graph (like
222 \ref FilterArcs is used for digraphs). \ref FilterNodes serves for filtering
223 nodes along with the incident arcs or edges in a directed or undirected graph.
224 If both arcs/edges and nodes have to be hidden, then you could use
225 \ref SubDigraph or \ref SubGraph adaptors.
229 ListGraph::NodeMap<bool> node_filter(ug);
230 ListGraph::EdgeMap<bool> edge_filter(ug);
232 SubGraph<ListGraph> sg(ug, node_filter, edge_filter);
235 As you see, we needed two filter maps in this case: one for the nodes and
236 another for the edges. If a node is hidden, then all of its incident edges
237 are also considered to be hidden independently of their own filter values.
239 The subgraph adaptors also make it possible to modify the filter values
240 even after the construction of the adaptor class, thus the corresponding
241 graph items can be hidden or shown on the fly.
242 The adaptors store references to the filter maps, thus the map values can be
243 set directly and even by using the \c enable(), \c disable() and \c status()
248 ListDigraph::Node x = g.addNode();
249 ListDigraph::Node y = g.addNode();
250 ListDigraph::Node z = g.addNode();
252 ListDigraph::NodeMap<bool> filter(g, true);
253 FilterNodes<ListDigraph> subgraph(g, filter);
254 std::cout << countNodes(subgraph) << ", ";
257 std::cout << countNodes(subgraph) << ", ";
261 subgraph.status(z, !subgraph.status(z));
262 std::cout << countNodes(subgraph) << std::endl;
265 The above example prints out this line.
270 Similarly to \ref ReverseDigraph, the subgraph adaptors also allow the
271 modification of the underlying graph structures unless the graph template
272 parameter is set to be \c const type.
273 Moreover the item types of the original graphs and the subgraphs are
274 convertible to each other.
276 The iterators of the subgraph adaptors use the iterators of the original
277 graph structures in such a way that each item with \c false filter value
278 is skipped. If both the node and arc sets are filtered, then the arc iterators
279 check for each arc the status of its end nodes in addition to its own assigned
280 filter value. If the arc or one of its end nodes is hidden, then the arc
281 is left out and the next arc is considered.
282 (It is the same for edges in undirected graphs.)
283 Therefore, the iterators of these adaptors are significantly slower than the
286 Using adaptors, these efficiency aspects should be kept in mind.
287 For example, if rather complex algorithms have to be performed on a
288 subgraph (e.g. the nodes and arcs need to be traversed several times),
289 then it could worth copying the altered graph into an efficient
290 structure (e.g. \ref StaticDigraph) and run the algorithm on it.
291 Note that the adaptor classes can also be used for doing this easily,
292 without having to copy the graph manually, as shown in the following
297 ListDigraph::NodeMap<bool> filter_map(g);
298 // construct the graph and fill the filter map
301 StaticDigraph tmp_graph;
302 ListDigraph::NodeMap<StaticDigraph::Node> node_ref(g);
303 digraphCopy(filterNodes(g, filter_map), tmp_graph)
304 .nodeRef(node_ref).run();
310 \note Using \ref ReverseDigraph could be as efficient as working with the
311 original graph, but most of the adaptors cannot be so fast, of course.
314 [SEC]sec_other_adaptors[SEC] Other Graph Adaptors
316 Two other practical adaptors are \ref Undirector and \ref Orienter.
317 \ref Undirector makes an undirected graph from a digraph disregarding the
318 orientations of the arcs. More precisely, an arc of the original digraph
319 is considered as an edge (and two arcs, as well) in the adaptor.
320 \ref Orienter can be used for the reverse alteration, it assigns a certain
321 orientation to each edge of an undirected graph to form a directed graph.
322 A \c bool edge map of the underlying graph must be given to the constructor
323 of the class, which define the direction of the arcs in the created adaptor
324 (with respect to the inherent orientation of the original edges).
328 ListGraph::EdgeMap<bool> dir_map(graph, true);
329 Orienter<ListGraph> directed_graph(graph, dir_map);
332 Sine the adaptor classes conform to the \ref graph_concepts "graph concepts",
333 we can even apply an adaptor to another one.
334 The following image illustrates a situation when a \ref SubDigraph and an
335 \ref Undirector adaptor is applied to a digraph.
337 \image html adaptors2.png
338 \image latex adaptors2.eps "Arc disjoint paths" width=\textwidth
340 LEMON also provides some more complex adaptors, for
341 instance, \ref SplitNodes, which can be used for splitting each node of a
342 directed graph into an in-node and an out-node.
343 Formally, the adaptor replaces each node u in the graph with two nodes,
344 namely u<sub>in</sub> and u<sub>out</sub>. Each arc (u,v) of the original
345 graph will correspond to an arc (u<sub>out</sub>,v<sub>in</sub>).
346 The adaptor also adds an additional bind arc (u<sub>in</sub>,u<sub>out</sub>)
347 for each node u of the original digraph.
349 The aim of this class is to assign costs or capacities to the nodes when using
350 algorithms which would otherwise consider arc costs or capacities only.
351 For example, let us suppose that we have a digraph \c g with costs assigned to
352 both the nodes and the arcs. Then Dijkstra's algorithm can be used in
353 connection with \ref SplitNodes as follows.
356 typedef SplitNodes<ListDigraph> SplitGraph;
358 SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap>
359 combined_cost(node_cost, arc_cost);
360 SplitGraph::NodeMap<double> dist(sg);
361 dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u));
364 \note This problem can also be solved using map adaptors to create
365 an implicit arc map that assigns for each arc the sum of its cost
366 and the cost of its target node. This map can be used with the original
367 graph more efficiently than using the above solution.
369 Another nice application is the problem of finding disjoint paths in
371 The maximum number of \e edge \e disjoint paths from a source node to
372 a sink node in a digraph can be easily computed using a maximum flow
373 algorithm with all arc capacities set to 1.
374 For example, in the following digraph, four arc disjoint paths can be found
375 from the node on the left to the node on the right.
377 \image html splitnodes1.png
378 \image latex splitnodes1.eps "Arc disjoint paths" width=\textwidth
380 On the other hand, \e node \e disjoint paths cannot be found directly
381 using a standard algorithm.
382 However, \ref SplitNodes adaptor makes it really simple.
383 If a maximum flow computation is performed on this adaptor, then the
384 bottleneck of the flow (i.e. the minimum cut) will be formed by bind arcs,
385 thus the found flow will correspond to the union of some node disjoint
386 paths in terms of the original digraph.
387 For example, in the above digraph, there are only three node disjoint paths.
389 \image html splitnodes2.png
390 \image latex splitnodes2.eps "Node disjoint paths" width=\textwidth
392 In flow, circulation and matching problems, the residual network is of
393 particular importance, which is implemented in \ref ResidualDigraph.
394 Combining this adaptor with various algorithms, a range of weighted and
395 cardinality optimization methods can be implemented easily.
397 To construct a residual network, a digraph structure, a flow map and a
398 capacity map have to be given to the constructor of the adaptor as shown
399 in the following code.
403 ListDigraph::ArcMap<int> flow(g);
404 ListDigraph::ArcMap<int> capacity(g);
406 ResidualDigraph<ListDigraph> res_graph(g, capacity, flow);
409 \note In fact, this class is implemented using two other adaptors:
410 \ref Undirector and \ref FilterArcs.