lemon-0.x: src/work/marci/graph_wrapper.h@6e6db1c49bc1

     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 GraphWrapper {

    11   protected:

    12     Graph* graph;

    14   public:

    15     typedef Graph BaseGraph;

    16     typedef Graph ParentGraph;

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

    19     GraphWrapper(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 Node : public Graph::Node {

    25       friend class GraphWrapper<Graph>;

    26     public:

    27       Node() { }

    28       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }

    29       Node(const Invalid& i) : Graph::Node(i) { }

    30     };

    31     class NodeIt {

    32       friend class GraphWrapper<Graph>;

    33       typename Graph::NodeIt n;

    34      public:

    35       NodeIt() { }

    36       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

    37       NodeIt(const Invalid& i) : n(i) { }

    38       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }

    39       operator Node() const { return Node(typename Graph::Node(n)); }

    40     };

    41 //     class Node : public Graph::Node {

    42 //     public:

    43 //       Node() { }

    44 //       Node(const typename Graph::Node& n) : Graph::Node(n) { }

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

    46 //     };

    47 //     class NodeIt : public Graph::NodeIt {

    48 //       typedef typename Graph::NodeIt GraphNodeIt;

    49 //     public:

    50 //       NodeIt() { }

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

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

    53 //       NodeIt(const GraphWrapper<Graph>& _G) :

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

    55 //       operator Node() const {

    56 // 	return Node(typename Graph::Node(

    57 // 		      static_cast<typename Graph::NodeIt>(*this)

    58 // 		      ));

    59 //       }

    60 //     };

    61 //    typedef typename Graph::Edge Edge;

    62     class Edge : public Graph::Edge {

    63       friend class GraphWrapper<Graph>;

    64     public:

    65       Edge() { }

    66       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }

    67       Edge(const Invalid& i) : Graph::Edge(i) { }

    68     };

    69     class OutEdgeIt {

    70       friend class GraphWrapper<Graph>;

    71 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

    72       typename Graph::OutEdgeIt e;

    73     public:

    74       OutEdgeIt() { }

    75       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

    76       OutEdgeIt(const Invalid& i) : e(i) { }

    77       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :

    78 	e(*(_G.graph), typename Graph::Node(_n)) { }

    79       operator Edge() const { return Edge(typename Graph::Edge(e)); }

    80     };

    81     class InEdgeIt {

    82       friend class GraphWrapper<Graph>;

    83 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

    84       typename Graph::InEdgeIt e;

    85     public:

    86       InEdgeIt() { }

    87       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

    88       InEdgeIt(const Invalid& i) : e(i) { }

    89       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :

    90 	e(*(_G.graph), typename Graph::Node(_n)) { }

    91       operator Edge() const { return Edge(typename Graph::Edge(e)); }

    92     };

    93     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    94     class EdgeIt {

    95       friend class GraphWrapper<Graph>;

    96 //      typedef typename Graph::EdgeIt GraphEdgeIt;

    97       typename Graph::EdgeIt e;

    98     public:

    99       EdgeIt() { }

   100       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

   101       EdgeIt(const Invalid& i) : e(i) { }

   102       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }

   103       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   104     };

   106     NodeIt& first(NodeIt& i) const {

   107       i=NodeIt(*this); return i;

   108     }

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

   110       i=OutEdgeIt(*this, p); return i;

   111     }

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

   113       i=InEdgeIt(*this, p); return i;

   114     }

   115     EdgeIt& first(EdgeIt& i) const {

   116       i=EdgeIt(*this); return i;

   117     }

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

   119 //       i=I(*this);

   120 //       return i;

   121 //     }

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

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

   124 //       return i;

   125 //     }

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

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

   130     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }

   131     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }

   132     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }

   133     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }

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

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

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

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

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

   141     Node head(const Edge& e) const {

   142       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }

   143     Node tail(const Edge& e) const {

   144       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }

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

   147     bool valid(const Node& n) const {

   148       return graph->valid(static_cast<typename Graph::Node>(n)); }

   149     bool valid(const Edge& e) const {

   150       return graph->valid(static_cast<typename Graph::Edge>(e)); }

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

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

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

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

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

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

   160     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   161     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   162     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }

   163     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

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

   165 //       return Node(graph->aNode(e.e)); }

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

   167 //       return Node(graph->bNode(e.e)); }

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

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

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

   173     void erase(const Node& i) const { graph->erase(i); }

   174     void erase(const Edge& i) const { graph->erase(i); }

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

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

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

   180     public:

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

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

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

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

   185 //       T operator[](const Node& n) const {

   186 // 	return Graph::NodeMap<T>::operator[](n);

   187 //       }

   188     };

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

   191     public:

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

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

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

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

   196     };

   197   };

   200 //   template<typename Graph>

   201 //   class RevGraphWrapper

   202 //   {

   203 //   protected:

   204 //     Graph* graph;

   206 //   public:

   207 //     typedef Graph ParentGraph;

   209 //     typedef typename Graph::Node Node;

   210 //     typedef typename Graph::NodeIt NodeIt;

   212 //     typedef typename Graph::Edge Edge;

   213 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   214 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   215 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   216 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   264 //     public:

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

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

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

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

   269 //     };

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

   272 //     public:

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

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

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

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

   277 //     };

   278 //   };

   281   template<typename Graph>

   282   class RevGraphWrapper : public GraphWrapper<Graph> {

   283   public:

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

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

   286     //FIXME

   287     //If Graph::OutEdgeIt is not defined

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

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

   290     //OR

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

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

   293     //unlike other stuff

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

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

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

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

   300     Node head(const Edge& e) const

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

   302     Node tail(const Edge& e) const

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

   304   };

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

   307   template<typename Graph, typename NodeFilterMap,

   308 	   typename EdgeFilterMap>

   309   class SubGraphWrapper : public GraphWrapper<Graph> {

   310   protected:

   311     NodeFilterMap* node_filter_map;

   312     EdgeFilterMap* edge_filter_map;

   313   public:

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

   315     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   316 		    EdgeFilterMap& _edge_filter_map) :

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

   318       edge_filter_map(&_edge_filter_map) { }

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

   321     class NodeIt {

   322       friend class GraphWrapper<Graph>;

   323       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   324       typename Graph::NodeIt n;

   325      public:

   326       NodeIt() { }

   327       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

   328       NodeIt(const Invalid& i) : n(i) { }

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

   330 	n(*(_G.graph)) {

   331 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])

   332 	  _G.graph->next(n);

   333       }

   334       operator Node() const { return Node(typename Graph::Node(n)); }

   335     };

   336 //     class NodeIt : public Graph::NodeIt {

   337 // //      typedef typename Graph::NodeIt GraphNodeIt;

   338 //     public:

   339 //       NodeIt() { }

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

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

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

   343 // 	Graph::NodeIt(*(_G.graph)) {

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

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

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

   347 //       }

   348 //     };

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

   350     class OutEdgeIt {

   351       friend class GraphWrapper<Graph>;

   352       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   353 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   354       typename Graph::OutEdgeIt e;

   355     public:

   356       OutEdgeIt() { }

   357       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

   358       OutEdgeIt(const Invalid& i) : e(i) { }

   359       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,

   360 		const Node& _n) :

   361 	e(*(_G.graph), typename Graph::Node(_n)) {

   362       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])

   363 	  _G.graph->next(e);

   364       }

   365       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   366     };

   367     class InEdgeIt {

   368       friend class GraphWrapper<Graph>;

   369       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   370 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   371       typename Graph::InEdgeIt e;

   372     public:

   373       InEdgeIt() { }

   374       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

   375       InEdgeIt(const Invalid& i) : e(i) { }

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

   377 	       const Node& _n) :

   378 	e(*(_G.graph), typename Graph::Node(_n)) {

   379       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])

   380 	  _G.graph->next(e);

   381       }

   382       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   383     };

   384     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   385     class EdgeIt {

   386       friend class GraphWrapper<Graph>;

   387       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;

   388 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   389       typename Graph::EdgeIt e;

   390     public:

   391       EdgeIt() { }

   392       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

   393       EdgeIt(const Invalid& i) : e(i) { }

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

   395 	e(*(_G.graph)) {

   396       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])

   397 	  _G.graph->next(e);

   398       }

   399       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   400     };

   401 //       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   402 //     };

   403 //     class OutEdgeIt : public Graph::OutEdgeIt {

   404 // //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   405 //     public:

   406 //       OutEdgeIt() { }

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

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

   409 //       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&

   410 // 		_G, const Node& n) :

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

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

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

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

   415 //       }

   416 //     };

   417 //     class InEdgeIt : public Graph::InEdgeIt {

   418 // //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   419 //     public:

   420 //       InEdgeIt() { }

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

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

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

   424 // 	       const Node& n) :

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

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

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

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

   429 //       }

   430 //     };

   431 // //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   432 //     class EdgeIt : public Graph::EdgeIt {

   433 // //      typedef typename Graph::EdgeIt GraphEdgeIt;

   434 //     public:

   435 //       EdgeIt() { }

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

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

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

   439 // 	Graph::EdgeIt(*(_G.graph)) {

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

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

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

   443 //       }

   444 //     };

   447     NodeIt& first(NodeIt& i) const {

   448       i=NodeIt(*this); return i;

   449     }

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

   451       i=OutEdgeIt(*this, p); return i;

   452     }

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

   454       i=InEdgeIt(*this, p); return i;

   455     }

   456     EdgeIt& first(EdgeIt& i) const {

   457       i=EdgeIt(*this); return i;

   458     }

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

   461 //       graph->first(i);

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

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

   464 //       return i;

   465 //     }

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

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

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

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

   470 //       return i;

   471 //     }

   473     NodeIt& next(NodeIt& i) const {

   474       graph->next(i.n);

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

   476       return i;

   477     }

   478     OutEdgeIt& next(OutEdgeIt& i) const {

   479       graph->next(i.e);

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

   481       return i;

   482     }

   483     InEdgeIt& next(InEdgeIt& i) const {

   484       graph->next(i.e);

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

   486       return i;

   487     }

   488     EdgeIt& next(EdgeIt& i) const {

   489       graph->next(i.e);

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

   491       return i;

   492     }

   495     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   496     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }

   497     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }

   498     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

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

   501     //  return gw.getNext(i);

   502     //}

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

   504 //       graph->next(i);

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

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

   507 //       return i;

   508 //     }

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

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

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

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

   515   };

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

   518 //   template<typename Graph, typename NodeFilterMap,

   519 // 	   typename EdgeFilterMap>

   520 //   class SubGraphWrapper : public GraphWrapper<Graph> {

   521 //   protected:

   522 //     NodeFilterMap* node_filter_map;

   523 //     EdgeFilterMap* edge_filter_map;

   524 //   public:

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

   526 //     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   527 // 		    EdgeFilterMap& _edge_filter_map) :

   528 //       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),

   529 //       edge_filter_map(&_edge_filter_map) { }

   532 //     typedef typename Graph::Node Node;

   533 //     class NodeIt : public Graph::NodeIt {

   534 // //      typedef typename Graph::NodeIt GraphNodeIt;

   535 //     public:

   536 //       NodeIt() { }

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

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

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

   540 // 	Graph::NodeIt(*(_G.graph)) {

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

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

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

   544 //       }

   545 //     };

   546 //     typedef typename Graph::Edge Edge;

   547 //     class OutEdgeIt : public Graph::OutEdgeIt {

   548 // //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   549 //     public:

   550 //       OutEdgeIt() { }

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

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

   553 //       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&

   554 // 		_G, const Node& n) :

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

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

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

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

   559 //       }

   560 //     };

   561 //     class InEdgeIt : public Graph::InEdgeIt {

   562 // //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   563 //     public:

   564 //       InEdgeIt() { }

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

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

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

   568 // 	       const Node& n) :

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

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

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

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

   573 //       }

   574 //     };

   575 // //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   576 //     class EdgeIt : public Graph::EdgeIt {

   577 // //      typedef typename Graph::EdgeIt GraphEdgeIt;

   578 //     public:

   579 //       EdgeIt() { }

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

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

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

   583 // 	Graph::EdgeIt(*(_G.graph)) {

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

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

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

   587 //       }

   588 //     };

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

   591 //       i=NodeIt(*this);

   592 //       return i;

   593 //     }

   594 //     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {

   595 //       i=OutEdgeIt(*this, n);

   596 //       return i;

   597 //     }

   598 //     InEdgeIt& first(InEdgeIt& i, const Node& n) const {

   599 //       i=InEdgeIt(*this, n);

   600 //       return i;

   601 //     }

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

   603 //       i=EdgeIt(*this);

   604 //       return i;

   605 //     }

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

   608 // //       graph->first(i);

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

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

   611 // //       return i;

   612 // //     }

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

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

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

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

   617 // //       return i;

   618 // //     }

   620 //     NodeIt& next(NodeIt& i) const {

   621 //       graph->next(i);

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

   623 //       return i;

   624 //     }

   625 //     OutEdgeIt& next(OutEdgeIt& i) const {

   626 //       graph->next(i);

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

   628 //       return i;

   629 //     }

   630 //     InEdgeIt& next(InEdgeIt& i) const {

   631 //       graph->next(i);

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

   633 //       return i;

   634 //     }

   635 //     EdgeIt& next(EdgeIt& i) const {

   636 //       graph->next(i);

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

   638 //       return i;

   639 //     }

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

   642 //     //  return gw.getNext(i);

   643 //     //}

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

   645 // //       graph->next(i);

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

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

   648 // //       return i;

   649 // //     }

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

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

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

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

   656 //   };

   658 //   template<typename GraphWrapper>

   659 //   class UndirGraphWrapper {

   660 //   protected:

   661 //     //Graph* graph;

   662 //     GraphWrapper gw;

   664 //   public:

   665 //     typedef GraphWrapper ParentGraph;

   667 //     typedef typename GraphWrapper::Node Node;

   668 //     typedef typename GraphWrapper::NodeIt NodeIt;

   670 //     //typedef typename Graph::Edge Edge;

   671 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   672 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   673 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   674 //     //typedef typename Graph::EdgeIt EdgeIt;

   676 //     //private:

   677 //     typedef typename GraphWrapper::Edge GraphEdge;

   678 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   679 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   680 //     //public:

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

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

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

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

   688 //     class Edge {

   689 //       friend class UndirGraphWrapper<GraphWrapper>;

   690 //       bool out_or_in; //true iff out

   691 //       GraphOutEdgeIt out;

   692 //       GraphInEdgeIt in;

   693 //     public:

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

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

   696 //       operator GraphEdge() const {

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

   698 //       }

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

   700 // 	if (v.out_or_in)

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

   702 // 	else

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

   704 //       }

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

   706 // 	if (v.out_or_in)

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

   708 // 	else

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

   710 //       }

   711 //     };

   713 //     class OutEdgeIt : public Edge {

   714 //       friend class UndirGraphWrapper<GraphWrapper>;

   715 //     public:

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

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

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

   719 // 	: Edge() {

   720 // 	out_or_in=true;

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

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

   723 // 	  out_or_in=false;

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

   725 // 	}

   726 //       }

   727 //     };

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

   730 //       e.out_or_in=true;

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

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

   733 // 	e.out_or_in=false;

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

   735 //       }

   736 //       return e;

   737 //     }

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

   740 //       if (e.out_or_in) {

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

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

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

   744 // 	  e.out_or_in=false;

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

   746 // 	}

   747 //       } else {

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

   749 //       }

   750 //       return e;

   751 //     }

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

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

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

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

   758 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   801 //     public:

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

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

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

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

   806 //     };

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

   809 //     public:

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

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

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

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

   814 //     };

   815 //   };

   818   template<typename Graph>

   819   class UndirGraphWrapper : public GraphWrapper<Graph> {

   820 //  protected:

   821 //    typedef typename Graph::Edge GraphEdge;

   822 //    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   823 //    typedef typename Graph::InEdgeIt GraphInEdgeIt;

   824   public:

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

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

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

   828     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;

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

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

   834 //     class Edge {

   835 //       friend class UndirGraphWrapper<Graph>;

   836 //     protected:

   837 //       bool out_or_in; //true iff out

   838 //       GraphOutEdgeIt out;

   839 //       GraphInEdgeIt in;

   840 //     public:

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

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

   843 //       operator GraphEdge() const {

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

   845 //       }

   846 // //FIXME

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

   848 // //is it good?

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

   850 // 	if (v.out_or_in)

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

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

   853 // 	else

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

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

   856 //       }

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

   858 // 	if (v.out_or_in)

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

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

   861 // 	else

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

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

   864 //       }

   865 //     };

   867     class OutEdgeIt {

   868       friend class UndirGraphWrapper<Graph>;

   869       bool out_or_in; //true iff out

   870       typename Graph::OutEdgeIt out;

   871       typename Graph::InEdgeIt in;

   872     public:

   873       OutEdgeIt() { }

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

   875       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {

   876 	out_or_in=true; _G.graph->first(out, _n);

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

   878       }

   879       operator Edge() const {

   880 	if (out_or_in) return Edge(out); else return Edge(in);

   881       }

   882     };

   883 //     class OutEdgeIt : public Edge {

   884 //       friend class UndirGraphWrapper<Graph>;

   885 //     public:

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

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

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

   889 // 	: Edge() {

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

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

   892 //       }

   893 //     };

   895 //FIXME InEdgeIt

   896     typedef OutEdgeIt InEdgeIt;

   898 //     class EdgeIt : public Edge {

   899 //       friend class UndirGraphWrapper<Graph>;

   900 //     protected:

   901 //       NodeIt v;

   902 //     public:

   903 //       EdgeIt() : Edge() { }

   904 //       EdgeIt(const Invalid& i) : Edge(i) { }

   905 //       EdgeIt(const UndirGraphWrapper<Graph>& _G)

   906 // 	: Edge() {

   907 // 	out_or_in=true;

   908 // 	//Node v;

   909 // 	_G.first(v);

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

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

   912 // 	  _G.graph->next(v);

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

   914 // 	}

   915 //       }

   916 //     };

   918     NodeIt& first(NodeIt& i) const {

   919       i=NodeIt(*this); return i;

   920     }

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

   922       i=OutEdgeIt(*this, p); return i;

   923     }

   924 //FIXME

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

   926 //       i=InEdgeIt(*this, p); return i;

   927 //     }

   928     EdgeIt& first(EdgeIt& i) const {

   929       i=EdgeIt(*this); return i;

   930     }

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

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

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

   936     NodeIt& next(NodeIt& n) const {

   937       GraphWrapper<Graph>::next(n);

   938       return n;

   939     }

   940     OutEdgeIt& next(OutEdgeIt& e) const {

   941       if (e.out_or_in) {

   942 	typename Graph::Node n=graph->tail(e.out);

   943 	graph->next(e.out);

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

   945       } else {

   946 	graph->next(e.in);

   947       }

   948       return e;

   949     }

   950     //FIXME InEdgeIt

   951     EdgeIt& next(EdgeIt& e) const {

   952       GraphWrapper<Graph>::next(n);

   953 //      graph->next(e.e);

   954       return e;

   955     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   980     Node aNode(const OutEdgeIt& e) const {

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

   982     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   996 //     public:

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

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

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

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

  1001 //     };

  1003 //     template<typename T> class EdgeMap :

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

  1005 //     public:

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

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

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

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

  1010 //     };

  1011    };

  1017 //   template<typename Graph>

  1018 //   class SymGraphWrapper

  1019 //   {

  1020 //     Graph* graph;

  1022 //   public:

  1023 //     typedef Graph ParentGraph;

  1025 //     typedef typename Graph::Node Node;

  1026 //     typedef typename Graph::Edge Edge;

  1028 //     typedef typename Graph::NodeIt NodeIt;

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

  1031 //     //iranyitatlant, ami van

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

  1033 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

  1035 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1036 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1083 //   };

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

  1089   class ResGraphWrapper : public GraphWrapper<Graph> {

  1090   protected:

  1091 //    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

  1092 //    typedef typename Graph::InEdgeIt GraphInEdgeIt;

  1093 //    typedef typename Graph::Edge GraphEdge;

  1094     FlowMap* flow;

  1095     const CapacityMap* capacity;

  1096   public:

  1098     ResGraphWrapper(Graph& _graph, FlowMap& _flow,

  1099 		    const CapacityMap& _capacity) :

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

  1102     class Edge;

  1103     class OutEdgeIt;

  1104     friend class Edge;

  1105     friend class OutEdgeIt;

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

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

  1109     class Edge : public Graph::Edge {

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

  1111     protected:

  1112       bool forward; //true, iff forward

  1113 //      typename Graph::Edge e;

  1114     public:

  1115       Edge() { }

  1116       Edge(const typename Graph::Edge& _e, bool _forward) :

  1117 	Graph::Edge(_e), forward(_forward) { }

  1118       Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }

  1119 //the unique invalid iterator

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

  1121 	return (v.forward==u.forward &&

  1122 		static_cast<typename Graph::Edge>(u)==

  1123 		static_cast<typename Graph::Edge>(v));

  1124       }

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

  1126 	return (v.forward!=u.forward ||

  1127 		static_cast<typename Graph::Edge>(u)!=

  1128 		static_cast<typename Graph::Edge>(v));

  1129       }

  1130     };

  1131 //     class Edge {

  1132 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1133 //     protected:

  1134 //       bool out_or_in; //true, iff out

  1135 //       GraphOutEdgeIt out;

  1136 //       GraphInEdgeIt in;

  1137 //     public:

  1138 //       Edge() : out_or_in(true) { }

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

  1140 // //       bool valid() const {

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

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

  1143 // 	if (v.out_or_in)

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

  1145 // 	else

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

  1147 //       }

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

  1149 // 	if (v.out_or_in)

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

  1151 // 	else

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

  1153 //       }

  1154 //       operator GraphEdge() const {

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

  1156 //       }

  1157 //     };

  1158     class OutEdgeIt {

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

  1160     protected:

  1161       typename Graph::OutEdgeIt out;

  1162       typename Graph::InEdgeIt in;

  1163       bool forward;

  1164     public:

  1165       OutEdgeIt() { }

  1166       //FIXME

  1167 //      OutEdgeIt(const Edge& e) : Edge(e) { }

  1168       OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }

  1169 //the unique invalid iterator

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

  1171 	forward=true;

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

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

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

  1175 	  forward=false;

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

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

  1178 	}

  1179       }

  1180       operator Edge() const {

  1181 //	Edge e;

  1182 //	e.forward=this->forward;

  1183 //	if (this->forward) e=out; else e=in;

  1184 //	return e;

  1185 	if (this->forward)

  1186 	  return Edge(out, this->forward);

  1187 	else

  1188 	  return Edge(in, this->forward);

  1189       }

  1190     };

  1191 //     class OutEdgeIt : public Edge {

  1192 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1193 //     public:

  1194 //       OutEdgeIt() { }

  1195 //       //FIXME

  1196 //       OutEdgeIt(const Edge& e) : Edge(e) { }

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

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

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

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

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

  1202 // 	  out_or_in=0;

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

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

  1205 // 	}

  1206 //       }

  1207 //     public:

  1208 //       OutEdgeIt& operator++() {

  1209 // 	if (out_or_in) {

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

  1211 // 	  ++out;

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

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

  1214 // 	    out_or_in=0;

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

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

  1217 // 	  }

  1218 // 	} else {

  1219 // 	  ++in;

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

  1221 // 	}

  1222 // 	return *this;

  1223 //       }

  1224 //    };

  1226     //FIXME This is just for having InEdgeIt

  1227 //    class InEdgeIt : public Edge { };

  1229     class InEdgeIt {

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

  1231     protected:

  1232       typename Graph::OutEdgeIt out;

  1233       typename Graph::InEdgeIt in;

  1234       bool forward;

  1235     public:

  1236       InEdgeIt() { }

  1237       //FIXME

  1238 //      OutEdgeIt(const Edge& e) : Edge(e) { }

  1239       InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }

  1240 //the unique invalid iterator

  1241       InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {

  1242 	forward=true;

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

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

  1245 	if (!resG.graph->valid(in)) {

  1246 	  forward=false;

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

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

  1249 	}

  1250       }

  1251       operator Edge() const {

  1252 //	Edge e;

  1253 //	e.forward=this->forward;

  1254 //	if (this->forward) e=out; else e=in;

  1255 //	return e;

  1256 	if (this->forward)

  1257 	  return Edge(in, this->forward);

  1258 	else

  1259 	  return Edge(out, this->forward);

  1260       }

  1261     };

  1263     class EdgeIt {

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

  1265     protected:

  1266       typename Graph::EdgeIt e;

  1267       bool forward;

  1268     public:

  1269       EdgeIt() { }

  1270       EdgeIt(const Invalid& i) : e(i), forward(false) { }

  1271       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {

  1272 	forward=true;

  1273 	resG.graph->first(e);

  1274 	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);

  1275 	if (!resG.graph->valid(e)) {

  1276 	  forward=false;

  1277 	  resG.graph->first(e);

  1278 	  while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);

  1279 	}

  1280       }

  1281       operator Edge() const {

  1282 	return Edge(e, this->forward);

  1283       }

  1284     };

  1285 //     class EdgeIt : public Edge {

  1286 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1287 //       NodeIt v;

  1288 //     public:

  1289 //       EdgeIt() { }

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

  1291 //       EdgeIt(const Invalid& i) : Edge(i) { }

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

  1293 // 	resG.graph->first(v);

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

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

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

  1297 // 	  resG.graph->next(v);

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

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

  1300 // 	}

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

  1302 // 	  out_or_in=0;

  1303 // 	  resG.graph->first(v);

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

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

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

  1307 // 	    resG.graph->next(v);

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

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

  1310 // 	  }

  1311 // 	}

  1312 //       }

  1313 //       EdgeIt& operator++() {

  1314 // 	if (out_or_in) {

  1315 // 	  ++out;

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

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

  1318 // 	    ++v;

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

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

  1321 // 	  }

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

  1323 // 	    out_or_in=0;

  1324 // 	    G->first(v);

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

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

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

  1328 // 	      ++v;

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

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

  1331 // 	    }

  1332 // 	  }

  1333 // 	} else {

  1334 // 	  ++in;

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

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

  1337 // 	    ++v;

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

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

  1340 // 	  }

  1341 // 	}

  1342 // 	return *this;

  1343 //       }

  1344 //    };

  1346     NodeIt& first(NodeIt& i) const {

  1347       i=NodeIt(*this); return i;

  1348     }

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

  1350       i=OutEdgeIt(*this, p); return i;

  1351     }

  1352 //    FIXME not tested

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

  1354       i=InEdgeIt(*this, p); return i;

  1355     }

  1356     EdgeIt& first(EdgeIt& i) const {

  1357       i=EdgeIt(*this); return i;

  1358     }

  1360     NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }

  1361     OutEdgeIt& next(OutEdgeIt& e) const {

  1362       if (e.forward) {

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

  1364 	graph->next(e.out);

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

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

  1367 	  e.forward=false;

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

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

  1370 	}

  1371       } else {

  1372 	graph->next(e.in);

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

  1374       }

  1375       return e;

  1376     }

  1377 //     FIXME Not tested

  1378     InEdgeIt& next(InEdgeIt& e) const {

  1379       if (e.forward) {

  1380 	Node v=graph->aNode(e.in);

  1381 	graph->next(e.in);

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

  1383 	if (!graph->valid(e.in)) {

  1384 	  e.forward=false;

  1385 	  graph->first(e.out, v);

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

  1387 	}

  1388       } else {

  1389 	graph->next(e.out);

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

  1391       }

  1392       return e;

  1393     }

  1394     EdgeIt& next(EdgeIt& e) const {

  1395       if (e.forward) {

  1396 	graph->next(e.e);

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

  1398 	if (!graph->valid(e.e)) {

  1399 	  e.forward=false;

  1400 	  graph->first(e.e);

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

  1402 	}

  1403       } else {

  1404 	graph->next(e.e);

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

  1406       }

  1407       return e;

  1408     }

  1409 //     EdgeIt& next(EdgeIt& e) const {

  1410 //       if (e.out_or_in) {

  1411 // 	graph->next(e.out);

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

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

  1414 // 	    graph->next(e.v);

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

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

  1417 // 	  }

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

  1419 // 	    e.out_or_in=0;

  1420 // 	    graph->first(e.v);

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

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

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

  1424 // 	      graph->next(e.v);

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

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

  1427 // 	    }

  1428 // 	  }

  1429 // 	} else {

  1430 // 	  graph->next(e.in);

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

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

  1433 // 	    graph->next(e.v);

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

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

  1436 // 	  }

  1437 // 	}

  1438 // 	return e;

  1439 //       }

  1442     template< typename It >

  1443     It first() const {

  1444       It e;

  1445       first(e);

  1446       return e;

  1447     }

  1449     template< typename It >

  1450     It first(Node v) const {

  1451       It e;

  1452       first(e, v);

  1453       return e;

  1454     }

  1456     Node tail(Edge e) const {

  1457       return ((e.forward) ? graph->tail(e) : graph->head(e)); }

  1458     Node head(Edge e) const {

  1459       return ((e.forward) ? graph->head(e) : graph->tail(e)); }

  1461     Node aNode(OutEdgeIt e) const {

  1462       return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }

  1463     Node bNode(OutEdgeIt e) const {

  1464       return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }

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

  1467     //FIXME

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

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

  1473     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }

  1474     bool valid(Edge e) const {

  1475       return graph->valid(e);

  1476 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in);

  1477     }

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

  1480       if (e.forward)

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

  1482 	flow->set(e, (*flow)[e]+a);

  1483       else

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

  1485 	flow->set(e, (*flow)[e]-a);

  1486     }

  1488     Number resCap(const Edge& e) const {

  1489       if (e.forward)

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

  1491 	return ((*capacity)[e]-(*flow)[e]);

  1492       else

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

  1494 	return ((*flow)[e]);

  1495     }

  1497 //     Number resCap(typename Graph::OutEdgeIt out) const {

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

  1499 //       return ((*capacity)[out]-(*flow)[out]);

  1500 //     }

  1502 //     Number resCap(typename Graph::InEdgeIt in) const {

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

  1504 //       return ((*flow)[in]);

  1505 //     }

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

  1508 //     public:

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

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

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

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

  1513 //     };

  1515 //     template <typename T>

  1516 //     class NodeMap {

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

  1518 //     public:

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

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

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

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

  1523 //     };

  1525     template <typename T>

  1526     class EdgeMap {

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

  1528     public:

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

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

  1531       void set(Edge e, T a) {

  1532 	if (e.forward)

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

  1534 	else

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

  1536       }

  1537       T operator[](Edge e) const {

  1538 	if (e.forward)

  1539 	  return forward_map[e.out];

  1540 	else

  1541 	  return backward_map[e.in];

  1542       }

  1543 //       T get(Edge e) const {

  1544 // 	if (e.out_or_in)

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

  1546 // 	else

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

  1548 //       }

  1549     };

  1550   };

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

  1555 //   class ResGraphWrapper : public GraphWrapper<Graph> {

  1556 //   protected:

  1557 //     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

  1558 //     typedef typename Graph::InEdgeIt GraphInEdgeIt;

  1559 //     typedef typename Graph::Edge GraphEdge;

  1560 //     FlowMap* flow;

  1561 //     const CapacityMap* capacity;

  1562 //   public:

  1564 //     ResGraphWrapper(Graph& _graph, FlowMap& _flow,

  1565 // 		    const CapacityMap& _capacity) :

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

  1568 //     class Edge;

  1569 //     class OutEdgeIt;

  1570 //     friend class Edge;

  1571 //     friend class OutEdgeIt;

  1573 //     typedef typename GraphWrapper<Graph>::Node Node;

  1574 //     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;

  1575 //     class Edge {

  1576 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1577 //     protected:

  1578 //       bool out_or_in; //true, iff out

  1579 //       GraphOutEdgeIt out;

  1580 //       GraphInEdgeIt in;

  1581 //     public:

  1582 //       Edge() : out_or_in(true) { }

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

  1584 // //       bool valid() const {

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

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

  1587 // 	if (v.out_or_in)

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

  1589 // 	else

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

  1591 //       }

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

  1593 // 	if (v.out_or_in)

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

  1595 // 	else

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

  1597 //       }

  1598 //       operator GraphEdge() const {

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

  1600 //       }

  1601 //     };

  1602 //     class OutEdgeIt : public Edge {

  1603 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1604 //     public:

  1605 //       OutEdgeIt() { }

  1606 //       //FIXME

  1607 //       OutEdgeIt(const Edge& e) : Edge(e) { }

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

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

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

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

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

  1613 // 	  out_or_in=0;

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

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

  1616 // 	}

  1617 //       }

  1618 // //     public:

  1619 // //       OutEdgeIt& operator++() {

  1620 // // 	if (out_or_in) {

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

  1622 // // 	  ++out;

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

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

  1625 // // 	    out_or_in=0;

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

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

  1628 // // 	  }

  1629 // // 	} else {

  1630 // // 	  ++in;

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

  1632 // // 	}

  1633 // // 	return *this;

  1634 // //       }

  1635 //     };

  1637 //     //FIXME This is just for having InEdgeIt

  1638 // //    class InEdgeIt : public Edge { };

  1640 //     class EdgeIt : public Edge {

  1641 //       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;

  1642 //       NodeIt v;

  1643 //     public:

  1644 //       EdgeIt() { }

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

  1646 //       EdgeIt(const Invalid& i) : Edge(i) { }

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

  1648 // 	resG.graph->first(v);

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

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

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

  1652 // 	  resG.graph->next(v);

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

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

  1655 // 	}

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

  1657 // 	  out_or_in=0;

  1658 // 	  resG.graph->first(v);

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

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

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

  1662 // 	    resG.graph->next(v);

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

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

  1665 // 	  }

  1666 // 	}

  1667 //       }

  1668 // //       EdgeIt& operator++() {

  1669 // // 	if (out_or_in) {

  1670 // // 	  ++out;

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

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

  1673 // // 	    ++v;

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

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

  1676 // // 	  }

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

  1678 // // 	    out_or_in=0;

  1679 // // 	    G->first(v);

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

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

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

  1683 // // 	      ++v;

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

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

  1686 // // 	    }

  1687 // // 	  }

  1688 // // 	} else {

  1689 // // 	  ++in;

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

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

  1692 // // 	    ++v;

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

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

  1695 // // 	  }

  1696 // // 	}

  1697 // // 	return *this;

  1698 // //       }

  1699 //     };

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

  1702 //       i=NodeIt(*this);

  1703 //       return i;

  1704 //     }

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

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

  1707 //       return i;

  1708 //     }

  1709 //     //FIXME Not yet implemented

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

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

  1712 //     //  return i;

  1713 //     //}

  1714 //     EdgeIt& first(EdgeIt& e) const {

  1715 //       e=EdgeIt(*this);

  1716 //       return e;

  1717 //     }

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

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

  1721 //       if (e.out_or_in) {

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

  1723 // 	graph->next(e.out);

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

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

  1726 // 	  e.out_or_in=0;

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

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

  1729 // 	}

  1730 //       } else {

  1731 // 	graph->next(e.in);

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

  1733 //       }

  1734 //       return e;

  1735 //     }

  1736 //     //FIXME Not yet implemented

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

  1738 //     //  return e;

  1739 //     //}

  1740 //     EdgeIt& next(EdgeIt& e) const {

  1741 //       if (e.out_or_in) {

  1742 // 	graph->next(e.out);

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

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

  1745 // 	    graph->next(e.v);

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

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

  1748 // 	  }

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

  1750 // 	    e.out_or_in=0;

  1751 // 	    graph->first(e.v);

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

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

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

  1755 // 	      graph->next(e.v);

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

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

  1758 // 	    }

  1759 // 	  }

  1760 // 	} else {

  1761 // 	  graph->next(e.in);

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

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

  1764 // 	    graph->next(e.v);

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

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

  1767 // 	  }

  1768 // 	}

  1769 // 	return e;

  1770 //       }

  1773 //     template< typename It >

  1774 //     It first() const {

  1775 //       It e;

  1776 //       first(e);

  1777 //       return e;

  1778 //     }

  1780 //     template< typename It >

  1781 //     It first(Node v) const {

  1782 //       It e;

  1783 //       first(e, v);

  1784 //       return e;

  1785 //     }

  1787 //     Node tail(Edge e) const {

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

  1789 //     Node head(Edge e) const {

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

  1792 //     Node aNode(OutEdgeIt e) const {

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

  1794 //     Node bNode(OutEdgeIt e) const {

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

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

  1798 //     //FIXME

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

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

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

  1805 //     bool valid(Edge e) const {

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

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

  1809 //       if (e.out_or_in)

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

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

  1812 //       else

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

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

  1815 //     }

  1817 //     Number resCap(const Edge& e) const {

  1818 //       if (e.out_or_in)

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

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

  1821 //       else

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

  1823 // 	return ((*flow)[e.in]);

  1824 //     }

  1826 //     Number resCap(GraphOutEdgeIt out) const {

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

  1828 //       return ((*capacity)[out]-(*flow)[out]);

  1829 //     }

  1831 //     Number resCap(GraphInEdgeIt in) const {

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

  1833 //       return ((*flow)[in]);

  1834 //     }

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

  1837 // //     public:

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

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

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

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

  1842 // //     };

  1844 // //     template <typename T>

  1845 // //     class NodeMap {

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

  1847 // //     public:

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

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

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

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

  1852 // //     };

  1854 //     template <typename T>

  1855 //     class EdgeMap {

  1856 //       typename Graph::EdgeMap<T> forward_map, backward_map;

  1857 //     public:

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

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

  1860 //       void set(Edge e, T a) {

  1861 // 	if (e.out_or_in)

  1862 // 	  forward_map.set(e.out, a);

  1863 // 	else

  1864 // 	  backward_map.set(e.in, a);

  1865 //       }

  1866 //       T operator[](Edge e) const {

  1867 // 	if (e.out_or_in)

  1868 // 	  return forward_map[e.out];

  1869 // 	else

  1870 // 	  return backward_map[e.in];

  1871 //       }

  1872 // //       T get(Edge e) const {

  1873 // // 	if (e.out_or_in)

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

  1875 // // 	else

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

  1877 // //       }

  1878 //     };

  1879 //   };

  1882   //ErasingFirstGraphWrapper for blocking flows

  1883   template<typename Graph, typename FirstOutEdgesMap>

  1884   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1885   protected:

  1886     FirstOutEdgesMap* first_out_edges;

  1887   public:

  1888     ErasingFirstGraphWrapper(Graph& _graph,

  1889 			     FirstOutEdgesMap& _first_out_edges) :

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

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

  1893     class NodeIt {

  1894       friend class GraphWrapper<Graph>;

  1895       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1896       typename Graph::NodeIt n;

  1897      public:

  1898       NodeIt() { }

  1899       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }

  1900       NodeIt(const Invalid& i) : n(i) { }

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

  1902 	n(*(_G.graph)) { }

  1903       operator Node() const { return Node(typename Graph::Node(n)); }

  1904     };

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

  1906     class OutEdgeIt {

  1907       friend class GraphWrapper<Graph>;

  1908       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1909 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

  1910       typename Graph::OutEdgeIt e;

  1911     public:

  1912       OutEdgeIt() { }

  1913       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }

  1914       OutEdgeIt(const Invalid& i) : e(i) { }

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

  1916 		const Node& _n) :

  1917 	e((*_G.first_out_edges)[_n]) { }

  1918       operator Edge() const { return Edge(typename Graph::Edge(e)); }

  1919     };

  1920     class InEdgeIt {

  1921       friend class GraphWrapper<Graph>;

  1922       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1923 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

  1924       typename Graph::InEdgeIt e;

  1925     public:

  1926       InEdgeIt() { }

  1927       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }

  1928       InEdgeIt(const Invalid& i) : e(i) { }

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

  1930 	       const Node& _n) :

  1931 	e(*(_G.graph), typename Graph::Node(_n)) { }

  1932       operator Edge() const { return Edge(typename Graph::Edge(e)); }

  1933     };

  1934     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1935     class EdgeIt {

  1936       friend class GraphWrapper<Graph>;

  1937       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1938 //      typedef typename Graph::EdgeIt GraphEdgeIt;

  1939       typename Graph::EdgeIt e;

  1940     public:

  1941       EdgeIt() { }

  1942       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }

  1943       EdgeIt(const Invalid& i) : e(i) { }

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

  1945 	e(*(_G.graph)) { }

  1946       operator Edge() const { return Edge(typename Graph::Edge(e)); }

  1947     };

  1949     NodeIt& first(NodeIt& i) const {

  1950       i=NodeIt(*this); return i;

  1951     }

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

  1953       i=OutEdgeIt(*this, p); return i;

  1954     }

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

  1956       i=InEdgeIt(*this, p); return i;

  1957     }

  1958     EdgeIt& first(EdgeIt& i) const {

  1959       i=EdgeIt(*this); return i;

  1960     }

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

  1963 //       graph->first(i);

  1964 //       return i;

  1965 //     }

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

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

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

  1969 //       return e;

  1970 //     }

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

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

  1973 //       return i;

  1974 //     }

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

  1977     //  return gw.getNext(i);

  1978     //}

  1981     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }

  1982     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }

  1983     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }

  1984     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }

  1986     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }

  1987     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }

  1988     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }

  1989     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }

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

  1992 //       graph->next(i);

  1993 //       return i;

  1994 //     }

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

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

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

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

  2002     void erase(const OutEdgeIt& e) const {

  2003       OutEdgeIt f=e;

  2004       this->next(f);

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

  2006     }

  2007   };

  2009 //   //ErasingFirstGraphWrapper for blocking flows

  2010 //   template<typename Graph, typename FirstOutEdgesMap>

  2011 //   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  2012 //   protected:

  2013 //     FirstOutEdgesMap* first_out_edges;

  2014 //   public:

  2015 //     ErasingFirstGraphWrapper(Graph& _graph,

  2016 // 			     FirstOutEdgesMap& _first_out_edges) :

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

  2019 //     typedef typename Graph::Node Node;

  2020 //     class NodeIt : public Graph::NodeIt {

  2021 //     public:

  2022 //       NodeIt() { }

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

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

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

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

  2027 //     };

  2028 //     typedef typename Graph::Edge Edge;

  2029 //     class OutEdgeIt : public Graph::OutEdgeIt {

  2030 //     public:

  2031 //       OutEdgeIt() { }

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

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

  2034 //       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  2035 // 		const Node& n) :

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

  2037 //     };

  2038 //     class InEdgeIt : public Graph::InEdgeIt {

  2039 //     public:

  2040 //       InEdgeIt() { }

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

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

  2043 //       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,

  2044 // 	       const Node& n) :

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

  2046 //     };

  2047 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  2048 //     class EdgeIt : public Graph::EdgeIt {

  2049 //     public:

  2050 //       EdgeIt() { }

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

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

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

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

  2055 //     };

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

  2058 //       i=NodeIt(*this);

  2059 //       return i;

  2060 //     }

  2061 //     OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {

  2062 //       i=OutEdgeIt(*this, n);

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

  2064 //       return i;

  2065 //     }

  2066 //     InEdgeIt& first(InEdgeIt& i, const Node& n) const {

  2067 //       i=InEdgeIt(*this, n);

  2068 //       return i;

  2069 //     }

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

  2071 //       i=EdgeIt(*this);

  2072 //       return i;

  2073 //     }

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

  2076 // //       graph->first(i);

  2077 // //       return i;

  2078 // //     }

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

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

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

  2082 // //       return e;

  2083 // //     }

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

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

  2086 // //       return i;

  2087 // //     }

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

  2090 //     //  return gw.getNext(i);

  2091 //     //}

  2094 //     NodeIt& next(NodeIt& i) const {

  2095 //       graph->next(i);

  2096 //       return i;

  2097 //     }

  2098 //     OutEdgeIt& next(OutEdgeIt& i) const {

  2099 //       graph->next(i);

  2100 //       return i;

  2101 //     }

  2102 //     InEdgeIt& next(InEdgeIt& i) const {

  2103 //       graph->next(i);

  2104 //       return i;

  2105 //     }

  2106 //     EdgeIt& next(EdgeIt& i) const {

  2107 //       graph->next(i);

  2108 //       return i;

  2109 //     }

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

  2112 // //       graph->next(i);

  2113 // //       return i;

  2114 // //     }

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

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

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

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

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

  2123 //       OutEdgeIt f=e;

  2124 //       this->next(f);

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

  2126 //     }

  2127 //   };

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

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

  2132 //   class ResGraphWrapper

  2133 //   {

  2134 //     Graph* graph;

  2136 //   public:

  2137 //     typedef Graph ParentGraph;

  2139 //     typedef typename Graph::Node Node;

  2140 //     typedef typename Graph::Edge Edge;

  2142 //     typedef typename Graph::NodeIt NodeIt;

  2144 //     class OutEdgeIt {

  2145 //     public:

  2146 //       //Graph::Node n;

  2147 //       bool out_or_in;

  2148 //       typename Graph::OutEdgeIt o;

  2149 //       typename Graph::InEdgeIt i;

  2150 //     };

  2151 //     class InEdgeIt {

  2152 //     public:

  2153 //       //Graph::Node n;

  2154 //       bool out_or_in;

  2155 //       typename Graph::OutEdgeIt o;

  2156 //       typename Graph::InEdgeIt i;

  2157 //     };

  2158 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  2159 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  2166 //     // Edge and SymEdge  is missing!!!!

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

  2169 //     //FIXME

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

  2171 //       {

  2172 // 	e.n=n;

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

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

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

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

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

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

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

  2180 // 	}

  2181 // 	return e;

  2182 //       }

  2183 // /*

  2184 //   OutEdgeIt &goNext(OutEdgeIt &e)

  2185 //   {

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

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

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

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

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

  2191 //   }

  2192 //   else {

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

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

  2195 //   return e;

  2196 //   }

  2197 //   }

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

  2199 // */

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

  2202 //     //FIXME

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

  2204 //       {

  2205 // 	e.n=n;

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

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

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

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

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

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

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

  2213 // 	}

  2214 // 	return e;

  2215 //       }

  2216 // /*

  2217 //   InEdgeIt &goNext(InEdgeIt &e)

  2218 //   {

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

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

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

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

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

  2224 //   }

  2225 //   else {

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

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

  2228 //   return e;

  2229 //   }

  2230 //   }

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

  2232 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  2274 //   };

  2276 } //namespace hugo

  2278 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Tue, 13 Apr 2004 20:35:47 +0000
changeset 317	6e6db1c49bc1
parent 312	54e07057eb47
child 318	7bec4e8fb7dd
permissions	-rw-r--r--