Changeset 1172:37338ae42a2b in lemon0.x for doc
 Timestamp:
 02/23/05 23:00:05 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1578
 Location:
 doc
 Files:

 2 edited
 1 copied
Legend:
 Unmodified
 Added
 Removed

doc/Doxyfile
r1170 r1172 459 459 graph_io.dox \ 460 460 dirs.dox \ 461 gwrappers.dox \ 461 462 ../src/lemon \ 462 463 ../src/lemon/concept \ 
doc/groups.dox
r1151 r1172 10 10 \brief Graph structures implemented in LEMON. 11 11 12 LEMON provides several data structures to meet the diverging requirements 13 of the possible users. 14 In order to save on running time or on memory usage, some structures may 15 fail to provide 16 some graph features like edge or node deletion. 12 The implementation of combinatorial algorithms heavily relies on 13 efficient graph implementations. LEMON offers data structures which are 14 planned to be easily used in an experimental phase of implementation studies, 15 and thereafter the program code can be made efficient by small modifications. 17 16 18 LEMON also offers special graphs that cannot be used alone but only 19 in conjunction with other graph representation. The examples for this are 20 \ref lemon::EdgeSet "EdgeSet", \ref lemon::NodeSet "NodeSet" 21 and the large variety of \ref gwrappers "graph wrappers". 17 The most efficient implementation of diverse applications require the usage of different physical graph implementations. These differences appear in the size of 18 graph we require to handle, memory or time usage limitations or in 19 the set of operations through which the graph can be accessed. 20 LEMON provides several physical graph structures to meet the 21 diverging requirements of the possible users. 22 In order to save on running time or on memory usage, some structures may 23 fail to provide some graph features like edge or node deletion. 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 strutures, different operations are needed which do 28 not alter the physical graph, but gives an other view. If some nodes or 29 edges 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 implemenation 31 the residual graph can be accessed by an other algorithm, or a nodeset 32 is to be shrunk for an other algorithm. 33 LEMON also provides a variety of graphs for these requirements called 34 \ref gwrappers "graph wrappers". Wrappers cannot be used alone but only 35 in conjunction with other graph representation. 22 36 23 37 You are free to use the graph structure that fit your requirements 24 38 the best, most graph algorithms and auxiliary data structures can be used 25 with any graph structures. 39 with any graph structures. 26 40 */ 27 41 … … 51 65 This group describes the tools that makes it easier to make graph maps that 52 66 dynamically update with the graph changes. 53 */54 55 /**56 @defgroup gwrappers Wrapper Classes for Graphs57 \brief This group contains several wrapper classes for graphs58 @ingroup graphs59 67 */ 60 68 
doc/gwrappers.dox
r1164 r1172 1 /* * C++ * 2 * src/lemon/graph_wrapper.h  Part of LEMON, a generic C++ optimization library 3 * 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Combinatorial Optimization Research Group, EGRES). 6 * 7 * Permission to use, modify and distribute this software is granted 8 * provided that this copyright notice appears in all copies. For 9 * precise terms see the accompanying LICENSE file. 10 * 11 * This software is provided "AS IS" with no warranty of any kind, 12 * express or implied, and with no claim as to its suitability for any 13 * purpose. 14 * 15 */ 16 17 #ifndef LEMON_GRAPH_WRAPPER_H 18 #define LEMON_GRAPH_WRAPPER_H 19 20 ///\ingroup gwrappers 21 ///\file 22 ///\brief Several graph wrappers. 23 /// 24 ///This file contains several useful graph wrapper functions. 25 /// 26 ///\author Marton Makai 27 28 #include <lemon/invalid.h> 29 #include <lemon/maps.h> 30 #include <lemon/iterable_graph_extender.h> 31 #include <iostream> 32 33 namespace lemon { 34 35 // Graph wrappers 36 37 /*! \addtogroup gwrappers 38 The main parts of LEMON are the different graph structures, 39 generic graph algorithms, graph concepts which couple these, and 40 graph wrappers. While the previous ones are more or less clear, the 41 latter notion needs further explanation. 42 Graph wrappers are graph classes which serve for considering graph 43 structures in different ways. A short example makes the notion much 44 clearer. 45 Suppose that we have an instance \c g of a directed graph 46 type say \c ListGraph and an algorithm 47 \code template<typename Graph> int algorithm(const Graph&); \endcode 48 is needed to run on the reversely oriented graph. 49 It may be expensive (in time or in memory usage) to copy 50 \c g with the reverse orientation. 51 Thus, a wrapper class 52 \code template<typename Graph> class RevGraphWrapper; \endcode is used. 53 The code looks as follows 54 \code 55 ListGraph g; 56 RevGraphWrapper<ListGraph> rgw(g); 57 int result=algorithm(rgw); 58 \endcode 59 After running the algorithm, the original graph \c g 60 remains untouched. Thus the graph wrapper used above is to consider the 61 original graph with reverse orientation. 62 This techniques gives rise to an elegant code, and 63 based on stable graph wrappers, complex algorithms can be 64 implemented easily. 65 In flow, circulation and bipartite matching problems, the residual 66 graph is of particular importance. Combining a wrapper implementing 67 this, shortest path algorithms and minimum mean cycle algorithms, 68 a range of weighted and cardinality optimization algorithms can be 69 obtained. For lack of space, for other examples, 70 the interested user is referred to the detailed documentation of graph 71 wrappers. 72 The behavior of graph wrappers can be very different. Some of them keep 73 capabilities of the original graph while in other cases this would be 74 meaningless. This means that the concepts that they are a model of depend 75 on the graph wrapper, and the wrapped graph(s). 76 If an edge of \c rgw is deleted, this is carried out by 77 deleting the corresponding edge of \c g. But for a residual 78 graph, this operation has no sense. 79 Let we stand one more example here to simplify your work. 80 wrapper class 81 \code template<typename Graph> class RevGraphWrapper; \endcode 82 has constructor 83 <tt> RevGraphWrapper(Graph& _g)</tt>. 84 This means that in a situation, 85 when a <tt> const ListGraph& </tt> reference to a graph is given, 86 then it have to be instantiated with <tt>Graph=const ListGraph</tt>. 87 \code 88 int algorithm1(const ListGraph& g) { 89 RevGraphWrapper<const ListGraph> rgw(g); 90 return algorithm2(rgw); 91 } 92 \endcode 93 94 \addtogroup gwrappers 95 @{ 96 97 Base type for the Graph Wrappers 98 99 \warning Graph wrappers are in even more experimental state than the other 100 parts of the lib. Use them at you own risk. 101 102 This is the base type for most of LEMON graph wrappers. 103 This class implements a trivial graph wrapper i.e. it only wraps the 104 functions and types of the graph. The purpose of this class is to 105 make easier implementing graph wrappers. E.g. if a wrapper is 106 considered which differs from the wrapped graph only in some of its 107 functions or types, then it can be derived from GraphWrapper, and only the 108 differences should be implemented. 109 110 \author Marton Makai 111 */ 112 template<typename _Graph> 113 class GraphWrapperBase { 114 public: 115 typedef _Graph Graph; 116 /// \todo Is it needed? 117 typedef Graph BaseGraph; 118 typedef Graph ParentGraph; 119 120 protected: 121 Graph* graph; 122 GraphWrapperBase() : graph(0) { } 123 void setGraph(Graph& _graph) { graph=&_graph; } 124 125 public: 126 GraphWrapperBase(Graph& _graph) : graph(&_graph) { } 127 128 typedef typename Graph::Node Node; 129 typedef typename Graph::Edge Edge; 1 /** 2 @defgroup gwrappers Wrapper Classes for Graphs 3 \brief This group contains several wrapper classes for graphs 4 @ingroup graphs 130 5 131 void first(Node& i) const { graph>first(i); } 132 void first(Edge& i) const { graph>first(i); } 133 void firstIn(Edge& i, const Node& n) const { graph>firstIn(i, n); } 134 void firstOut(Edge& i, const Node& n ) const { graph>firstOut(i, n); } 135 136 void next(Node& i) const { graph>next(i); } 137 void next(Edge& i) const { graph>next(i); } 138 void nextIn(Edge& i) const { graph>nextIn(i); } 139 void nextOut(Edge& i) const { graph>nextOut(i); } 140 141 Node source(const Edge& e) const { return graph>source(e); } 142 Node target(const Edge& e) const { return graph>target(e); } 143 144 int nodeNum() const { return graph>nodeNum(); } 145 int edgeNum() const { return graph>edgeNum(); } 146 147 Node addNode() const { return Node(graph>addNode()); } 148 Edge addEdge(const Node& source, const Node& target) const { 149 return Edge(graph>addEdge(source, target)); } 150 151 void erase(const Node& i) const { graph>erase(i); } 152 void erase(const Edge& i) const { graph>erase(i); } 153 154 void clear() const { graph>clear(); } 155 156 bool forward(const Edge& e) const { return graph>forward(e); } 157 bool backward(const Edge& e) const { return graph>backward(e); } 158 159 int id(const Node& v) const { return graph>id(v); } 160 int id(const Edge& e) const { return graph>id(e); } 161 162 Edge opposite(const Edge& e) const { return Edge(graph>opposite(e)); } 163 164 template <typename _Value> 165 class NodeMap : public _Graph::template NodeMap<_Value> { 166 public: 167 typedef typename _Graph::template NodeMap<_Value> Parent; 168 NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { } 169 NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value) 170 : Parent(*gw.graph, value) { } 171 }; 172 173 template <typename _Value> 174 class EdgeMap : public _Graph::template EdgeMap<_Value> { 175 public: 176 typedef typename _Graph::template EdgeMap<_Value> Parent; 177 EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { } 178 EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value) 179 : Parent(*gw.graph, value) { } 180 }; 181 182 }; 183 184 template <typename _Graph> 185 class GraphWrapper : 186 public IterableGraphExtender<GraphWrapperBase<_Graph> > { 187 public: 188 typedef _Graph Graph; 189 typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent; 190 protected: 191 GraphWrapper() : Parent() { } 192 193 public: 194 GraphWrapper(Graph& _graph) { setGraph(_graph); } 195 }; 196 197 template <typename _Graph> 198 class RevGraphWrapperBase : public GraphWrapperBase<_Graph> { 199 public: 200 typedef _Graph Graph; 201 typedef GraphWrapperBase<_Graph> Parent; 202 protected: 203 RevGraphWrapperBase() : Parent() { } 204 public: 205 typedef typename Parent::Node Node; 206 typedef typename Parent::Edge Edge; 207 208 using Parent::first; 209 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); } 210 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); } 211 212 using Parent::next; 213 void nextIn(Edge& i) const { Parent::nextOut(i); } 214 void nextOut(Edge& i) const { Parent::nextIn(i); } 215 216 Node source(const Edge& e) const { return Parent::target(e); } 217 Node target(const Edge& e) const { return Parent::source(e); } 218 }; 219 220 221 /// A graph wrapper which reverses the orientation of the edges. 222 223 ///\warning Graph wrappers are in even more experimental state than the other 224 ///parts of the lib. Use them at you own risk. 225 /// 226 /// Let \f$G=(V, A)\f$ be a directed graph and 227 /// suppose that a graph instange \c g of type 228 /// \c ListGraph implements \f$G\f$. 229 /// \code 230 /// ListGraph g; 231 /// \endcode 232 /// For each directed edge 233 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 234 /// reversing its orientation. 235 /// Then RevGraphWrapper implements the graph structure with nodeset 236 /// \f$V\f$ and edgeset 237 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 238 /// reversing the orientation of its edges. The following code shows how 239 /// such an instance can be constructed. 240 /// \code 241 /// RevGraphWrapper<ListGraph> gw(g); 242 /// \endcode 243 ///\author Marton Makai 244 template<typename _Graph> 245 class RevGraphWrapper : 246 public IterableGraphExtender<RevGraphWrapperBase<_Graph> > { 247 public: 248 typedef _Graph Graph; 249 typedef IterableGraphExtender< 250 RevGraphWrapperBase<_Graph> > Parent; 251 protected: 252 RevGraphWrapper() { } 253 public: 254 RevGraphWrapper(_Graph& _graph) { setGraph(_graph); } 255 }; 256 257 258 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> 259 class SubGraphWrapperBase : public GraphWrapperBase<_Graph> { 260 public: 261 typedef _Graph Graph; 262 typedef GraphWrapperBase<_Graph> Parent; 263 protected: 264 NodeFilterMap* node_filter_map; 265 EdgeFilterMap* edge_filter_map; 266 SubGraphWrapperBase() : Parent(), 267 node_filter_map(0), edge_filter_map(0) { } 268 269 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { 270 node_filter_map=&_node_filter_map; 271 } 272 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { 273 edge_filter_map=&_edge_filter_map; 274 } 275 276 public: 277 // SubGraphWrapperBase(Graph& _graph, 278 // NodeFilterMap& _node_filter_map, 279 // EdgeFilterMap& _edge_filter_map) : 280 // Parent(&_graph), 281 // node_filter_map(&node_filter_map), 282 // edge_filter_map(&edge_filter_map) { } 283 284 typedef typename Parent::Node Node; 285 typedef typename Parent::Edge Edge; 286 287 void first(Node& i) const { 288 Parent::first(i); 289 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 290 } 291 void first(Edge& i) const { 292 Parent::first(i); 293 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 294 } 295 void firstIn(Edge& i, const Node& n) const { 296 Parent::firstIn(i, n); 297 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 298 } 299 void firstOut(Edge& i, const Node& n) const { 300 Parent::firstOut(i, n); 301 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 302 } 303 304 void next(Node& i) const { 305 Parent::next(i); 306 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 307 } 308 void next(Edge& i) const { 309 Parent::next(i); 310 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 311 } 312 void nextIn(Edge& i) const { 313 Parent::nextIn(i); 314 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 315 } 316 void nextOut(Edge& i) const { 317 Parent::nextOut(i); 318 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 319 } 320 321 /// This function hides \c n in the graph, i.e. the iteration 322 /// jumps over it. This is done by simply setting the value of \c n 323 /// to be false in the corresponding nodemap. 324 void hide(const Node& n) const { node_filter_map>set(n, false); } 325 326 /// This function hides \c e in the graph, i.e. the iteration 327 /// jumps over it. This is done by simply setting the value of \c e 328 /// to be false in the corresponding edgemap. 329 void hide(const Edge& e) const { edge_filter_map>set(e, false); } 330 331 /// The value of \c n is set to be true in the nodemap which stores 332 /// hide information. If \c n was hidden previuosly, then it is shown 333 /// again 334 void unHide(const Node& n) const { node_filter_map>set(n, true); } 335 336 /// The value of \c e is set to be true in the edgemap which stores 337 /// hide information. If \c e was hidden previuosly, then it is shown 338 /// again 339 void unHide(const Edge& e) const { edge_filter_map>set(e, true); } 340 341 /// Returns true if \c n is hidden. 342 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 343 344 /// Returns true if \c n is hidden. 345 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 346 347 /// \warning This is a linear time operation and works only if s 348 /// \c Graph::NodeIt is defined. 349 /// \todo assign tags. 350 int nodeNum() const { 351 int i=0; 352 Node n; 353 for (first(n); n!=INVALID; next(n)) ++i; 354 return i; 355 } 356 357 /// \warning This is a linear time operation and works only if 358 /// \c Graph::EdgeIt is defined. 359 /// \todo assign tags. 360 int edgeNum() const { 361 int i=0; 362 Edge e; 363 for (first(e); e!=INVALID; next(e)) ++i; 364 return i; 365 } 366 367 368 }; 369 370 /*! \brief A graph wrapper for hiding nodes and edges from a graph. 371 372 \warning Graph wrappers are in even more experimental state than the other 373 parts of the lib. Use them at you own risk. 374 375 This wrapper shows a graph with filtered nodeset and 376 edgeset. 377 Given a boolvalued map on the nodeset and one on 378 the edgeset of the graph, the iterators show only the objects 379 having true value. We have to note that this does not mean that an 380 induced subgraph is obtained, the nodeiterator cares only the filter 381 on the nodeset, and the edgeiterators care only the filter on the 382 edgeset. 383 \code 384 typedef SmartGraph Graph; 385 Graph g; 386 typedef Graph::Node Node; 387 typedef Graph::Edge Edge; 388 Node u=g.addNode(); //node of id 0 389 Node v=g.addNode(); //node of id 1 390 Node e=g.addEdge(u, v); //edge of id 0 391 Node f=g.addEdge(v, u); //edge of id 1 392 Graph::NodeMap<bool> nm(g, true); 393 nm.set(u, false); 394 Graph::EdgeMap<bool> em(g, true); 395 em.set(e, false); 396 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW; 397 SubGW gw(g, nm, em); 398 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 399 std::cout << ":)" << std::endl; 400 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 401 \endcode 402 The output of the above code is the following. 403 \code 404 1 405 :) 406 1 407 \endcode 408 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to 409 \c Graph::Node that is why \c g.id(n) can be applied. 410 411 For other examples see also the documentation of NodeSubGraphWrapper and 412 EdgeSubGraphWrapper. 413 414 \author Marton Makai 415 */ 416 template<typename _Graph, typename NodeFilterMap, 417 typename EdgeFilterMap> 418 class SubGraphWrapper : 419 public IterableGraphExtender< 420 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > { 421 public: 422 typedef _Graph Graph; 423 typedef IterableGraphExtender< 424 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 425 protected: 426 SubGraphWrapper() { } 427 public: 428 SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map, 429 EdgeFilterMap& _edge_filter_map) { 430 setGraph(_graph); 431 setNodeFilterMap(_node_filter_map); 432 setEdgeFilterMap(_edge_filter_map); 433 } 434 }; 435 436 437 438 /*! \brief A wrapper for hiding nodes from a graph. 439 440 \warning Graph wrappers are in even more experimental state than the other 441 parts of the lib. Use them at you own risk. 442 443 A wrapper for hiding nodes from a graph. 444 This wrapper specializes SubGraphWrapper in the way that only the nodeset 445 can be filtered. Note that this does not mean of considering induced 446 subgraph, the edgeiterators consider the original edgeset. 447 \author Marton Makai 448 */ 449 template<typename Graph, typename NodeFilterMap> 450 class NodeSubGraphWrapper : 451 public SubGraphWrapper<Graph, NodeFilterMap, 452 ConstMap<typename Graph::Edge,bool> > { 453 public: 454 typedef SubGraphWrapper<Graph, NodeFilterMap, 455 ConstMap<typename Graph::Edge,bool> > Parent; 456 protected: 457 ConstMap<typename Graph::Edge, bool> const_true_map; 458 public: 459 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) : 460 Parent(), const_true_map(true) { 461 Parent::setGraph(_graph); 462 Parent::setNodeFilterMap(_node_filter_map); 463 Parent::setEdgeFilterMap(const_true_map); 464 } 465 }; 466 467 468 /*! \brief A wrapper for hiding edges from a graph. 469 470 \warning Graph wrappers are in even more experimental state than the other 471 parts of the lib. Use them at you own risk. 472 473 A wrapper for hiding edges from a graph. 474 This wrapper specializes SubGraphWrapper in the way that only the edgeset 475 can be filtered. The usefulness of this wrapper is demonstrated in the 476 problem of searching a maximum number of edgedisjoint shortest paths 477 between 478 two nodes \c s and \c t. Shortest here means being shortest w.r.t. 479 nonnegative edgelengths. Note that 480 the comprehension of the presented solution 481 need's some knowledge from elementary combinatorial optimization. 482 483 If a single shortest path is to be 484 searched between two nodes \c s and \c t, then this can be done easily by 485 applying the Dijkstra algorithm class. What happens, if a maximum number of 486 edgedisjoint shortest paths is to be computed. It can be proved that an 487 edge can be in a shortest path if and only if it is tight with respect to 488 the potential function computed by Dijkstra. Moreover, any path containing 489 only such edges is a shortest one. Thus we have to compute a maximum number 490 of edgedisjoint paths between \c s and \c t in the graph which has edgeset 491 all the tight edges. The computation will be demonstrated on the following 492 graph, which is read from a dimacs file. 493 494 \dot 495 digraph lemon_dot_example { 496 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 497 n0 [ label="0 (s)" ]; 498 n1 [ label="1" ]; 499 n2 [ label="2" ]; 500 n3 [ label="3" ]; 501 n4 [ label="4" ]; 502 n5 [ label="5" ]; 503 n6 [ label="6 (t)" ]; 504 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 505 n5 > n6 [ label="9, length:4" ]; 506 n4 > n6 [ label="8, length:2" ]; 507 n3 > n5 [ label="7, length:1" ]; 508 n2 > n5 [ label="6, length:3" ]; 509 n2 > n6 [ label="5, length:5" ]; 510 n2 > n4 [ label="4, length:2" ]; 511 n1 > n4 [ label="3, length:3" ]; 512 n0 > n3 [ label="2, length:1" ]; 513 n0 > n2 [ label="1, length:2" ]; 514 n0 > n1 [ label="0, length:3" ]; 515 } 516 \enddot 517 518 \code 519 Graph g; 520 Node s, t; 521 LengthMap length(g); 522 523 readDimacs(std::cin, g, length, s, t); 524 525 cout << "edges with lengths (of form id, sourcelength>target): " << endl; 526 for(EdgeIt e(g); e!=INVALID; ++e) 527 cout << g.id(e) << ", " << g.id(g.source(e)) << "" 528 << length[e] << ">" << g.id(g.target(e)) << endl; 529 530 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; 531 \endcode 532 Next, the potential function is computed with Dijkstra. 533 \code 534 typedef Dijkstra<Graph, LengthMap> Dijkstra; 535 Dijkstra dijkstra(g, length); 536 dijkstra.run(s); 537 \endcode 538 Next, we consrtruct a map which filters the edgeset to the tight edges. 539 \code 540 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 541 TightEdgeFilter; 542 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); 543 544 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW; 545 SubGW gw(g, tight_edge_filter); 546 \endcode 547 Then, the maximum nimber of edgedisjoint \c s\c t paths are computed 548 with a max flow algorithm Preflow. 549 \code 550 ConstMap<Edge, int> const_1_map(1); 551 Graph::EdgeMap<int> flow(g, 0); 552 553 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 554 preflow(gw, s, t, const_1_map, flow); 555 preflow.run(); 556 \endcode 557 Last, the output is: 558 \code 559 cout << "maximum number of edgedisjoint shortest path: " 560 << preflow.flowValue() << endl; 561 cout << "edges of the maximum number of edgedisjoint shortest st paths: " 562 << endl; 563 for(EdgeIt e(g); e!=INVALID; ++e) 564 if (flow[e]) 565 cout << " " << g.id(g.source(e)) << "" 566 << length[e] << ">" << g.id(g.target(e)) << endl; 567 \endcode 568 The program has the following (expected :)) output: 569 \code 570 edges with lengths (of form id, sourcelength>target): 571 9, 54>6 572 8, 42>6 573 7, 31>5 574 6, 23>5 575 5, 25>6 576 4, 22>4 577 3, 13>4 578 2, 01>3 579 1, 02>2 580 0, 03>1 581 s: 0 t: 6 582 maximum number of edgedisjoint shortest path: 2 583 edges of the maximum number of edgedisjoint shortest st paths: 584 9, 54>6 585 8, 42>6 586 7, 31>5 587 4, 22>4 588 2, 01>3 589 1, 02>2 590 \endcode 591 592 \author Marton Makai 593 */ 594 template<typename Graph, typename EdgeFilterMap> 595 class EdgeSubGraphWrapper : 596 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 597 EdgeFilterMap> { 598 public: 599 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 600 EdgeFilterMap> Parent; 601 protected: 602 ConstMap<typename Graph::Node, bool> const_true_map; 603 public: 604 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 605 Parent(), const_true_map(true) { 606 Parent::setGraph(_graph); 607 Parent::setNodeFilterMap(const_true_map); 608 Parent::setEdgeFilterMap(_edge_filter_map); 609 } 610 }; 611 612 613 template<typename Graph> 614 class UndirGraphWrapper : public GraphWrapper<Graph> { 615 public: 616 typedef GraphWrapper<Graph> Parent; 617 protected: 618 UndirGraphWrapper() : GraphWrapper<Graph>() { } 619 620 public: 621 typedef typename GraphWrapper<Graph>::Node Node; 622 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 623 typedef typename GraphWrapper<Graph>::Edge Edge; 624 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; 625 626 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 627 628 class OutEdgeIt { 629 friend class UndirGraphWrapper<Graph>; 630 bool out_or_in; //true iff out 631 typename Graph::OutEdgeIt out; 632 typename Graph::InEdgeIt in; 633 public: 634 OutEdgeIt() { } 635 OutEdgeIt(const Invalid& i) : Edge(i) { } 636 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) { 637 out_or_in=true; _G.graph>first(out, _n); 638 if (!(_G.graph>valid(out))) { out_or_in=false; _G.graph>first(in, _n); } 639 } 640 operator Edge() const { 641 if (out_or_in) return Edge(out); else return Edge(in); 642 } 643 }; 644 645 typedef OutEdgeIt InEdgeIt; 646 647 using GraphWrapper<Graph>::first; 648 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 649 i=OutEdgeIt(*this, p); return i; 650 } 651 652 using GraphWrapper<Graph>::next; 653 654 OutEdgeIt& next(OutEdgeIt& e) const { 655 if (e.out_or_in) { 656 typename Graph::Node n=this>graph>source(e.out); 657 this>graph>next(e.out); 658 if (!this>graph>valid(e.out)) { 659 e.out_or_in=false; this>graph>first(e.in, n); } 660 } else { 661 this>graph>next(e.in); 662 } 663 return e; 664 } 665 666 Node aNode(const OutEdgeIt& e) const { 667 if (e.out_or_in) return this>graph>source(e); else 668 return this>graph>target(e); } 669 Node bNode(const OutEdgeIt& e) const { 670 if (e.out_or_in) return this>graph>target(e); else 671 return this>graph>source(e); } 672 673 // KEEP_MAPS(Parent, UndirGraphWrapper); 674 675 }; 676 677 // /// \brief An undirected graph template. 678 // /// 679 // ///\warning Graph wrappers are in even more experimental state than the other 680 // ///parts of the lib. Use them at your own risk. 681 // /// 682 // /// An undirected graph template. 683 // /// This class works as an undirected graph and a directed graph of 684 // /// class \c Graph is used for the physical storage. 685 // /// \ingroup graphs 686 template<typename Graph> 687 class UndirGraph : public UndirGraphWrapper<Graph> { 688 typedef UndirGraphWrapper<Graph> Parent; 689 protected: 690 Graph gr; 691 public: 692 UndirGraph() : UndirGraphWrapper<Graph>() { 693 Parent::setGraph(gr); 694 } 695 696 // KEEP_MAPS(Parent, UndirGraph); 697 }; 698 699 700 template <typename _Graph, 701 typename ForwardFilterMap, typename BackwardFilterMap> 702 class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> { 703 public: 704 typedef _Graph Graph; 705 typedef GraphWrapperBase<_Graph> Parent; 706 protected: 707 ForwardFilterMap* forward_filter; 708 BackwardFilterMap* backward_filter; 709 SubBidirGraphWrapperBase() : Parent(), 710 forward_filter(0), backward_filter(0) { } 711 712 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { 713 forward_filter=&_forward_filter; 714 } 715 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { 716 backward_filter=&_backward_filter; 717 } 718 719 public: 720 // SubGraphWrapperBase(Graph& _graph, 721 // NodeFilterMap& _node_filter_map, 722 // EdgeFilterMap& _edge_filter_map) : 723 // Parent(&_graph), 724 // node_filter_map(&node_filter_map), 725 // edge_filter_map(&edge_filter_map) { } 726 727 typedef typename Parent::Node Node; 728 typedef typename _Graph::Edge GraphEdge; 729 template <typename T> class EdgeMap; 730 /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from 731 /// _Graph::Edge. It contains an extra bool flag which is true 732 /// if and only if the 733 /// edge is the backward version of the original edge. 734 class Edge : public _Graph::Edge { 735 friend class SubBidirGraphWrapperBase< 736 Graph, ForwardFilterMap, BackwardFilterMap>; 737 template<typename T> friend class EdgeMap; 738 protected: 739 bool backward; //true, iff backward 740 public: 741 Edge() { } 742 /// \todo =false is needed, or causes problems? 743 /// If \c _backward is false, then we get an edge corresponding to the 744 /// original one, otherwise its oppositely directed pair is obtained. 745 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 746 _Graph::Edge(e), backward(_backward) { } 747 Edge(Invalid i) : _Graph::Edge(i), backward(true) { } 748 bool operator==(const Edge& v) const { 749 return (this>backward==v.backward && 750 static_cast<typename _Graph::Edge>(*this)== 751 static_cast<typename _Graph::Edge>(v)); 752 } 753 bool operator!=(const Edge& v) const { 754 return (this>backward!=v.backward  755 static_cast<typename _Graph::Edge>(*this)!= 756 static_cast<typename _Graph::Edge>(v)); 757 } 758 }; 759 760 void first(Node& i) const { 761 Parent::first(i); 762 } 763 764 void first(Edge& i) const { 765 Parent::first(i); 766 i.backward=false; 767 while (*static_cast<GraphEdge*>(&i)!=INVALID && 768 !(*forward_filter)[i]) Parent::next(i); 769 if (*static_cast<GraphEdge*>(&i)==INVALID) { 770 Parent::first(i); 771 i.backward=true; 772 while (*static_cast<GraphEdge*>(&i)!=INVALID && 773 !(*backward_filter)[i]) Parent::next(i); 774 } 775 } 776 777 void firstIn(Edge& i, const Node& n) const { 778 Parent::firstIn(i, n); 779 i.backward=false; 780 while (*static_cast<GraphEdge*>(&i)!=INVALID && 781 !(*forward_filter)[i]) Parent::nextOut(i); 782 if (*static_cast<GraphEdge*>(&i)==INVALID) { 783 Parent::firstOut(i, n); 784 i.backward=true; 785 while (*static_cast<GraphEdge*>(&i)!=INVALID && 786 !(*backward_filter)[i]) Parent::nextOut(i); 787 } 788 } 789 790 void firstOut(Edge& i, const Node& n) const { 791 Parent::firstOut(i, n); 792 i.backward=false; 793 while (*static_cast<GraphEdge*>(&i)!=INVALID && 794 !(*forward_filter)[i]) Parent::nextOut(i); 795 if (*static_cast<GraphEdge*>(&i)==INVALID) { 796 Parent::firstIn(i, n); 797 i.backward=true; 798 while (*static_cast<GraphEdge*>(&i)!=INVALID && 799 !(*backward_filter)[i]) Parent::nextIn(i); 800 } 801 } 802 803 void next(Node& i) const { 804 Parent::next(i); 805 } 806 807 void next(Edge& i) const { 808 if (!(i.backward)) { 809 Parent::next(i); 810 while (*static_cast<GraphEdge*>(&i)!=INVALID && 811 !(*forward_filter)[i]) Parent::next(i); 812 if (*static_cast<GraphEdge*>(&i)==INVALID) { 813 Parent::first(i); 814 i.backward=true; 815 while (*static_cast<GraphEdge*>(&i)!=INVALID && 816 !(*backward_filter)[i]) Parent::next(i); 817 } 818 } else { 819 Parent::next(i); 820 while (*static_cast<GraphEdge*>(&i)!=INVALID && 821 !(*backward_filter)[i]) Parent::next(i); 822 } 823 } 824 825 void nextIn(Edge& i) const { 826 if (!(i.backward)) { 827 Node n=Parent::target(i); 828 Parent::nextIn(i); 829 while (*static_cast<GraphEdge*>(&i)!=INVALID && 830 !(*forward_filter)[i]) Parent::nextIn(i); 831 if (*static_cast<GraphEdge*>(&i)==INVALID) { 832 Parent::firstOut(i, n); 833 i.backward=true; 834 while (*static_cast<GraphEdge*>(&i)!=INVALID && 835 !(*backward_filter)[i]) Parent::nextOut(i); 836 } 837 } else { 838 Parent::nextOut(i); 839 while (*static_cast<GraphEdge*>(&i)!=INVALID && 840 !(*backward_filter)[i]) Parent::nextOut(i); 841 } 842 } 843 844 void nextOut(Edge& i) const { 845 if (!(i.backward)) { 846 Node n=Parent::source(i); 847 Parent::nextOut(i); 848 while (*static_cast<GraphEdge*>(&i)!=INVALID && 849 !(*forward_filter)[i]) Parent::nextOut(i); 850 if (*static_cast<GraphEdge*>(&i)==INVALID) { 851 Parent::firstIn(i, n); 852 i.backward=true; 853 while (*static_cast<GraphEdge*>(&i)!=INVALID && 854 !(*backward_filter)[i]) Parent::nextIn(i); 855 } 856 } else { 857 Parent::nextIn(i); 858 while (*static_cast<GraphEdge*>(&i)!=INVALID && 859 !(*backward_filter)[i]) Parent::nextIn(i); 860 } 861 } 862 863 Node source(Edge e) const { 864 return ((!e.backward) ? this>graph>source(e) : this>graph>target(e)); } 865 Node target(Edge e) const { 866 return ((!e.backward) ? this>graph>target(e) : this>graph>source(e)); } 867 868 /// Gives back the opposite edge. 869 Edge opposite(const Edge& e) const { 870 Edge f=e; 871 f.backward=!f.backward; 872 return f; 873 } 874 875 /// \warning This is a linear time operation and works only if 876 /// \c Graph::EdgeIt is defined. 877 /// \todo hmm 878 int edgeNum() const { 879 int i=0; 880 Edge e; 881 for (first(e); e!=INVALID; next(e)) ++i; 882 return i; 883 } 884 885 bool forward(const Edge& e) const { return !e.backward; } 886 bool backward(const Edge& e) const { return e.backward; } 887 888 template <typename T> 889 /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two 890 /// _Graph::EdgeMap one for the forward edges and 891 /// one for the backward edges. 892 class EdgeMap { 893 template <typename TT> friend class EdgeMap; 894 typename _Graph::template EdgeMap<T> forward_map, backward_map; 895 public: 896 typedef T Value; 897 typedef Edge Key; 898 899 EdgeMap(const SubBidirGraphWrapperBase<_Graph, 900 ForwardFilterMap, BackwardFilterMap>& g) : 901 forward_map(*(g.graph)), backward_map(*(g.graph)) { } 902 903 EdgeMap(const SubBidirGraphWrapperBase<_Graph, 904 ForwardFilterMap, BackwardFilterMap>& g, T a) : 905 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } 906 907 void set(Edge e, T a) { 908 if (!e.backward) 909 forward_map.set(e, a); 910 else 911 backward_map.set(e, a); 912 } 913 914 // typename _Graph::template EdgeMap<T>::ConstReference 915 // operator[](Edge e) const { 916 // if (!e.backward) 917 // return forward_map[e]; 918 // else 919 // return backward_map[e]; 920 // } 921 922 // typename _Graph::template EdgeMap<T>::Reference 923 T operator[](Edge e) const { 924 if (!e.backward) 925 return forward_map[e]; 926 else 927 return backward_map[e]; 928 } 929 930 void update() { 931 forward_map.update(); 932 backward_map.update(); 933 } 934 }; 935 936 }; 937 938 939 ///\brief A wrapper for composing a subgraph of a 940 /// bidirected graph made from a directed one. 941 /// 942 /// A wrapper for composing a subgraph of a 943 /// bidirected graph made from a directed one. 944 /// 945 ///\warning Graph wrappers are in even more experimental state than the other 946 ///parts of the lib. Use them at you own risk. 947 /// 948 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 949 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 950 /// reversing its orientation. We are given moreover two bool valued 951 /// maps on the edgeset, 952 /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 953 /// SubBidirGraphWrapper implements the graph structure with nodeset 954 /// \f$V\f$ and edgeset 955 /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$. 956 /// The purpose of writing + instead of union is because parallel 957 /// edges can arise. (Similarly, antiparallel edges also can arise). 958 /// In other words, a subgraph of the bidirected graph obtained, which 959 /// is given by orienting the edges of the original graph in both directions. 960 /// As the oppositely directed edges are logically different, 961 /// the maps are able to attach different values for them. 962 /// 963 /// An example for such a construction is \c RevGraphWrapper where the 964 /// forward_filter is everywhere false and the backward_filter is 965 /// everywhere true. We note that for sake of efficiency, 966 /// \c RevGraphWrapper is implemented in a different way. 967 /// But BidirGraphWrapper is obtained from 968 /// SubBidirGraphWrapper by considering everywhere true 969 /// valued maps both for forward_filter and backward_filter. 970 /// Finally, one of the most important applications of SubBidirGraphWrapper 971 /// is ResGraphWrapper, which stands for the residual graph in directed 972 /// flow and circulation problems. 973 /// As wrappers usually, the SubBidirGraphWrapper implements the 974 /// above mentioned graph structure without its physical storage, 975 /// that is the whole stuff is stored in constant memory. 976 template<typename _Graph, 977 typename ForwardFilterMap, typename BackwardFilterMap> 978 class SubBidirGraphWrapper : 979 public IterableGraphExtender< 980 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { 981 public: 982 typedef _Graph Graph; 983 typedef IterableGraphExtender< 984 SubBidirGraphWrapperBase< 985 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; 986 protected: 987 SubBidirGraphWrapper() { } 988 public: 989 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter, 990 BackwardFilterMap& _backward_filter) { 991 setGraph(_graph); 992 setForwardFilterMap(_forward_filter); 993 setBackwardFilterMap(_backward_filter); 994 } 995 }; 996 997 998 999 ///\brief A wrapper for composing bidirected graph from a directed one. 1000 /// 1001 ///\warning Graph wrappers are in even more experimental state than the other 1002 ///parts of the lib. Use them at you own risk. 1003 /// 1004 /// A wrapper for composing bidirected graph from a directed one. 1005 /// A bidirected graph is composed over the directed one without physical 1006 /// storage. As the oppositely directed edges are logically different ones 1007 /// the maps are able to attach different values for them. 1008 template<typename Graph> 1009 class BidirGraphWrapper : 1010 public SubBidirGraphWrapper< 1011 Graph, 1012 ConstMap<typename Graph::Edge, bool>, 1013 ConstMap<typename Graph::Edge, bool> > { 1014 public: 1015 typedef SubBidirGraphWrapper< 1016 Graph, 1017 ConstMap<typename Graph::Edge, bool>, 1018 ConstMap<typename Graph::Edge, bool> > Parent; 1019 protected: 1020 ConstMap<typename Graph::Edge, bool> cm; 1021 1022 BidirGraphWrapper() : Parent(), cm(true) { 1023 Parent::setForwardFilterMap(cm); 1024 Parent::setBackwardFilterMap(cm); 1025 } 1026 public: 1027 BidirGraphWrapper(Graph& _graph) : Parent() { 1028 Parent::setGraph(_graph); 1029 Parent::setForwardFilterMap(cm); 1030 Parent::setBackwardFilterMap(cm); 1031 } 1032 1033 int edgeNum() const { 1034 return 2*this>graph>edgeNum(); 1035 } 1036 // KEEP_MAPS(Parent, BidirGraphWrapper); 1037 }; 1038 1039 1040 template<typename Graph, typename Number, 1041 typename CapacityMap, typename FlowMap> 1042 class ResForwardFilter { 1043 // const Graph* graph; 1044 const CapacityMap* capacity; 1045 const FlowMap* flow; 1046 public: 1047 ResForwardFilter(/*const Graph& _graph, */ 1048 const CapacityMap& _capacity, const FlowMap& _flow) : 1049 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } 1050 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } 1051 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } 1052 void setFlow(const FlowMap& _flow) { flow=&_flow; } 1053 bool operator[](const typename Graph::Edge& e) const { 1054 return (Number((*flow)[e]) < Number((*capacity)[e])); 1055 } 1056 }; 1057 1058 template<typename Graph, typename Number, 1059 typename CapacityMap, typename FlowMap> 1060 class ResBackwardFilter { 1061 const CapacityMap* capacity; 1062 const FlowMap* flow; 1063 public: 1064 ResBackwardFilter(/*const Graph& _graph,*/ 1065 const CapacityMap& _capacity, const FlowMap& _flow) : 1066 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } 1067 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } 1068 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } 1069 void setFlow(const FlowMap& _flow) { flow=&_flow; } 1070 bool operator[](const typename Graph::Edge& e) const { 1071 return (Number(0) < Number((*flow)[e])); 1072 } 1073 }; 1074 1075 1076 /// A wrapper for composing the residual graph for directed flow and circulation problems. 1077 1078 ///\warning Graph wrappers are in even more experimental state than the other 1079 ///parts of the lib. Use them at you own risk. 1080 /// 1081 /// A wrapper for composing the residual graph for directed flow and circulation problems. 1082 template<typename Graph, typename Number, 1083 typename CapacityMap, typename FlowMap> 1084 class ResGraphWrapper : 1085 public SubBidirGraphWrapper< 1086 Graph, 1087 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 1088 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > { 1089 public: 1090 typedef SubBidirGraphWrapper< 1091 Graph, 1092 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 1093 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent; 1094 protected: 1095 const CapacityMap* capacity; 1096 FlowMap* flow; 1097 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter; 1098 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter; 1099 ResGraphWrapper() : Parent(), 1100 capacity(0), flow(0) { } 1101 void setCapacityMap(const CapacityMap& _capacity) { 1102 capacity=&_capacity; 1103 forward_filter.setCapacity(_capacity); 1104 backward_filter.setCapacity(_capacity); 1105 } 1106 void setFlowMap(FlowMap& _flow) { 1107 flow=&_flow; 1108 forward_filter.setFlow(_flow); 1109 backward_filter.setFlow(_flow); 1110 } 1111 public: 1112 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 1113 FlowMap& _flow) : 1114 Parent(), capacity(&_capacity), flow(&_flow), 1115 forward_filter(/*_graph,*/ _capacity, _flow), 1116 backward_filter(/*_graph,*/ _capacity, _flow) { 1117 Parent::setGraph(_graph); 1118 Parent::setForwardFilterMap(forward_filter); 1119 Parent::setBackwardFilterMap(backward_filter); 1120 } 1121 1122 typedef typename Parent::Edge Edge; 1123 1124 void augment(const Edge& e, Number a) const { 1125 if (Parent::forward(e)) 1126 flow>set(e, (*flow)[e]+a); 1127 else 1128 flow>set(e, (*flow)[e]a); 1129 } 1130 1131 /// \brief Residual capacity map. 1132 /// 1133 /// In generic residual graphs the residual capacity can be obtained 1134 /// as a map. 1135 class ResCap { 1136 protected: 1137 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph; 1138 public: 1139 typedef Number Value; 1140 typedef Edge Key; 1141 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& 1142 _res_graph) : res_graph(&_res_graph) { } 1143 Number operator[](const Edge& e) const { 1144 if (res_graph>forward(e)) 1145 return (*(res_graph>capacity))[e](*(res_graph>flow))[e]; 1146 else 1147 return (*(res_graph>flow))[e]; 1148 } 1149 }; 1150 1151 // KEEP_MAPS(Parent, ResGraphWrapper); 1152 }; 1153 1154 1155 1156 template <typename _Graph, typename FirstOutEdgesMap> 1157 class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> { 1158 public: 1159 typedef _Graph Graph; 1160 typedef GraphWrapperBase<_Graph> Parent; 1161 protected: 1162 FirstOutEdgesMap* first_out_edges; 1163 ErasingFirstGraphWrapperBase() : Parent(), 1164 first_out_edges(0) { } 1165 1166 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) { 1167 first_out_edges=&_first_out_edges; 1168 } 1169 1170 public: 1171 1172 typedef typename Parent::Node Node; 1173 typedef typename Parent::Edge Edge; 1174 1175 void firstOut(Edge& i, const Node& n) const { 1176 i=(*first_out_edges)[n]; 1177 } 1178 1179 void erase(const Edge& e) const { 1180 Node n=source(e); 1181 Edge f=e; 1182 Parent::nextOut(f); 1183 first_out_edges>set(n, f); 1184 } 1185 }; 1186 1187 1188 /// For blocking flows. 1189 1190 ///\warning Graph wrappers are in even more experimental state than the other 1191 ///parts of the lib. Use them at you own risk. 1192 /// 1193 /// This graph wrapper is used for onthefly 1194 /// Dinits blocking flow computations. 1195 /// For each node, an outedge is stored which is used when the 1196 /// \code 1197 /// OutEdgeIt& first(OutEdgeIt&, const Node&) 1198 /// \endcode 1199 /// is called. 1200 /// 1201 /// \author Marton Makai 1202 template <typename _Graph, typename FirstOutEdgesMap> 1203 class ErasingFirstGraphWrapper : 1204 public IterableGraphExtender< 1205 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > { 1206 public: 1207 typedef _Graph Graph; 1208 typedef IterableGraphExtender< 1209 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent; 1210 ErasingFirstGraphWrapper(Graph& _graph, 1211 FirstOutEdgesMap& _first_out_edges) { 1212 setGraph(_graph); 1213 setFirstOutEdgesMap(_first_out_edges); 1214 } 1215 1216 }; 1217 1218 ///@} 1219 1220 } //namespace lemon 1221 1222 #endif //LEMON_GRAPH_WRAPPER_H 1223 6 The main parts of LEMON are the different graph structures, 7 generic graph algorithms, graph concepts which couple these, and 8 graph wrappers. While the previous ones are more or less clear, the 9 latter notion needs further explanation. 10 Graph wrappers are graph classes which serve for considering graph 11 structures in different ways. A short example makes the notion much 12 clearer. 13 Suppose that we have an instance \c g of a directed graph 14 type say \c ListGraph and an algorithm 15 \code template<typename Graph> int algorithm(const Graph&); \endcode 16 is needed to run on the reversely oriented graph. 17 It may be expensive (in time or in memory usage) to copy 18 \c g with the reverse orientation. 19 Thus, a wrapper class 20 \code template<typename Graph> class RevGraphWrapper; \endcode is used. 21 The code looks as follows 22 \code 23 ListGraph g; 24 RevGraphWrapper<ListGraph> rgw(g); 25 int result=algorithm(rgw); 26 \endcode 27 After running the algorithm, the original graph \c g 28 remains untouched. Thus the graph wrapper used above is to consider the 29 original graph with reverse orientation. 30 This techniques gives rise to an elegant code, and 31 based on stable graph wrappers, complex algorithms can be 32 implemented easily. 33 In flow, circulation and bipartite matching problems, the residual 34 graph is of particular importance. Combining a wrapper implementing 35 this, shortest path algorithms and minimum mean cycle algorithms, 36 a range of weighted and cardinality optimization algorithms can be 37 obtained. For lack of space, for other examples, 38 the interested user is referred to the detailed documentation of graph 39 wrappers. 40 The behavior of graph wrappers can be very different. Some of them keep 41 capabilities of the original graph while in other cases this would be 42 meaningless. This means that the concepts that they are a model of depend 43 on the graph wrapper, and the wrapped graph(s). 44 If an edge of \c rgw is deleted, this is carried out by 45 deleting the corresponding edge of \c g. But for a residual 46 graph, this operation has no sense. 47 Let we stand one more example here to simplify your work. 48 wrapper class 49 \code template<typename Graph> class RevGraphWrapper; \endcode 50 has constructor 51 <tt> RevGraphWrapper(Graph& _g)</tt>. 52 This means that in a situation, 53 when a <tt> const ListGraph& </tt> reference to a graph is given, 54 then it have to be instantiated with <tt>Graph=const ListGraph</tt>. 55 \code 56 int algorithm1(const ListGraph& g) { 57 RevGraphWrapper<const ListGraph> rgw(g); 58 return algorithm2(rgw); 59 } 60 \endcode 61 */
Note: See TracChangeset
for help on using the changeset viewer.