COIN-OR::LEMON - Graph Library

source: lemon-tutorial/adaptors.dox @ 29:bc3ef6652f1b

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

Add a preliminary page of graph adaptors

File size: 8.3 KB
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-2009
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
23\todo Clarify this section.
25Alteration of standard containers need a very limited number of
26operations, these together satisfy the everyday requirements.
27In the case of graph structures, different operations are needed which do
28not alter the physical graph, but gives another view. If some nodes or
29arcs have to be hidden or the reverse oriented graph have to be used, then
30this is the case. It also may happen that in a flow implementation
31the residual graph can be accessed by another algorithm, or a node-set
32is to be shrunk for another algorithm.
33LEMON also provides a variety of graphs for these requirements called
34\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
35in conjunction with other graph representations.
37The main parts of LEMON are the different graph structures, generic
38graph algorithms, graph concepts, which couple them, and graph
39adaptors. While the previous notions are more or less clear, the
40latter one needs further explanation. Graph adaptors are graph classes
41which serve for considering graph structures in different ways.
43A short example makes this much clearer.  Suppose that we have an
44instance \c g of a directed graph type, say ListDigraph and an algorithm
46template <typename Digraph>
47int algorithm(const Digraph&);
49is needed to run on the reverse oriented graph.  It may be expensive
50(in time or in memory usage) to copy \c g with the reversed
51arcs.  In this case, an adaptor class is used, which (according
52to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
53The adaptor uses the original digraph structure and digraph operations when
54methods of the reversed oriented graph are called.  This means that the adaptor
55have minor memory usage, and do not perform sophisticated algorithmic
56actions.  The purpose of it is to give a tool for the cases when a
57graph have to be used in a specific alteration.  If this alteration is
58obtained by a usual construction like filtering the node or the arc set or
59considering a new orientation, then an adaptor is worthwhile to use.
60To come back to the reverse oriented graph, in this situation
62template<typename Digraph> class ReverseDigraph;
64template class can be used. The code looks as follows
66ListDigraph g;
67ReverseDigraph<ListDigraph> rg(g);
68int result = algorithm(rg);
70During running the algorithm, the original digraph \c g is untouched.
71This techniques give rise to an elegant code, and based on stable
72graph adaptors, complex algorithms can be implemented easily.
74In flow, circulation and matching problems, the residual
75graph is of particular importance. Combining an adaptor implementing
76this with shortest path algorithms or minimum mean cycle algorithms,
77a range of weighted and cardinality optimization algorithms can be
78obtained. For other examples, the interested user is referred to the
79detailed documentation of particular adaptors.
81The behavior of graph adaptors can be very different. Some of them keep
82capabilities of the original graph while in other cases this would be
83meaningless. This means that the concepts that they meet depend
84on the graph adaptor, and the wrapped graph.
85For example, if an arc of a reversed digraph is deleted, this is carried
86out by deleting the corresponding arc of the original digraph, thus the
87adaptor modifies the original digraph.
88However in case of a residual digraph, this operation has no sense.
90Let us stand one more example here to simplify your work.
91ReverseDigraph has constructor
93ReverseDigraph(Digraph& digraph);
95This means that in a situation, when a <tt>const %ListDigraph&</tt>
96reference to a graph is given, then it have to be instantiated with
97<tt>Digraph=const %ListDigraph</tt>.
99int algorithm1(const ListDigraph& g) {
100  ReverseDigraph<const ListDigraph> rg(g);
101  return algorithm2(rg);
107The LEMON graph adaptor classes serve for considering graphs in
108different ways. The adaptors can be used exactly the same as "real"
109graphs (i.e., they conform to the graph concepts), thus all generic
110algorithms can be performed on them. However, the adaptor classes use
111the underlying graph structures and operations when their methods are
112called, thus they have only negligible memory usage and do not perform
113sophisticated algorithmic actions. This technique yields convenient and
114elegant tools for the cases when a graph has to be used in a specific
115alteration, but copying it would be too expensive (in time or in memory
116usage) compared to the algorithm that should be executed on it. The
117following example shows how the \ref ReverseDigraph adaptor can be used
118to run Dijksta's algorithm on the reverse oriented graph. Note that the
119maps of the original graph can be used in connection with the adaptor,
120since the node and arc types of the adaptors convert to the original
121item types.
124dijkstra(reverseDigraph(g), length).distMap(dist).run(s);
127Using \ref ReverseDigraph could be as efficient as working with the
128original graph, but not all adaptors can be so fast, of course. For
129example, the subgraph adaptors have to access filter maps for the nodes
130and/or the arcs, thus their iterators are significantly slower than the
131original iterators. LEMON also provides some more complex adaptors, for
132instance, \ref SplitNodes, which can be used for splitting each node in
133a directed graph and \ref ResidualDigraph for modeling the residual
134network for flow and matching problems.
136Therefore, in cases when rather complex algorithms have to be used
137on a subgraph (e.g. when the nodes and arcs have to be traversed several
138times), it could worth copying the altered graph into an efficient structure
139and run the algorithm on it.
140Note that the adaptor classes can also be used for doing this easily,
141without having to copy the graph manually, as shown in the following
145  ListDigraph g;
146  ListDigraph::NodeMap<bool> filter_map(g);
147  // construct the graph and fill the filter map
149  {
150    SmartDigraph temp_graph;
151    ListDigraph::NodeMap<SmartDigraph::Node> node_ref(g);
152    digraphCopy(filterNodes(g, filter_map), temp_graph)
153      .nodeRef(node_ref).run();
155    // use temp_graph
156  }
161Another interesting adaptor in LEMON is \ref SplitNodes.
162It can be used for splitting each node into an in-node and an out-node
163in a directed graph. Formally, the adaptor replaces each node
164u in the graph with two nodes, namely node u<sub>in</sub> and node
165u<sub>out</sub>. Each arc (u,c) in the original graph will correspond to an
166arc (u<sub>out</sub>,v<sub>in</sub>). The adaptor also adds an
167additional bind arc (u<sub>in</sub>,u<sub>out</sub>) for each node u
168of the original digraph.
170The aim of this class is to assign costs to the nodes when using
171algorithms which would otherwise consider arc costs only.
172For example, let us suppose that we have a directed graph with costs
173given for both the nodes and the arcs.
174Then Dijkstra's algorithm can be used in connection with \ref SplitNodes
175as follows.
178  typedef SplitNodes<ListDigraph> SplitGraph;
179  SplitGraph sg(g);
180  SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap>
181    combined_cost(node_cost, arc_cost);
182  SplitGraph::NodeMap<double> dist(sg);
183  dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u));
186Note that this problem can be solved more efficiently with
187map adaptors.
189These techniques help writing compact and elegant code, and makes it possible
190to easily implement complex algorithms based on well tested standard components.
191For instance, in flow and matching problems the residual graph is of
192particular importance.
193Combining \ref ResidualDigraph adaptor with various algorithms, a
194range of weighted and cardinality optimization methods can be obtained
Note: See TracBrowser for help on using the repository browser.