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