sub_graph.h

00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_SUB_GRAPH_H
00020 #define LEMON_SUB_GRAPH_H
00021 
00022 #include <lemon/graph_adaptor.h>
00023 
00024 namespace lemon {
00025 
00029   template <typename _Graph>
00030   class SubGraphBase : public GraphAdaptorBase<const _Graph> {
00031   public:
00032     typedef _Graph Graph;
00033     typedef SubGraphBase<_Graph> SubGraph;
00034     typedef GraphAdaptorBase<const _Graph> Parent;
00035     typedef Parent Base;
00036 
00037     typedef typename Parent::Node Node;
00038     typedef typename Parent::Edge Edge;
00039 
00040 
00041   protected:
00042 
00043     class NodesImpl;
00044     class EdgesImpl;
00045 
00046     SubGraphBase() {}
00047 
00048     void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
00049       Parent::setGraph(_graph);
00050       nodes = &_nodes;
00051       edges = &_edges;
00052       firstNode = INVALID;
00053 
00054       Node node;
00055       Parent::first(node);
00056       while (node != INVALID) {
00057         (*nodes)[node].prev = node;
00058         (*nodes)[node].firstIn = INVALID;
00059         (*nodes)[node].firstOut = INVALID;
00060         Parent::next(node);
00061       }
00062 
00063       Edge edge;
00064       Parent::first(edge);
00065       while (edge != INVALID) {
00066         (*edges)[edge].prevOut = edge;
00067         Parent::next(edge);
00068       }
00069     }
00070 
00071   public:
00072 
00073     void first(Node& node) const {
00074       node = firstNode;
00075     }
00076     void next(Node& node) const {
00077       node = (*nodes)[node].next;
00078     }
00079 
00080     void first(Edge& edge) const {
00081       Node node = firstNode;
00082       while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00083         node = (*nodes)[node].next;
00084       }
00085       if (node == INVALID) {
00086         edge = INVALID;
00087       } else {
00088         edge = (*nodes)[node].firstOut;
00089       }
00090     }
00091     void next(Edge& edge) const {
00092       if ((*edges)[edge].nextOut != INVALID) {
00093         edge = (*edges)[edge].nextOut;
00094       } else {
00095         Node node = (*nodes)[source(edge)].next;
00096         while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00097           node = (*nodes)[node].next;
00098         }
00099         if (node == INVALID) {
00100           edge = INVALID;
00101         } else {
00102           edge = (*nodes)[node].firstOut;
00103         }
00104       }
00105     }
00106 
00107     void firstOut(Edge& edge, const Node& node) const {
00108       edge = (*nodes)[node].firstOut;
00109     }
00110     void nextOut(Edge& edge) const {
00111       edge = (*edges)[edge].nextOut;
00112     }
00113 
00114     void firstIn(Edge& edge, const Node& node) const {
00115       edge = (*nodes)[node].firstIn;
00116     }
00117     void nextIn(Edge& edge) const {
00118       edge = (*edges)[edge].nextIn;
00119     }
00120 
00124     bool hidden(const Node& node) const {
00125       return (*nodes)[node].prev == node;
00126     }
00127 
00133     void hide(const Node& node) {
00134       if (hidden(node)) return;
00135       Edge edge;
00136       firstOut(edge, node);
00137       while (edge != INVALID) {
00138         hide(edge);
00139         firstOut(edge, node);
00140       }
00141 
00142       firstOut(edge, node);
00143       while (edge != INVALID) {
00144         hide(edge);
00145         firstOut(edge, node);
00146       }
00147       if ((*nodes)[node].prev != INVALID) {
00148         (*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
00149       } else {
00150         firstNode = (*nodes)[node].next;
00151       }
00152       if ((*nodes)[node].next != INVALID) {
00153         (*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
00154       }
00155       (*nodes)[node].prev = node;
00156       (*nodes)[node].firstIn = INVALID;
00157       (*nodes)[node].firstOut = INVALID;
00158     }
00159 
00164     void unHide(const Node& node) {
00165       if (!hidden(node)) return;
00166       (*nodes)[node].next = firstNode;
00167       (*nodes)[node].prev = INVALID;
00168       if ((*nodes)[node].next != INVALID) {
00169         (*nodes)[(*nodes)[node].next].prev = node;
00170       }
00171       firstNode = node;
00172     }
00173 
00177     bool hidden(const Edge& edge) const {
00178       return (*edges)[edge].prevOut == edge;
00179     }
00180 
00185     void hide(const Edge& edge) {
00186       if (hidden(edge)) return;
00187       if ((*edges)[edge].prevOut == edge) return;
00188       if ((*edges)[edge].prevOut != INVALID) {
00189         (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
00190       } else {
00191         (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
00192       }
00193       if ((*edges)[edge].nextOut != INVALID) {
00194         (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
00195       }
00196 
00197       if ((*edges)[edge].prevIn != INVALID) {
00198         (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
00199       } else {
00200         (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
00201       }
00202       if ((*edges)[edge].nextIn != INVALID) {
00203         (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
00204       }
00205       (*edges)[edge].next = edge;
00206     }
00207 
00213     void unHide(const Edge& edge) {
00214       if (!hidden(edge)) return;
00215 
00216       Node node;
00217 
00218       node = Parent::source(edge);
00219       unHide(node);
00220       (*edges)[edge].nextOut = (*nodes)[node].firstOut;
00221       (*edges)[edge].prevOut = INVALID;
00222       if ((*edges)[edge].nextOut != INVALID) {
00223         (*edges)[(*edges)[edge].nextOut].prevOut = edge;
00224       }
00225       (*nodes)[node].firstOut = edge;
00226 
00227       node = Parent::target(edge);
00228       unHide(node);
00229       (*edges)[edge].nextIn = (*nodes)[node].firstIn;
00230       (*edges)[edge].prevIn = INVALID;
00231       if ((*edges)[edge].nextIn != INVALID) {
00232         (*edges)[(*edges)[edge].nextIn].prevIn = edge;
00233       }
00234       (*nodes)[node].firstIn = edge;      
00235     }
00236     
00237     typedef False NodeNumTag;
00238     typedef False EdgeNumTag;
00239 
00240   protected:
00241     struct NodeT {
00242       Node prev, next;
00243       Edge firstIn, firstOut;
00244     };
00245     class NodesImpl : public Graph::template NodeMap<NodeT> {
00246       friend class SubGraphBase;
00247     public:
00248       typedef typename Graph::template NodeMap<NodeT> Parent;
00249 
00250       NodesImpl(SubGraph& _adaptor, const Graph& _graph) 
00251         : Parent(_graph), adaptor(_adaptor) {}
00252 
00253       virtual ~NodesImpl() {}
00254 
00255       virtual void build() {
00256         Parent::build();
00257         Node node;
00258         adaptor.Base::first(node);
00259         while (node != INVALID) {
00260           Parent::operator[](node).prev = node;
00261           Parent::operator[](node).firstIn = INVALID;
00262           Parent::operator[](node).firstOut = INVALID;
00263           adaptor.Base::next(node);
00264         }
00265       }
00266 
00267       virtual void clear() {
00268         adaptor.firstNode = INVALID;
00269         Parent::clear();
00270       }
00271 
00272       virtual void add(const Node& node) {
00273         Parent::add(node);
00274         Parent::operator[](node).prev = node;
00275         Parent::operator[](node).firstIn = INVALID;
00276         Parent::operator[](node).firstOut = INVALID;
00277       }
00278       virtual void add(const std::vector<Node>& nodes) {
00279         Parent::add(nodes);
00280         for (int i = 0; i < (int)nodes.size(); ++i) {
00281           Parent::operator[](nodes[i]).prev = nodes[i];
00282           Parent::operator[](nodes[i]).firstIn = INVALID;
00283           Parent::operator[](nodes[i]).firstOut = INVALID;
00284         }
00285       } 
00286 
00287       virtual void erase(const Node& node) {
00288         adaptor.hide(node);
00289         Parent::erase(node);
00290       }
00291 
00292       virtual void erase(const std::vector<Node>& nodes) {
00293         for (int i = 0; i < (int)nodes.size(); ++i) {
00294           adaptor.hide(nodes[i]);
00295         }
00296         Parent::erase(nodes);
00297       }
00298 
00299     private:
00300       SubGraph& adaptor;
00301     };
00302 
00303     struct EdgeT {
00304       Edge prevOut, nextOut;
00305       Edge prevIn, nextIn;
00306     };
00307     class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
00308       friend class SubGraphBase;
00309     public:
00310       typedef typename Graph::template EdgeMap<EdgeT> Parent;
00311 
00312       EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 
00313         : Parent(_graph), adaptor(_adaptor) {}
00314 
00315       virtual ~EdgesImpl() {}
00316 
00317       virtual void build() {
00318         Parent::build();
00319         Edge edge;
00320         adaptor.Base::first(edge);
00321         while (edge != INVALID) {
00322           Parent::operator[](edge).prevOut = edge;
00323           adaptor.Base::next(edge);
00324         }
00325       }
00326 
00327       virtual void clear() {
00328         Node node;
00329         adaptor.first(node);
00330         while (node != INVALID) {
00331           (*adaptor.nodes).firstIn = INVALID;
00332           (*adaptor.nodes).firstOut = INVALID;
00333           adaptor.next(node);
00334         }
00335         Parent::clear();
00336       }
00337 
00338       virtual void add(const Edge& edge) {
00339         Parent::add(edge);
00340         Parent::operator[](edge).prevOut = edge;
00341       }
00342 
00343       virtual void add(const std::vector<Edge>& edges) {
00344         Parent::add(edges);
00345         for (int i = 0; i < (int)edges.size(); ++i) {
00346           Parent::operator[](edges[i]).prevOut = edges[i];
00347         }
00348       }
00349 
00350       virtual void erase(const Edge& edge) {
00351         adaptor.hide(edge);
00352         Parent::erase(edge);
00353       }
00354 
00355       virtual void erase(const std::vector<Edge>& edges) {
00356         for (int i = 0; i < (int)edges.size(); ++i) {
00357           adaptor.hide(edges[i]);
00358         }
00359         Parent::erase(edge);
00360       }
00361 
00362     private:
00363       SubGraph& adaptor;
00364     };
00365 
00366     NodesImpl* nodes;
00367     EdgesImpl* edges;
00368     Node firstNode;
00369   };
00370 
00386   template <typename Graph>
00387   class SubGraph 
00388     : public IterableGraphExtender< SubGraphBase<Graph> > {
00389   public:
00390     typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
00391   public:
00396     SubGraph(const Graph& _graph) 
00397       : Parent(), nodes(*this, _graph), edges(*this, _graph) { 
00398       Parent::construct(_graph, nodes, edges);
00399     }
00400   private:
00401     typename Parent::NodesImpl nodes;
00402     typename Parent::EdgesImpl edges;
00403   };
00404 
00408   template <typename _Graph>
00409   class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
00410   public:
00411     typedef _Graph Graph;
00412     typedef EdgeSubGraphBase<_Graph> SubGraph;
00413     typedef GraphAdaptorBase<const _Graph> Parent;
00414     typedef Parent Base;
00415 
00416     typedef typename Parent::Node Node;
00417     typedef typename Parent::Edge Edge;
00418 
00419 
00420   protected:
00421 
00422     class NodesImpl;
00423     class EdgesImpl;
00424 
00425     EdgeSubGraphBase() {}
00426 
00427     void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
00428       Parent::setGraph(_graph);
00429       nodes = &_nodes;
00430       edges = &_edges;
00431 
00432       Node node;
00433       Parent::first(node);
00434       while (node != INVALID) {
00435         (*nodes)[node].firstIn = INVALID;
00436         (*nodes)[node].firstOut = INVALID;
00437         Parent::next(node);
00438       }
00439 
00440       Edge edge;
00441       Parent::first(edge);
00442       while (edge != INVALID) {
00443         (*edges)[edge].prevOut = edge;
00444         Parent::next(edge);
00445       }
00446     }
00447 
00448   public:
00449 
00450     void first(Node& node) const {
00451       Parent::first(node);
00452     }
00453     void next(Node& node) const {
00454       Parent::next(node);
00455     }
00456 
00457     void first(Edge& edge) const {
00458       Node node;
00459       Parent::first(node);
00460       while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00461         Parent::next(node);
00462       }
00463       if (node == INVALID) {
00464         edge = INVALID;
00465       } else {
00466         edge = (*nodes)[node].firstOut;
00467       }
00468     }
00469     void next(Edge& edge) const {
00470       if ((*edges)[edge].nextOut != INVALID) {
00471         edge = (*edges)[edge].nextOut;
00472       } else {
00473         Node node = source(edge);
00474         Parent::next(node);
00475         while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
00476           Parent::next(node);
00477         }
00478         if (node == INVALID) {
00479           edge = INVALID;
00480         } else {
00481           edge = (*nodes)[node].firstOut;
00482         }
00483       }
00484     }
00485 
00486     void firstOut(Edge& edge, const Node& node) const {
00487       edge = (*nodes)[node].firstOut;
00488     }
00489     void nextOut(Edge& edge) const {
00490       edge = (*edges)[edge].nextOut;
00491     }
00492 
00493     void firstIn(Edge& edge, const Node& node) const {
00494       edge = (*nodes)[node].firstIn;
00495     }
00496     void nextIn(Edge& edge) const {
00497       edge = (*edges)[edge].nextIn;
00498     }
00499 
00503     bool hidden(const Edge& edge) const {
00504       return (*edges)[edge].prevOut == edge;
00505     }
00506 
00511     void hide(const Edge& edge) {
00512       if (hidden(edge)) return;
00513       if ((*edges)[edge].prevOut != INVALID) {
00514         (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
00515       } else {
00516         (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
00517       }
00518       if ((*edges)[edge].nextOut != INVALID) {
00519         (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
00520       }
00521 
00522       if ((*edges)[edge].prevIn != INVALID) {
00523         (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
00524       } else {
00525         (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
00526       }
00527       if ((*edges)[edge].nextIn != INVALID) {
00528         (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
00529       }
00530       (*edges)[edge].prevOut = edge;
00531     }
00532 
00537     void unHide(const Edge& edge) {
00538       if (!hidden(edge)) return;
00539       Node node;
00540 
00541       node = Parent::source(edge);
00542       (*edges)[edge].nextOut = (*nodes)[node].firstOut;
00543       (*edges)[edge].prevOut = INVALID;
00544       if ((*edges)[edge].nextOut != INVALID) {
00545         (*edges)[(*edges)[edge].nextOut].prevOut = edge;
00546       }
00547       (*nodes)[node].firstOut = edge;
00548 
00549       node = Parent::target(edge);
00550       (*edges)[edge].nextIn = (*nodes)[node].firstIn;
00551       (*edges)[edge].prevIn = INVALID;
00552       if ((*edges)[edge].nextIn != INVALID) {
00553         (*edges)[(*edges)[edge].nextIn].prevIn = edge;
00554       }
00555       (*nodes)[node].firstIn = edge;      
00556     }
00557     
00558   protected:
00559     struct NodeT {
00560       Edge firstIn, firstOut;
00561     };
00562     class NodesImpl : public Graph::template NodeMap<NodeT> {
00563       friend class EdgeSubGraphBase;
00564     public:
00565       typedef typename Graph::template NodeMap<NodeT> Parent;
00566 
00567       NodesImpl(SubGraph& _adaptor, const Graph& _graph) 
00568         : Parent(_graph), adaptor(_adaptor) {}
00569 
00570       virtual ~NodesImpl() {}
00571 
00572       virtual void build() {
00573         Parent::build();
00574         Node node;
00575         adaptor.Base::first(node);
00576         while (node != INVALID) {
00577           Parent::operator[](node).firstIn = INVALID;
00578           Parent::operator[](node).firstOut = INVALID;
00579           adaptor.Base::next(node);
00580         }
00581       }
00582 
00583       virtual void add(const Node& node) {
00584         Parent::add(node);
00585         Parent::operator[](node).firstIn = INVALID;
00586         Parent::operator[](node).firstOut = INVALID;
00587       }
00588 
00589     private:
00590       SubGraph& adaptor;
00591     };
00592 
00593     struct EdgeT {
00594       Edge prevOut, nextOut;
00595       Edge prevIn, nextIn;
00596     };
00597     class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
00598       friend class EdgeSubGraphBase;
00599     public:
00600       typedef typename Graph::template EdgeMap<EdgeT> Parent;
00601 
00602       EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 
00603         : Parent(_graph), adaptor(_adaptor) {}
00604 
00605       virtual ~EdgesImpl() {}
00606 
00607       virtual void build() {
00608         Parent::build();
00609         Edge edge;
00610         adaptor.Base::first(edge);
00611         while (edge != INVALID) {
00612           Parent::operator[](edge).prevOut = edge;
00613           adaptor.Base::next(edge);
00614         }
00615       }
00616 
00617       virtual void clear() {
00618         Node node;
00619         adaptor.Base::first(node);
00620         while (node != INVALID) {
00621           (*adaptor.nodes)[node].firstIn = INVALID;
00622           (*adaptor.nodes)[node].firstOut = INVALID;
00623           adaptor.Base::next(node);
00624         }
00625         Parent::clear();
00626       }
00627 
00628       virtual void add(const Edge& edge) {
00629         Parent::add(edge);
00630         Parent::operator[](edge).prevOut = edge;
00631       }
00632 
00633       virtual void add(const std::vector<Edge>& edges) {
00634         Parent::add(edges);
00635         for (int i = 0; i < (int)edges.size(); ++i) {
00636           Parent::operator[](edges[i]).prevOut = edges[i];
00637         }
00638       }
00639 
00640       virtual void erase(const Edge& edge) {
00641         adaptor.hide(edge);
00642         Parent::erase(edge);
00643       }
00644 
00645       virtual void erase(const std::vector<Edge>& edges) {
00646         for (int i = 0; i < (int)edges.size(); ++i) {
00647           adaptor.hide(edges[i]);
00648         }
00649         Parent::erase(edge);
00650       }
00651 
00652     private:
00653       SubGraph& adaptor;
00654     };
00655 
00656     NodesImpl* nodes;
00657     EdgesImpl* edges;
00658   };
00659 
00675   template <typename Graph>
00676   class EdgeSubGraph 
00677     : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
00678   public:
00679     typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
00680   public:
00685     EdgeSubGraph(const Graph& _graph) 
00686       : Parent(), nodes(*this, _graph), edges(*this, _graph) { 
00687       Parent::construct(_graph, nodes, edges);
00688     }
00689   private:
00690     typename Parent::NodesImpl nodes;
00691     typename Parent::EdgesImpl edges;
00692   };
00693 
00694 
00695 //   template<typename Graph, typename Number, 
00696 //         typename CapacityMap, typename FlowMap>
00697 //   class ResGraph
00698 //     : public IterableGraphExtender<EdgeSubGraphBase<
00699 //     UGraphAdaptor<Graph> > > {
00700 //   public:
00701 //     typedef IterableGraphExtender<EdgeSubGraphBase<
00702 //       UGraphAdaptor<Graph> > > Parent;
00703 
00704 //   protected:
00705 //     UGraphAdaptor<Graph> u;
00706 
00707 //     const CapacityMap* capacity;
00708 //     FlowMap* flow;
00709 
00710 //     typename Parent::NodesImpl nodes;
00711 //     typename Parent::EdgesImpl edges;
00712 
00713 //     void setCapacityMap(const CapacityMap& _capacity) {
00714 //       capacity=&_capacity;
00715 //     }
00716 
00717 //     void setFlowMap(FlowMap& _flow) {
00718 //       flow=&_flow;
00719 //     }
00720 
00721 //   public:
00722 
00723 //     typedef typename UGraphAdaptor<Graph>::Node Node;
00724 //     typedef typename UGraphAdaptor<Graph>::Edge Edge;
00725 //     typedef typename UGraphAdaptor<Graph>::UEdge UEdge;
00726 
00727 //     ResGraphAdaptor(Graph& _graph, 
00728 //                  const CapacityMap& _capacity, FlowMap& _flow) 
00729 //       : Parent(), u(_graph), capacity(&_capacity), flow(&_flow),
00730 //      nodes(*this, _graph), edges(*this, _graph) {
00731 //       Parent::construct(u, nodes, edges);
00732 //       setFlowMap(_flow);
00733 //       setCapacityMap(_capacity);
00734 //       typename Graph::Edge edge; 
00735 //       for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
00736 //      if ((*flow)[edge] != (*capacity)[edge]) {
00737 //        Parent::unHide(direct(edge, true));
00738 //      }
00739 //      if ((*flow)[edge] != 0) {
00740 //        Parent::unHide(direct(edge, false));
00741 //      }
00742 //       }
00743 //     }
00744 
00745 //     void augment(const Edge& e, Number a) {
00746 //       if (direction(e)) {
00747 //      flow->set(e, (*flow)[e]+a);
00748 //       } else { 
00749 //      flow->set(e, (*flow)[e]-a);
00750 //       }
00751 //       if ((*flow)[e] == (*capacity)[e]) {
00752 //      Parent::hide(e);
00753 //       } else {
00754 //      Parent::unHide(e);
00755 //       }
00756 //       if ((*flow)[e] == 0) {
00757 //      Parent::hide(oppositeEdge(e));
00758 //       } else {
00759 //      Parent::unHide(oppositeEdge(e));
00760 //       }
00761 //     }
00762 
00763 //     Number resCap(const Edge& e) {
00764 //       if (direction(e)) { 
00765 //      return (*capacity)[e]-(*flow)[e]; 
00766 //       } else { 
00767 //      return (*flow)[e];
00768 //       }
00769 //     }
00770     
00771 //     bool direction(const Edge& edge) const {
00772 //       return Parent::getGraph().direction(edge);
00773 //     }
00774 
00775 //     Edge direct(const UEdge& edge, bool direction) const {
00776 //       return Parent::getGraph().direct(edge, direction);
00777 //     }
00778 
00779 //     Edge direct(const UEdge& edge, const Node& node) const {
00780 //       return Parent::getGraph().direct(edge, node);
00781 //     }
00782 
00783 //     Edge oppositeEdge(const Edge& edge) const {
00784 //       return Parent::getGraph().oppositeEdge(edge);
00785 //     }
00786 
00787 //     /// \brief Residual capacity map.
00788 //     ///
00789 //     /// In generic residual graphs the residual capacity can be obtained 
00790 //     /// as a map. 
00791 //     class ResCap {
00792 //     protected:
00793 //       const ResGraphAdaptor* res_graph;
00794 //     public:
00795 //       typedef Number Value;
00796 //       typedef Edge Key;
00797 //       ResCap(const ResGraphAdaptor& _res_graph) 
00798 //      : res_graph(&_res_graph) {}
00799 //       Number operator[](const Edge& e) const {
00800 //      return res_graph->resCap(e);
00801 //       }
00802 //     };
00803 //   };
00804 
00805 }
00806 
00807 #endif

Generated on Fri Feb 3 18:39:45 2006 for LEMON by  doxygen 1.4.6