Changeset 39:31a1a79019bb in lemontutorial
 Timestamp:
 02/21/10 15:07:59 (11 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

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