Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

graph_wrapper.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_GRAPH_WRAPPER_H
00018 #define LEMON_GRAPH_WRAPPER_H
00019 
00027 
00028 #include <lemon/invalid.h>
00029 #include <lemon/maps.h>
00030 #include <lemon/iterable_graph_extender.h>
00031 #include <iostream>
00032 
00033 namespace lemon {
00034 
00035   // Graph wrappers
00036 
00112   template<typename _Graph>
00113   class GraphWrapperBase {
00114   public:
00115     typedef _Graph Graph;
00117     typedef Graph BaseGraph;
00118     typedef Graph ParentGraph;
00119 
00120   protected:
00121     Graph* graph;
00122     GraphWrapperBase() : graph(0) { }
00123     void setGraph(Graph& _graph) { graph=&_graph; }
00124 
00125   public:
00126     GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
00127  
00128     typedef typename Graph::Node Node;
00129     typedef typename Graph::Edge Edge;
00130    
00131     void first(Node& i) const { graph->first(i); }
00132     void first(Edge& i) const { graph->first(i); }
00133     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
00134     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
00135 
00136     void next(Node& i) const { graph->next(i); }
00137     void next(Edge& i) const { graph->next(i); }
00138     void nextIn(Edge& i) const { graph->nextIn(i); }
00139     void nextOut(Edge& i) const { graph->nextOut(i); }
00140 
00141     Node source(const Edge& e) const { return graph->source(e); }
00142     Node target(const Edge& e) const { return graph->target(e); }
00143 
00144     int nodeNum() const { return graph->nodeNum(); }
00145     int edgeNum() const { return graph->edgeNum(); }
00146   
00147     Node addNode() const { return Node(graph->addNode()); }
00148     Edge addEdge(const Node& source, const Node& target) const { 
00149       return Edge(graph->addEdge(source, target)); }
00150 
00151     void erase(const Node& i) const { graph->erase(i); }
00152     void erase(const Edge& i) const { graph->erase(i); }
00153   
00154     void clear() const { graph->clear(); }
00155     
00156     bool forward(const Edge& e) const { return graph->forward(e); }
00157     bool backward(const Edge& e) const { return graph->backward(e); }
00158 
00159     int id(const Node& v) const { return graph->id(v); }
00160     int id(const Edge& e) const { return graph->id(e); }
00161     
00162     Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
00163 
00164     template <typename _Value>
00165     class NodeMap : public _Graph::template NodeMap<_Value> {
00166     public:
00167       typedef typename _Graph::template NodeMap<_Value> Parent;
00168       NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
00169       NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
00170       : Parent(*gw.graph, value) { }
00171     };
00172 
00173     template <typename _Value>
00174     class EdgeMap : public _Graph::template EdgeMap<_Value> {
00175     public:
00176       typedef typename _Graph::template EdgeMap<_Value> Parent;
00177       EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
00178       EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
00179       : Parent(*gw.graph, value) { }
00180     };
00181 
00182   };
00183 
00184   template <typename _Graph>
00185   class GraphWrapper :
00186     public IterableGraphExtender<GraphWrapperBase<_Graph> > { 
00187   public:
00188     typedef _Graph Graph;
00189     typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
00190   protected:
00191     GraphWrapper() : Parent() { }
00192 
00193   public:
00194     GraphWrapper(Graph& _graph) { setGraph(_graph); }
00195   };
00196 
00197   template <typename _Graph>
00198   class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
00199   public:
00200     typedef _Graph Graph;
00201     typedef GraphWrapperBase<_Graph> Parent;
00202   protected:
00203     RevGraphWrapperBase() : Parent() { }
00204   public:
00205     typedef typename Parent::Node Node;
00206     typedef typename Parent::Edge Edge;
00207 
00208     using Parent::first;
00209     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
00210     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
00211 
00212     using Parent::next;
00213     void nextIn(Edge& i) const { Parent::nextOut(i); }
00214     void nextOut(Edge& i) const { Parent::nextIn(i); }
00215 
00216     Node source(const Edge& e) const { return Parent::target(e); }
00217     Node target(const Edge& e) const { return Parent::source(e); }
00218   };
00219     
00220 
00222 
00244   template<typename _Graph>
00245   class RevGraphWrapper : 
00246     public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
00247   public:
00248     typedef _Graph Graph;
00249     typedef IterableGraphExtender<
00250       RevGraphWrapperBase<_Graph> > Parent;
00251   protected:
00252     RevGraphWrapper() { }
00253   public:
00254     RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
00255   };
00256 
00257   
00258   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
00259   class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
00260   public:
00261     typedef _Graph Graph;
00262     typedef GraphWrapperBase<_Graph> Parent;
00263   protected:
00264     NodeFilterMap* node_filter_map;
00265     EdgeFilterMap* edge_filter_map;
00266     SubGraphWrapperBase() : Parent(), 
00267                             node_filter_map(0), edge_filter_map(0) { }
00268 
00269     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
00270       node_filter_map=&_node_filter_map;
00271     }
00272     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
00273       edge_filter_map=&_edge_filter_map;
00274     }
00275 
00276   public:
00277 //     SubGraphWrapperBase(Graph& _graph, 
00278 //                      NodeFilterMap& _node_filter_map, 
00279 //                      EdgeFilterMap& _edge_filter_map) : 
00280 //       Parent(&_graph), 
00281 //       node_filter_map(&node_filter_map), 
00282 //       edge_filter_map(&edge_filter_map) { }
00283 
00284     typedef typename Parent::Node Node;
00285     typedef typename Parent::Edge Edge;
00286 
00287     void first(Node& i) const { 
00288       Parent::first(i); 
00289       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
00290     }
00291     void first(Edge& i) const { 
00292       Parent::first(i); 
00293       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
00294     }
00295     void firstIn(Edge& i, const Node& n) const { 
00296       Parent::firstIn(i, n); 
00297       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
00298     }
00299     void firstOut(Edge& i, const Node& n) const { 
00300       Parent::firstOut(i, n); 
00301       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
00302     }
00303 
00304     void next(Node& i) const { 
00305       Parent::next(i); 
00306       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
00307     }
00308     void next(Edge& i) const { 
00309       Parent::next(i); 
00310       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
00311     }
00312     void nextIn(Edge& i) const { 
00313       Parent::nextIn(i); 
00314       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
00315     }
00316     void nextOut(Edge& i) const { 
00317       Parent::nextOut(i); 
00318       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
00319     }
00320 
00324     void hide(const Node& n) const { node_filter_map->set(n, false); }
00325 
00329     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
00330 
00334      void unHide(const Node& n) const { node_filter_map->set(n, true); }
00335 
00339     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
00340 
00342     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
00343 
00345     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
00346 
00350     int nodeNum() const { 
00351       int i=0;
00352       Node n;
00353       for (first(n); n!=INVALID; next(n)) ++i;
00354       return i; 
00355     }
00356 
00360     int edgeNum() const { 
00361       int i=0;
00362       Edge e;
00363       for (first(e); e!=INVALID; next(e)) ++i;
00364       return i; 
00365     }
00366 
00367 
00368   };
00369 
00416   template<typename _Graph, typename NodeFilterMap, 
00417            typename EdgeFilterMap>
00418   class SubGraphWrapper : 
00419     public IterableGraphExtender<
00420     SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
00421   public:
00422     typedef _Graph Graph;
00423     typedef IterableGraphExtender<
00424       SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
00425   protected:
00426     SubGraphWrapper() { }
00427   public:
00428     SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map, 
00429                     EdgeFilterMap& _edge_filter_map) { 
00430       setGraph(_graph);
00431       setNodeFilterMap(_node_filter_map);
00432       setEdgeFilterMap(_edge_filter_map);
00433     }
00434   };
00435 
00436 
00437 
00449   template<typename Graph, typename NodeFilterMap>
00450   class NodeSubGraphWrapper : 
00451     public SubGraphWrapper<Graph, NodeFilterMap, 
00452                            ConstMap<typename Graph::Edge,bool> > {
00453   public:
00454     typedef SubGraphWrapper<Graph, NodeFilterMap, 
00455                             ConstMap<typename Graph::Edge,bool> > Parent;
00456   protected:
00457     ConstMap<typename Graph::Edge, bool> const_true_map;
00458   public:
00459     NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) : 
00460       Parent(), const_true_map(true) { 
00461       Parent::setGraph(_graph);
00462       Parent::setNodeFilterMap(_node_filter_map);
00463       Parent::setEdgeFilterMap(const_true_map);
00464     }
00465   };
00466 
00467 
00594   template<typename Graph, typename EdgeFilterMap>
00595   class EdgeSubGraphWrapper : 
00596     public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 
00597                            EdgeFilterMap> {
00598   public:
00599     typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 
00600                             EdgeFilterMap> Parent;
00601   protected:
00602     ConstMap<typename Graph::Node, bool> const_true_map;
00603   public:
00604     EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
00605       Parent(), const_true_map(true) { 
00606       Parent::setGraph(_graph);
00607       Parent::setNodeFilterMap(const_true_map);
00608       Parent::setEdgeFilterMap(_edge_filter_map);
00609     }
00610   };
00611 
00612 
00613   template<typename Graph>
00614   class UndirGraphWrapper : public GraphWrapper<Graph> {
00615   public:
00616     typedef GraphWrapper<Graph> Parent; 
00617   protected:
00618     UndirGraphWrapper() : GraphWrapper<Graph>() { }
00619     
00620   public:
00621     typedef typename GraphWrapper<Graph>::Node Node;
00622     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
00623     typedef typename GraphWrapper<Graph>::Edge Edge;
00624     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
00625 
00626     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
00627 
00628     class OutEdgeIt {
00629       friend class UndirGraphWrapper<Graph>;
00630       bool out_or_in; //true iff out
00631       typename Graph::OutEdgeIt out;
00632       typename Graph::InEdgeIt in;
00633     public:
00634       OutEdgeIt() { }
00635       OutEdgeIt(const Invalid& i) : Edge(i) { }
00636       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
00637         out_or_in=true; _G.graph->first(out, _n);
00638         if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
00639       } 
00640       operator Edge() const { 
00641         if (out_or_in) return Edge(out); else return Edge(in); 
00642       }
00643     };
00644 
00645     typedef OutEdgeIt InEdgeIt; 
00646 
00647     using GraphWrapper<Graph>::first;
00648     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
00649       i=OutEdgeIt(*this, p); return i;
00650     }
00651 
00652     using GraphWrapper<Graph>::next;
00653 
00654     OutEdgeIt& next(OutEdgeIt& e) const {
00655       if (e.out_or_in) {
00656         typename Graph::Node n=this->graph->source(e.out);
00657         this->graph->next(e.out);
00658         if (!this->graph->valid(e.out)) { 
00659           e.out_or_in=false; this->graph->first(e.in, n); }
00660       } else {
00661         this->graph->next(e.in);
00662       }
00663       return e;
00664     }
00665 
00666     Node aNode(const OutEdgeIt& e) const { 
00667       if (e.out_or_in) return this->graph->source(e); else 
00668         return this->graph->target(e); }
00669     Node bNode(const OutEdgeIt& e) const { 
00670       if (e.out_or_in) return this->graph->target(e); else 
00671         return this->graph->source(e); }
00672 
00673     //    KEEP_MAPS(Parent, UndirGraphWrapper);
00674 
00675   };
00676   
00677 //   /// \brief An undirected graph template.
00678 //   ///
00679 //   ///\warning Graph wrappers are in even more experimental state than the other
00680 //   ///parts of the lib. Use them at your own risk.
00681 //   ///
00682 //   /// An undirected graph template.
00683 //   /// This class works as an undirected graph and a directed graph of 
00684 //   /// class \c Graph is used for the physical storage.
00685 //   /// \ingroup graphs
00686   template<typename Graph>
00687   class UndirGraph : public UndirGraphWrapper<Graph> {
00688     typedef UndirGraphWrapper<Graph> Parent;
00689   protected:
00690     Graph gr;
00691   public:
00692     UndirGraph() : UndirGraphWrapper<Graph>() { 
00693       Parent::setGraph(gr); 
00694     }
00695 
00696     //    KEEP_MAPS(Parent, UndirGraph);
00697   };
00698 
00699   
00700   template <typename _Graph, 
00701             typename ForwardFilterMap, typename BackwardFilterMap>
00702   class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
00703   public:
00704     typedef _Graph Graph;
00705     typedef GraphWrapperBase<_Graph> Parent;
00706   protected:
00707     ForwardFilterMap* forward_filter;
00708     BackwardFilterMap* backward_filter;
00709     SubBidirGraphWrapperBase() : Parent(), 
00710                                  forward_filter(0), backward_filter(0) { }
00711 
00712     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
00713       forward_filter=&_forward_filter;
00714     }
00715     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
00716       backward_filter=&_backward_filter;
00717     }
00718 
00719   public:
00720 //     SubGraphWrapperBase(Graph& _graph, 
00721 //                      NodeFilterMap& _node_filter_map, 
00722 //                      EdgeFilterMap& _edge_filter_map) : 
00723 //       Parent(&_graph), 
00724 //       node_filter_map(&node_filter_map), 
00725 //       edge_filter_map(&edge_filter_map) { }
00726 
00727     typedef typename Parent::Node Node;
00728     typedef typename _Graph::Edge GraphEdge;
00729     template <typename T> class EdgeMap;
00734     class Edge : public _Graph::Edge {
00735       friend class SubBidirGraphWrapperBase<
00736         Graph, ForwardFilterMap, BackwardFilterMap>;
00737       template<typename T> friend class EdgeMap;
00738     protected:
00739       bool backward; //true, iff backward
00740     public:
00741       Edge() { }
00745       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
00746         _Graph::Edge(e), backward(_backward) { }
00747       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
00748       bool operator==(const Edge& v) const { 
00749         return (this->backward==v.backward && 
00750                 static_cast<typename _Graph::Edge>(*this)==
00751                 static_cast<typename _Graph::Edge>(v));
00752       } 
00753       bool operator!=(const Edge& v) const { 
00754         return (this->backward!=v.backward || 
00755                 static_cast<typename _Graph::Edge>(*this)!=
00756                 static_cast<typename _Graph::Edge>(v));
00757       }
00758     };
00759 
00760     void first(Node& i) const { 
00761       Parent::first(i); 
00762     }
00763 
00764     void first(Edge& i) const { 
00765       Parent::first(i); 
00766       i.backward=false;
00767       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00768              !(*forward_filter)[i]) Parent::next(i);
00769       if (*static_cast<GraphEdge*>(&i)==INVALID) {
00770         Parent::first(i); 
00771         i.backward=true;
00772         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00773                !(*backward_filter)[i]) Parent::next(i);
00774       }
00775     }
00776 
00777     void firstIn(Edge& i, const Node& n) const { 
00778       Parent::firstIn(i, n); 
00779       i.backward=false;
00780       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00781              !(*forward_filter)[i]) Parent::nextOut(i);
00782       if (*static_cast<GraphEdge*>(&i)==INVALID) {
00783         Parent::firstOut(i, n); 
00784         i.backward=true;
00785         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00786                !(*backward_filter)[i]) Parent::nextOut(i);
00787       }
00788     }
00789 
00790     void firstOut(Edge& i, const Node& n) const { 
00791       Parent::firstOut(i, n); 
00792       i.backward=false;
00793       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00794              !(*forward_filter)[i]) Parent::nextOut(i);
00795       if (*static_cast<GraphEdge*>(&i)==INVALID) {
00796         Parent::firstIn(i, n); 
00797         i.backward=true;
00798         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00799                !(*backward_filter)[i]) Parent::nextIn(i);
00800       }
00801     }
00802 
00803     void next(Node& i) const { 
00804       Parent::next(i); 
00805     }
00806 
00807     void next(Edge& i) const { 
00808       if (!(i.backward)) {
00809         Parent::next(i);
00810         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00811                !(*forward_filter)[i]) Parent::next(i);
00812         if (*static_cast<GraphEdge*>(&i)==INVALID) {
00813           Parent::first(i); 
00814           i.backward=true;
00815           while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00816                  !(*backward_filter)[i]) Parent::next(i);
00817         }
00818       } else {
00819         Parent::next(i);
00820         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00821                !(*backward_filter)[i]) Parent::next(i);
00822       }
00823     }
00824 
00825     void nextIn(Edge& i) const { 
00826       if (!(i.backward)) {
00827         Node n=Parent::target(i);
00828         Parent::nextIn(i);
00829         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00830                !(*forward_filter)[i]) Parent::nextIn(i);
00831         if (*static_cast<GraphEdge*>(&i)==INVALID) {
00832           Parent::firstOut(i, n); 
00833           i.backward=true;
00834           while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00835                  !(*backward_filter)[i]) Parent::nextOut(i);
00836         }
00837       } else {
00838         Parent::nextOut(i);
00839         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00840                !(*backward_filter)[i]) Parent::nextOut(i);
00841       }
00842     }
00843 
00844     void nextOut(Edge& i) const { 
00845       if (!(i.backward)) {
00846         Node n=Parent::source(i);
00847         Parent::nextOut(i);
00848         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00849                !(*forward_filter)[i]) Parent::nextOut(i);
00850         if (*static_cast<GraphEdge*>(&i)==INVALID) {
00851           Parent::firstIn(i, n); 
00852           i.backward=true;
00853           while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00854                  !(*backward_filter)[i]) Parent::nextIn(i);
00855         }
00856       } else {
00857         Parent::nextIn(i);
00858         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00859                !(*backward_filter)[i]) Parent::nextIn(i);
00860       }
00861     }
00862 
00863     Node source(Edge e) const { 
00864       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
00865     Node target(Edge e) const { 
00866       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
00867 
00869     Edge opposite(const Edge& e) const { 
00870       Edge f=e;
00871       f.backward=!f.backward;
00872       return f;
00873     }
00874 
00878     int edgeNum() const { 
00879       int i=0;
00880       Edge e;
00881       for (first(e); e!=INVALID; next(e)) ++i;
00882       return i; 
00883     }
00884 
00885     bool forward(const Edge& e) const { return !e.backward; }
00886     bool backward(const Edge& e) const { return e.backward; }
00887 
00888     template <typename T>
00892     class EdgeMap {
00893       template <typename TT> friend class EdgeMap;
00894       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
00895     public:
00896       typedef T Value;
00897       typedef Edge Key;
00898 
00899       EdgeMap(const SubBidirGraphWrapperBase<_Graph, 
00900               ForwardFilterMap, BackwardFilterMap>& g) : 
00901         forward_map(*(g.graph)), backward_map(*(g.graph)) { }
00902 
00903       EdgeMap(const SubBidirGraphWrapperBase<_Graph, 
00904               ForwardFilterMap, BackwardFilterMap>& g, T a) : 
00905         forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
00906       
00907       void set(Edge e, T a) { 
00908         if (!e.backward) 
00909           forward_map.set(e, a); 
00910         else 
00911           backward_map.set(e, a); 
00912       }
00913 
00914 //       typename _Graph::template EdgeMap<T>::ConstReference 
00915 //       operator[](Edge e) const { 
00916 //      if (!e.backward) 
00917 //        return forward_map[e]; 
00918 //      else 
00919 //        return backward_map[e]; 
00920 //       }
00921 
00922 //      typename _Graph::template EdgeMap<T>::Reference 
00923       T operator[](Edge e) const { 
00924         if (!e.backward) 
00925           return forward_map[e]; 
00926         else 
00927           return backward_map[e]; 
00928       }
00929 
00930       void update() { 
00931         forward_map.update(); 
00932         backward_map.update();
00933       }
00934     };
00935 
00936   };
00937 
00938 
00976   template<typename _Graph, 
00977            typename ForwardFilterMap, typename BackwardFilterMap>
00978   class SubBidirGraphWrapper : 
00979     public IterableGraphExtender<
00980     SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
00981   public:
00982     typedef _Graph Graph;
00983     typedef IterableGraphExtender<
00984       SubBidirGraphWrapperBase<
00985       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
00986   protected:
00987     SubBidirGraphWrapper() { }
00988   public:
00989     SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter, 
00990                          BackwardFilterMap& _backward_filter) { 
00991       setGraph(_graph);
00992       setForwardFilterMap(_forward_filter);
00993       setBackwardFilterMap(_backward_filter);
00994     }
00995   };
00996 
00997 
00998 
01008   template<typename Graph>
01009   class BidirGraphWrapper : 
01010     public SubBidirGraphWrapper<
01011     Graph, 
01012     ConstMap<typename Graph::Edge, bool>, 
01013     ConstMap<typename Graph::Edge, bool> > {
01014   public:
01015     typedef  SubBidirGraphWrapper<
01016       Graph, 
01017       ConstMap<typename Graph::Edge, bool>, 
01018       ConstMap<typename Graph::Edge, bool> > Parent; 
01019   protected:
01020     ConstMap<typename Graph::Edge, bool> cm;
01021 
01022     BidirGraphWrapper() : Parent(), cm(true) { 
01023       Parent::setForwardFilterMap(cm);
01024       Parent::setBackwardFilterMap(cm);
01025     }
01026   public:
01027     BidirGraphWrapper(Graph& _graph) : Parent() { 
01028       Parent::setGraph(_graph);
01029       Parent::setForwardFilterMap(cm);
01030       Parent::setBackwardFilterMap(cm);
01031     }
01032 
01033     int edgeNum() const { 
01034       return 2*this->graph->edgeNum();
01035     }
01036     //    KEEP_MAPS(Parent, BidirGraphWrapper);
01037   };
01038 
01039 
01040   template<typename Graph, typename Number,
01041            typename CapacityMap, typename FlowMap>
01042   class ResForwardFilter {
01043     //    const Graph* graph;
01044     const CapacityMap* capacity;
01045     const FlowMap* flow;
01046   public:
01047     ResForwardFilter(/*const Graph& _graph, */
01048                      const CapacityMap& _capacity, const FlowMap& _flow) :
01049       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
01050     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
01051     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01052     void setFlow(const FlowMap& _flow) { flow=&_flow; }
01053     bool operator[](const typename Graph::Edge& e) const {
01054       return (Number((*flow)[e]) < Number((*capacity)[e]));
01055     }
01056   };
01057 
01058   template<typename Graph, typename Number,
01059            typename CapacityMap, typename FlowMap>
01060   class ResBackwardFilter {
01061     const CapacityMap* capacity;
01062     const FlowMap* flow;
01063   public:
01064     ResBackwardFilter(/*const Graph& _graph,*/ 
01065                       const CapacityMap& _capacity, const FlowMap& _flow) :
01066       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
01067     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
01068     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01069     void setFlow(const FlowMap& _flow) { flow=&_flow; }
01070     bool operator[](const typename Graph::Edge& e) const {
01071       return (Number(0) < Number((*flow)[e]));
01072     }
01073   };
01074 
01075   
01077 
01082   template<typename Graph, typename Number, 
01083            typename CapacityMap, typename FlowMap>
01084   class ResGraphWrapper : 
01085     public SubBidirGraphWrapper< 
01086     Graph, 
01087     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
01088     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
01089   public:
01090     typedef SubBidirGraphWrapper< 
01091       Graph, 
01092       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
01093       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
01094   protected:
01095     const CapacityMap* capacity;
01096     FlowMap* flow;
01097     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
01098     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
01099     ResGraphWrapper() : Parent(), 
01100                         capacity(0), flow(0) { }
01101     void setCapacityMap(const CapacityMap& _capacity) {
01102       capacity=&_capacity;
01103       forward_filter.setCapacity(_capacity);
01104       backward_filter.setCapacity(_capacity);
01105     }
01106     void setFlowMap(FlowMap& _flow) {
01107       flow=&_flow;
01108       forward_filter.setFlow(_flow);
01109       backward_filter.setFlow(_flow);
01110     }
01111   public:
01112     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
01113                        FlowMap& _flow) : 
01114       Parent(), capacity(&_capacity), flow(&_flow), 
01115       forward_filter(/*_graph,*/ _capacity, _flow), 
01116       backward_filter(/*_graph,*/ _capacity, _flow) {
01117       Parent::setGraph(_graph);
01118       Parent::setForwardFilterMap(forward_filter);
01119       Parent::setBackwardFilterMap(backward_filter);
01120     }
01121 
01122     typedef typename Parent::Edge Edge;
01123 
01124     void augment(const Edge& e, Number a) const {
01125       if (Parent::forward(e))  
01126         flow->set(e, (*flow)[e]+a);
01127       else  
01128         flow->set(e, (*flow)[e]-a);
01129     }
01130 
01135     class ResCap {
01136     protected:
01137       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
01138     public:
01139       typedef Number Value;
01140       typedef Edge Key;
01141       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& 
01142              _res_graph) : res_graph(&_res_graph) { }
01143       Number operator[](const Edge& e) const { 
01144         if (res_graph->forward(e)) 
01145           return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
01146         else 
01147           return (*(res_graph->flow))[e]; 
01148       }
01149     };
01150 
01151     //    KEEP_MAPS(Parent, ResGraphWrapper);
01152   };
01153 
01154 
01155 
01156   template <typename _Graph, typename FirstOutEdgesMap>
01157   class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
01158   public:
01159     typedef _Graph Graph;
01160     typedef GraphWrapperBase<_Graph> Parent;
01161   protected:
01162     FirstOutEdgesMap* first_out_edges;
01163     ErasingFirstGraphWrapperBase() : Parent(), 
01164                                      first_out_edges(0) { }
01165 
01166     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
01167       first_out_edges=&_first_out_edges;
01168     }
01169 
01170   public:
01171 
01172     typedef typename Parent::Node Node;
01173     typedef typename Parent::Edge Edge;
01174 
01175     void firstOut(Edge& i, const Node& n) const { 
01176       i=(*first_out_edges)[n];
01177     }
01178 
01179     void erase(const Edge& e) const {
01180       Node n=source(e);
01181       Edge f=e;
01182       Parent::nextOut(f);
01183       first_out_edges->set(n, f);
01184     }    
01185   };
01186 
01187 
01189 
01202   template <typename _Graph, typename FirstOutEdgesMap>
01203   class ErasingFirstGraphWrapper : 
01204     public IterableGraphExtender<
01205     ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
01206   public:
01207     typedef _Graph Graph;
01208     typedef IterableGraphExtender<
01209       ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
01210     ErasingFirstGraphWrapper(Graph& _graph, 
01211                              FirstOutEdgesMap& _first_out_edges) { 
01212       setGraph(_graph);
01213       setFirstOutEdgesMap(_first_out_edges);
01214     } 
01215 
01216   };
01217 
01219 
01220 } //namespace lemon
01221 
01222 #endif //LEMON_GRAPH_WRAPPER_H
01223 

Generated on Mon Feb 21 15:02:21 2005 for LEMON by  doxygen 1.4.1