lemon-0.x: src/work/marci/graph_wrapper.h@30c5179f296b

     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;

    16 //     typedef Graph ParentGraph;

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

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

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

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

    23 //     typedef typename Graph::Node Node;

    24 //     class NodeIt : public Graph::NodeIt {

    25 //     public:

    26 //       NodeIt() { }

    27 //       NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }

    28 //       NodeIt(const Invalid& i) : Graph::NodeIt(i) { }

    29 //       NodeIt(const TrivGraphWrapper<Graph>& _G) :

    30 // 	Graph::NodeIt(*(_G.graph)) { }

    31 //     };

    32 //     typedef typename Graph::Edge Edge;

    33 //     class OutEdgeIt : public Graph::OutEdgeIt {

    34 //     public:

    35 //       OutEdgeIt() { }

    36 //       OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }

    37 //       OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }

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

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

    40 //     };

    41 //     class InEdgeIt : public Graph::InEdgeIt {

    42 //     public:

    43 //       InEdgeIt() { }

    44 //       InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }

    45 //       InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }

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

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

    48 //     };

    49 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    50 //     class EdgeIt : public Graph::EdgeIt {

    51 //     public:

    52 //       EdgeIt() { }

    53 //       EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }

    54 //       EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }

    55 //       EdgeIt(const TrivGraphWrapper<Graph>& _G) :

    56 // 	Graph::EdgeIt(*(_G.graph)) { }

    57 //     };

    59 //     NodeIt& first(NodeIt& i) const {

    60 //       i=NodeIt(*this);

    61 //       return i;

    62 //     }

    63 //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

    64 //       i=OutEdgeIt(*this, p);

    65 //       return i;

    66 //     }

    67 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

    68 //       i=InEdgeIt(*this, p);

    69 //       return i;

    70 //     }

    71 //     EdgeIt& first(EdgeIt& i) const {

    72 //       i=EdgeIt(*this);

    73 //       return i;

    74 //     }

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

    76 // //       i=I(*this);

    77 // //       return i;

    78 // //     }

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

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

    81 // //       return i;

    82 // //     }

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

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

    87 //     NodeIt& next(NodeIt& i) const { graph->next(i); return i; }

    88 //     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }

    89 //     InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }

    90 //     EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }

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

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

    93 //       It e; this->first(e); return e; }

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

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

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

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

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

   102 //       return graph->valid(i); }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   124 //     public:

   125 //       NodeMap(const TrivGraphWrapper<Graph>& _G) :

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

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

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

   129 //     };

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

   132 //     public:

   133 //       EdgeMap(const TrivGraphWrapper<Graph>& _G) :

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

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

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

   137 //     };

   139 // //     template<typename Map, typename T> class NodeMapWrapper {

   140 // //     protected:

   141 // //       Map* map;

   142 // //     public:

   143 // //       NodeMapWrapper(Map& _map) : map(&_map) { }

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

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

   146 // //     };

   148 // //     template<typename Map, typename T> class EdgeMapWrapper {

   149 // //     protected:

   150 // //       Map* map;

   151 // //     public:

   152 // //       EdgeMapWrapper(Map& _map) : map(&_map) { }

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

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

   155 // //     };

   156 //   };

   159   template<typename Graph>

   160   class GraphWrapper {

   161   protected:

   162     Graph* graph;

   164   public:

   165     typedef Graph BaseGraph;

   166     typedef Graph ParentGraph;

   168 //     GraphWrapper() : graph(0) { }

   169     GraphWrapper(Graph& _graph) : graph(&_graph) { }

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

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

   173     typedef typename Graph::Node Node;

   174     class NodeIt : public Graph::NodeIt {

   175       typedef typename Graph::NodeIt GraphNodeIt;

   176     public:

   177       NodeIt() { }

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

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

   180       NodeIt(const GraphWrapper<Graph>& _G) :

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

   182 //      operator Node() const {

   183 //	std::cout << "ize" << std::endl;

   184 //	return Node(this->GraphNodeIt);

   185 //      }

   186     };

   187     typedef typename Graph::Edge Edge;

   188     class OutEdgeIt : public Graph::OutEdgeIt {

   189       typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   190     public:

   191       OutEdgeIt() { }

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

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

   194       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :

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

   196 //      operator Edge() const {

   197 //	std::cout << "ize" << std::endl;

   198 //	return Edge(this->GraphOutEdgeIt);

   199 //      }

   200     };

   201     class InEdgeIt : public Graph::InEdgeIt {

   202       typedef typename Graph::InEdgeIt GraphInEdgeIt;

   203     public:

   204       InEdgeIt() { }

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

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

   207       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :

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

   209 //      operator Edge() const {

   210 //	std::cout << "ize" << std::endl;

   211 //	return Edge(this->InOutEdgeIt);

   212 //      }

   213     };

   214     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   215     class EdgeIt : public Graph::EdgeIt {

   216       typedef typename Graph::EdgeIt GraphEdgeIt;

   217     public:

   218       EdgeIt() { }

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

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

   221       EdgeIt(const GraphWrapper<Graph>& _G) :

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

   223 //      operator Edge() const {

   224 //	std::cout << "ize" << std::endl;

   225 //	return Edge(this->GraphEdgeIt);

   226 //      }

   227     };

   229     NodeIt& first(NodeIt& i) const {

   230       i=NodeIt(*this);

   231       return i;

   232     }

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

   234       i=OutEdgeIt(*this, p);

   235       return i;

   236     }

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

   238       i=InEdgeIt(*this, p);

   239       return i;

   240     }

   241     EdgeIt& first(EdgeIt& i) const {

   242       i=EdgeIt(*this);

   243       return i;

   244     }

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

   246 //       i=I(*this);

   247 //       return i;

   248 //     }

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

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

   251 //       return i;

   252 //     }

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

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

   257     NodeIt& next(NodeIt& i) const { graph->next(i); return i; }

   258     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }

   259     InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }

   260     EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }

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

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

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

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

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

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

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

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

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

   273       return graph->valid(i); }

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

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

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

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

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

   282       return graph->aNode(e); }

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

   284       return graph->bNode(e); }

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

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

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

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

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

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

   295     public:

   296       NodeMap(const GraphWrapper<Graph>& _G) :

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

   298       NodeMap(const GraphWrapper<Graph>& _G, T a) :

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

   300     };

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

   303     public:

   304       EdgeMap(const GraphWrapper<Graph>& _G) :

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

   306       EdgeMap(const GraphWrapper<Graph>& _G, T a) :

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

   308     };

   309   };

   312 //   template<typename Graph>

   313 //   class RevGraphWrapper

   314 //   {

   315 //   protected:

   316 //     Graph* graph;

   318 //   public:

   319 //     typedef Graph ParentGraph;

   321 //     typedef typename Graph::Node Node;

   322 //     typedef typename Graph::NodeIt NodeIt;

   324 //     typedef typename Graph::Edge Edge;

   325 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   326 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   327 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   328 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   376 //     public:

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

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

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

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

   381 //     };

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

   384 //     public:

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

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

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

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

   389 //     };

   390 //   };

   393   template<typename Graph>

   394   class RevGraphWrapper : public GraphWrapper<Graph> {

   395   public:

   396     typedef typename GraphWrapper<Graph>::Node Node;

   397     typedef typename GraphWrapper<Graph>::Edge Edge;

   398     //FIXME

   399     //If Graph::OutEdgeIt is not defined

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

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

   402     //OR

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

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

   405     //unlike other stuff

   406     typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;

   407     typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

   409 //     RevGraphWrapper() : GraphWrapper<Graph>() { }

   410     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }

   412     Node head(const Edge& e) const

   413       { return GraphWrapper<Graph>::tail(e); }

   414     Node tail(const Edge& e) const

   415       { return GraphWrapper<Graph>::head(e); }

   416   };

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

   419   template<typename Graph, typename NodeFilterMap,

   420 	   typename EdgeFilterMap>

   421   class SubGraphWrapper : public GraphWrapper<Graph> {

   422   protected:

   423     NodeFilterMap* node_filter_map;

   424     EdgeFilterMap* edge_filter_map;

   425   public:

   426 //     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }

   427     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   428 		    EdgeFilterMap& _edge_filter_map) :

   429       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),

   430       edge_filter_map(&_edge_filter_map) { }

   433     typedef typename Graph::Node Node;

   434     class NodeIt : public Graph::NodeIt {

   435 //      typedef typename Graph::NodeIt GraphNodeIt;

   436     public:

   437       NodeIt() { }

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

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

   440       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   441 	Graph::NodeIt(*(_G.graph)) {

   442 	while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&

   443 	       !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])

   444 	  _G.graph->next((*this)/*.GraphNodeIt*/);

   445       }

   446     };

   447     typedef typename Graph::Edge Edge;

   448     class OutEdgeIt : public Graph::OutEdgeIt {

   449 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   450     public:

   451       OutEdgeIt() { }

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

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

   454       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&

   455 		_G, const Node& n) :

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

   457 	while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&

   458 	       !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])

   459 	  _G.graph->next((*this)/*.GraphOutEdgeIt*/);

   460       }

   461     };

   462     class InEdgeIt : public Graph::InEdgeIt {

   463 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   464     public:

   465       InEdgeIt() { }

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

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

   468       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,

   469 	       const Node& n) :

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

   471 	while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&

   472 	       !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])

   473 	  _G.graph->next((*this)/*.GraphInEdgeIt*/);

   474       }

   475     };

   476 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   477     class EdgeIt : public Graph::EdgeIt {

   478 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   479     public:

   480       EdgeIt() { }

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

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

   483       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :

   484 	Graph::EdgeIt(*(_G.graph)) {

   485 	while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&

   486 	       !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])

   487 	  _G.graph->next((*this)/*.GraphEdgeIt*/);

   488       }

   489     };

   491     NodeIt& first(NodeIt& i) const {

   492       i=NodeIt(*this);

   493       return i;

   494     }

   495     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {

   496       i=OutEdgeIt(*this, n);

   497       return i;

   498     }

   499     InEdgeIt& first(InEdgeIt& i, const Node& n) const {

   500       i=InEdgeIt(*this, n);

   501       return i;

   502     }

   503     EdgeIt& first(EdgeIt& i) const {

   504       i=EdgeIt(*this);

   505       return i;

   506     }

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

   509 //       graph->first(i);

   510 //       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   511 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   512 //       return i;

   513 //     }

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

   515 //       graph->first(i, p);

   516 // //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }

   517 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   518 //       return i;

   519 //     }

   521     NodeIt& next(NodeIt& i) const {

   522       graph->next(i);

   523       while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }

   524       return i;

   525     }

   526     OutEdgeIt& next(OutEdgeIt& i) const {

   527       graph->next(i);

   528       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   529       return i;

   530     }

   531     InEdgeIt& next(InEdgeIt& i) const {

   532       graph->next(i);

   533       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   534       return i;

   535     }

   536     EdgeIt& next(EdgeIt& i) const {

   537       graph->next(i);

   538       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   539       return i;

   540     }

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

   543     //  return gw.getNext(i);

   544     //}

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

   546 //       graph->next(i);

   547 // //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }

   548 //       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }

   549 //       return i;

   550 //     }

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

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

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

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

   557   };

   559 //   template<typename GraphWrapper>

   560 //   class UndirGraphWrapper {

   561 //   protected:

   562 //     //Graph* graph;

   563 //     GraphWrapper gw;

   565 //   public:

   566 //     typedef GraphWrapper ParentGraph;

   568 //     typedef typename GraphWrapper::Node Node;

   569 //     typedef typename GraphWrapper::NodeIt NodeIt;

   571 //     //typedef typename Graph::Edge Edge;

   572 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   573 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   574 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   575 //     //typedef typename Graph::EdgeIt EdgeIt;

   577 //     //private:

   578 //     typedef typename GraphWrapper::Edge GraphEdge;

   579 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   580 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   581 //     //public:

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

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

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

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

   589 //     class Edge {

   590 //       friend class UndirGraphWrapper<GraphWrapper>;

   591 //       bool out_or_in; //true iff out

   592 //       GraphOutEdgeIt out;

   593 //       GraphInEdgeIt in;

   594 //     public:

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

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

   597 //       operator GraphEdge() const {

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

   599 //       }

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

   601 // 	if (v.out_or_in)

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

   603 // 	else

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

   605 //       }

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

   607 // 	if (v.out_or_in)

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

   609 // 	else

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

   611 //       }

   612 //     };

   614 //     class OutEdgeIt : public Edge {

   615 //       friend class UndirGraphWrapper<GraphWrapper>;

   616 //     public:

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

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

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

   620 // 	: Edge() {

   621 // 	out_or_in=true;

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

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

   624 // 	  out_or_in=false;

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

   626 // 	}

   627 //       }

   628 //     };

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

   631 //       e.out_or_in=true;

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

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

   634 // 	e.out_or_in=false;

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

   636 //       }

   637 //       return e;

   638 //     }

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

   641 //       if (e.out_or_in) {

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

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

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

   645 // 	  e.out_or_in=false;

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

   647 // 	}

   648 //       } else {

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

   650 //       }

   651 //       return e;

   652 //     }

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

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

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

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

   659 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   702 //     public:

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

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

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

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

   707 //     };

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

   710 //     public:

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

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

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

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

   715 //     };

   716 //   };

   719   template<typename Graph>

   720   class UndirGraphWrapper : public GraphWrapper<Graph> {

   721   protected:

   722     typedef typename Graph::Edge GraphEdge;

   723     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   724     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   725   public:

   726     typedef typename GraphWrapper<Graph>::Node Node;

   727     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   729 //     UndirGraphWrapper() : GraphWrapper<Graph>() { }

   730     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }

   732     class Edge {

   733       friend class UndirGraphWrapper<Graph>;

   734     protected:

   735       bool out_or_in; //true iff out

   736       GraphOutEdgeIt out;

   737       GraphInEdgeIt in;

   738     public:

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

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

   741       operator GraphEdge() const {

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

   743       }

   744 //FIXME

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

   746 //is it good?

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

   748 	if (v.out_or_in)

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

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

   751 	else

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

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

   754       }

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

   756 	if (v.out_or_in)

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

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

   759 	else

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

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

   762       }

   763     };

   765     class OutEdgeIt : public Edge {

   766       friend class UndirGraphWrapper<Graph>;

   767     public:

   768       OutEdgeIt() : Edge() { }

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

   770       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)

   771 	: Edge() {

   772 	out_or_in=true; _G.graph->first(out, n);

   773 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n);	}

   774       }

   775     };

   777     typedef OutEdgeIt InEdgeIt;

   779     class EdgeIt : public Edge {

   780       friend class UndirGraphWrapper<Graph>;

   781     protected:

   782       NodeIt v;

   783     public:

   784       EdgeIt() : Edge() { }

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

   786       EdgeIt(const UndirGraphWrapper<Graph>& _G)

   787 	: Edge() {

   788 	out_or_in=true;

   789 	//Node v;

   790 	_G.first(v);

   791 	if (_G.valid(v)) _G.graph->first(out); else out=INVALID;

   792 	while (_G.valid(v) && !_G.graph->valid(out)) {

   793 	  _G.graph->next(v);

   794 	  if (_G.valid(v)) _G.graph->first(out);

   795 	}

   796       }

   797     };

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

   800       e.out_or_in=true; graph->first(e.out, n);

   801       if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }

   802       return e;

   803     }

   805     EdgeIt& first(EdgeIt& e) const {

   806       e.out_or_in=true;

   807       //NodeIt v;

   808       first(e.v);

   809       if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;

   810       while (valid(e.v) && !graph->valid(e.out)) {

   811 	graph->next(e.v);

   812 	if (valid(e.v)) graph->first(e.out, e.v);

   813       }

   814       return e;

   815     }

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

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

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

   821     OutEdgeIt& next(OutEdgeIt& e) const {

   822       if (e.out_or_in) {

   823 	Node n=graph->tail(e.out);

   824 	graph->next(e.out);

   825 	if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }

   826       } else {

   827 	graph->next(e.in);

   828       }

   829       return e;

   830     }

   832     EdgeIt& next(EdgeIt& e) const {

   833       //NodeIt v=tail(e);

   834       graph->next(e.out);

   835       while (valid(e.v) && !graph->valid(e.out)) {

   836 	next(e.v);

   837 	if (valid(e.v)) graph->first(e.out, e.v);

   838       }

   839       return e;

   840     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   865     Node aNode(const OutEdgeIt& e) const {

   866       if (e.out_or_in) return graph->tail(e); else return graph->head(e); }

   867     Node bNode(const OutEdgeIt& e) const {

   868       if (e.out_or_in) return graph->head(e); else return graph->tail(e); }

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

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

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

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

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

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

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

   881 //     public:

   882 //       NodeMap(const UndirGraphWrapper<Graph>& _G) :

   883 // 	Graph::NodeMap<T>(_G.gw) { }

   884 //       NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :

   885 // 	Graph::NodeMap<T>(_G.gw, a) { }

   886 //     };

   888 //     template<typename T> class EdgeMap :

   889 //       public GraphWrapperSkeleton<Graph>::EdgeMap<T> {

   890 //     public:

   891 //       EdgeMap(const UndirGraphWrapper<Graph>& _G) :

   892 // 	GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { }

   893 //       EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :

   894 // 	Graph::EdgeMap<T>(_G.gw, a) { }

   895 //     };

   896    };

   902 //   template<typename Graph>

   903 //   class SymGraphWrapper

   904 //   {

   905 //     Graph* graph;

   907 //   public:

   908 //     typedef Graph ParentGraph;

   910 //     typedef typename Graph::Node Node;

   911 //     typedef typename Graph::Edge Edge;

   913 //     typedef typename Graph::NodeIt NodeIt;

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

   916 //     //iranyitatlant, ami van

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

   918 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   920 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   921 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   968 //   };

   971   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   972   class ResGraphWrapper : public GraphWrapper<Graph> {

   973   protected:

   974     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   975     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   976     typedef typename Graph::Edge GraphEdge;

   977     FlowMap* flow;

   978     const CapacityMap* capacity;

   979   public:

   981     ResGraphWrapper(Graph& _graph, FlowMap& _flow,

   982 		    const CapacityMap& _capacity) :

   983       GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }

   985     class Edge;

   986     class OutEdgeIt;

   987     friend class Edge;

   988     friend class OutEdgeIt;

   990     typedef typename GraphWrapper<Graph>::Node Node;

   991     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

   992     class Edge {

   993       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

   994     protected:

   995       bool out_or_in; //true, iff out

   996       GraphOutEdgeIt out;

   997       GraphInEdgeIt in;

   998     public:

   999       Edge() : out_or_in(true) { }

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

  1001 //       bool valid() const {

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

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

  1004 	if (v.out_or_in)

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

  1006 	else

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

  1008       }

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

  1010 	if (v.out_or_in)

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

  1012 	else

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

  1014       }

  1015       operator GraphEdge() const {

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

  1017       }

  1018     };

  1019     class OutEdgeIt : public Edge {

  1020       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1021     public:

  1022       OutEdgeIt() { }

  1023       //FIXME

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

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

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

  1027 	resG.graph->first(out, v);

  1028 	while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1029 	if (!resG.graph->valid(out)) {

  1030 	  out_or_in=0;

  1031 	  resG.graph->first(in, v);

  1032 	  while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1033 	}

  1034       }

  1035 //     public:

  1036 //       OutEdgeIt& operator++() {

  1037 // 	if (out_or_in) {

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

  1039 // 	  ++out;

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

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

  1042 // 	    out_or_in=0;

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

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

  1045 // 	  }

  1046 // 	} else {

  1047 // 	  ++in;

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

  1049 // 	}

  1050 // 	return *this;

  1051 //       }

  1052     };

  1054     //FIXME This is just for having InEdgeIt

  1055 //    class InEdgeIt : public Edge { };

  1057     class EdgeIt : public Edge {

  1058       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1059       NodeIt v;

  1060     public:

  1061       EdgeIt() { }

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

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

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

  1065 	resG.graph->first(v);

  1066 	if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;

  1067 	while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1068 	while (resG.graph->valid(v) && !resG.graph->valid(out)) {

  1069 	  resG.graph->next(v);

  1070 	  if (resG.graph->valid(v)) resG.graph->first(out, v);

  1071 	  while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }

  1072 	}

  1073 	if (!resG.graph->valid(out)) {

  1074 	  out_or_in=0;

  1075 	  resG.graph->first(v);

  1076 	  if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;

  1077 	  while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1078 	  while (resG.graph->valid(v) && !resG.graph->valid(in)) {

  1079 	    resG.graph->next(v);

  1080 	    if (resG.graph->valid(v)) resG.graph->first(in, v);

  1081 	    while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }

  1082 	  }

  1083 	}

  1084       }

  1085 //       EdgeIt& operator++() {

  1086 // 	if (out_or_in) {

  1087 // 	  ++out;

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

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

  1090 // 	    ++v;

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

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

  1093 // 	  }

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

  1095 // 	    out_or_in=0;

  1096 // 	    G->first(v);

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

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

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

  1100 // 	      ++v;

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

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

  1103 // 	    }

  1104 // 	  }

  1105 // 	} else {

  1106 // 	  ++in;

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

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

  1109 // 	    ++v;

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

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

  1112 // 	  }

  1113 // 	}

  1114 // 	return *this;

  1115 //       }

  1116     };

  1118     NodeIt& first(NodeIt& i) const {

  1119       i=NodeIt(*this);

  1120       return i;

  1121     }

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

  1123       i=OutEdgeIt(*this, p);

  1124       return i;

  1125     }

  1126     //FIXME Not yet implemented

  1127     //InEdgeIt& first(InEdgeIt& i, const Node& p) const {

  1128     //i=InEdgeIt(*this, p);

  1129     //  return i;

  1130     //}

  1131     EdgeIt& first(EdgeIt& e) const {

  1132       e=EdgeIt(*this);

  1133       return e;

  1134     }

  1136     NodeIt& next(NodeIt& n) const { graph->next(n); return n; }

  1137     OutEdgeIt& next(OutEdgeIt& e) const {

  1138       if (e.out_or_in) {

  1139 	Node v=graph->aNode(e.out);

  1140 	graph->next(e.out);

  1141 	while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1142 	if (!graph->valid(e.out)) {

  1143 	  e.out_or_in=0;

  1144 	  graph->first(e.in, v);

  1145 	  while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1146 	}

  1147       } else {

  1148 	graph->next(e.in);

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

  1150       }

  1151       return e;

  1152     }

  1153     //FIXME Not yet implemented

  1154     //InEdgeIt& next(InEdgeIt& e) const {

  1155     //  return e;

  1156     //}

  1157     EdgeIt& next(EdgeIt& e) const {

  1158       if (e.out_or_in) {

  1159 	graph->next(e.out);

  1160 	while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1161 	  while (graph->valid(e.v) && !graph->valid(e.out)) {

  1162 	    graph->next(e.v);

  1163 	    if (graph->valid(e.v)) graph->first(e.out, e.v);

  1164 	    while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }

  1165 	  }

  1166 	  if (!graph->valid(e.out)) {

  1167 	    e.out_or_in=0;

  1168 	    graph->first(e.v);

  1169 	    if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;

  1170 	    while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1171 	    while (graph->valid(e.v) && !graph->valid(e.in)) {

  1172 	      graph->next(e.v);

  1173 	      if (graph->valid(e.v)) graph->first(e.in, e.v);

  1174 	      while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1175 	    }

  1176 	  }

  1177 	} else {

  1178 	  graph->next(e.in);

  1179 	  while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1180 	  while (graph->valid(e.v) && !graph->valid(e.in)) {

  1181 	    graph->next(e.v);

  1182 	    if (graph->valid(e.v)) graph->first(e.in, e.v);

  1183 	    while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }

  1184 	  }

  1185 	}

  1186 	return e;

  1187       }

  1190     template< typename It >

  1191     It first() const {

  1192       It e;

  1193       first(e);

  1194       return e;

  1195     }

  1197     template< typename It >

  1198     It first(Node v) const {

  1199       It e;

  1200       first(e, v);

  1201       return e;

  1202     }

  1204     Node tail(Edge e) const {

  1205       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }

  1206     Node head(Edge e) const {

  1207       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }

  1209     Node aNode(OutEdgeIt e) const {

  1210       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }

  1211     Node bNode(OutEdgeIt e) const {

  1212       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }

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

  1215     //FIXME

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

  1219     int id(Node v) const { return graph->id(v); }

  1221     bool valid(Node n) const { return graph->valid(n); }

  1222     bool valid(Edge e) const {

  1223       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }

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

  1226       if (e.out_or_in)

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

  1228 	flow->set(e.out, (*flow)[e.out]+a);

  1229       else

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

  1231 	flow->set(e.in, (*flow)[e.in]-a);

  1232     }

  1234     Number resCap(const Edge& e) const {

  1235       if (e.out_or_in)

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

  1237 	return ((*capacity)[e.out]-(*flow)[e.out]);

  1238       else

  1239 //	return (flow->get(e.in));

  1240 	return ((*flow)[e.in]);

  1241     }

  1243     Number resCap(GraphOutEdgeIt out) const {

  1244 //      return (capacity->get(out)-flow->get(out));

  1245       return ((*capacity)[out]-(*flow)[out]);

  1246     }

  1248     Number resCap(GraphInEdgeIt in) const {

  1249 //      return (flow->get(in));

  1250       return ((*flow)[in]);

  1251     }

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

  1254 //     public:

  1255 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)

  1256 // 	: Graph::NodeMap<T>(_G.gw) { }

  1257 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,

  1258 // 	      T a) : Graph::NodeMap<T>(_G.gw, a) { }

  1259 //     };

  1261 //     template <typename T>

  1262 //     class NodeMap {

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

  1264 //     public:

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

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

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

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

  1269 //     };

  1271     template <typename T>

  1272     class EdgeMap {

  1273       typename Graph::EdgeMap<T> forward_map, backward_map;

  1274     public:

  1275       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }

  1276       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }

  1277       void set(Edge e, T a) {

  1278 	if (e.out_or_in)

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

  1280 	else

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

  1282       }

  1283       T operator[](Edge e) const {

  1284 	if (e.out_or_in)

  1285 	  return forward_map[e.out];

  1286 	else

  1287 	  return backward_map[e.in];

  1288       }

  1289 //       T get(Edge e) const {

  1290 // 	if (e.out_or_in)

  1291 // 	  return forward_map.get(e.out);

  1292 // 	else

  1293 // 	  return backward_map.get(e.in);

  1294 //       }

  1295     };

  1296   };

  1298   //ErasingFirstGraphWrapper for blocking flows

  1299   template<typename Graph, typename FirstOutEdgesMap>

  1300   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1301   protected:

  1302     FirstOutEdgesMap* first_out_edges;

  1303   public:

  1304     ErasingFirstGraphWrapper(Graph& _graph,

  1305 			     FirstOutEdgesMap& _first_out_edges) :

  1306       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }

  1308     typedef typename Graph::Node Node;

  1309     class NodeIt : public Graph::NodeIt {

  1310     public:

  1311       NodeIt() { }

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

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

  1314       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :

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

  1316     };

  1317     typedef typename Graph::Edge Edge;

  1318     class OutEdgeIt : public Graph::OutEdgeIt {

  1319     public:

  1320       OutEdgeIt() { }

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

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

  1323       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  1324 		const Node& n) :

  1325 	Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }

  1326     };

  1327     class InEdgeIt : public Graph::InEdgeIt {

  1328     public:

  1329       InEdgeIt() { }

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

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

  1332       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  1333 	       const Node& n) :

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

  1335     };

  1336     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1337     class EdgeIt : public Graph::EdgeIt {

  1338     public:

  1339       EdgeIt() { }

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

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

  1342       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :

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

  1344     };

  1346     NodeIt& first(NodeIt& i) const {

  1347       i=NodeIt(*this);

  1348       return i;

  1349     }

  1350     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {

  1351       i=OutEdgeIt(*this, n);

  1352 //      i=(*first_out_edges)[n];

  1353       return i;

  1354     }

  1355     InEdgeIt& first(InEdgeIt& i, const Node& n) const {

  1356       i=InEdgeIt(*this, n);

  1357       return i;

  1358     }

  1359     EdgeIt& first(EdgeIt& i) const {

  1360       i=EdgeIt(*this);

  1361       return i;

  1362     }

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

  1365 //       graph->first(i);

  1366 //       return i;

  1367 //     }

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

  1369 // //      e=first_out_edges->get(n);

  1370 //       e=(*first_out_edges)[n];

  1371 //       return e;

  1372 //     }

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

  1374 //       graph->first(i, p);

  1375 //       return i;

  1376 //     }

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

  1379     //  return gw.getNext(i);

  1380     //}

  1383     NodeIt& next(NodeIt& i) const {

  1384       graph->next(i);

  1385       return i;

  1386     }

  1387     OutEdgeIt& next(OutEdgeIt& i) const {

  1388       graph->next(i);

  1389       return i;

  1390     }

  1391     InEdgeIt& next(InEdgeIt& i) const {

  1392       graph->next(i);

  1393       return i;

  1394     }

  1395     EdgeIt& next(EdgeIt& i) const {

  1396       graph->next(i);

  1397       return i;

  1398     }

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

  1401 //       graph->next(i);

  1402 //       return i;

  1403 //     }

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

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

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

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

  1411     void erase(const OutEdgeIt& e) const {

  1412       OutEdgeIt f=e;

  1413       this->next(f);

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

  1415     }

  1416   };

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

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

  1420 //   class ResGraphWrapper

  1421 //   {

  1422 //     Graph* graph;

  1424 //   public:

  1425 //     typedef Graph ParentGraph;

  1427 //     typedef typename Graph::Node Node;

  1428 //     typedef typename Graph::Edge Edge;

  1430 //     typedef typename Graph::NodeIt NodeIt;

  1432 //     class OutEdgeIt {

  1433 //     public:

  1434 //       //Graph::Node n;

  1435 //       bool out_or_in;

  1436 //       typename Graph::OutEdgeIt o;

  1437 //       typename Graph::InEdgeIt i;

  1438 //     };

  1439 //     class InEdgeIt {

  1440 //     public:

  1441 //       //Graph::Node n;

  1442 //       bool out_or_in;

  1443 //       typename Graph::OutEdgeIt o;

  1444 //       typename Graph::InEdgeIt i;

  1445 //     };

  1446 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1447 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1454 //     // Edge and SymEdge  is missing!!!!

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

  1457 //     //FIXME

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

  1459 //       {

  1460 // 	e.n=n;

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

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

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

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

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

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

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

  1468 // 	}

  1469 // 	return e;

  1470 //       }

  1471 // /*

  1472 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1473 //   {

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

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

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

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

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

  1479 //   }

  1480 //   else {

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

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

  1483 //   return e;

  1484 //   }

  1485 //   }

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

  1487 // */

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

  1490 //     //FIXME

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

  1492 //       {

  1493 // 	e.n=n;

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

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

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

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

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

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

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

  1501 // 	}

  1502 // 	return e;

  1503 //       }

  1504 // /*

  1505 //   InEdgeIt &goNext(InEdgeIt &e)

  1506 //   {

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

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

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

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

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

  1512 //   }

  1513 //   else {

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

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

  1516 //   return e;

  1517 //   }

  1518 //   }

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

  1520 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1562 //   };

  1564 } //namespace hugo

  1566 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Wed, 07 Apr 2004 11:02:00 +0000
changeset 313	30c5179f296b
parent 311	6635b11938fe
child 317	6e6db1c49bc1
permissions	-rw-r--r--