lemon-0.x: src/work/marci/graph_wrapper.h@6635b11938fe

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

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_GRAPH_WRAPPER_H

     5 #include <invalid.h>

     7 namespace hugo {

     9   template<typename Graph>

    10   class TrivGraphWrapper {

    11   protected:

    12     Graph* graph;

    14   public:

    15 //    typedef Graph BaseGraph;

    16     typedef Graph ParentGraph;

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

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

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

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

    23     typedef typename Graph::Node Node;

    24     class NodeIt : public Graph::NodeIt {

    25     public:

    26       NodeIt() { }

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

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

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

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

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

    32 //      operator typename BaseGraph::NodeIt() {

    33 //	return typename BaseGraph::NodeIt(this->Graph::NodeIt);

    34 //      }

    35     };

    36     typedef typename Graph::Edge Edge;

    37     class OutEdgeIt : public Graph::OutEdgeIt {

    38     public:

    39       OutEdgeIt() { }

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

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

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

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

    44     };

    45     class InEdgeIt : public Graph::InEdgeIt {

    46     public:

    47       InEdgeIt() { }

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

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

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

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

    52     };

    53     //typedef typename Graph::SymEdgeIt SymEdgeIt;

    54     class EdgeIt : public Graph::EdgeIt {

    55     public:

    56       EdgeIt() { }

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

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

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

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

    61     };

    63     NodeIt& first(NodeIt& i) const {

    64       i=NodeIt(*this);

    65       return i;

    66     }

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

    68 //       i=I(*this);

    69 //       return i;

    70 //     }

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

    72       i=OutEdgeIt(*this, p);

    73       return i;

    74     }

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

    76       i=InEdgeIt(*this, p);

    77       return i;

    78     }

    79     EdgeIt& first(EdgeIt& i) const {

    80       i=EdgeIt(*this);

    81       return i;

    82     }

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

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

    85 //       return i;

    86 //     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   106       return graph->valid(i); }

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

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

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

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

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

   115       return graph->aNode(e); }

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

   117       return graph->bNode(e); }

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

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

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

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

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

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

   128     public:

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

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

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

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

   133     };

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

   136     public:

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

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

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

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

   141     };

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

   144 //     protected:

   145 //       Map* map;

   146 //     public:

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

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

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

   150 //     };

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

   153 //     protected:

   154 //       Map* map;

   155 //     public:

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

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

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

   159 //     };

   160   };

   163   template<typename Graph>

   164   class GraphWrapper {

   165   protected:

   166     Graph* graph;

   168   public:

   169     typedef Graph BaseGraph;

   170     typedef Graph ParentGraph;

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

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

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

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

   177     typedef typename Graph::Node Node;

   178     class NodeIt : public Graph::NodeIt {

   179     public:

   180       NodeIt() { }

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

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

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

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

   185     };

   186     typedef typename Graph::Edge Edge;

   187     class OutEdgeIt : public Graph::OutEdgeIt {

   188     public:

   189       OutEdgeIt() { }

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

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

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

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

   194     };

   195     class InEdgeIt : public Graph::InEdgeIt {

   196     public:

   197       InEdgeIt() { }

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

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

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

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

   202     };

   203     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   204     class EdgeIt : public Graph::EdgeIt {

   205     public:

   206       EdgeIt() { }

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

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

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

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

   211     };

   213     NodeIt& first(NodeIt& i) const {

   214       i=NodeIt(*this);

   215       return i;

   216     }

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

   218 //       i=I(*this);

   219 //       return i;

   220 //     }

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

   222       i=OutEdgeIt(*this, p);

   223       return i;

   224     }

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

   226       i=InEdgeIt(*this, p);

   227       return i;

   228     }

   229     EdgeIt& first(EdgeIt& i) const {

   230       i=EdgeIt(*this);

   231       return i;

   232     }

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

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

   235 //       return i;

   236 //     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   256       return graph->valid(i); }

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

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

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

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

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

   265       return graph->aNode(e); }

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

   267       return graph->bNode(e); }

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

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

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

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

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

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

   278     public:

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

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

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

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

   283     };

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

   286     public:

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

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

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

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

   291     };

   292   };

   295 //   template<typename Graph>

   296 //   class RevGraphWrapper

   297 //   {

   298 //   protected:

   299 //     Graph* graph;

   301 //   public:

   302 //     typedef Graph ParentGraph;

   304 //     typedef typename Graph::Node Node;

   305 //     typedef typename Graph::NodeIt NodeIt;

   307 //     typedef typename Graph::Edge Edge;

   308 //     typedef typename Graph::OutEdgeIt InEdgeIt;

   309 //     typedef typename Graph::InEdgeIt OutEdgeIt;

   310 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   311 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   359 //     public:

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

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

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

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

   364 //     };

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

   367 //     public:

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

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

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

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

   372 //     };

   373 //   };

   376   template<typename Graph>

   377   class RevGraphWrapper : public GraphWrapper<Graph> {

   378   public:

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

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

   381     //FIXME

   382     //If Graph::OutEdgeIt is not defined

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

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

   385     //OR

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

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

   388     //unlike other stuff

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

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

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

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

   395     Node head(const Edge& e) const

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

   397     Node tail(const Edge& e) const

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

   399   };

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

   402   template<typename Graph, typename NodeFilterMap,

   403 	   typename EdgeFilterMap>

   404   class SubGraphWrapper : public GraphWrapper<Graph> {

   405   protected:

   406     NodeFilterMap* node_filter_map;

   407     EdgeFilterMap* edge_filter_map;

   408   public:

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

   410     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   411 		    EdgeFilterMap& _edge_filter_map) :

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

   413       edge_filter_map(&_edge_filter_map) { }

   416     typedef typename Graph::Node Node;

   417     class NodeIt : public Graph::NodeIt {

   418 //      typedef typename Graph::NodeIt GraphNodeIt;

   419     public:

   420       NodeIt() { }

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

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

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

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

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

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

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

   428       }

   429     };

   430     typedef typename Graph::Edge Edge;

   431     class OutEdgeIt : public Graph::OutEdgeIt {

   432 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   433     public:

   434       OutEdgeIt() { }

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

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

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

   438 		_G, const Node& n) :

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

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

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

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

   443       }

   444     };

   445     class InEdgeIt : public Graph::InEdgeIt {

   446 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   447     public:

   448       InEdgeIt() { }

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

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

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

   452 	       const Node& n) :

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

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

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

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

   457       }

   458     };

   459 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   460     class EdgeIt : public Graph::EdgeIt {

   461 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   462     public:

   463       EdgeIt() { }

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

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

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

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

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

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

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

   471       }

   472     };

   474     NodeIt& first(NodeIt& i) const {

   475       i=NodeIt(*this);

   476       return i;

   477     }

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

   479       i=OutEdgeIt(*this, n);

   480       return i;

   481     }

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

   483       i=InEdgeIt(*this, n);

   484       return i;

   485     }

   486     EdgeIt& first(EdgeIt& i) const {

   487       i=EdgeIt(*this);

   488       return i;

   489     }

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

   492 //       graph->first(i);

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

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

   495 //       return i;

   496 //     }

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

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

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

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

   501 //       return i;

   502 //     }

   504     NodeIt& next(NodeIt& i) const {

   505       graph->next(i);

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

   507       return i;

   508     }

   509     OutEdgeIt& next(OutEdgeIt& i) const {

   510       graph->next(i);

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

   512       return i;

   513     }

   514     InEdgeIt& next(InEdgeIt& i) const {

   515       graph->next(i);

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

   517       return i;

   518     }

   519     EdgeIt& next(EdgeIt& i) const {

   520       graph->next(i);

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

   522       return i;

   523     }

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

   526     //  return gw.getNext(i);

   527     //}

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

   529 //       graph->next(i);

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

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

   532 //       return i;

   533 //     }

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

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

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

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

   540   };

   542 //   template<typename GraphWrapper>

   543 //   class UndirGraphWrapper {

   544 //   protected:

   545 //     //Graph* graph;

   546 //     GraphWrapper gw;

   548 //   public:

   549 //     typedef GraphWrapper ParentGraph;

   551 //     typedef typename GraphWrapper::Node Node;

   552 //     typedef typename GraphWrapper::NodeIt NodeIt;

   554 //     //typedef typename Graph::Edge Edge;

   555 //     //typedef typename Graph::OutEdgeIt OutEdgeIt;

   556 //     //typedef typename Graph::InEdgeIt InEdgeIt;

   557 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   558 //     //typedef typename Graph::EdgeIt EdgeIt;

   560 //     //private:

   561 //     typedef typename GraphWrapper::Edge GraphEdge;

   562 //     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;

   563 //     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;

   564 //     //public:

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

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

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

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

   572 //     class Edge {

   573 //       friend class UndirGraphWrapper<GraphWrapper>;

   574 //       bool out_or_in; //true iff out

   575 //       GraphOutEdgeIt out;

   576 //       GraphInEdgeIt in;

   577 //     public:

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

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

   580 //       operator GraphEdge() const {

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

   582 //       }

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

   584 // 	if (v.out_or_in)

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

   586 // 	else

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

   588 //       }

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

   590 // 	if (v.out_or_in)

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

   592 // 	else

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

   594 //       }

   595 //     };

   597 //     class OutEdgeIt : public Edge {

   598 //       friend class UndirGraphWrapper<GraphWrapper>;

   599 //     public:

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

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

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

   603 // 	: Edge() {

   604 // 	out_or_in=true;

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

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

   607 // 	  out_or_in=false;

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

   609 // 	}

   610 //       }

   611 //     };

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

   614 //       e.out_or_in=true;

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

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

   617 // 	e.out_or_in=false;

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

   619 //       }

   620 //       return e;

   621 //     }

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

   624 //       if (e.out_or_in) {

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

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

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

   628 // 	  e.out_or_in=false;

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

   630 // 	}

   631 //       } else {

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

   633 //       }

   634 //       return e;

   635 //     }

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

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

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

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

   642 //     typedef OutEdgeIt InEdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   685 //     public:

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

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

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

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

   690 //     };

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

   693 //     public:

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

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

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

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

   698 //     };

   699 //   };

   702   template<typename Graph>

   703   class UndirGraphWrapper : public GraphWrapper<Graph> {

   704   protected:

   705     typedef typename Graph::Edge GraphEdge;

   706     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   707     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   708   public:

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

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

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

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

   715     class Edge {

   716       friend class UndirGraphWrapper<Graph>;

   717     protected:

   718       bool out_or_in; //true iff out

   719       GraphOutEdgeIt out;

   720       GraphInEdgeIt in;

   721     public:

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

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

   724       operator GraphEdge() const {

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

   726       }

   727 //FIXME

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

   729 //is it good?

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

   731 	if (v.out_or_in)

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

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

   734 	else

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

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

   737       }

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

   739 	if (v.out_or_in)

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

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

   742 	else

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

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

   745       }

   746     };

   748     class OutEdgeIt : public Edge {

   749       friend class UndirGraphWrapper<Graph>;

   750     public:

   751       OutEdgeIt() : Edge() { }

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

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

   754 	: Edge() {

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

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

   757       }

   758     };

   760     typedef OutEdgeIt InEdgeIt;

   762     class EdgeIt : public Edge {

   763       friend class UndirGraphWrapper<Graph>;

   764     protected:

   765       NodeIt v;

   766     public:

   767       EdgeIt() : Edge() { }

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

   769       EdgeIt(const UndirGraphWrapper<Graph>& _G)

   770 	: Edge() {

   771 	out_or_in=true;

   772 	//Node v;

   773 	_G.first(v);

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

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

   776 	  _G.graph->next(v);

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

   778 	}

   779       }

   780     };

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

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

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

   785       return e;

   786     }

   788     EdgeIt& first(EdgeIt& e) const {

   789       e.out_or_in=true;

   790       //NodeIt v;

   791       first(e.v);

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

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

   794 	graph->next(e.v);

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

   796       }

   797       return e;

   798     }

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

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

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

   804     OutEdgeIt& next(OutEdgeIt& e) const {

   805       if (e.out_or_in) {

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

   807 	graph->next(e.out);

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

   809       } else {

   810 	graph->next(e.in);

   811       }

   812       return e;

   813     }

   815     EdgeIt& next(EdgeIt& e) const {

   816       //NodeIt v=tail(e);

   817       graph->next(e.out);

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

   819 	next(e.v);

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

   821       }

   822       return e;

   823     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   848     Node aNode(const OutEdgeIt& e) const {

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

   850     Node bNode(const OutEdgeIt& e) const {

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

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

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

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

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

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

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

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

   864 //     public:

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

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

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

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

   869 //     };

   871 //     template<typename T> class EdgeMap :

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

   873 //     public:

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

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

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

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

   878 //     };

   879    };

   885 //   template<typename Graph>

   886 //   class SymGraphWrapper

   887 //   {

   888 //     Graph* graph;

   890 //   public:

   891 //     typedef Graph ParentGraph;

   893 //     typedef typename Graph::Node Node;

   894 //     typedef typename Graph::Edge Edge;

   896 //     typedef typename Graph::NodeIt NodeIt;

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

   899 //     //iranyitatlant, ami van

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

   901 //     typedef typename Graph::OutEdgeIt SymEdgeIt;

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

   903 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   904 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   951 //   };

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

   955   class ResGraphWrapper : public GraphWrapper<Graph> {

   956   protected:

   957     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   958     typedef typename Graph::InEdgeIt GraphInEdgeIt;

   959     typedef typename Graph::Edge GraphEdge;

   960     FlowMap* flow;

   961     const CapacityMap* capacity;

   962   public:

   964     ResGraphWrapper(Graph& _graph, FlowMap& _flow,

   965 		    const CapacityMap& _capacity) :

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

   968     class Edge;

   969     class OutEdgeIt;

   970     friend class Edge;

   971     friend class OutEdgeIt;

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

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

   975     class Edge {

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

   977     protected:

   978       bool out_or_in; //true, iff out

   979       GraphOutEdgeIt out;

   980       GraphInEdgeIt in;

   981     public:

   982       Edge() : out_or_in(true) { }

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

   984 //       bool valid() const {

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

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

   987 	if (v.out_or_in)

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

   989 	else

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

   991       }

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

   993 	if (v.out_or_in)

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

   995 	else

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

   997       }

   998       operator GraphEdge() const {

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

  1000       }

  1001     };

  1002     class OutEdgeIt : public Edge {

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

  1004     public:

  1005       OutEdgeIt() { }

  1006       //FIXME

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

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

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

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

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

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

  1013 	  out_or_in=0;

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

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

  1016 	}

  1017       }

  1018 //     public:

  1019 //       OutEdgeIt& operator++() {

  1020 // 	if (out_or_in) {

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

  1022 // 	  ++out;

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

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

  1025 // 	    out_or_in=0;

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

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

  1028 // 	  }

  1029 // 	} else {

  1030 // 	  ++in;

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

  1032 // 	}

  1033 // 	return *this;

  1034 //       }

  1035     };

  1037     //FIXME This is just for having InEdgeIt

  1038 //    class InEdgeIt : public Edge { };

  1040     class EdgeIt : public Edge {

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

  1042       NodeIt v;

  1043     public:

  1044       EdgeIt() { }

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

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

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

  1048 	resG.graph->first(v);

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

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

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

  1052 	  resG.graph->next(v);

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

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

  1055 	}

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

  1057 	  out_or_in=0;

  1058 	  resG.graph->first(v);

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

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

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

  1062 	    resG.graph->next(v);

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

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

  1065 	  }

  1066 	}

  1067       }

  1068 //       EdgeIt& operator++() {

  1069 // 	if (out_or_in) {

  1070 // 	  ++out;

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

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

  1073 // 	    ++v;

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

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

  1076 // 	  }

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

  1078 // 	    out_or_in=0;

  1079 // 	    G->first(v);

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

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

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

  1083 // 	      ++v;

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

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

  1086 // 	    }

  1087 // 	  }

  1088 // 	} else {

  1089 // 	  ++in;

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

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

  1092 // 	    ++v;

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

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

  1095 // 	  }

  1096 // 	}

  1097 // 	return *this;

  1098 //       }

  1099     };

  1101     NodeIt& first(NodeIt& i) const {

  1102       i=NodeIt(*this);

  1103       return i;

  1104     }

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

  1106       i=OutEdgeIt(*this, p);

  1107       return i;

  1108     }

  1109     //FIXME Not yet implemented

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

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

  1112     //  return i;

  1113     //}

  1114     EdgeIt& first(EdgeIt& e) const {

  1115       e=EdgeIt(*this);

  1116       return e;

  1117     }

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

  1120     OutEdgeIt& next(OutEdgeIt& e) const {

  1121       if (e.out_or_in) {

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

  1123 	graph->next(e.out);

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

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

  1126 	  e.out_or_in=0;

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

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

  1129 	}

  1130       } else {

  1131 	graph->next(e.in);

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

  1133       }

  1134       return e;

  1135     }

  1136     //FIXME Not yet implemented

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

  1138     //  return e;

  1139     //}

  1140     EdgeIt& next(EdgeIt& e) const {

  1141       if (e.out_or_in) {

  1142 	graph->next(e.out);

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

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

  1145 	    graph->next(e.v);

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

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

  1148 	  }

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

  1150 	    e.out_or_in=0;

  1151 	    graph->first(e.v);

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

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

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

  1155 	      graph->next(e.v);

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

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

  1158 	    }

  1159 	  }

  1160 	} else {

  1161 	  graph->next(e.in);

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

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

  1164 	    graph->next(e.v);

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

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

  1167 	  }

  1168 	}

  1169 	return e;

  1170       }

  1173     template< typename It >

  1174     It first() const {

  1175       It e;

  1176       first(e);

  1177       return e;

  1178     }

  1180     template< typename It >

  1181     It first(Node v) const {

  1182       It e;

  1183       first(e, v);

  1184       return e;

  1185     }

  1187     Node tail(Edge e) const {

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

  1189     Node head(Edge e) const {

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

  1192     Node aNode(OutEdgeIt e) const {

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

  1194     Node bNode(OutEdgeIt e) const {

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

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

  1198     //FIXME

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

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

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

  1205     bool valid(Edge e) const {

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

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

  1209       if (e.out_or_in)

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

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

  1212       else

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

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

  1215     }

  1217     Number resCap(const Edge& e) const {

  1218       if (e.out_or_in)

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

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

  1221       else

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

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

  1224     }

  1226     Number resCap(GraphOutEdgeIt out) const {

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

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

  1229     }

  1231     Number resCap(GraphInEdgeIt in) const {

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

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

  1234     }

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

  1237 //     public:

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

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

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

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

  1242 //     };

  1244 //     template <typename T>

  1245 //     class NodeMap {

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

  1247 //     public:

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

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

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

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

  1252 //     };

  1254     template <typename T>

  1255     class EdgeMap {

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

  1257     public:

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

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

  1260       void set(Edge e, T a) {

  1261 	if (e.out_or_in)

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

  1263 	else

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

  1265       }

  1266       T operator[](Edge e) const {

  1267 	if (e.out_or_in)

  1268 	  return forward_map[e.out];

  1269 	else

  1270 	  return backward_map[e.in];

  1271       }

  1272 //       T get(Edge e) const {

  1273 // 	if (e.out_or_in)

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

  1275 // 	else

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

  1277 //       }

  1278     };

  1279   };

  1281   //ErasingFirstGraphWrapper for blocking flows

  1282   template<typename Graph, typename FirstOutEdgesMap>

  1283   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1284   protected:

  1285     FirstOutEdgesMap* first_out_edges;

  1286   public:

  1287     ErasingFirstGraphWrapper(Graph& _graph,

  1288 			     FirstOutEdgesMap& _first_out_edges) :

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

  1291     typedef typename Graph::Node Node;

  1292     class NodeIt : public Graph::NodeIt {

  1293     public:

  1294       NodeIt() { }

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

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

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

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

  1299     };

  1300     typedef typename Graph::Edge Edge;

  1301     class OutEdgeIt : public Graph::OutEdgeIt {

  1302     public:

  1303       OutEdgeIt() { }

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

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

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

  1307 		const Node& n) :

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

  1309     };

  1310     class InEdgeIt : public Graph::InEdgeIt {

  1311     public:

  1312       InEdgeIt() { }

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

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

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

  1316 	       const Node& n) :

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

  1318     };

  1319     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1320     class EdgeIt : public Graph::EdgeIt {

  1321     public:

  1322       EdgeIt() { }

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

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

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

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

  1327     };

  1329     NodeIt& first(NodeIt& i) const {

  1330       i=NodeIt(*this);

  1331       return i;

  1332     }

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

  1334       i=OutEdgeIt(*this, n);

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

  1336       return i;

  1337     }

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

  1339       i=InEdgeIt(*this, n);

  1340       return i;

  1341     }

  1342     EdgeIt& first(EdgeIt& i) const {

  1343       i=EdgeIt(*this);

  1344       return i;

  1345     }

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

  1348 //       graph->first(i);

  1349 //       return i;

  1350 //     }

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

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

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

  1354 //       return e;

  1355 //     }

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

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

  1358 //       return i;

  1359 //     }

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

  1362     //  return gw.getNext(i);

  1363     //}

  1366     NodeIt& next(NodeIt& i) const {

  1367       graph->next(i);

  1368       return i;

  1369     }

  1370     OutEdgeIt& next(OutEdgeIt& i) const {

  1371       graph->next(i);

  1372       return i;

  1373     }

  1374     InEdgeIt& next(InEdgeIt& i) const {

  1375       graph->next(i);

  1376       return i;

  1377     }

  1378     EdgeIt& next(EdgeIt& i) const {

  1379       graph->next(i);

  1380       return i;

  1381     }

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

  1384 //       graph->next(i);

  1385 //       return i;

  1386 //     }

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

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

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

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

  1394     void erase(const OutEdgeIt& e) const {

  1395       OutEdgeIt f=e;

  1396       this->next(f);

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

  1398     }

  1399   };

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

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

  1403 //   class ResGraphWrapper

  1404 //   {

  1405 //     Graph* graph;

  1407 //   public:

  1408 //     typedef Graph ParentGraph;

  1410 //     typedef typename Graph::Node Node;

  1411 //     typedef typename Graph::Edge Edge;

  1413 //     typedef typename Graph::NodeIt NodeIt;

  1415 //     class OutEdgeIt {

  1416 //     public:

  1417 //       //Graph::Node n;

  1418 //       bool out_or_in;

  1419 //       typename Graph::OutEdgeIt o;

  1420 //       typename Graph::InEdgeIt i;

  1421 //     };

  1422 //     class InEdgeIt {

  1423 //     public:

  1424 //       //Graph::Node n;

  1425 //       bool out_or_in;

  1426 //       typename Graph::OutEdgeIt o;

  1427 //       typename Graph::InEdgeIt i;

  1428 //     };

  1429 //     typedef typename Graph::SymEdgeIt SymEdgeIt;

  1430 //     typedef typename Graph::EdgeIt EdgeIt;

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

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

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

  1437 //     // Edge and SymEdge  is missing!!!!

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

  1440 //     //FIXME

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

  1442 //       {

  1443 // 	e.n=n;

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

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

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

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

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

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

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

  1451 // 	}

  1452 // 	return e;

  1453 //       }

  1454 // /*

  1455 //   OutEdgeIt &goNext(OutEdgeIt &e)

  1456 //   {

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

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

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

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

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

  1462 //   }

  1463 //   else {

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

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

  1466 //   return e;

  1467 //   }

  1468 //   }

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

  1470 // */

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

  1473 //     //FIXME

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

  1475 //       {

  1476 // 	e.n=n;

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

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

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

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

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

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

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

  1484 // 	}

  1485 // 	return e;

  1486 //       }

  1487 // /*

  1488 //   InEdgeIt &goNext(InEdgeIt &e)

  1489 //   {

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

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

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

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

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

  1495 //   }

  1496 //   else {

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

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

  1499 //   return e;

  1500 //   }

  1501 //   }

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

  1503 // */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1545 //   };

  1547 } //namespace hugo

  1549 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Tue, 06 Apr 2004 12:00:34 +0000
changeset 311	6635b11938fe
parent 307	0fac67bef95a
child 312	54e07057eb47
permissions	-rw-r--r--