lemon-0.x: src/work/marci/experiment/graph

     1 // -*- c++ -*-

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_GRAPH_WRAPPER_H

     5 #include <invalid.h>

     7 namespace hugo {

     9   template<typename Graph>

    10   class TrivGraphWrapper {

    11   protected:

    12     Graph* graph;

    14   public:

    15     typedef Graph BaseGraph;

    17     typedef typename Graph::Node Node;

    18     class NodeIt : public Graph::NodeIt {

    19     public:

    20       NodeIt() { }

    21       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

    22       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

    23       NodeIt(const TrivGraphWrapper<Graph>& _G) :

    24 	Graph::NodeIt(*(_G.graph)) { }

    25     };

    26     typedef typename Graph::Edge Edge;

    27     //typedef typename Graph::OutEdgeIt OutEdgeIt;

    28     class OutEdgeIt : public Graph::OutEdgeIt {

    29     public:

    30       OutEdgeIt() { }

    31       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

    32       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

    33       OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :

    34 	Graph::OutEdgeIt(*(_G.graph), n) { }

    35     };

    36     //typedef typename Graph::InEdgeIt InEdgeIt;

    37     class InEdgeIt : public Graph::InEdgeIt {

    38     public:

    39       InEdgeIt() { }

    40       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

    41       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

    42       InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :

    43 	Graph::InEdgeIt(*(_G.graph), n) { }

    44     };

    45     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    46     //typedef typename Graph::EdgeIt EdgeIt;

    47     class EdgeIt : public Graph::EdgeIt {

    48     public:

    49       EdgeIt() { }

    50       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

    51       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

    52       EdgeIt(const TrivGraphWrapper<Graph>& _G) :

    53 	Graph::EdgeIt(*(_G.graph)) { }

    54     };

    56     //TrivGraphWrapper() : graph(0) { }

    57     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }

    59 //    void setGraph(Graph& _graph) { graph = &_graph; }

    60 //    Graph& getGraph() const { return (*graph); }

    62     NodeIt& first(NodeIt& i) const {

    63       i=NodeIt(*this);

    64       return i;

    65     }

    66     EdgeIt& first(EdgeIt& i) const {

    67       i=EdgeIt(*this);

    68       return i;

    69     }

    70 //     template<typename I> I& first(I& i) const {

    71 //       //return graph->first(i);

    72 //       i=I(*this);

    73 //       return i;

    74 //     }

    75     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

    76       i=OutEdgeIt(*this, p);

    77       return i;

    78     }

    79     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

    80       i=InEdgeIt(*this, p);

    81       return i;

    82     }

    83 //     template<typename I, typename P> I& first(I& i, const P& p) const {

    84 //       //return graph->first(i, p);

    85 //       i=I(*this, p);

    86 //       return i;

    87 //     }

    89 //    template<typename I> I getNext(const I& i) const {

    90 //      return graph->getNext(i); }

    91     template<typename I> I& next(I &i) const { graph->next(i); return i; }

    93     template< typename It > It first() const {

    94       It e; first(e); return e; }

    96     template< typename It > It first(const Node& v) const {

    97       It e; first(e, v); return e; }

    99     Node head(const Edge& e) const { return graph->head(e); }

   100     Node tail(const Edge& e) const { return graph->tail(e); }

   102     template<typename I> bool valid(const I& i) const

   103       { return graph->valid(i); }

   105     //template<typename I> void setInvalid(const I &i);

   106     //{ return graph->setInvalid(i); }

   108     int nodeNum() const { return graph->nodeNum(); }

   109     int edgeNum() const { return graph->edgeNum(); }

   111     template<typename I> Node aNode(const I& e) const {

   112       return graph->aNode(e); }

   113     template<typename I> Node bNode(const I& e) const {

   114       return graph->bNode(e); }

   116     Node addNode() const { return graph->addNode(); }

   117     Edge addEdge(const Node& tail, const Node& head) const {

   118       return graph->addEdge(tail, head); }

   120     template<typename I> void erase(const I& i) const { graph->erase(i); }

   122     void clear() const { graph->clear(); }

   124     template<typename T> class NodeMap : public Graph::NodeMap<T> {

   125     public:

   126       NodeMap(const TrivGraphWrapper<Graph>& _G) :

   127 	Graph::NodeMap<T>(*(_G.graph)) { }

   128       NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :

   129 	Graph::NodeMap<T>(*(_G.graph), a) { }

   130     };

   132     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   133     public:

   134       EdgeMap(const TrivGraphWrapper<Graph>& _G) :

   135 	Graph::EdgeMap<T>(*(_G.graph)) { }

   136       EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :

   137 	Graph::EdgeMap<T>(*(_G.graph), a) { }

   138     };

   140     template<typename Map, typename T> class NodeMapWrapper {

   141     protected:

   142       Map* map;

   143     public:

   144       NodeMapWrapper(Map& _map) : map(&_map) { }

   145       //template<typename T>

   146       void set(Node n, T a) { map->set(n, a); }

   147       //template<typename T>

   148       T get(Node n) const { return map->get(n); }

   149     };

   151     template<typename Map, typename T> class EdgeMapWrapper {

   152     protected:

   153       Map* map;

   154     public:

   155       EdgeMapWrapper(Map& _map) : map(&_map) { }

   156       //template<typename T>

   157       void set(Edge n, T a) { map->set(n, a); }

   158       //template<typename T>

   159       T get(Edge n) const { return map->get(n); }

   160     };

   161   };

   163   template<typename GraphWrapper>

   164   class GraphWrapperSkeleton {

   165   protected:

   166     GraphWrapper gw;

   168   public:

   169     //typedef typename GraphWrapper::BaseGraph BaseGraph;

   171 //     typedef typename GraphWrapper::Node Node;

   172 //     typedef typename GraphWrapper::NodeIt NodeIt;

   174 //     typedef typename GraphWrapper::Edge Edge;

   175 //     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   176 //     typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   177 //     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

   178 //     typedef typename GraphWrapper::EdgeIt EdgeIt;

   180     typedef typename GraphWrapper::Node Node;

   181     class NodeIt : public GraphWrapper::NodeIt {

   182     public:

   183       NodeIt() { }

   184       NodeIt(const typename GraphWrapper::NodeIt& n) :

   185 	GraphWrapper::NodeIt(n) { }

   186       NodeIt(const Invalid& i) : GraphWrapper::NodeIt(i) { }

   187       NodeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   188 	GraphWrapper::NodeIt(_G.gw) { }

   189     };

   190     typedef typename GraphWrapper::Edge Edge;

   191     //typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;

   192     class OutEdgeIt : public GraphWrapper::OutEdgeIt {

   193     public:

   194       OutEdgeIt() { }

   195       OutEdgeIt(const typename GraphWrapper::OutEdgeIt& e) :

   196 	GraphWrapper::OutEdgeIt(e) { }

   197       OutEdgeIt(const Invalid& i) : GraphWrapper::OutEdgeIt(i) { }

   198       OutEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :

   199 	GraphWrapper::OutEdgeIt(_G.gw, n) { }

   200     };

   201     //typedef typename GraphWrapper::InEdgeIt InEdgeIt;

   202     class InEdgeIt : public GraphWrapper::InEdgeIt {

   203     public:

   204       InEdgeIt() { }

   205       InEdgeIt(const typename GraphWrapper::InEdgeIt& e) :

   206 	GraphWrapper::InEdgeIt(e) { }

   207       InEdgeIt(const Invalid& i) : GraphWrapper::InEdgeIt(i) { }

   208       InEdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G, const Node& n) :

   209 	GraphWrapper::InEdgeIt(_G.gw, n) { }

   210     };

   211     //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;

   212     //typedef typename GraphWrapper::EdgeIt EdgeIt;

   213     class EdgeIt : public GraphWrapper::EdgeIt {

   214     public:

   215       EdgeIt() { }

   216       EdgeIt(const typename GraphWrapper::EdgeIt& e) :

   217 	GraphWrapper::EdgeIt(e) { }

   218       EdgeIt(const Invalid& i) : GraphWrapper::EdgeIt(i) { }

   219       EdgeIt(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   220 	GraphWrapper::EdgeIt(_G.gw) { }

   221     };

   224     //GraphWrapperSkeleton() : gw() { }

   225     GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { }

   227     //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }

   228     //BaseGraph& getGraph() const { return gw.getGraph(); }

   230     template<typename I> I& first(I& i) const {

   231       i=I(*this);

   232       return i;

   233     }

   234     template<typename I, typename P> I& first(I& i, const P& p) const {

   235       i=I(*this, p);

   236       return i;

   237     }

   239 //    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }

   240     template<typename I> I& next(I &i) const { gw.next(i); return i; }

   242     template< typename It > It first() const {

   243       It e; this->first(e); return e; }

   245     template< typename It > It first(const Node& v) const {

   246       It e; this->first(e, v); return e; }

   248     Node head(const Edge& e) const { return gw.head(e); }

   249     Node tail(const Edge& e) const { return gw.tail(e); }

   251     template<typename I> bool valid(const I& i) const { return gw.valid(i); }

   253     //template<typename I> void setInvalid(const I &i);

   254     //{ return graph->setInvalid(i); }

   256     int nodeNum() const { return gw.nodeNum(); }

   257     int edgeNum() const { return gw.edgeNum(); }

   259     template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }

   260     template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }

   262     Node addNode() const { return gw.addNode(); }

   263     Edge addEdge(const Node& tail, const Node& head) const {

   264       return gw.addEdge(tail, head); }

   266     template<typename I> void erase(const I& i) const { gw.erase(i); }

   268     void clear() const { gw.clear(); }

   270     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

   271     public:

   272       NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   273 	GraphWrapper::NodeMap<T>(_G.gw) { }

   274       NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :

   275 	GraphWrapper::NodeMap<T>(_G.gw, a) { }

   276     };

   278     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {

   279     public:

   280       EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :

   281 	GraphWrapper::EdgeMap<T>(_G.gw) { }

   282       EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :

   283 	GraphWrapper::EdgeMap<T>(_G.gw, a) { }

   284     };

   285   };

   287 //   template<typename Graph>

   288 //   class RevGraphWrapper

   289 //   {

   290 //   protected:

   291 //     Graph* graph;

   293 //   public:

   294 //     typedef Graph BaseGraph;

   296 //     typedef typename Graph::Node Node;

   297 //     typedef typename Graph::NodeIt NodeIt;

   299 //     typedef typename Graph::Edge Edge;

   300 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   301 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   302 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   303 //     typedef typename Graph::EdgeIt EdgeIt;

   305 //     //RevGraphWrapper() : graph(0) { }

   306 //     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }

   308 //     void setGraph(Graph& _graph) { graph = &_graph; }

   309 //     Graph& getGraph() const { return (*graph); }

   311 //     template<typename I> I& first(I& i) const { return graph->first(i); }

   312 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   313 //       return graph->first(i, p); }

   315 //     template<typename I> I getNext(const I& i) const {

   316 //       return graph->getNext(i); }

   317 //     template<typename I> I& next(I &i) const { return graph->next(i); }

   319 //     template< typename It > It first() const {

   320 //       It e; first(e); return e; }

   322 //     template< typename It > It first(const Node& v) const {

   323 //       It e; first(e, v); return e; }

   325 //     Node head(const Edge& e) const { return graph->tail(e); }

   326 //     Node tail(const Edge& e) const { return graph->head(e); }

   328 //     template<typename I> bool valid(const I& i) const

   329 //       { return graph->valid(i); }

   331 //     //template<typename I> void setInvalid(const I &i);

   332 //     //{ return graph->setInvalid(i); }

   334 //     template<typename I> Node aNode(const I& e) const {

   335 //       return graph->aNode(e); }

   336 //     template<typename I> Node bNode(const I& e) const {

   337 //       return graph->bNode(e); }

   339 //     Node addNode() const { return graph->addNode(); }

   340 //     Edge addEdge(const Node& tail, const Node& head) const {

   341 //       return graph->addEdge(tail, head); }

   343 //     int nodeNum() const { return graph->nodeNum(); }

   344 //     int edgeNum() const { return graph->edgeNum(); }

   346 //     template<typename I> void erase(const I& i) const { graph->erase(i); }

   348 //     void clear() const { graph->clear(); }

   350 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {

   351 //     public:

   352 //       NodeMap(const RevGraphWrapper<Graph>& _G) :

   353 // 	Graph::NodeMap<T>(_G.getGraph()) { }

   354 //       NodeMap(const RevGraphWrapper<Graph>& _G, T a) :

   355 // 	Graph::NodeMap<T>(_G.getGraph(), a) { }

   356 //     };

   358 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {

   359 //     public:

   360 //       EdgeMap(const RevGraphWrapper<Graph>& _G) :

   361 // 	Graph::EdgeMap<T>(_G.getGraph()) { }

   362 //       EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :

   363 // 	Graph::EdgeMap<T>(_G.getGraph(), a) { }

   364 //     };

   365 //   };

   367 //   template<typename /*Graph*/GraphWrapper

   368 //   /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ >

   369 //   class RevGraphWrapper :

   370 //     public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ {

   371 //   protected:

   372 //     //Graph* graph;

   374 //   public:

   375 //     //typedef Graph BaseGraph;

   377 //     //typedef typename Graph::Node Node;

   378 //     //typedef typename Graph::NodeIt NodeIt;

   380 //     //typedef typename Graph::Edge Edge;

   381 //     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt;

   382 //     typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt;

   383 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   384 //     //typedef typename Graph::EdgeIt EdgeIt;

   386 //     //RevGraphWrapper() : graph(0) { }

   387 //     RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { }

   389 //     //void setGraph(Graph& _graph) { graph = &_graph; }

   390 //     //Graph& getGraph() const { return (*graph); }

   392 //     //template<typename I> I& first(I& i) const { return graph->first(i); }

   393 //     //template<typename I, typename P> I& first(I& i, const P& p) const {

   394 //     //  return graph->first(i, p); }

   396 //     //template<typename I> I getNext(const I& i) const {

   397 //     //  return graph->getNext(i); }

   398 //     //template<typename I> I& next(I &i) const { return graph->next(i); }

   400 //     //template< typename It > It first() const {

   401 //     //  It e; first(e); return e; }

   403 //     //template< typename It > It first(const Node& v) const {

   404 //     //  It e; first(e, v); return e; }

   406 //     //Node head(const Edge& e) const { return graph->tail(e); }

   407 //     //Node tail(const Edge& e) const { return graph->head(e); }

   409 //     //template<typename I> bool valid(const I& i) const

   410 //     //  { return graph->valid(i); }

   412 //     //template<typename I> void setInvalid(const I &i);

   413 //     //{ return graph->setInvalid(i); }

   415 //     //template<typename I> Node aNode(const I& e) const {

   416 //     //  return graph->aNode(e); }

   417 //     //template<typename I> Node bNode(const I& e) const {

   418 //     //  return graph->bNode(e); }

   420 //     //Node addNode() const { return graph->addNode(); }

   421 //     //Edge addEdge(const Node& tail, const Node& head) const {

   422 //     //  return graph->addEdge(tail, head); }

   424 //     //int nodeNum() const { return graph->nodeNum(); }

   425 //     //int edgeNum() const { return graph->edgeNum(); }

   427 //     //template<typename I> void erase(const I& i) const { graph->erase(i); }

   429 //     //void clear() const { graph->clear(); }

   431 //     template<typename T> class NodeMap :

   432 //       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>

   433 //     {

   434 //     public:

   435 //       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) :

   436 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { }

   437 //       NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :

   438 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { }

   439 //     };

   441 //     template<typename T> class EdgeMap :

   442 //       public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> {

   443 //     public:

   444 //       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) :

   445 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { }

   446 //       EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) :

   447 // 	GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { }

   448 //     };

   449 //   };

   451   template<typename GraphWrapper>

   452   class RevGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   453   public:

   454     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   455     typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;

   456     //FIXME

   457     //If GraphWrapper::OutEdgeIt is not defined

   458     //and we do not want to use RevGraphWrapper::InEdgeIt,

   459     //this won't work, because of typedef

   460     //OR

   461     //graphs have to define their non-existing iterators to void

   462     //Unfortunately all the typedefs are instantiated in templates,

   463     //unlike other stuff

   464     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt InEdgeIt;

   465     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;

   467     RevGraphWrapper(GraphWrapper _gw) :

   468       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

   470     Node head(const Edge& e) const

   471       { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }

   472     Node tail(const Edge& e) const

   473       { return GraphWrapperSkeleton<GraphWrapper>::head(e); }

   474   };

   476   //Subgraph on the same node-set and partial edge-set

   477   template<typename GraphWrapper, typename EdgeFilterMap>

   478   class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   479   protected:

   480     EdgeFilterMap* filter_map;

   481   public:

   482     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   483     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

   484     typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;

   485     typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;

   486     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;

   487     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;

   489     SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) :

   490       GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { }

   492     template<typename I> I& first(I& i) const {

   493       gw.first(i);

   494       while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

   495       return i;

   496     }

   497     template<typename I, typename P> I& first(I& i, const P& p) const {

   498       gw.first(i, p);

   499       while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

   500       return i;

   501     }

   503     //template<typename I> I getNext(const I& i) const {

   504     //  return gw.getNext(i);

   505     //}

   506     template<typename I> I& next(I &i) const {

   507       gw.next(i);

   508       while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

   509       return i;

   510     }

   512     template< typename It > It first() const {

   513       It e; this->first(e); return e; }

   515     template< typename It > It first(const Node& v) const {

   516       It e; this->first(e, v); return e; }

   517   };

   519 //   template<typename GraphWrapper>

   520 //   class UndirGraphWrapper {

   521 //   protected:

   522 //     //Graph* graph;

   523 //     GraphWrapper gw;

   525 //   public:

   526 //     typedef GraphWrapper BaseGraph;

   528 //     typedef typename GraphWrapper::Node Node;

   529 //     typedef typename GraphWrapper::NodeIt NodeIt;

   531 //     //typedef typename Graph::Edge Edge;

   532 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   533 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   534 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   535 //     //typedef typename Graph::EdgeIt EdgeIt;

   537 //     //private:

   538 //     typedef typename GraphWrapper::Edge GraphEdge;

   539 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   540 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   541 //     //public:

   543 //     //UndirGraphWrapper() : graph(0) { }

   544 //     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }

   546 //     //void setGraph(Graph& _graph) { graph = &_graph; }

   547 //     //Graph& getGraph() const { return (*graph); }

   549 //     class Edge {

   550 //       friend class UndirGraphWrapper<GraphWrapper>;

   551 //       bool out_or_in; //true iff out

   552 //       GraphOutEdgeIt out;

   553 //       GraphInEdgeIt in;

   554 //     public:

   555 //       Edge() : out_or_in(), out(), in() { }

   556 //       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

   557 //       operator GraphEdge() const {

   558 // 	if (out_or_in) return(out); else return(in);

   559 //       }

   560 //       friend bool operator==(const Edge& u, const Edge& v) {

   561 // 	if (v.out_or_in)

   562 // 	  return (u.out_or_in && u.out==v.out);

   563 // 	else

   564 // 	  return (!u.out_or_in && u.in==v.in);

   565 //       }

   566 //       friend bool operator!=(const Edge& u, const Edge& v) {

   567 // 	if (v.out_or_in)

   568 // 	  return (!u.out_or_in || u.out!=v.out);

   569 // 	else

   570 // 	  return (u.out_or_in || u.in!=v.in);

   571 //       }

   572 //     };

   574 //     class OutEdgeIt : public Edge {

   575 //       friend class UndirGraphWrapper<GraphWrapper>;

   576 //     public:

   577 //       OutEdgeIt() : Edge() { }

   578 //       OutEdgeIt(const Invalid& i) : Edge(i) { }

   579 //       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)

   580 // 	: Edge() {

   581 // 	out_or_in=true;

   582 // 	_G.gw.first(out, n);

   583 // 	if (!(_G.gw.valid(out))) {

   584 // 	  out_or_in=false;

   585 // 	  _G.gw.first(in, n);

   586 // 	}

   587 //       }

   588 //     };

   590 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

   591 //       e.out_or_in=true;

   592 //       gw.first(e.out, n);

   593 //       if (!(gw.valid(e.out))) {

   594 // 	e.out_or_in=false;

   595 // 	gw.first(e.in, n);

   596 //       }

   597 //       return e;

   598 //     }

   600 //     OutEdgeIt& next(OutEdgeIt& e) const {

   601 //       if (e.out_or_in) {

   602 // 	Node n=gw.tail(e.out);

   603 // 	gw.next(e.out);

   604 // 	if (!gw.valid(e.out)) {

   605 // 	  e.out_or_in=false;

   606 // 	  gw.first(e.in, n);

   607 // 	}

   608 //       } else {

   609 // 	gw.next(e.in);

   610 //       }

   611 //       return e;

   612 //     }

   614 //     Node aNode(const OutEdgeIt& e) const {

   615 //       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }

   616 //     Node bNode(const OutEdgeIt& e) const {

   617 //       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }

   619 //     typedef OutEdgeIt InEdgeIt;

   621 //     template<typename I> I& first(I& i) const { return gw.first(i); }

   622 // //     template<typename I, typename P> I& first(I& i, const P& p) const {

   623 // //       return graph->first(i, p); }

   625 //     template<typename I> I getNext(const I& i) const {

   626 //       return gw.getNext(i); }

   627 //     template<typename I> I& next(I &i) const { return gw.next(i); }

   629 //     template< typename It > It first() const {

   630 //       It e; first(e); return e; }

   632 //     template< typename It > It first(const Node& v) const {

   633 //       It e; first(e, v); return e; }

   635 //     Node head(const Edge& e) const { return gw.head(e); }

   636 //     Node tail(const Edge& e) const { return gw.tail(e); }

   638 //     template<typename I> bool valid(const I& i) const

   639 //       { return gw.valid(i); }

   641 //     //template<typename I> void setInvalid(const I &i);

   642 //     //{ return graph->setInvalid(i); }

   644 //     int nodeNum() const { return gw.nodeNum(); }

   645 //     int edgeNum() const { return gw.edgeNum(); }

   647 // //     template<typename I> Node aNode(const I& e) const {

   648 // //       return graph->aNode(e); }

   649 // //     template<typename I> Node bNode(const I& e) const {

   650 // //       return graph->bNode(e); }

   652 //     Node addNode() const { return gw.addNode(); }

   653 // // FIXME: ez igy nem jo, mert nem

   654 // //    Edge addEdge(const Node& tail, const Node& head) const {

   655 // //      return graph->addEdge(tail, head); }

   657 //     template<typename I> void erase(const I& i) const { gw.erase(i); }

   659 //     void clear() const { gw.clear(); }

   661 //     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

   662 //     public:

   663 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   664 // 	GraphWrapper::NodeMap<T>(_G.gw) { }

   665 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   666 // 	GraphWrapper::NodeMap<T>(_G.gw, a) { }

   667 //     };

   669 //     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {

   670 //     public:

   671 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   672 // 	GraphWrapper::EdgeMap<T>(_G.gw) { }

   673 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   674 // 	GraphWrapper::EdgeMap<T>(_G.gw, a) { }

   675 //     };

   676 //   };

   679   template<typename GraphWrapper>

   680   class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

   681   protected:

   682 //    GraphWrapper gw;

   684   public:

   685     //typedef GraphWrapper BaseGraph;

   687     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   688     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

   690     //private:

   691     //FIXME ezeknek valojaban a GraphWrapper megfelelo dolgai kellene hogy

   692     //legyenek, at kell irni

   693     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   694     GraphWrapper::Edge GraphEdge;

   695     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   696     GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   697     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   698     GraphWrapper::InEdgeIt GraphInEdgeIt;

   699     //public:

   701     //UndirGraphWrapper() : graph(0) { }

   702     UndirGraphWrapper(GraphWrapper _gw) :

   703       GraphWrapperSkeleton<GraphWrapper>(_gw) { }

   705     //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }

   707     //void setGraph(Graph& _graph) { graph = &_graph; }

   708     //Graph& getGraph() const { return (*graph); }

   710     class Edge {

   711       friend class UndirGraphWrapper<GraphWrapper>;

   712     protected:

   713       bool out_or_in; //true iff out

   714       GraphOutEdgeIt out;

   715       GraphInEdgeIt in;

   716     public:

   717       Edge() : out_or_in(), out(), in() { }

   718       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

   719       operator GraphEdge() const {

   720 	if (out_or_in) return(out); else return(in);

   721       }

   722 //FIXME

   723 //2 edges are equal if they "refer" to the same physical edge

   724 //is it good?

   725       friend bool operator==(const Edge& u, const Edge& v) {

   726 	if (v.out_or_in)

   727 	  if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);

   728 	//return (u.out_or_in && u.out==v.out);

   729 	else

   730 	  if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);

   731 	//return (!u.out_or_in && u.in==v.in);

   732       }

   733       friend bool operator!=(const Edge& u, const Edge& v) {

   734 	if (v.out_or_in)

   735 	  if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);

   736 	//return (!u.out_or_in || u.out!=v.out);

   737 	else

   738 	  if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);

   739 	//return (u.out_or_in || u.in!=v.in);

   740       }

   741     };

   743     class OutEdgeIt : public Edge {

   744       friend class UndirGraphWrapper<GraphWrapper>;

   745     public:

   746       OutEdgeIt() : Edge() { }

   747       OutEdgeIt(const Invalid& i) : Edge(i) { }

   748       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)

   749 	: Edge() {

   750 	out_or_in=true; _G.gw.first(out, n);

   751 	if (!(_G.gw.valid(out))) { out_or_in=false; _G.gw.first(in, n);	}

   752       }

   753     };

   755     typedef OutEdgeIt InEdgeIt;

   757     class EdgeIt : public Edge {

   758       friend class UndirGraphWrapper<GraphWrapper>;

   759     protected:

   760       NodeIt v;

   761     public:

   762       EdgeIt() : Edge() { }

   763       EdgeIt(const Invalid& i) : Edge(i) { }

   764       EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)

   765 	: Edge() {

   766 	out_or_in=true;

   767 	//Node v;

   768 	_G.first(v);

   769 	if (_G.valid(v)) _G.gw.first(out); else out=INVALID;

   770 	while (_G.valid(v) && !_G.gw.valid(out)) {

   771 	  _G.gw.next(v);

   772 	  if (_G.valid(v)) _G.gw.first(out);

   773 	}

   774       }

   775     };

   777     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

   778       e.out_or_in=true; gw.first(e.out, n);

   779       if (!(gw.valid(e.out))) { e.out_or_in=false; gw.first(e.in, n); }

   780       return e;

   781     }

   783     EdgeIt& first(EdgeIt& e) const {

   784       e.out_or_in=true;

   785       //NodeIt v;

   786       first(e.v);

   787       if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;

   788       while (valid(e.v) && !gw.valid(e.out)) {

   789 	gw.next(e.v);

   790 	if (valid(e.v)) gw.first(e.out, e.v);

   791       }

   792       return e;

   793     }

   795     template<typename I> I& first(I& i) const { gw.first(i); return i; }

   796     template<typename I, typename P> I& first(I& i, const P& p) const {

   797       gw.first(i, p); return i; }

   799     OutEdgeIt& next(OutEdgeIt& e) const {

   800       if (e.out_or_in) {

   801 	Node n=gw.tail(e.out);

   802 	gw.next(e.out);

   803 	if (!gw.valid(e.out)) { e.out_or_in=false; gw.first(e.in, n); }

   804       } else {

   805 	gw.next(e.in);

   806       }

   807       return e;

   808     }

   810     EdgeIt& next(EdgeIt& e) const {

   811       //NodeIt v=tail(e);

   812       gw.next(e.out);

   813       while (valid(e.v) && !gw.valid(e.out)) {

   814 	next(e.v);

   815 	if (valid(e.v)) gw.first(e.out, e.v);

   816       }

   817       return e;

   818     }

   820     template<typename I> I& next(I &i) const { return gw.next(i); }

   821 //    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }

   823     template< typename It > It first() const {

   824       It e; first(e); return e; }

   826     template< typename It > It first(const Node& v) const {

   827       It e; first(e, v); return e; }

   829 //    Node head(const Edge& e) const { return gw.head(e); }

   830 //    Node tail(const Edge& e) const { return gw.tail(e); }

   832 //    template<typename I> bool valid(const I& i) const

   833 //      { return gw.valid(i); }

   835 //    int nodeNum() const { return gw.nodeNum(); }

   836 //    int edgeNum() const { return gw.edgeNum(); }

   838 //     template<typename I> Node aNode(const I& e) const {

   839 //       return graph->aNode(e); }

   840 //     template<typename I> Node bNode(const I& e) const {

   841 //       return graph->bNode(e); }

   843     Node aNode(const OutEdgeIt& e) const {

   844       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }

   845     Node bNode(const OutEdgeIt& e) const {

   846       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }

   848 //    Node addNode() const { return gw.addNode(); }

   850 // FIXME: ez igy nem jo, mert nem

   851 //    Edge addEdge(const Node& tail, const Node& head) const {

   852 //      return graph->addEdge(tail, head); }

   854 //    template<typename I> void erase(const I& i) const { gw.erase(i); }

   856 //    void clear() const { gw.clear(); }

   858 //     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

   859 //     public:

   860 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   861 // 	GraphWrapper::NodeMap<T>(_G.gw) { }

   862 //       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   863 // 	GraphWrapper::NodeMap<T>(_G.gw, a) { }

   864 //     };

   866 //     template<typename T> class EdgeMap :

   867 //       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {

   868 //     public:

   869 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :

   870 // 	GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }

   871 //       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :

   872 // 	GraphWrapper::EdgeMap<T>(_G.gw, a) { }

   873 //     };

   874    };

   880 //   template<typename Graph>

   881 //   class SymGraphWrapper

   882 //   {

   883 //     Graph* graph;

   885 //   public:

   886 //     typedef Graph BaseGraph;

   888 //     typedef typename Graph::Node Node;

   889 //     typedef typename Graph::Edge Edge;

   891 //     typedef typename Graph::NodeIt NodeIt;

   893 //     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon

   894 //     //iranyitatlant, ami van

   895 //     //mert csak 1 dolgot lehet be typedef-elni

   896 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

   897 //     //typedef typename Graph::InEdgeIt SymEdgeIt;

   898 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   899 //     typedef typename Graph::EdgeIt EdgeIt;

   901 //     int nodeNum() const { return graph->nodeNum(); }

   902 //     int edgeNum() const { return graph->edgeNum(); }

   904 //     template<typename I> I& first(I& i) const { return graph->first(i); }

   905 //     template<typename I, typename P> I& first(I& i, const P& p) const {

   906 //       return graph->first(i, p); }

   907 //     //template<typename I> I next(const I i); { return graph->goNext(i); }

   908 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }

   910 //     template< typename It > It first() const {

   911 //       It e; first(e); return e; }

   913 //     template< typename It > It first(Node v) const {

   914 //       It e; first(e, v); return e; }

   916 //     Node head(const Edge& e) const { return graph->head(e); }

   917 //     Node tail(const Edge& e) const { return graph->tail(e); }

   919 //     template<typename I> Node aNode(const I& e) const {

   920 //       return graph->aNode(e); }

   921 //     template<typename I> Node bNode(const I& e) const {

   922 //       return graph->bNode(e); }

   924 //     //template<typename I> bool valid(const I i);

   925 //     //{ return graph->valid(i); }

   927 //     //template<typename I> void setInvalid(const I &i);

   928 //     //{ return graph->setInvalid(i); }

   930 //     Node addNode() { return graph->addNode(); }

   931 //     Edge addEdge(const Node& tail, const Node& head) {

   932 //       return graph->addEdge(tail, head); }

   934 //     template<typename I> void erase(const I& i) { graph->erase(i); }

   936 //     void clear() { graph->clear(); }

   938 //     template<typename T> class NodeMap : public Graph::NodeMap<T> { };

   939 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };

   941 //     void setGraph(Graph& _graph) { graph = &_graph; }

   942 //     Graph& getGraph() { return (*graph); }

   944 //     //SymGraphWrapper() : graph(0) { }

   945 //     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }

   946 //   };

   949   template<typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>

   950   class ResGraphWrapper : public GraphWrapperSkeleton<GraphWrapper>{

   951   public:

   952     //typedef Graph BaseGraph;

   953     //typedef TrivGraphWrapper<const Graph> GraphWrapper;

   954     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

   955     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

   956   private:

   957     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   958     GraphWrapper::OutEdgeIt OldOutEdgeIt;

   959     typedef typename /*GraphWrapperSkeleton<GraphWrapper>*/

   960     GraphWrapper::InEdgeIt OldInEdgeIt;

   961   protected:

   962     //const Graph* graph;

   963     //GraphWrapper gw;

   964     FlowMap* flow;

   965     const CapacityMap* capacity;

   966   public:

   968     ResGraphWrapper(const GraphWrapper& _gw, FlowMap& _flow,

   969 		    const CapacityMap& _capacity) :

   970       GraphWrapperSkeleton<GraphWrapper>(_gw),

   971       flow(&_flow), capacity(&_capacity) { }

   973     //void setGraph(const Graph& _graph) { graph = &_graph; }

   974     //const Graph& getGraph() const { return (*graph); }

   976     class Edge;

   977     class OutEdgeIt;

   978     friend class Edge;

   979     friend class OutEdgeIt;

   981     class Edge {

   982       friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;

   983     protected:

   984       bool out_or_in; //true, iff out

   985       OldOutEdgeIt out;

   986       OldInEdgeIt in;

   987     public:

   988       Edge() : out_or_in(true) { }

   989       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }

   990 //       bool valid() const {

   991 // 	return out_or_in && out.valid() || in.valid(); }

   992       friend bool operator==(const Edge& u, const Edge& v) {

   993 	if (v.out_or_in)

   994 	  return (u.out_or_in && u.out==v.out);

   995 	else

   996 	  return (!u.out_or_in && u.in==v.in);

   997       }

   998       friend bool operator!=(const Edge& u, const Edge& v) {

   999 	if (v.out_or_in)

  1000 	  return (!u.out_or_in || u.out!=v.out);

  1001 	else

  1002 	  return (u.out_or_in || u.in!=v.in);

  1003       }

  1004     };

  1007     class OutEdgeIt : public Edge {

  1008       friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;

  1009     public:

  1010       OutEdgeIt() { }

  1011       //FIXME

  1012       OutEdgeIt(const Edge& e) : Edge(e) { }

  1013       OutEdgeIt(const Invalid& i) : Edge(i) { }

  1014     protected:

  1015       OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {

  1016 	resG.gw.first(out, v);

  1017 	while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }

  1018 	if (!resG.gw.valid(out)) {

  1019 	  out_or_in=0;

  1020 	  resG.gw.first(in, v);

  1021 	  while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }

  1022 	}

  1023       }

  1024 //     public:

  1025 //       OutEdgeIt& operator++() {

  1026 // 	if (out_or_in) {

  1027 // 	  Node v=/*resG->*/G->aNode(out);

  1028 // 	  ++out;

  1029 // 	  while( out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1030 // 	  if (!out.valid()) {

  1031 // 	    out_or_in=0;

  1032 // 	    G->first(in, v);

  1033 // 	    while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1034 // 	  }

  1035 // 	} else {

  1036 // 	  ++in;

  1037 // 	  while( in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1038 // 	}

  1039 // 	return *this;

  1040 //       }

  1041     };

  1043     //FIXME This is just for having InEdgeIt

  1044     typedef void InEdgeIt;

  1046     class EdgeIt : public Edge {

  1047       friend class ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>;

  1048       NodeIt v;

  1049     public:

  1050       EdgeIt() { }

  1051       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }

  1052       EdgeIt(const Invalid& i) : Edge(i) { }

  1053       EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {

  1054 	resG.gw.first(v);

  1055 	if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;

  1056 	while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }

  1057 	while (resG.gw.valid(v) && !resG.gw.valid(out)) {

  1058 	  resG.gw.next(v);

  1059 	  if (resG.gw.valid(v)) resG.gw.first(out, v);

  1060 	  while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }

  1061 	}

  1062 	if (!resG.gw.valid(out)) {

  1063 	  out_or_in=0;

  1064 	  resG.gw.first(v);

  1065 	  if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;

  1066 	  while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }

  1067 	  while (resG.gw.valid(v) && !resG.gw.valid(in)) {

  1068 	    resG.gw.next(v);

  1069 	    if (resG.gw.valid(v)) resG.gw.first(in, v);

  1070 	    while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }

  1071 	  }

  1072 	}

  1073       }

  1074 //       EdgeIt& operator++() {

  1075 // 	if (out_or_in) {

  1076 // 	  ++out;

  1077 // 	  while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1078 // 	  while (v.valid() && !out.valid()) {

  1079 // 	    ++v;

  1080 // 	    if (v.valid()) G->first(out, v);

  1081 // 	    while (out.valid() && !(Edge::resCap()>0) ) { ++out; }

  1082 // 	  }

  1083 // 	  if (!out.valid()) {

  1084 // 	    out_or_in=0;

  1085 // 	    G->first(v);

  1086 // 	    if (v.valid()) G->first(in, v); else in=OldInEdgeIt();

  1087 // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1088 // 	    while (v.valid() && !in.valid()) {

  1089 // 	      ++v;

  1090 // 	      if (v.valid()) G->first(in, v);

  1091 // 	      while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1092 // 	    }

  1093 // 	  }

  1094 // 	} else {

  1095 // 	  ++in;

  1096 // 	  while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1097 // 	  while (v.valid() && !in.valid()) {

  1098 // 	    ++v;

  1099 // 	    if (v.valid()) G->first(in, v);

  1100 // 	    while (in.valid() && !(Edge::resCap()>0) ) { ++in; }

  1101 // 	  }

  1102 // 	}

  1103 // 	return *this;

  1104 //       }

  1105     };

  1107     NodeIt& first(NodeIt& v) const { gw.first(v); return v; }

  1108     OutEdgeIt& first(OutEdgeIt& e, Node v) const {

  1109       e=OutEdgeIt(*this, v);

  1110       return e;

  1111     }

  1112     EdgeIt& first(EdgeIt& e) const {

  1113       e=EdgeIt(*this);

  1114       return e;

  1115     }

  1117     NodeIt& next(NodeIt& n) const { return gw.next(n); }

  1119     OutEdgeIt& next(OutEdgeIt& e) const {

  1120       if (e.out_or_in) {

  1121 	Node v=gw.aNode(e.out);

  1122 	gw.next(e.out);

  1123 	while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }

  1124 	if (!gw.valid(e.out)) {

  1125 	  e.out_or_in=0;

  1126 	  gw.first(e.in, v);

  1127 	  while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1128 	}

  1129       } else {

  1130 	gw.next(e.in);

  1131 	while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1132       }

  1133       return e;

  1134     }

  1136     EdgeIt& next(EdgeIt& e) const {

  1137       if (e.out_or_in) {

  1138 	gw.next(e.out);

  1139 	while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }

  1140 	  while (gw.valid(e.v) && !gw.valid(e.out)) {

  1141 	    gw.next(e.v);

  1142 	    if (gw.valid(e.v)) gw.first(e.out, e.v);

  1143 	    while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }

  1144 	  }

  1145 	  if (!gw.valid(e.out)) {

  1146 	    e.out_or_in=0;

  1147 	    gw.first(e.v);

  1148 	    if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;

  1149 	    while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1150 	    while (gw.valid(e.v) && !gw.valid(e.in)) {

  1151 	      gw.next(e.v);

  1152 	      if (gw.valid(e.v)) gw.first(e.in, e.v);

  1153 	      while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1154 	    }

  1155 	  }

  1156 	} else {

  1157 	  gw.next(e.in);

  1158 	  while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1159 	  while (gw.valid(e.v) && !gw.valid(e.in)) {

  1160 	    gw.next(e.v);

  1161 	    if (gw.valid(e.v)) gw.first(e.in, e.v);

  1162 	    while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }

  1163 	  }

  1164 	}

  1165 	return e;

  1166       }

  1169     template< typename It >

  1170     It first() const {

  1171       It e;

  1172       first(e);

  1173       return e;

  1174     }

  1176     template< typename It >

  1177     It first(Node v) const {

  1178       It e;

  1179       first(e, v);

  1180       return e;

  1181     }

  1183     Node tail(Edge e) const {

  1184       return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }

  1185     Node head(Edge e) const {

  1186       return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

  1188     Node aNode(OutEdgeIt e) const {

  1189       return ((e.out_or_in) ? gw.aNode(e.out) : gw.aNode(e.in)); }

  1190     Node bNode(OutEdgeIt e) const {

  1191       return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); }

  1193     int nodeNum() const { return gw.nodeNum(); }

  1194     //FIXME

  1195     //int edgeNum() const { return gw.edgeNum(); }

  1198     int id(Node v) const { return gw.id(v); }

  1200     bool valid(Node n) const { return gw.valid(n); }

  1201     bool valid(Edge e) const {

  1202       return e.out_or_in ? gw.valid(e.out) : gw.valid(e.in); }

  1204     void augment(const Edge& e, Number a) const {

  1205       if (e.out_or_in)

  1206 	flow->set(e.out, flow->get(e.out)+a);

  1207       else

  1208 	flow->set(e.in, flow->get(e.in)-a);

  1209     }

  1211     Number resCap(const Edge& e) const {

  1212       if (e.out_or_in)

  1213 	return (capacity->get(e.out)-flow->get(e.out));

  1214       else

  1215 	return (flow->get(e.in));

  1216     }

  1218     Number resCap(OldOutEdgeIt out) const {

  1219       return (capacity->get(out)-flow->get(out));

  1220     }

  1222     Number resCap(OldInEdgeIt in) const {

  1223       return (flow->get(in));

  1224     }

  1226 //     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {

  1227 //     public:

  1228 //       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G)

  1229 // 	: GraphWrapper::NodeMap<T>(_G.gw) { }

  1230 //       NodeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G,

  1231 // 	      T a) : GraphWrapper::NodeMap<T>(_G.gw, a) { }

  1232 //     };

  1234 //     template <typename T>

  1235 //     class NodeMap {

  1236 //       typename Graph::NodeMap<T> node_map;

  1237 //     public:

  1238 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }

  1239 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }

  1240 //       void set(Node nit, T a) { node_map.set(nit, a); }

  1241 //       T get(Node nit) const { return node_map.get(nit); }

  1242 //     };

  1244     template <typename T>

  1245     class EdgeMap {

  1246       typename GraphWrapper::EdgeMap<T> forward_map, backward_map;

  1247     public:

  1248       EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.gw), backward_map(_G.gw) { }

  1249       EdgeMap(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.gw, a), backward_map(_G.gw, a) { }

  1250       void set(Edge e, T a) {

  1251 	if (e.out_or_in)

  1252 	  forward_map.set(e.out, a);

  1253 	else

  1254 	  backward_map.set(e.in, a);

  1255       }

  1256       T get(Edge e) {

  1257 	if (e.out_or_in)

  1258 	  return forward_map.get(e.out);

  1259 	else

  1260 	  return backward_map.get(e.in);

  1261       }

  1262     };

  1263   };

  1265   //Subgraph on the same node-set and partial edge-set

  1266   template<typename GraphWrapper, typename FirstOutEdgesMap>

  1267   class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {

  1268   protected:

  1269     FirstOutEdgesMap* first_out_edges;

  1270   public:

  1271     typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;

  1272     typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;

  1273     typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;

  1274     typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;

  1275     typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;

  1276     typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;

  1278     ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :

  1279       GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }

  1281     template<typename I> I& first(I& i) const {

  1282       gw.first(i);

  1283       //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

  1284       return i;

  1285     }

  1286     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1287       e=first_out_edges->get(n);

  1288       return e;

  1289     }

  1290     template<typename I, typename P> I& first(I& i, const P& p) const {

  1291       gw.first(i, p);

  1292       //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

  1293       return i;

  1294     }

  1296     //template<typename I> I getNext(const I& i) const {

  1297     //  return gw.getNext(i);

  1298     //}

  1299     template<typename I> I& next(I &i) const {

  1300       gw.next(i);

  1301       //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }

  1302       return i;

  1303     }

  1305     template< typename It > It first() const {

  1306       It e; this->first(e); return e; }

  1308     template< typename It > It first(const Node& v) const {

  1309       It e; this->first(e, v); return e; }

  1311     void erase(const OutEdgeIt& e) const {

  1312       OutEdgeIt f=e;

  1313       this->next(f);

  1314       first_out_edges->set(this->tail(e), f);

  1315     }

  1316   };

  1318 //   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

  1319 //   class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {

  1320 //   protected:

  1321 //     ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;

  1322 //     //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;

  1323 //   public:

  1324 //     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,

  1325 // 			   const CapacityMap& _capacity) :

  1326 //       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),

  1327 //       first_out_edges(*this) /*, dist(*this)*/ {

  1328 //       for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {

  1329 // 	OutEdgeIt e;

  1330 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);

  1331 // 	first_out_edges.set(n, e);

  1332 //       }

  1333 //     }

  1335 //     //void setGraph(Graph& _graph) { graph = &_graph; }

  1336 //     //Graph& getGraph() const { return (*graph); }

  1338 //     //TrivGraphWrapper() : graph(0) { }

  1339 //     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1341 //     //typedef Graph BaseGraph;

  1343 //     //typedef typename Graph::Node Node;

  1344 //     //typedef typename Graph::NodeIt NodeIt;

  1346 //     //typedef typename Graph::Edge Edge;

  1347 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

  1348 //     //typedef typename Graph::InEdgeIt InEdgeIt;

  1349 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1350 //     //typedef typename Graph::EdgeIt EdgeIt;

  1352 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;

  1353 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;

  1355 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;

  1356 //     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;

  1357 //     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;

  1358 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1359 //     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;

  1361 //     NodeIt& first(NodeIt& n) const {

  1362 //       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);

  1363 //     }

  1365 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1366 //       e=first_out_edges.get(n);

  1367 //       return e;

  1368 //     }

  1370 //     //ROSSZ template<typename I> I& first(I& i) const { return first(i); }

  1371 //     //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {

  1372 //     //  return first(i, p); }

  1374 //     //template<typename I> I getNext(const I& i) const {

  1375 //     //  return gw.getNext(i); }

  1376 //     //template<typename I> I& next(I &i) const { return gw.next(i); }

  1378 //     template< typename It > It first() const {

  1379 //       It e; first(e); return e; }

  1381 //     template< typename It > It first(const Node& v) const {

  1382 //       It e; first(e, v); return e; }

  1384 //     //Node head(const Edge& e) const { return gw.head(e); }

  1385 //     //Node tail(const Edge& e) const { return gw.tail(e); }

  1387 //     //template<typename I> bool valid(const I& i) const

  1388 //     //  { return gw.valid(i); }

  1390 //     //int nodeNum() const { return gw.nodeNum(); }

  1391 //     //int edgeNum() const { return gw.edgeNum(); }

  1393 //     //template<typename I> Node aNode(const I& e) const {

  1394 //     //  return gw.aNode(e); }

  1395 //     //template<typename I> Node bNode(const I& e) const {

  1396 //     //  return gw.bNode(e); }

  1398 //     //Node addNode() const { return gw.addNode(); }

  1399 //     //Edge addEdge(const Node& tail, const Node& head) const {

  1400 //     //  return gw.addEdge(tail, head); }

  1402 //     //void erase(const OutEdgeIt& e) {

  1403 //     //  first_out_edge(this->tail(e))=e;

  1404 //     //}

  1405 //     void erase(const Edge& e) {

  1406 //       OutEdgeIt f(e);

  1407 //       next(f);

  1408 //       first_out_edges.set(this->tail(e), f);

  1409 //     }

  1410 //     //template<typename I> void erase(const I& i) const { gw.erase(i); }

  1412 //     //void clear() const { gw.clear(); }

  1414 //     template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {

  1415 //     public:

  1416 //       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :

  1417 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }

  1418 //       NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :

  1419 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }

  1420 //     };

  1422 //     template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {

  1423 //     public:

  1424 //       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :

  1425 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }

  1426 //       EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :

  1427 // 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }

  1428 //     };

  1429 //   };

  1431 //   template<typename GraphWrapper>

  1432 //   class FilterGraphWrapper {

  1433 //   };

  1435 //   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

  1436 //   class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {

  1438 //     //Graph* graph;

  1440 //   public:

  1441 //     //typedef Graph BaseGraph;

  1443 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;

  1444 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;

  1446 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;

  1447 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;

  1448 //     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;

  1449 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1450 //     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;

  1452 //     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;

  1454 //   public:

  1455 //     FilterGraphWrapper(const Graph& _G, FlowMap& _flow,

  1456 // 			   const CapacityMap& _capacity) :

  1457 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, gw.nodeNum()) {

  1458 //     }

  1460 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {

  1461 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);

  1462 //       while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))

  1463 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1464 //       return e;

  1465 //     }

  1467 //     NodeIt& next(NodeIt& e) const {

  1468 //       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1469 //     }

  1471 //     OutEdgeIt& next(OutEdgeIt& e) const {

  1472 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1473 //       while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e))))

  1474 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);

  1475 //       return e;

  1476 //     }

  1478 //     NodeIt& first(NodeIt& n) const {

  1479 //       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);

  1480 //     }

  1482 //     void erase(const Edge& e) {

  1483 //       OutEdgeIt f(e);

  1484 //       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);

  1485 //       while (valid(f) && (dist.get(tail(f))/*+1!=*/>=dist.get(head(f))))

  1486 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);

  1487 //       first_out_edges.set(this->tail(e), f);

  1488 //     }

  1490 //     //TrivGraphWrapper() : graph(0) { }

  1491 //     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1493 //     //void setGraph(Graph& _graph) { graph = &_graph; }

  1494 //     //Graph& getGraph() const { return (*graph); }

  1496 //     //template<typename I> I& first(I& i) const { return gw.first(i); }

  1497 //     //template<typename I, typename P> I& first(I& i, const P& p) const {

  1498 //     //  return gw.first(i, p); }

  1500 //     //template<typename I> I getNext(const I& i) const {

  1501 //     //  return gw.getNext(i); }

  1502 //     //template<typename I> I& next(I &i) const { return gw.next(i); }

  1504 //     template< typename It > It first() const {

  1505 //       It e; first(e); return e; }

  1507 //     template< typename It > It first(const Node& v) const {

  1508 //       It e; first(e, v); return e; }

  1510 //     //Node head(const Edge& e) const { return gw.head(e); }

  1511 //     //Node tail(const Edge& e) const { return gw.tail(e); }

  1513 //     //template<typename I> bool valid(const I& i) const

  1514 //     //  { return gw.valid(i); }

  1516 //     //template<typename I> void setInvalid(const I &i);

  1517 //     //{ return gw.setInvalid(i); }

  1519 //     //int nodeNum() const { return gw.nodeNum(); }

  1520 //     //int edgeNum() const { return gw.edgeNum(); }

  1522 //     //template<typename I> Node aNode(const I& e) const {

  1523 //     //  return gw.aNode(e); }

  1524 //     //template<typename I> Node bNode(const I& e) const {

  1525 //     //  return gw.bNode(e); }

  1527 //     //Node addNode() const { return gw.addNode(); }

  1528 //     //Edge addEdge(const Node& tail, const Node& head) const {

  1529 //     //  return gw.addEdge(tail, head); }

  1531 //     //template<typename I> void erase(const I& i) const { gw.erase(i); }

  1533 //     //void clear() const { gw.clear(); }

  1535 //     template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {

  1536 //     public:

  1537 //       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :

  1538 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }

  1539 //       NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :

  1540 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }

  1541 //     };

  1543 //     template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {

  1544 //     public:

  1545 //       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :

  1546 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }

  1547 //       EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :

  1548 // 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }

  1549 //     };

  1551 //   public:

  1552 //     ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;

  1554 //   };

  1558 // // FIXME: comparison should be made better!!!

  1559 //   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>

  1560 //   class ResGraphWrapper

  1561 //   {

  1562 //     Graph* graph;

  1564 //   public:

  1565 //     typedef Graph BaseGraph;

  1567 //     typedef typename Graph::Node Node;

  1568 //     typedef typename Graph::Edge Edge;

  1570 //     typedef typename Graph::NodeIt NodeIt;

  1572 //     class OutEdgeIt {

  1573 //     public:

  1574 //       //Graph::Node n;

  1575 //       bool out_or_in;

  1576 //       typename Graph::OutEdgeIt o;

  1577 //       typename Graph::InEdgeIt i;

  1578 //     };

  1579 //     class InEdgeIt {

  1580 //     public:

  1581 //       //Graph::Node n;

  1582 //       bool out_or_in;

  1583 //       typename Graph::OutEdgeIt o;

  1584 //       typename Graph::InEdgeIt i;

  1585 //     };

  1586 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1587 //     typedef typename Graph::EdgeIt EdgeIt;

  1589 //     int nodeNum() const { return gw.nodeNum(); }

  1590 //     int edgeNum() const { return gw.edgeNum(); }

  1592 //     Node& first(Node& n) const { return gw.first(n); }

  1594 //     // Edge and SymEdge  is missing!!!!

  1595 //     // Edge <-> In/OutEdgeIt conversion is missing!!!!

  1597 //     //FIXME

  1598 //     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const

  1599 //       {

  1600 // 	e.n=n;

  1601 // 	gw.first(e.o,n);

  1602 // 	while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1603 // 	  gw.goNext(e.o);

  1604 // 	if(!gw.valid(e.o)) {

  1605 // 	  gw.first(e.i,n);

  1606 // 	  while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1607 // 	    gw.goNext(e.i);

  1608 // 	}

  1609 // 	return e;

  1610 //       }

  1611 // /*

  1612 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1613 //   {

  1614 //   if(gw.valid(e.o)) {

  1615 //   while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o))

  1616 //   gw.goNext(e.o);

  1617 //   if(gw.valid(e.o)) return e;

  1618 //   else gw.first(e.i,e.n);

  1619 //   }

  1620 //   else {

  1621 //   while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))

  1622 //   gw.goNext(e.i);

  1623 //   return e;

  1624 //   }

  1625 //   }

  1626 //   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}

  1627 // */

  1628 //     //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);}

  1630 //     //FIXME

  1631 //     InEdgeIt& first(InEdgeIt& e, const Node& n) const

  1632 //       {

  1633 // 	e.n=n;

  1634 // 	gw.first(e.i,n);

  1635 // 	while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1636 // 	  gw.goNext(e.i);

  1637 // 	if(!gw.valid(e.i)) {

  1638 // 	  gw.first(e.o,n);

  1639 // 	  while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1640 // 	    gw.goNext(e.o);

  1641 // 	}

  1642 // 	return e;

  1643 //       }

  1644 // /*

  1645 //   InEdgeIt &goNext(InEdgeIt &e)

  1646 //   {

  1647 //   if(gw.valid(e.i)) {

  1648 //   while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i))

  1649 //   gw.goNext(e.i);

  1650 //   if(gw.valid(e.i)) return e;

  1651 //   else gw.first(e.o,e.n);

  1652 //   }

  1653 //   else {

  1654 //   while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))

  1655 //   gw.goNext(e.o);

  1656 //   return e;

  1657 //   }

  1658 //   }

  1659 //   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}

  1660 // */

  1661 //     //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);}

  1663 //     //template<typename I> I &goNext(I &i); { return gw.goNext(i); }

  1664 //     //template<typename I> I next(const I i); { return gw.goNext(i); }

  1666 //     template< typename It > It first() const {

  1667 //       It e; first(e); return e; }

  1669 //     template< typename It > It first(Node v) const {

  1670 //       It e; first(e, v); return e; }

  1672 //     Node head(const Edge& e) const { return gw.head(e); }

  1673 //     Node tail(const Edge& e) const { return gw.tail(e); }

  1675 //     template<typename I> Node aNode(const I& e) const {

  1676 //       return gw.aNode(e); }

  1677 //     template<typename I> Node bNode(const I& e) const {

  1678 //       return gw.bNode(e); }

  1680 //     //template<typename I> bool valid(const I i);

  1681 //     //{ return gw.valid(i); }

  1683 //     //template<typename I> void setInvalid(const I &i);

  1684 //     //{ return gw.setInvalid(i); }

  1686 //     Node addNode() { return gw.addNode(); }

  1687 //     Edge addEdge(const Node& tail, const Node& head) {

  1688 //       return gw.addEdge(tail, head); }

  1690 //     template<typename I> void erase(const I& i) { gw.erase(i); }

  1692 //     void clear() { gw.clear(); }

  1694 //     template<typename S> class NodeMap : public Graph::NodeMap<S> { };

  1695 //     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };

  1697 //     void setGraph(Graph& _graph) { graph = &_graph; }

  1698 //     Graph& getGraph() { return (*graph); }

  1700 //     //ResGraphWrapper() : graph(0) { }

  1701 //     ResGraphWrapper(Graph& _graph) : graph(&_graph) { }

  1702 //   };

  1704 } //namespace hugo

  1706 #endif //HUGO_GRAPH_WRAPPER_H

author	athos
	Mon, 24 May 2004 10:43:44 +0000
changeset 657	531fc5f575ef
child 880	9d0bfd35b97c
permissions	-rw-r--r--