COIN-OR::LEMON - Graph Library

source: lemon-tutorial/adaptors.dox @ 40:e1725bb7e821

Last change on this file since 40:e1725bb7e821 was 40:e1725bb7e821, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Port two images for SplitNodes? from SVN -r3524

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