COIN-OR::LEMON - Graph Library

source: lemon-tutorial/adaptors.dox @ 45:725c60c7492d

Last change on this file since 45:725c60c7492d was 45:725c60c7492d, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Minor improvements

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