graph_adaptor.h

Go to the documentation of this file.
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_GRAPH_ADAPTOR_H
00020 #define LEMON_GRAPH_ADAPTOR_H
00021 
00029 
00030 #include <lemon/invalid.h>
00031 #include <lemon/maps.h>
00032 #include <lemon/bits/erasable_graph_extender.h>
00033 #include <lemon/bits/clearable_graph_extender.h>
00034 #include <lemon/bits/extendable_graph_extender.h>
00035 #include <lemon/bits/iterable_graph_extender.h>
00036 #include <lemon/bits/alteration_notifier.h>
00037 #include <lemon/bits/default_map.h>
00038 #include <lemon/bits/graph_extender.h>
00039 #include <iostream>
00040 
00041 namespace lemon {
00042 
00062   template<typename _Graph>
00063   class GraphAdaptorBase {
00064   public:
00065     typedef _Graph Graph;
00066     typedef Graph ParentGraph;
00067 
00068   protected:
00069     Graph* graph;
00070     GraphAdaptorBase() : graph(0) { }
00071     void setGraph(Graph& _graph) { graph=&_graph; }
00072 
00073   public:
00074     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
00075  
00076     typedef typename Graph::Node Node;
00077     typedef typename Graph::Edge Edge;
00078    
00079     void first(Node& i) const { graph->first(i); }
00080     void first(Edge& i) const { graph->first(i); }
00081     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
00082     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
00083 
00084     void next(Node& i) const { graph->next(i); }
00085     void next(Edge& i) const { graph->next(i); }
00086     void nextIn(Edge& i) const { graph->nextIn(i); }
00087     void nextOut(Edge& i) const { graph->nextOut(i); }
00088 
00089     Node source(const Edge& e) const { return graph->source(e); }
00090     Node target(const Edge& e) const { return graph->target(e); }
00091 
00092     typedef NodeNumTagIndicator<Graph> NodeNumTag;
00093     int nodeNum() const { return graph->nodeNum(); }
00094     
00095     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
00096     int edgeNum() const { return graph->edgeNum(); }
00097 
00098     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
00099     Edge findEdge(const Node& source, const Node& target, 
00100                   const Edge& prev = INVALID) {
00101       return graph->findEdge(source, target, prev);
00102     }
00103   
00104     Node addNode() const { 
00105       return Node(graph->addNode()); 
00106     }
00107 
00108     Edge addEdge(const Node& source, const Node& target) const { 
00109       return Edge(graph->addEdge(source, target)); 
00110     }
00111 
00112     void erase(const Node& i) const { graph->erase(i); }
00113     void erase(const Edge& i) const { graph->erase(i); }
00114   
00115     void clear() const { graph->clear(); }
00116     
00117     int id(const Node& v) const { return graph->id(v); }
00118     int id(const Edge& e) const { return graph->id(e); }
00119     
00120     Edge oppositeNode(const Edge& e) const { 
00121       return Edge(graph->opposite(e)); 
00122     }
00123 
00124     template <typename _Value>
00125     class NodeMap : public _Graph::template NodeMap<_Value> {
00126     public:
00127       typedef typename _Graph::template NodeMap<_Value> Parent;
00128       explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) 
00129         : Parent(*gw.graph) { }
00130       NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
00131         : Parent(*gw.graph, value) { }
00132     };
00133 
00134     template <typename _Value>
00135     class EdgeMap : public _Graph::template EdgeMap<_Value> {
00136     public:
00137       typedef typename _Graph::template EdgeMap<_Value> Parent;
00138       explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw) 
00139         : Parent(*gw.graph) { }
00140       EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
00141         : Parent(*gw.graph, value) { }
00142     };
00143 
00144   };
00145 
00146   template <typename _Graph>
00147   class GraphAdaptor :
00148     public IterableGraphExtender<GraphAdaptorBase<_Graph> > { 
00149   public:
00150     typedef _Graph Graph;
00151     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
00152   protected:
00153     GraphAdaptor() : Parent() { }
00154 
00155   public:
00156     explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
00157   };
00158 
00159   template <typename _Graph>
00160   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
00161   public:
00162     typedef _Graph Graph;
00163     typedef GraphAdaptorBase<_Graph> Parent;
00164   protected:
00165     RevGraphAdaptorBase() : Parent() { }
00166   public:
00167     typedef typename Parent::Node Node;
00168     typedef typename Parent::Edge Edge;
00169 
00170     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
00171     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
00172 
00173     void nextIn(Edge& i) const { Parent::nextOut(i); }
00174     void nextOut(Edge& i) const { Parent::nextIn(i); }
00175 
00176     Node source(const Edge& e) const { return Parent::target(e); }
00177     Node target(const Edge& e) const { return Parent::source(e); }
00178   };
00179     
00180 
00198 
00199   template<typename _Graph>
00200   class RevGraphAdaptor : 
00201     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
00202   public:
00203     typedef _Graph Graph;
00204     typedef IterableGraphExtender<
00205       RevGraphAdaptorBase<_Graph> > Parent;
00206   protected:
00207     RevGraphAdaptor() { }
00208   public:
00209     explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
00210   };
00211 
00212   
00213   template <typename _Graph, typename NodeFilterMap, 
00214             typename EdgeFilterMap, bool checked = true>
00215   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
00216   public:
00217     typedef _Graph Graph;
00218     typedef GraphAdaptorBase<_Graph> Parent;
00219   protected:
00220     NodeFilterMap* node_filter_map;
00221     EdgeFilterMap* edge_filter_map;
00222     SubGraphAdaptorBase() : Parent(), 
00223                             node_filter_map(0), edge_filter_map(0) { }
00224 
00225     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
00226       node_filter_map=&_node_filter_map;
00227     }
00228     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
00229       edge_filter_map=&_edge_filter_map;
00230     }
00231 
00232   public:
00233 
00234     typedef typename Parent::Node Node;
00235     typedef typename Parent::Edge Edge;
00236 
00237     void first(Node& i) const { 
00238       Parent::first(i); 
00239       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
00240     }
00241 
00242     void first(Edge& i) const { 
00243       Parent::first(i); 
00244       while (i!=INVALID && (!(*edge_filter_map)[i] 
00245              || !(*node_filter_map)[Parent::source(i)]
00246              || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
00247     }
00248 
00249     void firstIn(Edge& i, const Node& n) const { 
00250       Parent::firstIn(i, n); 
00251       while (i!=INVALID && (!(*edge_filter_map)[i] 
00252              || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
00253     }
00254 
00255     void firstOut(Edge& i, const Node& n) const { 
00256       Parent::firstOut(i, n); 
00257       while (i!=INVALID && (!(*edge_filter_map)[i] 
00258              || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
00259     }
00260 
00261     void next(Node& i) const { 
00262       Parent::next(i); 
00263       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
00264     }
00265 
00266     void next(Edge& i) const { 
00267       Parent::next(i); 
00268       while (i!=INVALID && (!(*edge_filter_map)[i] 
00269              || !(*node_filter_map)[Parent::source(i)]
00270              || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
00271     }
00272 
00273     void nextIn(Edge& i) const { 
00274       Parent::nextIn(i); 
00275       while (i!=INVALID && (!(*edge_filter_map)[i] 
00276              || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
00277     }
00278 
00279     void nextOut(Edge& i) const { 
00280       Parent::nextOut(i); 
00281       while (i!=INVALID && (!(*edge_filter_map)[i] 
00282              || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
00283     }
00284 
00286 
00290     void hide(const Node& n) const { node_filter_map->set(n, false); }
00291 
00293 
00297     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
00298 
00300 
00304      void unHide(const Node& n) const { node_filter_map->set(n, true); }
00305 
00307 
00311     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
00312 
00314     
00317     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
00318 
00320     
00323     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
00324 
00325     typedef False NodeNumTag;
00326     typedef False EdgeNumTag;
00327   };
00328 
00329   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
00330   class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 
00331     : public GraphAdaptorBase<_Graph> {
00332   public:
00333     typedef _Graph Graph;
00334     typedef GraphAdaptorBase<_Graph> Parent;
00335   protected:
00336     NodeFilterMap* node_filter_map;
00337     EdgeFilterMap* edge_filter_map;
00338     SubGraphAdaptorBase() : Parent(), 
00339                             node_filter_map(0), edge_filter_map(0) { }
00340 
00341     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
00342       node_filter_map=&_node_filter_map;
00343     }
00344     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
00345       edge_filter_map=&_edge_filter_map;
00346     }
00347 
00348   public:
00349 
00350     typedef typename Parent::Node Node;
00351     typedef typename Parent::Edge Edge;
00352 
00353     void first(Node& i) const { 
00354       Parent::first(i); 
00355       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
00356     }
00357 
00358     void first(Edge& i) const { 
00359       Parent::first(i); 
00360       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
00361     }
00362 
00363     void firstIn(Edge& i, const Node& n) const { 
00364       Parent::firstIn(i, n); 
00365       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
00366     }
00367 
00368     void firstOut(Edge& i, const Node& n) const { 
00369       Parent::firstOut(i, n); 
00370       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
00371     }
00372 
00373     void next(Node& i) const { 
00374       Parent::next(i); 
00375       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
00376     }
00377     void next(Edge& i) const { 
00378       Parent::next(i); 
00379       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
00380     }
00381     void nextIn(Edge& i) const { 
00382       Parent::nextIn(i); 
00383       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
00384     }
00385 
00386     void nextOut(Edge& i) const { 
00387       Parent::nextOut(i); 
00388       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
00389     }
00390 
00392 
00396     void hide(const Node& n) const { node_filter_map->set(n, false); }
00397 
00399 
00403     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
00404 
00406 
00410      void unHide(const Node& n) const { node_filter_map->set(n, true); }
00411 
00413 
00417     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
00418 
00420     
00423     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
00424 
00426     
00429     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
00430 
00431     typedef False NodeNumTag;
00432     typedef False EdgeNumTag;
00433   };
00434 
00495 
00496   template<typename _Graph, typename NodeFilterMap, 
00497            typename EdgeFilterMap, bool checked = true>
00498   class SubGraphAdaptor : 
00499     public IterableGraphExtender<
00500     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
00501   public:
00502     typedef _Graph Graph;
00503     typedef IterableGraphExtender<
00504       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
00505   protected:
00506     SubGraphAdaptor() { }
00507   public:
00508     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, 
00509                     EdgeFilterMap& _edge_filter_map) { 
00510       setGraph(_graph);
00511       setNodeFilterMap(_node_filter_map);
00512       setEdgeFilterMap(_edge_filter_map);
00513     }
00514   };
00515 
00516 
00517 
00532   template<typename Graph, typename NodeFilterMap, bool checked = true>
00533   class NodeSubGraphAdaptor : 
00534     public SubGraphAdaptor<Graph, NodeFilterMap, 
00535                            ConstMap<typename Graph::Edge,bool>, checked> {
00536   public:
00537     typedef SubGraphAdaptor<Graph, NodeFilterMap, 
00538                             ConstMap<typename Graph::Edge,bool> > Parent;
00539   protected:
00540     ConstMap<typename Graph::Edge, bool> const_true_map;
00541   public:
00542     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
00543       Parent(), const_true_map(true) { 
00544       Parent::setGraph(_graph);
00545       Parent::setNodeFilterMap(_node_filter_map);
00546       Parent::setEdgeFilterMap(const_true_map);
00547     }
00548   };
00549 
00550 
00687   template<typename Graph, typename EdgeFilterMap>
00688   class EdgeSubGraphAdaptor : 
00689     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
00690                            EdgeFilterMap, false> {
00691   public:
00692     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
00693                             EdgeFilterMap, false> Parent;
00694   protected:
00695     ConstMap<typename Graph::Node, bool> const_true_map;
00696   public:
00697     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
00698       Parent(), const_true_map(true) { 
00699       Parent::setGraph(_graph);
00700       Parent::setNodeFilterMap(const_true_map);
00701       Parent::setEdgeFilterMap(_edge_filter_map);
00702     }
00703   };
00704 
00705   template <typename _Graph>
00706   class UGraphAdaptorBase : 
00707     public UGraphExtender<GraphAdaptorBase<_Graph> > {
00708   public:
00709     typedef _Graph Graph;
00710     typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;
00711   protected:
00712     UGraphAdaptorBase() : Parent() { }
00713   public:
00714     typedef typename Parent::UEdge UEdge;
00715     typedef typename Parent::Edge Edge;
00716     
00717     template <typename T>
00718     class EdgeMap {
00719     protected:
00720       const UGraphAdaptorBase<_Graph>* g;
00721       template <typename TT> friend class EdgeMap;
00722       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
00723     public:
00724       typedef T Value;
00725       typedef Edge Key;
00726       
00727       EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g), 
00728         forward_map(*(g->graph)), backward_map(*(g->graph)) { }
00729 
00730       EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
00731         forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
00732       
00733       void set(Edge e, T a) { 
00734         if (g->direction(e)) 
00735           forward_map.set(e, a); 
00736         else 
00737           backward_map.set(e, a); 
00738       }
00739 
00740       T operator[](Edge e) const { 
00741         if (g->direction(e)) 
00742           return forward_map[e]; 
00743         else 
00744           return backward_map[e]; 
00745       }
00746     };
00747         
00748     template <typename T>
00749     class UEdgeMap {
00750       template <typename TT> friend class UEdgeMap;
00751       typename _Graph::template EdgeMap<T> map; 
00752     public:
00753       typedef T Value;
00754       typedef UEdge Key;
00755       
00756       UEdgeMap(const UGraphAdaptorBase<_Graph>& g) : 
00757         map(*(g.graph)) { }
00758 
00759       UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) : 
00760         map(*(g.graph), a) { }
00761       
00762       void set(UEdge e, T a) { 
00763         map.set(e, a); 
00764       }
00765 
00766       T operator[](UEdge e) const { 
00767         return map[e]; 
00768       }
00769     };
00770       
00771   };
00772 
00780   template<typename _Graph>
00781   class UGraphAdaptor : 
00782     public IterableUGraphExtender<
00783     UGraphAdaptorBase<_Graph> > {
00784   public:
00785     typedef _Graph Graph;
00786     typedef IterableUGraphExtender<
00787       UGraphAdaptorBase<_Graph> > Parent;
00788   protected:
00789     UGraphAdaptor() { }
00790   public:
00791     UGraphAdaptor(_Graph& _graph) { 
00792       setGraph(_graph);
00793     }
00794   };
00795 
00796   
00797   template <typename _Graph, 
00798             typename ForwardFilterMap, typename BackwardFilterMap>
00799   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
00800   public:
00801     typedef _Graph Graph;
00802     typedef GraphAdaptorBase<_Graph> Parent;
00803   protected:
00804     ForwardFilterMap* forward_filter;
00805     BackwardFilterMap* backward_filter;
00806     SubBidirGraphAdaptorBase() : Parent(), 
00807                                  forward_filter(0), backward_filter(0) { }
00808 
00809     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
00810       forward_filter=&_forward_filter;
00811     }
00812     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
00813       backward_filter=&_backward_filter;
00814     }
00815 
00816   public:
00817 //     SubGraphAdaptorBase(Graph& _graph, 
00818 //                      NodeFilterMap& _node_filter_map, 
00819 //                      EdgeFilterMap& _edge_filter_map) : 
00820 //       Parent(&_graph), 
00821 //       node_filter_map(&node_filter_map), 
00822 //       edge_filter_map(&edge_filter_map) { }
00823 
00824     typedef typename Parent::Node Node;
00825     typedef typename _Graph::Edge GraphEdge;
00826     template <typename T> class EdgeMap;
00827     // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 
00828     // _Graph::Edge. It contains an extra bool flag which is true 
00829     // if and only if the 
00830     // edge is the backward version of the original edge.
00831     class Edge : public _Graph::Edge {
00832       friend class SubBidirGraphAdaptorBase<
00833         Graph, ForwardFilterMap, BackwardFilterMap>;
00834       template<typename T> friend class EdgeMap;
00835     protected:
00836       bool backward; //true, iff backward
00837     public:
00838       Edge() { }
00839       // \todo =false is needed, or causes problems?
00840       // If \c _backward is false, then we get an edge corresponding to the 
00841       // original one, otherwise its oppositely directed pair is obtained.
00842       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
00843         _Graph::Edge(e), backward(_backward) { }
00844       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
00845       bool operator==(const Edge& v) const { 
00846         return (this->backward==v.backward && 
00847                 static_cast<typename _Graph::Edge>(*this)==
00848                 static_cast<typename _Graph::Edge>(v));
00849       } 
00850       bool operator!=(const Edge& v) const { 
00851         return (this->backward!=v.backward || 
00852                 static_cast<typename _Graph::Edge>(*this)!=
00853                 static_cast<typename _Graph::Edge>(v));
00854       }
00855     };
00856 
00857     void first(Node& i) const { 
00858       Parent::first(i); 
00859     }
00860 
00861     void first(Edge& i) const { 
00862       Parent::first(i); 
00863       i.backward=false;
00864       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00865              !(*forward_filter)[i]) Parent::next(i);
00866       if (*static_cast<GraphEdge*>(&i)==INVALID) {
00867         Parent::first(i); 
00868         i.backward=true;
00869         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00870                !(*backward_filter)[i]) Parent::next(i);
00871       }
00872     }
00873 
00874     void firstIn(Edge& i, const Node& n) const { 
00875       Parent::firstIn(i, n); 
00876       i.backward=false;
00877       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00878              !(*forward_filter)[i]) Parent::nextIn(i);
00879       if (*static_cast<GraphEdge*>(&i)==INVALID) {
00880         Parent::firstOut(i, n); 
00881         i.backward=true;
00882         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00883                !(*backward_filter)[i]) Parent::nextOut(i);
00884       }
00885     }
00886 
00887     void firstOut(Edge& i, const Node& n) const { 
00888       Parent::firstOut(i, n); 
00889       i.backward=false;
00890       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00891              !(*forward_filter)[i]) Parent::nextOut(i);
00892       if (*static_cast<GraphEdge*>(&i)==INVALID) {
00893         Parent::firstIn(i, n); 
00894         i.backward=true;
00895         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00896                !(*backward_filter)[i]) Parent::nextIn(i);
00897       }
00898     }
00899 
00900     void next(Node& i) const { 
00901       Parent::next(i); 
00902     }
00903 
00904     void next(Edge& i) const { 
00905       if (!(i.backward)) {
00906         Parent::next(i);
00907         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00908                !(*forward_filter)[i]) Parent::next(i);
00909         if (*static_cast<GraphEdge*>(&i)==INVALID) {
00910           Parent::first(i); 
00911           i.backward=true;
00912           while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00913                  !(*backward_filter)[i]) Parent::next(i);
00914         }
00915       } else {
00916         Parent::next(i);
00917         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00918                !(*backward_filter)[i]) Parent::next(i);
00919       }
00920     }
00921 
00922     void nextIn(Edge& i) const { 
00923       if (!(i.backward)) {
00924         Node n=Parent::target(i);
00925         Parent::nextIn(i);
00926         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00927                !(*forward_filter)[i]) Parent::nextIn(i);
00928         if (*static_cast<GraphEdge*>(&i)==INVALID) {
00929           Parent::firstOut(i, n); 
00930           i.backward=true;
00931           while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00932                  !(*backward_filter)[i]) Parent::nextOut(i);
00933         }
00934       } else {
00935         Parent::nextOut(i);
00936         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00937                !(*backward_filter)[i]) Parent::nextOut(i);
00938       }
00939     }
00940 
00941     void nextOut(Edge& i) const { 
00942       if (!(i.backward)) {
00943         Node n=Parent::source(i);
00944         Parent::nextOut(i);
00945         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00946                !(*forward_filter)[i]) Parent::nextOut(i);
00947         if (*static_cast<GraphEdge*>(&i)==INVALID) {
00948           Parent::firstIn(i, n); 
00949           i.backward=true;
00950           while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00951                  !(*backward_filter)[i]) Parent::nextIn(i);
00952         }
00953       } else {
00954         Parent::nextIn(i);
00955         while (*static_cast<GraphEdge*>(&i)!=INVALID && 
00956                !(*backward_filter)[i]) Parent::nextIn(i);
00957       }
00958     }
00959 
00960     Node source(Edge e) const { 
00961       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
00962     Node target(Edge e) const { 
00963       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
00964 
00966 
00969     Edge opposite(const Edge& e) const { 
00970       Edge f=e;
00971       f.backward=!f.backward;
00972       return f;
00973     }
00974 
00976 
00980     int edgeNum() const { 
00981       int i=0;
00982       Edge e;
00983       for (first(e); e!=INVALID; next(e)) ++i;
00984       return i; 
00985     }
00986 
00987     bool forward(const Edge& e) const { return !e.backward; }
00988     bool backward(const Edge& e) const { return e.backward; }
00989 
00991 
00995     template <typename T>
00996     class EdgeMap {
00997       template <typename TT> friend class EdgeMap;
00998       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
00999     public:
01000       typedef T Value;
01001       typedef Edge Key;
01002 
01003       EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
01004               ForwardFilterMap, BackwardFilterMap>& g) : 
01005         forward_map(*(g.graph)), backward_map(*(g.graph)) { }
01006 
01007       EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
01008               ForwardFilterMap, BackwardFilterMap>& g, T a) : 
01009         forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
01010       
01011       void set(Edge e, T a) { 
01012         if (!e.backward) 
01013           forward_map.set(e, a); 
01014         else 
01015           backward_map.set(e, a); 
01016       }
01017 
01018 //       typename _Graph::template EdgeMap<T>::ConstReference 
01019 //       operator[](Edge e) const { 
01020 //      if (!e.backward) 
01021 //        return forward_map[e]; 
01022 //      else 
01023 //        return backward_map[e]; 
01024 //       }
01025 
01026 //      typename _Graph::template EdgeMap<T>::Reference 
01027       T operator[](Edge e) const { 
01028         if (!e.backward) 
01029           return forward_map[e]; 
01030         else 
01031           return backward_map[e]; 
01032       }
01033 
01034       void update() { 
01035         forward_map.update(); 
01036         backward_map.update();
01037       }
01038     };
01039 
01040   };
01041 
01042 
01083   template<typename _Graph, 
01084            typename ForwardFilterMap, typename BackwardFilterMap>
01085   class SubBidirGraphAdaptor : 
01086     public IterableGraphExtender<
01087     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
01088   public:
01089     typedef _Graph Graph;
01090     typedef IterableGraphExtender<
01091       SubBidirGraphAdaptorBase<
01092       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
01093   protected:
01094     SubBidirGraphAdaptor() { }
01095   public:
01096     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, 
01097                          BackwardFilterMap& _backward_filter) { 
01098       setGraph(_graph);
01099       setForwardFilterMap(_forward_filter);
01100       setBackwardFilterMap(_backward_filter);
01101     }
01102   };
01103 
01104 
01105 
01117   template<typename Graph>
01118   class BidirGraphAdaptor : 
01119     public SubBidirGraphAdaptor<
01120     Graph, 
01121     ConstMap<typename Graph::Edge, bool>, 
01122     ConstMap<typename Graph::Edge, bool> > {
01123   public:
01124     typedef  SubBidirGraphAdaptor<
01125       Graph, 
01126       ConstMap<typename Graph::Edge, bool>, 
01127       ConstMap<typename Graph::Edge, bool> > Parent; 
01128   protected:
01129     ConstMap<typename Graph::Edge, bool> cm;
01130 
01131     BidirGraphAdaptor() : Parent(), cm(true) { 
01132       Parent::setForwardFilterMap(cm);
01133       Parent::setBackwardFilterMap(cm);
01134     }
01135   public:
01136     BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 
01137       Parent::setGraph(_graph);
01138       Parent::setForwardFilterMap(cm);
01139       Parent::setBackwardFilterMap(cm);
01140     }
01141 
01142     int edgeNum() const { 
01143       return 2*this->graph->edgeNum();
01144     }
01145   };
01146 
01147 
01148   template<typename Graph, typename Number,
01149            typename CapacityMap, typename FlowMap>
01150   class ResForwardFilter {
01151     //    const Graph* graph;
01152     const CapacityMap* capacity;
01153     const FlowMap* flow;
01154   public:
01155     ResForwardFilter(/*const Graph& _graph, */
01156                      const CapacityMap& _capacity, const FlowMap& _flow) :
01157       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
01158     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
01159     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01160     void setFlow(const FlowMap& _flow) { flow=&_flow; }
01161     bool operator[](const typename Graph::Edge& e) const {
01162       return (Number((*flow)[e]) < Number((*capacity)[e]));
01163     }
01164   };
01165 
01166   template<typename Graph, typename Number,
01167            typename CapacityMap, typename FlowMap>
01168   class ResBackwardFilter {
01169     const CapacityMap* capacity;
01170     const FlowMap* flow;
01171   public:
01172     ResBackwardFilter(/*const Graph& _graph,*/ 
01173                       const CapacityMap& _capacity, const FlowMap& _flow) :
01174       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
01175     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
01176     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01177     void setFlow(const FlowMap& _flow) { flow=&_flow; }
01178     bool operator[](const typename Graph::Edge& e) const {
01179       return (Number(0) < Number((*flow)[e]));
01180     }
01181   };
01182 
01183   
01219   template<typename Graph, typename Number, 
01220            typename CapacityMap, typename FlowMap>
01221   class ResGraphAdaptor : 
01222     public SubBidirGraphAdaptor< 
01223     Graph, 
01224     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
01225     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
01226   public:
01227     typedef SubBidirGraphAdaptor< 
01228       Graph, 
01229       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
01230       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
01231   protected:
01232     const CapacityMap* capacity;
01233     FlowMap* flow;
01234     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
01235     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
01236     ResGraphAdaptor() : Parent(), 
01237                         capacity(0), flow(0) { }
01238     void setCapacityMap(const CapacityMap& _capacity) {
01239       capacity=&_capacity;
01240       forward_filter.setCapacity(_capacity);
01241       backward_filter.setCapacity(_capacity);
01242     }
01243     void setFlowMap(FlowMap& _flow) {
01244       flow=&_flow;
01245       forward_filter.setFlow(_flow);
01246       backward_filter.setFlow(_flow);
01247     }
01248   public:
01249     ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity, 
01250                        FlowMap& _flow) : 
01251       Parent(), capacity(&_capacity), flow(&_flow), 
01252       forward_filter(/*_graph,*/ _capacity, _flow), 
01253       backward_filter(/*_graph,*/ _capacity, _flow) {
01254       Parent::setGraph(_graph);
01255       Parent::setForwardFilterMap(forward_filter);
01256       Parent::setBackwardFilterMap(backward_filter);
01257     }
01258 
01259     typedef typename Parent::Edge Edge;
01260 
01261     void augment(const Edge& e, Number a) const {
01262       if (Parent::forward(e))  
01263         flow->set(e, (*flow)[e]+a);
01264       else  
01265         flow->set(e, (*flow)[e]-a);
01266     }
01267 
01272     class ResCap {
01273     protected:
01274       const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
01275     public:
01276       typedef Number Value;
01277       typedef Edge Key;
01278       ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>& 
01279              _res_graph) : res_graph(&_res_graph) { }
01280       Number operator[](const Edge& e) const { 
01281         if (res_graph->forward(e)) 
01282           return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
01283         else 
01284           return (*(res_graph->flow))[e]; 
01285       }
01286     };
01287 
01288     //    KEEP_MAPS(Parent, ResGraphAdaptor);
01289   };
01290 
01291 
01292 
01293   template <typename _Graph, typename FirstOutEdgesMap>
01294   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
01295   public:
01296     typedef _Graph Graph;
01297     typedef GraphAdaptorBase<_Graph> Parent;
01298   protected:
01299     FirstOutEdgesMap* first_out_edges;
01300     ErasingFirstGraphAdaptorBase() : Parent(), 
01301                                      first_out_edges(0) { }
01302 
01303     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
01304       first_out_edges=&_first_out_edges;
01305     }
01306 
01307   public:
01308 
01309     typedef typename Parent::Node Node;
01310     typedef typename Parent::Edge Edge;
01311 
01312     void firstOut(Edge& i, const Node& n) const { 
01313       i=(*first_out_edges)[n];
01314     }
01315 
01316     void erase(const Edge& e) const {
01317       Node n=source(e);
01318       Edge f=e;
01319       Parent::nextOut(f);
01320       first_out_edges->set(n, f);
01321     }    
01322   };
01323 
01324 
01342   template <typename _Graph, typename FirstOutEdgesMap>
01343   class ErasingFirstGraphAdaptor : 
01344     public IterableGraphExtender<
01345     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
01346   public:
01347     typedef _Graph Graph;
01348     typedef IterableGraphExtender<
01349       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
01350     ErasingFirstGraphAdaptor(Graph& _graph, 
01351                              FirstOutEdgesMap& _first_out_edges) { 
01352       setGraph(_graph);
01353       setFirstOutEdgesMap(_first_out_edges);
01354     } 
01355 
01356   };
01357 
01358   template <typename _Graph>
01359   class SplitGraphAdaptorBase 
01360     : public GraphAdaptorBase<_Graph> {
01361   public:
01362     typedef GraphAdaptorBase<_Graph> Parent;
01363 
01364     class Node;
01365     class Edge;
01366     template <typename T> class NodeMap;
01367     template <typename T> class EdgeMap;
01368     
01369 
01370     class Node : public Parent::Node {
01371       friend class SplitGraphAdaptorBase;
01372       template <typename T> friend class NodeMap;
01373       typedef typename Parent::Node NodeParent;
01374     private:
01375 
01376       bool entry;
01377       Node(typename Parent::Node _node, bool _entry)
01378         : Parent::Node(_node), entry(_entry) {}
01379       
01380     public:
01381       Node() {}
01382       Node(Invalid) : NodeParent(INVALID), entry(true) {}
01383 
01384       bool operator==(const Node& node) const {
01385         return NodeParent::operator==(node) && entry == node.entry;
01386       }
01387       
01388       bool operator!=(const Node& node) const {
01389         return !(*this == node);
01390       }
01391       
01392       bool operator<(const Node& node) const {
01393         return NodeParent::operator<(node) || 
01394           (NodeParent::operator==(node) && entry < node.entry);
01395       }
01396     };
01397 
01399     class Edge : public Parent::Edge {
01400       friend class SplitGraphAdaptorBase;
01401       template <typename T> friend class EdgeMap;
01402     private:
01403       typedef typename Parent::Edge EdgeParent;
01404       typedef typename Parent::Node NodeParent;
01405       NodeParent bind;
01406 
01407       Edge(const EdgeParent& edge, const NodeParent& node)
01408         : EdgeParent(edge), bind(node) {}
01409     public:
01410       Edge() {}
01411       Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
01412 
01413       bool operator==(const Edge& edge) const {
01414         return EdgeParent::operator==(edge) && bind == edge.bind;
01415       }
01416       
01417       bool operator!=(const Edge& edge) const {
01418         return !(*this == edge);
01419       }
01420       
01421       bool operator<(const Edge& edge) const {
01422         return EdgeParent::operator<(edge) || 
01423           (EdgeParent::operator==(edge) && bind < edge.bind);
01424       }
01425     };
01426 
01427     void first(Node& node) const {
01428       Parent::first(node);
01429       node.entry = true;
01430     } 
01431 
01432     void next(Node& node) const {
01433       if (node.entry) {
01434         node.entry = false;
01435       } else {
01436         node.entry = true;
01437         Parent::next(node);
01438       }
01439     }
01440 
01441     void first(Edge& edge) const {
01442       Parent::first(edge);
01443       if ((typename Parent::Edge&)edge == INVALID) {
01444         Parent::first(edge.bind);
01445       } else {
01446         edge.bind = INVALID;
01447       }
01448     }
01449 
01450     void next(Edge& edge) const {
01451       if ((typename Parent::Edge&)edge != INVALID) {
01452         Parent::next(edge);
01453         if ((typename Parent::Edge&)edge == INVALID) {
01454           Parent::first(edge.bind);
01455         }
01456       } else {
01457         Parent::next(edge.bind);
01458       }      
01459     }
01460 
01461     void firstIn(Edge& edge, const Node& node) const {
01462       if (node.entry) {
01463         Parent::firstIn(edge, node);
01464         edge.bind = INVALID;
01465       } else {
01466         (typename Parent::Edge&)edge = INVALID;
01467         edge.bind = node;
01468       }
01469     }
01470 
01471     void nextIn(Edge& edge) const {
01472       if ((typename Parent::Edge&)edge != INVALID) {
01473         Parent::nextIn(edge);
01474       } else {
01475         edge.bind = INVALID;
01476       }      
01477     }
01478 
01479     void firstOut(Edge& edge, const Node& node) const {
01480       if (!node.entry) {
01481         Parent::firstOut(edge, node);
01482         edge.bind = INVALID;
01483       } else {
01484         (typename Parent::Edge&)edge = INVALID;
01485         edge.bind = node;
01486       }
01487     }
01488 
01489     void nextOut(Edge& edge) const {
01490       if ((typename Parent::Edge&)edge != INVALID) {
01491         Parent::nextOut(edge);
01492       } else {
01493         edge.bind = INVALID;
01494       }
01495     }
01496 
01497     Node source(const Edge& edge) const {
01498       if ((typename Parent::Edge&)edge != INVALID) {
01499         return Node(Parent::source(edge), false);
01500       } else {
01501         return Node(edge.bind, true);
01502       }
01503     }
01504 
01505     Node target(const Edge& edge) const {
01506       if ((typename Parent::Edge&)edge != INVALID) {
01507         return Node(Parent::target(edge), true);
01508       } else {
01509         return Node(edge.bind, false);
01510       }
01511     }
01512 
01513     static bool entryNode(const Node& node) {
01514       return node.entry;
01515     }
01516 
01517     static bool exitNode(const Node& node) {
01518       return !node.entry;
01519     }
01520 
01521     static Node getEntry(const typename Parent::Node& node) {
01522       return Node(node, true);
01523     }
01524 
01525     static Node getExit(const typename Parent::Node& node) {
01526       return Node(node, false);
01527     }
01528 
01529     static bool originalEdge(const Edge& edge) {
01530       return (typename Parent::Edge&)edge != INVALID;
01531     }
01532 
01533     static bool bindingEdge(const Edge& edge) {
01534       return edge.bind != INVALID;
01535     }
01536 
01537     static Node getBindedNode(const Edge& edge) {
01538       return edge.bind;
01539     }
01540 
01541     int nodeNum() const {
01542       return Parent::nodeNum() * 2;
01543     }
01544 
01545     typedef CompileTimeAnd<typename Parent::NodeNumTag, 
01546                            typename Parent::EdgeNumTag> EdgeNumTag;
01547     
01548     int edgeNum() const {
01549       return Parent::edgeNum() + Parent::nodeNum();
01550     }
01551 
01552     Edge findEdge(const Node& source, const Node& target, 
01553                   const Edge& prev = INVALID) const {
01554       if (exitNode(source) && entryNode(target)) {
01555         return Parent::findEdge(source, target, prev);
01556       } else {
01557         if (prev == INVALID && entryNode(source) && exitNode(target) && 
01558             (typename Parent::Node&)source == (typename Parent::Node&)target) {
01559           return Edge(INVALID, source);
01560         } else {
01561           return INVALID;
01562         }
01563       }
01564     }
01565     
01566     template <typename T>
01567     class NodeMap : public MapBase<Node, T> {
01568       typedef typename Parent::template NodeMap<T> NodeImpl;
01569     public:
01570       NodeMap(const SplitGraphAdaptorBase& _graph) 
01571         : entry(_graph), exit(_graph) {}
01572       NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
01573         : entry(_graph, t), exit(_graph, t) {}
01574       
01575       void set(const Node& key, const T& val) {
01576         if (key.entry) { entry.set(key, val); }
01577         else {exit.set(key, val); }
01578       }
01579       
01580       typename MapTraits<NodeImpl>::ReturnValue 
01581       operator[](const Node& key) {
01582         if (key.entry) { return entry[key]; }
01583         else { return exit[key]; }
01584       }
01585 
01586       typename MapTraits<NodeImpl>::ConstReturnValue
01587       operator[](const Node& key) const {
01588         if (key.entry) { return entry[key]; }
01589         else { return exit[key]; }
01590       }
01591 
01592     private:
01593       NodeImpl entry, exit;
01594     };
01595 
01596     template <typename T>
01597     class EdgeMap : public MapBase<Edge, T> {
01598       typedef typename Parent::template NodeMap<T> NodeImpl;
01599       typedef typename Parent::template EdgeMap<T> EdgeImpl;
01600     public:
01601       EdgeMap(const SplitGraphAdaptorBase& _graph) 
01602         : bind(_graph), orig(_graph) {}
01603       EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
01604         : bind(_graph, t), orig(_graph, t) {}
01605       
01606       void set(const Edge& key, const T& val) {
01607         if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
01608         else {bind.set(key.bind, val); }
01609       }
01610       
01611       typename MapTraits<EdgeImpl>::ReturnValue
01612       operator[](const Edge& key) {
01613         if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
01614         else {return bind[key.bind]; }
01615       }
01616 
01617       typename MapTraits<EdgeImpl>::ConstReturnValue
01618       operator[](const Edge& key) const {
01619         if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
01620         else {return bind[key.bind]; }
01621       }
01622 
01623     private:
01624       typename Parent::template NodeMap<T> bind;
01625       typename Parent::template EdgeMap<T> orig;
01626     };
01627 
01628     template <typename EntryMap, typename ExitMap>
01629     class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
01630     public:
01631       typedef MapBase<Node, typename EntryMap::Value> Parent;
01632 
01633       typedef typename Parent::Key Key;
01634       typedef typename Parent::Value Value;
01635 
01636       CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 
01637         : entryMap(_entryMap), exitMap(_exitMap) {}
01638 
01639       Value& operator[](const Key& key) {
01640         if (key.entry) {
01641           return entryMap[key];
01642         } else {
01643           return exitMap[key];
01644         }
01645       }
01646 
01647       Value operator[](const Key& key) const {
01648         if (key.entry) {
01649           return entryMap[key];
01650         } else {
01651           return exitMap[key];
01652         }
01653       }
01654 
01655       void set(const Key& key, const Value& value) {
01656         if (key.entry) {
01657           entryMap.set(key, value);
01658         } else {
01659           exitMap.set(key, value);
01660         }
01661       }
01662       
01663     private:
01664       
01665       EntryMap& entryMap;
01666       ExitMap& exitMap;
01667       
01668     };
01669 
01670     template <typename EdgeMap, typename NodeMap>
01671     class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
01672     public:
01673       typedef MapBase<Edge, typename EdgeMap::Value> Parent;
01674 
01675       typedef typename Parent::Key Key;
01676       typedef typename Parent::Value Value;
01677 
01678       CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 
01679         : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
01680 
01681       void set(const Edge& edge, const Value& val) {
01682         if (SplitGraphAdaptorBase::originalEdge(edge)) {
01683           edgeMap.set(edge, val);
01684         } else {
01685           nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
01686         }
01687       }
01688 
01689       Value operator[](const Key& edge) const {
01690         if (SplitGraphAdaptorBase::originalEdge(edge)) {
01691           return edgeMap[edge];
01692         } else {
01693           return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
01694         }
01695       }      
01696 
01697       Value& operator[](const Key& edge) {
01698         if (SplitGraphAdaptorBase::originalEdge(edge)) {
01699           return edgeMap[edge];
01700         } else {
01701           return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
01702         }
01703       }      
01704       
01705     private:
01706       EdgeMap& edgeMap;
01707       NodeMap& nodeMap;
01708     };
01709 
01710   };
01711 
01712   template <typename _Graph>
01713   class SplitGraphAdaptor 
01714     : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
01715   public:
01716     typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
01717 
01718     SplitGraphAdaptor(_Graph& graph) {
01719       Parent::setGraph(graph);
01720     }
01721 
01722 
01723   };
01724 
01725 } //namespace lemon
01726 
01727 #endif //LEMON_GRAPH_ADAPTOR_H
01728 

Generated on Fri Feb 3 18:37:04 2006 for LEMON by  doxygen 1.4.6