|
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 */ |
|
18 |
|
19 namespace lemon { |
|
20 /** |
|
21 [PAGE]sec_graph_adaptors[PAGE] Graph Adaptors |
|
22 |
|
23 \todo Clarify this section. |
|
24 |
|
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. |
|
36 |
|
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. |
|
42 |
|
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 |
|
45 \code |
|
46 template <typename Digraph> |
|
47 int algorithm(const Digraph&); |
|
48 \endcode |
|
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 |
|
61 \code |
|
62 template<typename Digraph> class ReverseDigraph; |
|
63 \endcode |
|
64 template class can be used. The code looks as follows |
|
65 \code |
|
66 ListDigraph g; |
|
67 ReverseDigraph<ListDigraph> rg(g); |
|
68 int result = algorithm(rg); |
|
69 \endcode |
|
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. |
|
73 |
|
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. |
|
80 |
|
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. |
|
89 |
|
90 Let us stand one more example here to simplify your work. |
|
91 ReverseDigraph has constructor |
|
92 \code |
|
93 ReverseDigraph(Digraph& digraph); |
|
94 \endcode |
|
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>. |
|
98 \code |
|
99 int algorithm1(const ListDigraph& g) { |
|
100 ReverseDigraph<const ListDigraph> rg(g); |
|
101 return algorithm2(rg); |
|
102 } |
|
103 \endcode |
|
104 |
|
105 <hr> |
|
106 |
|
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 |
|
121 item types. |
|
122 |
|
123 \code |
|
124 dijkstra(reverseDigraph(g), length).distMap(dist).run(s); |
|
125 \endcode |
|
126 |
|
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. |
|
135 |
|
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 |
|
142 example. |
|
143 |
|
144 \code |
|
145 ListDigraph g; |
|
146 ListDigraph::NodeMap<bool> filter_map(g); |
|
147 // construct the graph and fill the filter map |
|
148 |
|
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(); |
|
154 |
|
155 // use temp_graph |
|
156 } |
|
157 \endcode |
|
158 |
|
159 <hr> |
|
160 |
|
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. |
|
169 |
|
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 |
|
175 as follows. |
|
176 |
|
177 \code |
|
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)); |
|
184 \endcode |
|
185 |
|
186 Note that this problem can be solved more efficiently with |
|
187 map adaptors. |
|
188 |
|
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 |
|
195 directly. |
|
196 |
|
197 [TRAILER] |
|
198 */ |
|
199 } |