COIN-OR::LEMON - Graph Library

source: lemon-tutorial/adaptors.dox @ 56:11bd4cea8379

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

Minor improvements

File size: 15.3 KB
[29]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
[32]5 * Copyright (C) 2003-2010
[29]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 */
19namespace lemon {
21[PAGE]sec_graph_adaptors[PAGE] Graph Adaptors
[39]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.
[39]34[SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph
[39]36Let us suppose that we have an instance \c g of a directed graph type, say
37\ref ListDigraph and an algorithm
[39]39  template <typename Digraph>
40  int algorithm(const Digraph&);
[39]42is needed to run on the reverse oriented digraph.
43In this situation, a certain adaptor class
[39]45  template <typename Digraph>
46  class ReverseDigraph;
[39]48can be used.
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.
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.
64For solving the problem introduced above, we could use the follwing code.
[39]67  ListDigraph g;
68  ReverseDigraph<ListDigraph> rg(g);
69  int result = algorithm(rg);
[39]72Note that the original digraph \c g remains untouched during the whole
[39]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.
[39]81  ListDigraph g;
82  int result = algorithm(reverseDigraph(g));
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.
90In the following code, Dijksta's algorithm is run on the reverse oriented
91graph but using the original node and arc maps.
94  ListDigraph g;
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);
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
111For this, \ref ReverseDigraph "ReverseDigraph<GR>" has a constructor of the
112following form.
114  ReverseDigraph(GR& gr);
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.
123int algorithm1(const ListDigraph& g) {
124  ReverseDigraph<const ListDigraph> rg(g);
125  return algorithm2(rg);
[39]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.
[39]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.
[39]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;
149    // Run BFS on the original digraph
150    Bfs<Digraph> bfs(g);
152    for (NodeIt n(g); n != INVALID; ++n) {
153      if (!bfs.reached(n)) return false;
154    }
156    // Run BFS on the reverse oriented digraph
157    typedef ReverseDigraph<const Digraph> RDigraph;
158    RDigraph rg(g);
159    Bfs<RDigraph> rbfs(rg);
161    for (NodeIt n(g); n != INVALID; ++n) {
162      if (!rbfs.reached(n)) return false;
163    }
165    return true;
166  }
[39]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.
175[SEC]sec_subgraphs[SEC] Subgraph Adaptorts
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.
[45]180In the following image, a \ref SubDigraph adaptor is applied to an
[41]181underlying 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.
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.
195  ListDigraph::ArcMap filter(g, true);
196  filter[a1] = false;
197  filter[a2] = false;
198  // ...
199  FilterArcs<ListDigraph> subgraph(g, filter);
202The following more complex code runs Dijkstra's algorithm on a digraph
203that 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);
214Note the extensive use of map adaptors and creator functions, which makes
215the code really compact and elegant.
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.
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.
228  ListGraph ug;
229  ListGraph::NodeMap<bool> node_filter(ug);
230  ListGraph::EdgeMap<bool> edge_filter(ug);
232  SubGraph<ListGraph> sg(ug, node_filter, edge_filter);
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.
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()
247  ListDigraph g;
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) << ", ";
256  filter[x] = false;
257  std::cout << countNodes(subgraph) << ", ";
259  subgraph.enable(x);
260  subgraph.disable(y);
261  subgraph.status(z, !subgraph.status(z));
262  std::cout << countNodes(subgraph) << std::endl;
265The above example prints out this line.
267  3, 2, 1
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.
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.
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.
[29]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
296  ListDigraph g;
297  ListDigraph::NodeMap<bool> filter_map(g);
298  // construct the graph and fill the filter map
300  {
[39]301    StaticDigraph tmp_graph;
302    ListDigraph::NodeMap<StaticDigraph::Node> node_ref(g);
303    digraphCopy(filterNodes(g, filter_map), tmp_graph)
[29]304      .nodeRef(node_ref).run();
[39]306    // use tmp_graph
[29]307  }
[39]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.
[39]314[SEC]sec_other_adaptors[SEC] Other Graph Adaptors
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).
327  ListGraph graph;
328  ListGraph::EdgeMap<bool> dir_map(graph, true);
329  Orienter<ListGraph> directed_graph(graph, dir_map);
[41]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
[45]335\ref Undirector adaptor is applied to a digraph.
337\image html adaptors2.png
338\image latex adaptors2.eps "Arc disjoint paths" width=\textwidth
[39]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.
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.
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));
[39]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.
[39]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.
[40]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.
377\image html splitnodes1.png
378\image latex splitnodes1.eps "Arc disjoint paths" width=\textwidth
[39]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.
[40]387For 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
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.
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.
402  ListDigraph g;
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.
Note: See TracBrowser for help on using the repository browser.