Changeset 496:7c463a7635d4 in lemon0.x for src/work/marci/bipartite_graph_wrapper.h
 Timestamp:
 04/30/04 16:02:10 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@655
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bipartite_graph_wrapper.h
r495 r496 1 1 // * c++ * 2 #ifndef HUGO_ GRAPH_WRAPPER_H3 #define HUGO_ GRAPH_WRAPPER_H2 #ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H 3 #define HUGO_BIPARTITE_GRAPH_WRAPPER_H 4 4 5 5 ///\ingroup gwrappers … … 13 13 #include <invalid.h> 14 14 #include <iter_map.h> 15 #include <graph_wrapper.h> 15 16 16 17 namespace hugo { 17 18 // Graph wrappers19 20 /// \addtogroup gwrappers21 /// A main parts of HUGOlib are the different graph structures,22 /// generic graph algorithms, graph concepts which couple these, and23 /// graph wrappers. While the previous ones are more or less clear, the24 /// latter notion needs further explanation.25 /// Graph wrappers are graph classes which serve for considering graph26 /// structures in different ways. A short example makes the notion much27 /// clearer.28 /// Suppose that we have an instance \c g of a directed graph29 /// type say \c ListGraph and an algorithm30 /// \code template<typename Graph> int algorithm(const Graph&); \endcode31 /// is needed to run on the reversely oriented graph.32 /// It may be expensive (in time or in memory usage) to copy33 /// \c g with the reverse orientation.34 /// Thus, a wrapper class35 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.36 /// The code looks as follows37 /// \code38 /// ListGraph g;39 /// RevGraphWrapper<ListGraph> rgw(g);40 /// int result=algorithm(rgw);41 /// \endcode42 /// After running the algorithm, the original graph \c g43 /// remains untouched. Thus the graph wrapper used above is to consider the44 /// original graph with reverse orientation.45 /// This techniques gives rise to an elegant code, and46 /// based on stable graph wrappers, complex algorithms can be47 /// implemented easily.48 /// In flow, circulation and bipartite matching problems, the residual49 /// graph is of particular importance. Combining a wrapper implementing50 /// this, shortest path algorithms and minimum mean cycle algorithms,51 /// a range of weighted and cardinality optimization algorithms can be52 /// obtained. For lack of space, for other examples,53 /// the interested user is referred to the detailed documentation of graph54 /// wrappers.55 /// The behavior of graph wrappers can be very different. Some of them keep56 /// capabilities of the original graph while in other cases this would be57 /// meaningless. This means that the concepts that they are a model of depend58 /// on the graph wrapper, and the wrapped graph(s).59 /// If an edge of \c rgw is deleted, this is carried out by60 /// deleting the corresponding edge of \c g. But for a residual61 /// graph, this operation has no sense.62 /// Let we stand one more example here to simplify your work.63 /// wrapper class64 /// \code template<typename Graph> class RevGraphWrapper; \endcode65 /// has constructor66 /// <tt> RevGraphWrapper(Graph& _g)</tt>.67 /// This means that in a situation,68 /// when a <tt> const ListGraph& </tt> reference to a graph is given,69 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.70 /// \code71 /// int algorithm1(const ListGraph& g) {72 /// RevGraphWrapper<const ListGraph> rgw(g);73 /// return algorithm2(rgw);74 /// }75 /// \endcode76 77 /// \addtogroup gwrappers78 /// @{79 80 ///Base type for the Graph Wrappers81 82 ///This is the base type for the Graph Wrappers.83 ///\todo Some more docs...84 ///85 ///\author Marton Makai86 87 template<typename Graph>88 class GraphWrapper {89 protected:90 Graph* graph;91 92 public:93 typedef Graph BaseGraph;94 typedef Graph ParentGraph;95 96 // GraphWrapper() : graph(0) { }97 GraphWrapper(Graph& _graph) : graph(&_graph) { }98 // void setGraph(Graph& _graph) { graph=&_graph; }99 // Graph& getGraph() const { return *graph; }100 101 // typedef typename Graph::Node Node;102 class Node : public Graph::Node {103 friend class GraphWrapper<Graph>;104 public:105 Node() { }106 Node(const typename Graph::Node& _n) : Graph::Node(_n) { }107 Node(const Invalid& i) : Graph::Node(i) { }108 };109 class NodeIt {110 friend class GraphWrapper<Graph>;111 typename Graph::NodeIt n;112 public:113 NodeIt() { }114 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }115 NodeIt(const Invalid& i) : n(i) { }116 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }117 operator Node() const { return Node(typename Graph::Node(n)); }118 };119 // typedef typename Graph::Edge Edge;120 class Edge : public Graph::Edge {121 friend class GraphWrapper<Graph>;122 public:123 Edge() { }124 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }125 Edge(const Invalid& i) : Graph::Edge(i) { }126 };127 class OutEdgeIt {128 friend class GraphWrapper<Graph>;129 typename Graph::OutEdgeIt e;130 public:131 OutEdgeIt() { }132 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }133 OutEdgeIt(const Invalid& i) : e(i) { }134 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :135 e(*(_G.graph), typename Graph::Node(_n)) { }136 operator Edge() const { return Edge(typename Graph::Edge(e)); }137 };138 class InEdgeIt {139 friend class GraphWrapper<Graph>;140 typename Graph::InEdgeIt e;141 public:142 InEdgeIt() { }143 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }144 InEdgeIt(const Invalid& i) : e(i) { }145 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :146 e(*(_G.graph), typename Graph::Node(_n)) { }147 operator Edge() const { return Edge(typename Graph::Edge(e)); }148 };149 //typedef typename Graph::SymEdgeIt SymEdgeIt;150 class EdgeIt {151 friend class GraphWrapper<Graph>;152 typename Graph::EdgeIt e;153 public:154 EdgeIt() { }155 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }156 EdgeIt(const Invalid& i) : e(i) { }157 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }158 operator Edge() const { return Edge(typename Graph::Edge(e)); }159 };160 161 NodeIt& first(NodeIt& i) const {162 i=NodeIt(*this); return i;163 }164 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {165 i=OutEdgeIt(*this, p); return i;166 }167 InEdgeIt& first(InEdgeIt& i, const Node& p) const {168 i=InEdgeIt(*this, p); return i;169 }170 EdgeIt& first(EdgeIt& i) const {171 i=EdgeIt(*this); return i;172 }173 174 NodeIt& next(NodeIt& i) const { graph>next(i.n); return i; }175 OutEdgeIt& next(OutEdgeIt& i) const { graph>next(i.e); return i; }176 InEdgeIt& next(InEdgeIt& i) const { graph>next(i.e); return i; }177 EdgeIt& next(EdgeIt& i) const { graph>next(i.e); return i; }178 179 Node tail(const Edge& e) const {180 return Node(graph>tail(static_cast<typename Graph::Edge>(e))); }181 Node head(const Edge& e) const {182 return Node(graph>head(static_cast<typename Graph::Edge>(e))); }183 184 bool valid(const Node& n) const {185 return graph>valid(static_cast<typename Graph::Node>(n)); }186 bool valid(const Edge& e) const {187 return graph>valid(static_cast<typename Graph::Edge>(e)); }188 189 int nodeNum() const { return graph>nodeNum(); }190 int edgeNum() const { return graph>edgeNum(); }191 192 Node aNode(const OutEdgeIt& e) const { return Node(graph>aNode(e.e)); }193 Node aNode(const InEdgeIt& e) const { return Node(graph>aNode(e.e)); }194 Node bNode(const OutEdgeIt& e) const { return Node(graph>bNode(e.e)); }195 Node bNode(const InEdgeIt& e) const { return Node(graph>bNode(e.e)); }196 197 Node addNode() const { return Node(graph>addNode()); }198 Edge addEdge(const Node& tail, const Node& head) const {199 return Edge(graph>addEdge(tail, head)); }200 201 void erase(const Node& i) const { graph>erase(i); }202 void erase(const Edge& i) const { graph>erase(i); }203 204 void clear() const { graph>clear(); }205 206 template<typename T> class NodeMap : public Graph::template NodeMap<T> {207 typedef typename Graph::template NodeMap<T> Parent;208 public:209 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }210 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }211 };212 213 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {214 typedef typename Graph::template EdgeMap<T> Parent;215 public:216 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }217 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }218 };219 };220 221 /// A graph wrapper which reverses the orientation of the edges.222 223 /// A graph wrapper which reverses the orientation of the edges.224 ///225 ///\author Marton Makai226 template<typename Graph>227 class RevGraphWrapper : public GraphWrapper<Graph> {228 public:229 230 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }231 232 typedef typename GraphWrapper<Graph>::Node Node;233 typedef typename GraphWrapper<Graph>::Edge Edge;234 //If Graph::OutEdgeIt is not defined235 //and we do not want to use RevGraphWrapper::InEdgeIt,236 //the typdef techinque does not work.237 //Unfortunately all the typedefs are instantiated in templates.238 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;239 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;240 241 class OutEdgeIt {242 friend class GraphWrapper<Graph>;243 friend class RevGraphWrapper<Graph>;244 typename Graph::InEdgeIt e;245 public:246 OutEdgeIt() { }247 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }248 OutEdgeIt(const Invalid& i) : e(i) { }249 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :250 e(*(_G.graph), typename Graph::Node(_n)) { }251 operator Edge() const { return Edge(typename Graph::Edge(e)); }252 };253 class InEdgeIt {254 friend class GraphWrapper<Graph>;255 friend class RevGraphWrapper<Graph>;256 typename Graph::OutEdgeIt e;257 public:258 InEdgeIt() { }259 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }260 InEdgeIt(const Invalid& i) : e(i) { }261 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :262 e(*(_G.graph), typename Graph::Node(_n)) { }263 operator Edge() const { return Edge(typename Graph::Edge(e)); }264 };265 266 using GraphWrapper<Graph>::first;267 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {268 i=OutEdgeIt(*this, p); return i;269 }270 InEdgeIt& first(InEdgeIt& i, const Node& p) const {271 i=InEdgeIt(*this, p); return i;272 }273 274 using GraphWrapper<Graph>::next;275 OutEdgeIt& next(OutEdgeIt& i) const { this>graph>next(i.e); return i; }276 InEdgeIt& next(InEdgeIt& i) const { this>graph>next(i.e); return i; }277 278 Node aNode(const OutEdgeIt& e) const {279 return Node(this>graph>aNode(e.e)); }280 Node aNode(const InEdgeIt& e) const {281 return Node(this>graph>aNode(e.e)); }282 Node bNode(const OutEdgeIt& e) const {283 return Node(this>graph>bNode(e.e)); }284 Node bNode(const InEdgeIt& e) const {285 return Node(this>graph>bNode(e.e)); }286 287 Node tail(const Edge& e) const {288 return GraphWrapper<Graph>::head(e); }289 Node head(const Edge& e) const {290 return GraphWrapper<Graph>::tail(e); }291 292 };293 294 /// Wrapper for hiding nodes and edges from a graph.295 296 /// This wrapper shows a graph with filtered nodeset and297 /// edgeset. The quick brown fox iterator jumps over298 /// the lazy dog nodes or edges if the values for them are false299 /// in the bool maps.300 ///301 ///\author Marton Makai302 template<typename Graph, typename NodeFilterMap,303 typename EdgeFilterMap>304 class SubGraphWrapper : public GraphWrapper<Graph> {305 protected:306 NodeFilterMap* node_filter_map;307 EdgeFilterMap* edge_filter_map;308 public:309 310 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,311 EdgeFilterMap& _edge_filter_map) :312 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),313 edge_filter_map(&_edge_filter_map) { }314 315 typedef typename GraphWrapper<Graph>::Node Node;316 class NodeIt {317 friend class GraphWrapper<Graph>;318 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;319 typename Graph::NodeIt n;320 public:321 NodeIt() { }322 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }323 NodeIt(const Invalid& i) : n(i) { }324 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :325 n(*(_G.graph)) {326 while (_G.graph>valid(n) && !(*(_G.node_filter_map))[n])327 _G.graph>next(n);328 }329 operator Node() const { return Node(typename Graph::Node(n)); }330 };331 typedef typename GraphWrapper<Graph>::Edge Edge;332 class OutEdgeIt {333 friend class GraphWrapper<Graph>;334 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;335 typename Graph::OutEdgeIt e;336 public:337 OutEdgeIt() { }338 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }339 OutEdgeIt(const Invalid& i) : e(i) { }340 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,341 const Node& _n) :342 e(*(_G.graph), typename Graph::Node(_n)) {343 while (_G.graph>valid(e) && !(*(_G.edge_filter_map))[e])344 _G.graph>next(e);345 }346 operator Edge() const { return Edge(typename Graph::Edge(e)); }347 };348 class InEdgeIt {349 friend class GraphWrapper<Graph>;350 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;351 typename Graph::InEdgeIt e;352 public:353 InEdgeIt() { }354 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }355 InEdgeIt(const Invalid& i) : e(i) { }356 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,357 const Node& _n) :358 e(*(_G.graph), typename Graph::Node(_n)) {359 while (_G.graph>valid(e) && !(*(_G.edge_filter_map))[e])360 _G.graph>next(e);361 }362 operator Edge() const { return Edge(typename Graph::Edge(e)); }363 };364 //typedef typename Graph::SymEdgeIt SymEdgeIt;365 class EdgeIt {366 friend class GraphWrapper<Graph>;367 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;368 typename Graph::EdgeIt e;369 public:370 EdgeIt() { }371 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }372 EdgeIt(const Invalid& i) : e(i) { }373 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :374 e(*(_G.graph)) {375 while (_G.graph>valid(e) && !(*(_G.edge_filter_map))[e])376 _G.graph>next(e);377 }378 operator Edge() const { return Edge(typename Graph::Edge(e)); }379 };380 381 NodeIt& first(NodeIt& i) const {382 i=NodeIt(*this); return i;383 }384 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {385 i=OutEdgeIt(*this, p); return i;386 }387 InEdgeIt& first(InEdgeIt& i, const Node& p) const {388 i=InEdgeIt(*this, p); return i;389 }390 EdgeIt& first(EdgeIt& i) const {391 i=EdgeIt(*this); return i;392 }393 394 NodeIt& next(NodeIt& i) const {395 this>graph>next(i.n);396 while (this>graph>valid(i) && !(*node_filter_map)[i.n]) {397 this>graph>next(i.n); }398 return i;399 }400 OutEdgeIt& next(OutEdgeIt& i) const {401 this>graph>next(i.e);402 while (this>graph>valid(i) && !(*edge_filter_map)[i.e]) {403 this>graph>next(i.e); }404 return i;405 }406 InEdgeIt& next(InEdgeIt& i) const {407 this>graph>next(i.e);408 while (this>graph>valid(i) && !(*edge_filter_map)[i.e]) {409 this>graph>next(i.e); }410 return i;411 }412 EdgeIt& next(EdgeIt& i) const {413 this>graph>next(i.e);414 while (this>graph>valid(i) && !(*edge_filter_map)[i.e]) {415 this>graph>next(i.e); }416 return i;417 }418 419 Node aNode(const OutEdgeIt& e) const {420 return Node(this>graph>aNode(e.e)); }421 Node aNode(const InEdgeIt& e) const {422 return Node(this>graph>aNode(e.e)); }423 Node bNode(const OutEdgeIt& e) const {424 return Node(this>graph>bNode(e.e)); }425 Node bNode(const InEdgeIt& e) const {426 return Node(this>graph>bNode(e.e)); }427 428 ///\todo429 ///Some doki, please.430 void hide(const Node& n) const { node_filter_map>set(n, false); }431 ///\todo432 ///Some doki, please.433 void hide(const Edge& e) const { edge_filter_map>set(e, false); }434 435 ///\todo436 ///Some doki, please.437 void unHide(const Node& n) const { node_filter_map>set(n, true); }438 ///\todo439 ///Some doki, please.440 void unHide(const Edge& e) const { edge_filter_map>set(e, true); }441 442 ///\todo443 ///Some doki, please.444 bool hidden(const Node& n) const { return (*node_filter_map)[n]; }445 ///\todo446 ///Some doki, please.447 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }448 };449 450 /// A wrapper for forgetting the orientation of a graph.451 452 /// A wrapper for getting an undirected graph by forgetting453 /// the orientation of a directed one.454 template<typename Graph>455 class UndirGraphWrapper : public GraphWrapper<Graph> {456 public:457 typedef typename GraphWrapper<Graph>::Node Node;458 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;459 typedef typename GraphWrapper<Graph>::Edge Edge;460 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;461 462 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }463 464 class OutEdgeIt {465 friend class UndirGraphWrapper<Graph>;466 bool out_or_in; //true iff out467 typename Graph::OutEdgeIt out;468 typename Graph::InEdgeIt in;469 public:470 OutEdgeIt() { }471 OutEdgeIt(const Invalid& i) : Edge(i) { }472 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {473 out_or_in=true; _G.graph>first(out, _n);474 if (!(_G.graph>valid(out))) { out_or_in=false; _G.graph>first(in, _n); }475 }476 operator Edge() const {477 if (out_or_in) return Edge(out); else return Edge(in);478 }479 };480 481 //FIXME InEdgeIt482 typedef OutEdgeIt InEdgeIt;483 484 using GraphWrapper<Graph>::first;485 // NodeIt& first(NodeIt& i) const {486 // i=NodeIt(*this); return i;487 // }488 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {489 i=OutEdgeIt(*this, p); return i;490 }491 //FIXME492 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {493 // i=InEdgeIt(*this, p); return i;494 // }495 // EdgeIt& first(EdgeIt& i) const {496 // i=EdgeIt(*this); return i;497 // }498 499 using GraphWrapper<Graph>::next;500 // NodeIt& next(NodeIt& n) const {501 // GraphWrapper<Graph>::next(n);502 // return n;503 // }504 OutEdgeIt& next(OutEdgeIt& e) const {505 if (e.out_or_in) {506 typename Graph::Node n=this>graph>tail(e.out);507 this>graph>next(e.out);508 if (!this>graph>valid(e.out)) {509 e.out_or_in=false; this>graph>first(e.in, n); }510 } else {511 this>graph>next(e.in);512 }513 return e;514 }515 //FIXME InEdgeIt516 // EdgeIt& next(EdgeIt& e) const {517 // GraphWrapper<Graph>::next(n);518 // // graph>next(e.e);519 // return e;520 // }521 522 Node aNode(const OutEdgeIt& e) const {523 if (e.out_or_in) return this>graph>tail(e); else524 return this>graph>head(e); }525 Node bNode(const OutEdgeIt& e) const {526 if (e.out_or_in) return this>graph>head(e); else527 return this>graph>tail(e); }528 };529 530 /// A wrapper for composing the residual graph for directed flow and circulation problems.531 532 /// A wrapper for composing the residual graph for directed flow and circulation problems.533 template<typename Graph, typename Number,534 typename CapacityMap, typename FlowMap>535 class ResGraphWrapper : public GraphWrapper<Graph> {536 protected:537 const CapacityMap* capacity;538 FlowMap* flow;539 public:540 541 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,542 FlowMap& _flow) :543 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }544 545 class Edge;546 class OutEdgeIt;547 friend class Edge;548 friend class OutEdgeIt;549 550 typedef typename GraphWrapper<Graph>::Node Node;551 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;552 class Edge : public Graph::Edge {553 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;554 protected:555 bool forward; //true, iff forward556 // typename Graph::Edge e;557 public:558 Edge() { }559 Edge(const typename Graph::Edge& _e, bool _forward) :560 Graph::Edge(_e), forward(_forward) { }561 Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }562 //the unique invalid iterator563 friend bool operator==(const Edge& u, const Edge& v) {564 return (v.forward==u.forward &&565 static_cast<typename Graph::Edge>(u)==566 static_cast<typename Graph::Edge>(v));567 }568 friend bool operator!=(const Edge& u, const Edge& v) {569 return (v.forward!=u.forward 570 static_cast<typename Graph::Edge>(u)!=571 static_cast<typename Graph::Edge>(v));572 }573 };574 575 class OutEdgeIt {576 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;577 protected:578 typename Graph::OutEdgeIt out;579 typename Graph::InEdgeIt in;580 bool forward;581 public:582 OutEdgeIt() { }583 //FIXME584 // OutEdgeIt(const Edge& e) : Edge(e) { }585 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }586 //the unique invalid iterator587 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {588 forward=true;589 resG.graph>first(out, v);590 while( resG.graph>valid(out) && !(resG.resCap(*this)>0) ) { resG.graph>next(out); }591 if (!resG.graph>valid(out)) {592 forward=false;593 resG.graph>first(in, v);594 while( resG.graph>valid(in) && !(resG.resCap(*this)>0) ) { resG.graph>next(in); }595 }596 }597 operator Edge() const {598 // Edge e;599 // e.forward=this>forward;600 // if (this>forward) e=out; else e=in;601 // return e;602 if (this>forward)603 return Edge(out, this>forward);604 else605 return Edge(in, this>forward);606 }607 };608 609 class InEdgeIt {610 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;611 protected:612 typename Graph::OutEdgeIt out;613 typename Graph::InEdgeIt in;614 bool forward;615 public:616 InEdgeIt() { }617 //FIXME618 // OutEdgeIt(const Edge& e) : Edge(e) { }619 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }620 //the unique invalid iterator621 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {622 forward=true;623 resG.graph>first(in, v);624 while( resG.graph>valid(in) && !(resG.resCap(*this)>0) ) { resG.graph>next(in); }625 if (!resG.graph>valid(in)) {626 forward=false;627 resG.graph>first(out, v);628 while( resG.graph>valid(out) && !(resG.resCap(*this)>0) ) { resG.graph>next(out); }629 }630 }631 operator Edge() const {632 // Edge e;633 // e.forward=this>forward;634 // if (this>forward) e=out; else e=in;635 // return e;636 if (this>forward)637 return Edge(in, this>forward);638 else639 return Edge(out, this>forward);640 }641 };642 643 class EdgeIt {644 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;645 protected:646 typename Graph::EdgeIt e;647 bool forward;648 public:649 EdgeIt() { }650 EdgeIt(const Invalid& i) : e(i), forward(false) { }651 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {652 forward=true;653 resG.graph>first(e);654 while (resG.graph>valid(e) && !(resG.resCap(*this)>0)) resG.graph>next(e);655 if (!resG.graph>valid(e)) {656 forward=false;657 resG.graph>first(e);658 while (resG.graph>valid(e) && !(resG.resCap(*this)>0)) resG.graph>next(e);659 }660 }661 operator Edge() const {662 return Edge(e, this>forward);663 }664 };665 666 using GraphWrapper<Graph>::first;667 // NodeIt& first(NodeIt& i) const {668 // i=NodeIt(*this); return i;669 // }670 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {671 i=OutEdgeIt(*this, p); return i;672 }673 // FIXME not tested674 InEdgeIt& first(InEdgeIt& i, const Node& p) const {675 i=InEdgeIt(*this, p); return i;676 }677 EdgeIt& first(EdgeIt& i) const {678 i=EdgeIt(*this); return i;679 }680 681 using GraphWrapper<Graph>::next;682 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }683 OutEdgeIt& next(OutEdgeIt& e) const {684 if (e.forward) {685 Node v=this>graph>aNode(e.out);686 this>graph>next(e.out);687 while( this>graph>valid(e.out) && !(resCap(e)>0) ) {688 this>graph>next(e.out); }689 if (!this>graph>valid(e.out)) {690 e.forward=false;691 this>graph>first(e.in, v);692 while( this>graph>valid(e.in) && !(resCap(e)>0) ) {693 this>graph>next(e.in); }694 }695 } else {696 this>graph>next(e.in);697 while( this>graph>valid(e.in) && !(resCap(e)>0) ) {698 this>graph>next(e.in); }699 }700 return e;701 }702 // FIXME Not tested703 InEdgeIt& next(InEdgeIt& e) const {704 if (e.forward) {705 Node v=this>graph>aNode(e.in);706 this>graph>next(e.in);707 while( this>graph>valid(e.in) && !(resCap(e)>0) ) {708 this>graph>next(e.in); }709 if (!this>graph>valid(e.in)) {710 e.forward=false;711 this>graph>first(e.out, v);712 while( this>graph>valid(e.out) && !(resCap(e)>0) ) {713 this>graph>next(e.out); }714 }715 } else {716 this>graph>next(e.out);717 while( this>graph>valid(e.out) && !(resCap(e)>0) ) {718 this>graph>next(e.out); }719 }720 return e;721 }722 EdgeIt& next(EdgeIt& e) const {723 if (e.forward) {724 this>graph>next(e.e);725 while( this>graph>valid(e.e) && !(resCap(e)>0) ) {726 this>graph>next(e.e); }727 if (!this>graph>valid(e.e)) {728 e.forward=false;729 this>graph>first(e.e);730 while( this>graph>valid(e.e) && !(resCap(e)>0) ) {731 this>graph>next(e.e); }732 }733 } else {734 this>graph>next(e.e);735 while( this>graph>valid(e.e) && !(resCap(e)>0) ) {736 this>graph>next(e.e); }737 }738 return e;739 }740 741 Node tail(Edge e) const {742 return ((e.forward) ? this>graph>tail(e) : this>graph>head(e)); }743 Node head(Edge e) const {744 return ((e.forward) ? this>graph>head(e) : this>graph>tail(e)); }745 746 Node aNode(OutEdgeIt e) const {747 return ((e.forward) ? this>graph>aNode(e.out) :748 this>graph>aNode(e.in)); }749 Node bNode(OutEdgeIt e) const {750 return ((e.forward) ? this>graph>bNode(e.out) :751 this>graph>bNode(e.in)); }752 753 Node aNode(InEdgeIt e) const {754 return ((e.forward) ? this>graph>aNode(e.in) :755 this>graph>aNode(e.out)); }756 Node bNode(InEdgeIt e) const {757 return ((e.forward) ? this>graph>bNode(e.in) :758 this>graph>bNode(e.out)); }759 760 // int nodeNum() const { return graph>nodeNum(); }761 //FIXME762 void edgeNum() const { }763 //int edgeNum() const { return graph>edgeNum(); }764 765 766 // int id(Node v) const { return graph>id(v); }767 768 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }769 bool valid(Edge e) const {770 return this>graph>valid(e);771 //return e.forward ? graph>valid(e.out) : graph>valid(e.in);772 }773 774 void augment(const Edge& e, Number a) const {775 if (e.forward)776 // flow>set(e.out, flow>get(e.out)+a);777 flow>set(e, (*flow)[e]+a);778 else779 // flow>set(e.in, flow>get(e.in)a);780 flow>set(e, (*flow)[e]a);781 }782 783 Number resCap(const Edge& e) const {784 if (e.forward)785 // return (capacity>get(e.out)flow>get(e.out));786 return ((*capacity)[e](*flow)[e]);787 else788 // return (flow>get(e.in));789 return ((*flow)[e]);790 }791 792 // Number resCap(typename Graph::OutEdgeIt out) const {793 // // return (capacity>get(out)flow>get(out));794 // return ((*capacity)[out](*flow)[out]);795 // }796 797 // Number resCap(typename Graph::InEdgeIt in) const {798 // // return (flow>get(in));799 // return ((*flow)[in]);800 // }801 802 template <typename T>803 class EdgeMap {804 typename Graph::template EdgeMap<T> forward_map, backward_map;805 public:806 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }807 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }808 void set(Edge e, T a) {809 if (e.forward)810 forward_map.set(e.out, a);811 else812 backward_map.set(e.in, a);813 }814 T operator[](Edge e) const {815 if (e.forward)816 return forward_map[e.out];817 else818 return backward_map[e.in];819 }820 // T get(Edge e) const {821 // if (e.out_or_in)822 // return forward_map.get(e.out);823 // else824 // return backward_map.get(e.in);825 // }826 };827 };828 829 /// ErasingFirstGraphWrapper for blocking flows.830 831 /// ErasingFirstGraphWrapper for blocking flows.832 ///833 ///\author Marton Makai834 template<typename Graph, typename FirstOutEdgesMap>835 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {836 protected:837 FirstOutEdgesMap* first_out_edges;838 public:839 ErasingFirstGraphWrapper(Graph& _graph,840 FirstOutEdgesMap& _first_out_edges) :841 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }842 843 typedef typename GraphWrapper<Graph>::Node Node;844 // class NodeIt {845 // friend class GraphWrapper<Graph>;846 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;847 // typename Graph::NodeIt n;848 // public:849 // NodeIt() { }850 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }851 // NodeIt(const Invalid& i) : n(i) { }852 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :853 // n(*(_G.graph)) { }854 // operator Node() const { return Node(typename Graph::Node(n)); }855 // };856 typedef typename GraphWrapper<Graph>::Edge Edge;857 class OutEdgeIt {858 friend class GraphWrapper<Graph>;859 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;860 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;861 typename Graph::OutEdgeIt e;862 public:863 OutEdgeIt() { }864 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }865 OutEdgeIt(const Invalid& i) : e(i) { }866 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,867 const Node& _n) :868 e((*_G.first_out_edges)[_n]) { }869 operator Edge() const { return Edge(typename Graph::Edge(e)); }870 };871 class InEdgeIt {872 friend class GraphWrapper<Graph>;873 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;874 // typedef typename Graph::InEdgeIt GraphInEdgeIt;875 typename Graph::InEdgeIt e;876 public:877 InEdgeIt() { }878 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }879 InEdgeIt(const Invalid& i) : e(i) { }880 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,881 const Node& _n) :882 e(*(_G.graph), typename Graph::Node(_n)) { }883 operator Edge() const { return Edge(typename Graph::Edge(e)); }884 };885 //typedef typename Graph::SymEdgeIt SymEdgeIt;886 class EdgeIt {887 friend class GraphWrapper<Graph>;888 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;889 // typedef typename Graph::EdgeIt GraphEdgeIt;890 typename Graph::EdgeIt e;891 public:892 EdgeIt() { }893 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }894 EdgeIt(const Invalid& i) : e(i) { }895 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :896 e(*(_G.graph)) { }897 operator Edge() const { return Edge(typename Graph::Edge(e)); }898 };899 900 using GraphWrapper<Graph>::first;901 // NodeIt& first(NodeIt& i) const {902 // i=NodeIt(*this); return i;903 // }904 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {905 i=OutEdgeIt(*this, p); return i;906 }907 InEdgeIt& first(InEdgeIt& i, const Node& p) const {908 i=InEdgeIt(*this, p); return i;909 }910 EdgeIt& first(EdgeIt& i) const {911 i=EdgeIt(*this); return i;912 }913 914 using GraphWrapper<Graph>::next;915 // NodeIt& next(NodeIt& i) const { graph>next(i.n); return i; }916 OutEdgeIt& next(OutEdgeIt& i) const { this>graph>next(i.e); return i; }917 InEdgeIt& next(InEdgeIt& i) const { this>graph>next(i.e); return i; }918 EdgeIt& next(EdgeIt& i) const { this>graph>next(i.e); return i; }919 920 Node aNode(const OutEdgeIt& e) const {921 return Node(this>graph>aNode(e.e)); }922 Node aNode(const InEdgeIt& e) const {923 return Node(this>graph>aNode(e.e)); }924 Node bNode(const OutEdgeIt& e) const {925 return Node(this>graph>bNode(e.e)); }926 Node bNode(const InEdgeIt& e) const {927 return Node(this>graph>bNode(e.e)); }928 929 void erase(const OutEdgeIt& e) const {930 OutEdgeIt f=e;931 this>next(f);932 first_out_edges>set(this>tail(e), f.e);933 }934 };935 18 936 19 /// A wrapper for composing a bipartite graph.
Note: See TracChangeset
for help on using the changeset viewer.