lemon-0.x: src/hugo/graph_wrapper.h@6620dfc606af

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

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_GRAPH_WRAPPER_H

     5 ///\ingroup gwrappers

     6 ///\file

     7 ///\brief Several graph wrappers.

     8 ///

     9 ///This file contains several useful graph wrapper functions.

    10 ///

    11 ///\author Marton Makai

    13 #include <hugo/invalid.h>

    14 //#include <iter_map.h>

    16 namespace hugo {

    18   // Graph wrappers

    20   /// \addtogroup gwrappers

    21   /// A main parts of HUGOlib are the different graph structures,

    22   /// generic graph algorithms, graph concepts which couple these, and

    23   /// graph wrappers. While the previous ones are more or less clear, the

    24   /// latter notion needs further explanation.

    25   /// Graph wrappers are graph classes which serve for considering graph

    26   /// structures in different ways. A short example makes the notion much

    27   /// clearer.

    28   /// Suppose that we have an instance \c g of a directed graph

    29   /// type say \c ListGraph and an algorithm

    30   /// \code template<typename Graph> int algorithm(const Graph&); \endcode

    31   /// is needed to run on the reversely oriented graph.

    32   /// It may be expensive (in time or in memory usage) to copy

    33   /// \c g with the reverse orientation.

    34   /// Thus, a wrapper class

    35   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.

    36   /// The code looks as follows

    37   /// \code

    38   /// ListGraph g;

    39   /// RevGraphWrapper<ListGraph> rgw(g);

    40   /// int result=algorithm(rgw);

    41   /// \endcode

    42   /// After running the algorithm, the original graph \c g

    43   /// remains untouched. Thus the graph wrapper used above is to consider the

    44   /// original graph with reverse orientation.

    45   /// This techniques gives rise to an elegant code, and

    46   /// based on stable graph wrappers, complex algorithms can be

    47   /// implemented easily.

    48   /// In flow, circulation and bipartite matching problems, the residual

    49   /// graph is of particular importance. Combining a wrapper implementing

    50   /// this, shortest path algorithms and minimum mean cycle algorithms,

    51   /// a range of weighted and cardinality optimization algorithms can be

    52   /// obtained. For lack of space, for other examples,

    53   /// the interested user is referred to the detailed documentation of graph

    54   /// wrappers.

    55   /// The behavior of graph wrappers can be very different. Some of them keep

    56   /// capabilities of the original graph while in other cases this would be

    57   /// meaningless. This means that the concepts that they are a model of depend

    58   /// on the graph wrapper, and the wrapped graph(s).

    59   /// If an edge of \c rgw is deleted, this is carried out by

    60   /// deleting the corresponding edge of \c g. But for a residual

    61   /// graph, this operation has no sense.

    62   /// Let we stand one more example here to simplify your work.

    63   /// wrapper class

    64   /// \code template<typename Graph> class RevGraphWrapper; \endcode

    65   /// has constructor

    66   /// <tt> RevGraphWrapper(Graph& _g)</tt>.

    67   /// This means that in a situation,

    68   /// when a <tt> const ListGraph& </tt> reference to a graph is given,

    69   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.

    70   /// \code

    71   /// int algorithm1(const ListGraph& g) {

    72   ///   RevGraphWrapper<const ListGraph> rgw(g);

    73   ///   return algorithm2(rgw);

    74   /// }

    75   /// \endcode

    77   /// \addtogroup gwrappers

    78   /// @{

    80   ///Base type for the Graph Wrappers

    82   ///This is the base type for the Graph Wrappers.

    83   ///\todo Some more docs...

    84   ///

    85   ///\author Marton Makai

    86   template<typename Graph>

    87   class GraphWrapper {

    88   protected:

    89     Graph* graph;

    90     GraphWrapper() : graph(0) { }

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

    93   public:

    94     typedef Graph BaseGraph;

    95     typedef Graph ParentGraph;

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

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

   100 //    typedef typename Graph::Node Node;

   101     class Node : public Graph::Node {

   102       friend class GraphWrapper<Graph>;

   103     public:

   104       Node() { }

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

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

   107     };

   108     class NodeIt {

   109       friend class GraphWrapper<Graph>;

   110       typename Graph::NodeIt n;

   111      public:

   112       NodeIt() { }

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

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

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

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

   117     };

   118 //    typedef typename Graph::Edge Edge;

   119     class Edge : public Graph::Edge {

   120       friend class GraphWrapper<Graph>;

   121     public:

   122       Edge() { }

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

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

   125     };

   126     class OutEdgeIt {

   127       friend class GraphWrapper<Graph>;

   128       typename Graph::OutEdgeIt e;

   129     public:

   130       OutEdgeIt() { }

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

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

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

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

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

   136     };

   137     class InEdgeIt {

   138       friend class GraphWrapper<Graph>;

   139       typename Graph::InEdgeIt e;

   140     public:

   141       InEdgeIt() { }

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

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

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

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

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

   147     };

   148     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   149     class EdgeIt {

   150       friend class GraphWrapper<Graph>;

   151       typename Graph::EdgeIt e;

   152     public:

   153       EdgeIt() { }

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

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

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

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

   158     };

   160     NodeIt& first(NodeIt& i) const {

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

   162     }

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

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

   165     }

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

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

   168     }

   169     EdgeIt& first(EdgeIt& i) const {

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

   171     }

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

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

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

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

   178     Node tail(const Edge& e) const {

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

   180     Node head(const Edge& e) const {

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

   183     bool valid(const Node& n) const {

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

   185     bool valid(const Edge& e) const {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   206       typedef typename Graph::template NodeMap<T> Parent;

   207     public:

   208       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }

   209       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }

   210     };

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

   213       typedef typename Graph::template EdgeMap<T> Parent;

   214     public:

   215       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }

   216       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }

   217     };

   218   };

   222   /// A graph wrapper which reverses the orientation of the edges.

   224   /// A graph wrapper which reverses the orientation of the edges.

   225   /// Thus \c Graph have to be a directed graph type.

   226   ///

   227   ///\author Marton Makai

   228   template<typename Graph>

   229   class RevGraphWrapper : public GraphWrapper<Graph> {

   230   protected:

   231     RevGraphWrapper() : GraphWrapper<Graph>() { }

   232   public:

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

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

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

   237     //If Graph::OutEdgeIt is not defined

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

   239     //the typdef techinque does not work.

   240     //Unfortunately all the typedefs are instantiated in templates.

   241     //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;

   242     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;

   244     class OutEdgeIt {

   245       friend class GraphWrapper<Graph>;

   246       friend class RevGraphWrapper<Graph>;

   247       typename Graph::InEdgeIt e;

   248     public:

   249       OutEdgeIt() { }

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

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

   252       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :

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

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

   255     };

   256     class InEdgeIt {

   257       friend class GraphWrapper<Graph>;

   258       friend class RevGraphWrapper<Graph>;

   259       typename Graph::OutEdgeIt e;

   260     public:

   261       InEdgeIt() { }

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

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

   264       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :

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

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

   267     };

   269     using GraphWrapper<Graph>::first;

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

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

   272     }

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

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

   275     }

   277     using GraphWrapper<Graph>::next;

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

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

   281     Node aNode(const OutEdgeIt& e) const {

   282       return Node(this->graph->aNode(e.e)); }

   283     Node aNode(const InEdgeIt& e) const {

   284       return Node(this->graph->aNode(e.e)); }

   285     Node bNode(const OutEdgeIt& e) const {

   286       return Node(this->graph->bNode(e.e)); }

   287     Node bNode(const InEdgeIt& e) const {

   288       return Node(this->graph->bNode(e.e)); }

   290     Node tail(const Edge& e) const {

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

   292     Node head(const Edge& e) const {

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

   295   };

   299   /// A graph wrapper for hiding nodes and edges from a graph.

   301   /// This wrapper shows a graph with filtered node-set and

   302   /// edge-set. The quick brown fox iterator jumps over

   303   /// the lazy dog nodes or edges if the values for them are false

   304   /// in the bool maps.

   305   ///

   306   ///\author Marton Makai

   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;

   314     SubGraphWrapper() : GraphWrapper<Graph>(),

   315 			node_filter_map(0), edge_filter_map(0) { }

   316     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   317       node_filter_map=&_node_filter_map;

   318     }

   319     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

   320       edge_filter_map=&_edge_filter_map;

   321     }

   323   public:

   325     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   326 		    EdgeFilterMap& _edge_filter_map) :

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

   328       edge_filter_map(&_edge_filter_map) { }

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

   331     class NodeIt {

   332       friend class GraphWrapper<Graph>;

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

   334       typename Graph::NodeIt n;

   335      public:

   336       NodeIt() { }

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

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

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

   340 	n(*(_G.graph)) {

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

   342 	  _G.graph->next(n);

   343       }

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

   345     };

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

   347     class OutEdgeIt {

   348       friend class GraphWrapper<Graph>;

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

   350       typename Graph::OutEdgeIt e;

   351     public:

   352       OutEdgeIt() { }

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

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

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

   356 		const Node& _n) :

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

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

   359 	  _G.graph->next(e);

   360       }

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

   362     };

   363     class InEdgeIt {

   364       friend class GraphWrapper<Graph>;

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

   366       typename Graph::InEdgeIt e;

   367     public:

   368       InEdgeIt() { }

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

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

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

   372 	       const Node& _n) :

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

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

   375 	  _G.graph->next(e);

   376       }

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

   378     };

   379     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   380     class EdgeIt {

   381       friend class GraphWrapper<Graph>;

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

   383       typename Graph::EdgeIt e;

   384     public:

   385       EdgeIt() { }

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

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

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

   389 	e(*(_G.graph)) {

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

   391 	  _G.graph->next(e);

   392       }

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

   394     };

   396     NodeIt& first(NodeIt& i) const {

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

   398     }

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

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

   401     }

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

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

   404     }

   405     EdgeIt& first(EdgeIt& i) const {

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

   407     }

   409     NodeIt& next(NodeIt& i) const {

   410       this->graph->next(i.n);

   411       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {

   412 	this->graph->next(i.n); }

   413       return i;

   414     }

   415     OutEdgeIt& next(OutEdgeIt& i) const {

   416       this->graph->next(i.e);

   417       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {

   418 	this->graph->next(i.e); }

   419       return i;

   420     }

   421     InEdgeIt& next(InEdgeIt& i) const {

   422       this->graph->next(i.e);

   423       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {

   424 	this->graph->next(i.e); }

   425       return i;

   426     }

   427     EdgeIt& next(EdgeIt& i) const {

   428       this->graph->next(i.e);

   429       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {

   430 	this->graph->next(i.e); }

   431       return i;

   432     }

   434     Node aNode(const OutEdgeIt& e) const {

   435       return Node(this->graph->aNode(e.e)); }

   436     Node aNode(const InEdgeIt& e) const {

   437       return Node(this->graph->aNode(e.e)); }

   438     Node bNode(const OutEdgeIt& e) const {

   439       return Node(this->graph->bNode(e.e)); }

   440     Node bNode(const InEdgeIt& e) const {

   441       return Node(this->graph->bNode(e.e)); }

   443     /// This function hides \c n in the graph, i.e. the iteration

   444     /// jumps over it. This is done by simply setting the value of \c n

   445     /// to be false in the corresponding node-map.

   446     void hide(const Node& n) const { node_filter_map->set(n, false); }

   448     /// This function hides \c e in the graph, i.e. the iteration

   449     /// jumps over it. This is done by simply setting the value of \c e

   450     /// to be false in the corresponding edge-map.

   451     void hide(const Edge& e) const { edge_filter_map->set(e, false); }

   453     /// The value of \c n is set to be true in the node-map which stores

   454     /// hide information. If \c n was hidden previuosly, then it is shown

   455     /// again

   456      void unHide(const Node& n) const { node_filter_map->set(n, true); }

   458     /// The value of \c e is set to be true in the edge-map which stores

   459     /// hide information. If \c e was hidden previuosly, then it is shown

   460     /// again

   461     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }

   463     /// Returns true if \c n is hidden.

   464     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

   466     /// Returns true if \c n is hidden.

   467     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }

   469     /// This is a linear time operation and works only if

   470     /// NodeIt is defined.

   471     int nodeNum() const {

   472       int i=0;

   473       NodeIt n;

   474       for (this->first(n); this->valid(n); this->next(n)) ++i;

   475       return i;

   476     }

   478     /// This is a linear time operation and works only if

   479     /// EdgeIt is defined.

   480     int edgeNum() const {

   481       int i=0;

   482       EdgeIt e;

   483       for (this->first(e); this->valid(e); this->next(e)) ++i;

   484       return i;

   485     }

   487   };

   491   /// \brief A wrapper for forgetting the orientation of a graph.

   492   ///

   493   /// A wrapper for getting an undirected graph by forgetting

   494   /// the orientation of a directed one.

   495   ///

   496   /// \author Marton Makai

   497   template<typename Graph>

   498   class UndirGraphWrapper : public GraphWrapper<Graph> {

   499   protected:

   500     UndirGraphWrapper() : GraphWrapper<Graph>() { }

   502   public:

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

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

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

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

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

   510     class OutEdgeIt {

   511       friend class UndirGraphWrapper<Graph>;

   512       bool out_or_in; //true iff out

   513       typename Graph::OutEdgeIt out;

   514       typename Graph::InEdgeIt in;

   515     public:

   516       OutEdgeIt() { }

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

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

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

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

   521       }

   522       operator Edge() const {

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

   524       }

   525     };

   527 //FIXME InEdgeIt

   528     typedef OutEdgeIt InEdgeIt;

   530     using GraphWrapper<Graph>::first;

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

   532 //       i=NodeIt(*this); return i;

   533 //     }

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

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

   536     }

   537 //FIXME

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

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

   540 //     }

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

   542 //       i=EdgeIt(*this); return i;

   543 //     }

   545     using GraphWrapper<Graph>::next;

   546 //     NodeIt& next(NodeIt& n) const {

   547 //       GraphWrapper<Graph>::next(n);

   548 //       return n;

   549 //     }

   550     OutEdgeIt& next(OutEdgeIt& e) const {

   551       if (e.out_or_in) {

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

   553 	this->graph->next(e.out);

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

   555 	  e.out_or_in=false; this->graph->first(e.in, n); }

   556       } else {

   557 	this->graph->next(e.in);

   558       }

   559       return e;

   560     }

   561     //FIXME InEdgeIt

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

   563 //       GraphWrapper<Graph>::next(n);

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

   565 //       return e;

   566 //     }

   568     Node aNode(const OutEdgeIt& e) const {

   569       if (e.out_or_in) return this->graph->tail(e); else

   570 	return this->graph->head(e); }

   571     Node bNode(const OutEdgeIt& e) const {

   572       if (e.out_or_in) return this->graph->head(e); else

   573 	return this->graph->tail(e); }

   574   };

   576   /// \brief An undirected graph template.

   577   ///

   578   /// An undirected graph template.

   579   /// This class works as an undirected graph and a directed graph of

   580   /// class \c Graph is used for the physical storage.

   581   /// \ingroup graphs

   582   template<typename Graph>

   583   class UndirGraph : public UndirGraphWrapper<Graph> {

   584     typedef UndirGraphWrapper<Graph> Parent;

   585   protected:

   586     Graph gr;

   587   public:

   588     UndirGraph() : UndirGraphWrapper<Graph>() {

   589       Parent::setGraph(gr);

   590     }

   591   };

   594   ///\brief A wrapper for composing bidirected graph from a directed one.

   595   /// experimental, for fezso's sake.

   596   ///

   597   /// A wrapper for composing bidirected graph from a directed one.

   598   /// experimental, for fezso's sake.

   599   /// A bidirected graph is composed over the directed one without physical

   600   /// storage. As the oppositely directed edges are logically different ones

   601   /// the maps are able to attach different values for them.

   602   template<typename Graph>

   603   class BidirGraphWrapper : public GraphWrapper<Graph> {

   604   protected:

   605     //const CapacityMap* capacity;

   606     //FlowMap* flow;

   608     BidirGraphWrapper() : GraphWrapper<Graph>()/*,

   609 						 capacity(0), flow(0)*/ { }

   610 //     void setCapacityMap(const CapacityMap& _capacity) {

   611 //       capacity=&_capacity;

   612 //     }

   613 //     void setFlowMap(FlowMap& _flow) {

   614 //       flow=&_flow;

   615 //     }

   617   public:

   619     BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,

   620 				     FlowMap& _flow*/) :

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

   623     class Edge;

   624     class OutEdgeIt;

   625     friend class Edge;

   626     friend class OutEdgeIt;

   628     //template<typename T> class NodeMap;

   629     template<typename T> class EdgeMap;

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

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

   634     class Edge : public Graph::Edge {

   635       friend class BidirGraphWrapper<Graph>;

   636       ///\bug ez nem is kell

   637       //template<typename T> friend class NodeMap;

   638       template<typename T> friend class EdgeMap;

   639     protected:

   640       bool backward; //true, iff backward

   641 //      typename Graph::Edge e;

   642     public:

   643       Edge() { }

   644       ///\bug =false kell-e? zsoltnak kell az addEdge miatt

   645       Edge(const typename Graph::Edge& _e, bool _backward=false) :

   646 	Graph::Edge(_e), backward(_backward) { }

   647       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }

   648 //the unique invalid iterator

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

   650 	return (v.backward==u.backward &&

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

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

   653       }

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

   655 	return (v.backward!=u.backward ||

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

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

   658       }

   659     };

   661     class OutEdgeIt {

   662       friend class BidirGraphWrapper<Graph>;

   663     protected:

   664       typename Graph::OutEdgeIt out;

   665       typename Graph::InEdgeIt in;

   666       bool backward;

   667     public:

   668       OutEdgeIt() { }

   669       //FIXME

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

   671       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

   672 //the unique invalid iterator

   673       OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {

   674 	backward=false;

   675 	_G.graph->first(out, v);

   676 	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }

   677 	if (!_G.graph->valid(out)) {

   678 	  backward=true;

   679 	  _G.graph->first(in, v);

   680 	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }

   681 	}

   682       }

   683       operator Edge() const {

   684 //	Edge e;

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

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

   687 //	return e;

   688 	if (this->backward)

   689 	  return Edge(in, this->backward);

   690 	else

   691 	  return Edge(out, this->backward);

   692       }

   693     };

   695     class InEdgeIt {

   696       friend class BidirGraphWrapper<Graph>;

   697     protected:

   698       typename Graph::OutEdgeIt out;

   699       typename Graph::InEdgeIt in;

   700       bool backward;

   701     public:

   702       InEdgeIt() { }

   703       //FIXME

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

   705       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

   706 //the unique invalid iterator

   707       InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {

   708 	backward=false;

   709 	_G.graph->first(in, v);

   710 	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }

   711 	if (!_G.graph->valid(in)) {

   712 	  backward=true;

   713 	  _G.graph->first(out, v);

   714 	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }

   715 	}

   716       }

   717       operator Edge() const {

   718 //	Edge e;

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

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

   721 //	return e;

   722 	if (this->backward)

   723 	  return Edge(out, this->backward);

   724 	else

   725 	  return Edge(in, this->backward);

   726       }

   727     };

   729     class EdgeIt {

   730       friend class BidirGraphWrapper<Graph>;

   731     protected:

   732       typename Graph::EdgeIt e;

   733       bool backward;

   734     public:

   735       EdgeIt() { }

   736       EdgeIt(const Invalid& i) : e(i), backward(true) { }

   737       EdgeIt(const BidirGraphWrapper<Graph>& _G) {

   738 	backward=false;

   739 	_G.graph->first(e);

   740 	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);

   741 	if (!_G.graph->valid(e)) {

   742 	  backward=true;

   743 	  _G.graph->first(e);

   744 	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);

   745 	}

   746       }

   747       operator Edge() const {

   748 	return Edge(e, this->backward);

   749       }

   750     };

   752     using GraphWrapper<Graph>::first;

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

   754 //       i=NodeIt(*this); return i;

   755 //     }

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

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

   758     }

   759 //    FIXME not tested

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

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

   762     }

   763     EdgeIt& first(EdgeIt& i) const {

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

   765     }

   767     using GraphWrapper<Graph>::next;

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

   769     OutEdgeIt& next(OutEdgeIt& e) const {

   770       if (!e.backward) {

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

   772 	this->graph->next(e.out);

   773 	while(this->graph->valid(e.out) && !enabled(e)) {

   774 	  this->graph->next(e.out); }

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

   776 	  e.backward=true;

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

   778 	  while(this->graph->valid(e.in) && !enabled(e)) {

   779 	    this->graph->next(e.in); }

   780 	}

   781       } else {

   782 	this->graph->next(e.in);

   783 	while(this->graph->valid(e.in) && !enabled(e)) {

   784 	  this->graph->next(e.in); }

   785       }

   786       return e;

   787     }

   788 //     FIXME Not tested

   789     InEdgeIt& next(InEdgeIt& e) const {

   790       if (!e.backward) {

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

   792 	this->graph->next(e.in);

   793 	while(this->graph->valid(e.in) && !enabled(e)) {

   794 	  this->graph->next(e.in); }

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

   796 	  e.backward=true;

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

   798 	  while(this->graph->valid(e.out) && !enabled(e)) {

   799 	    this->graph->next(e.out); }

   800 	}

   801       } else {

   802 	this->graph->next(e.out);

   803 	while(this->graph->valid(e.out) && !enabled(e)) {

   804 	  this->graph->next(e.out); }

   805       }

   806       return e;

   807     }

   808     EdgeIt& next(EdgeIt& e) const {

   809       if (!e.backward) {

   810 	this->graph->next(e.e);

   811 	while(this->graph->valid(e.e) && !enabled(e)) {

   812 	  this->graph->next(e.e); }

   813 	if (!this->graph->valid(e.e)) {

   814 	  e.backward=true;

   815 	  this->graph->first(e.e);

   816 	  while(this->graph->valid(e.e) && !enabled(e)) {

   817 	    this->graph->next(e.e); }

   818 	}

   819       } else {

   820 	this->graph->next(e.e);

   821 	while(this->graph->valid(e.e) && !enabled(e)) {

   822 	  this->graph->next(e.e); }

   823       }

   824       return e;

   825     }

   827     Node tail(Edge e) const {

   828       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }

   829     Node head(Edge e) const {

   830       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

   832     Node aNode(OutEdgeIt e) const {

   833       return ((!e.backward) ? this->graph->aNode(e.out) :

   834 	      this->graph->aNode(e.in)); }

   835     Node bNode(OutEdgeIt e) const {

   836       return ((!e.backward) ? this->graph->bNode(e.out) :

   837 	      this->graph->bNode(e.in)); }

   839     Node aNode(InEdgeIt e) const {

   840       return ((!e.backward) ? this->graph->aNode(e.in) :

   841 	      this->graph->aNode(e.out)); }

   842     Node bNode(InEdgeIt e) const {

   843       return ((!e.backward) ? this->graph->bNode(e.in) :

   844 	      this->graph->bNode(e.out)); }

   846     /// Gives back the opposite edge.

   847     Edge opposite(const Edge& e) const {

   848       Edge f=e;

   849       f.backward=!f.backward;

   850       return f;

   851     }

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

   854     //FIXME

   855     void edgeNum() const { }

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

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

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

   862     bool valid(Edge e) const {

   863       return this->graph->valid(e);

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

   865     }

   867     bool forward(const Edge& e) const { return !e.backward; }

   868     bool backward(const Edge& e) const { return e.backward; }

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

   871 //       if (!e.backward)

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

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

   874 //       else

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

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

   877 //     }

   879     bool enabled(const Edge& e) const {

   880       if (!e.backward)

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

   882 	//return ((*capacity)[e]-(*flow)[e]);

   883 	return true;

   884       else

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

   886 	//return ((*flow)[e]);

   887 	return true;

   888     }

   890 //     Number enabled(typename Graph::OutEdgeIt out) const {

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

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

   893 //     }

   895 //     Number enabled(typename Graph::InEdgeIt in) const {

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

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

   898 //     }

   900     template <typename T>

   901     class EdgeMap {

   902       typename Graph::template EdgeMap<T> forward_map, backward_map;

   903     public:

   904       typedef T ValueType;

   905       typedef Edge KeyType;

   906       EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }

   907       EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }

   908       void set(Edge e, T a) {

   909 	if (!e.backward)

   910 	  forward_map.set(e/*.out*/, a);

   911 	else

   912 	  backward_map.set(e/*.in*/, a);

   913       }

   914       T operator[](Edge e) const {

   915 	if (!e.backward)

   916 	  return forward_map[e/*.out*/];

   917 	else

   918 	  return backward_map[e/*.in*/];

   919       }

   920       void update() {

   921 	forward_map.update();

   922 	backward_map.update();

   923       }

   924 //       T get(Edge e) const {

   925 // 	if (e.out_or_in)

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

   927 // 	else

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

   929 //       }

   930     };

   931   };

   933   /// \brief A bidirected graph template.

   934   ///

   935   /// A bidirected graph template.

   936   /// Such a bidirected graph stores each pair of oppositely directed edges

   937   /// ones in the memory, i.e. a directed graph of type

   938   /// \c Graph is used for that.

   939   /// As the oppositely directed edges are logically different ones

   940   /// the maps are able to attach different values for them.

   941   /// \ingroup graphs

   942   template<typename Graph>

   943   class BidirGraph : public BidirGraphWrapper<Graph> {

   944     typedef UndirGraphWrapper<Graph> Parent;

   945   protected:

   946     Graph gr;

   947   public:

   948     BidirGraph() : BidirGraphWrapper<Graph>() {

   949       Parent::setGraph(gr);

   950     }

   951   };

   954   /// A wrapper for composing the residual graph for directed flow and circulation problems.

   956   /// A wrapper for composing the residual graph for directed flow and circulation problems.

   957   template<typename Graph, typename Number,

   958 	   typename CapacityMap, typename FlowMap>

   959   class ResGraphWrapper : public GraphWrapper<Graph> {

   960   protected:

   961     const CapacityMap* capacity;

   962     FlowMap* flow;

   964     ResGraphWrapper() : GraphWrapper<Graph>(0),

   965 			capacity(0), flow(0) { }

   966     void setCapacityMap(const CapacityMap& _capacity) {

   967       capacity=&_capacity;

   968     }

   969     void setFlowMap(FlowMap& _flow) {

   970       flow=&_flow;

   971     }

   973   public:

   975     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,

   976 		    FlowMap& _flow) :

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

   979     class Edge;

   980     class OutEdgeIt;

   981     friend class Edge;

   982     friend class OutEdgeIt;

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

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

   986     class Edge : public Graph::Edge {

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

   988     protected:

   989       bool backward; //true, iff backward

   990 //      typename Graph::Edge e;

   991     public:

   992       Edge() { }

   993       Edge(const typename Graph::Edge& _e, bool _backward) :

   994 	Graph::Edge(_e), backward(_backward) { }

   995       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }

   996 //the unique invalid iterator

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

   998 	return (v.backward==u.backward &&

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

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

  1001       }

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

  1003 	return (v.backward!=u.backward ||

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

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

  1006       }

  1007     };

  1009     class OutEdgeIt {

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

  1011     protected:

  1012       typename Graph::OutEdgeIt out;

  1013       typename Graph::InEdgeIt in;

  1014       bool backward;

  1015     public:

  1016       OutEdgeIt() { }

  1017       //FIXME

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

  1019       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

  1020 //the unique invalid iterator

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

  1022 	backward=false;

  1023 	_G.graph->first(out, v);

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

  1025 	if (!_G.graph->valid(out)) {

  1026 	  backward=true;

  1027 	  _G.graph->first(in, v);

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

  1029 	}

  1030       }

  1031       operator Edge() const {

  1032 //	Edge e;

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

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

  1035 //	return e;

  1036 	if (this->backward)

  1037 	  return Edge(in, this->backward);

  1038 	else

  1039 	  return Edge(out, this->backward);

  1040       }

  1041     };

  1043     class InEdgeIt {

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

  1045     protected:

  1046       typename Graph::OutEdgeIt out;

  1047       typename Graph::InEdgeIt in;

  1048       bool backward;

  1049     public:

  1050       InEdgeIt() { }

  1051       //FIXME

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

  1053       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }

  1054 //the unique invalid iterator

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

  1056 	backward=false;

  1057 	_G.graph->first(in, v);

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

  1059 	if (!_G.graph->valid(in)) {

  1060 	  backward=true;

  1061 	  _G.graph->first(out, v);

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

  1063 	}

  1064       }

  1065       operator Edge() const {

  1066 //	Edge e;

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

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

  1069 //	return e;

  1070 	if (this->backward)

  1071 	  return Edge(out, this->backward);

  1072 	else

  1073 	  return Edge(in, this->backward);

  1074       }

  1075     };

  1077     class EdgeIt {

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

  1079     protected:

  1080       typename Graph::EdgeIt e;

  1081       bool backward;

  1082     public:

  1083       EdgeIt() { }

  1084       EdgeIt(const Invalid& i) : e(i), backward(true) { }

  1085       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {

  1086 	backward=false;

  1087 	_G.graph->first(e);

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

  1089 	if (!_G.graph->valid(e)) {

  1090 	  backward=true;

  1091 	  _G.graph->first(e);

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

  1093 	}

  1094       }

  1095       operator Edge() const {

  1096 	return Edge(e, this->backward);

  1097       }

  1098     };

  1100     using GraphWrapper<Graph>::first;

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

  1102 //       i=NodeIt(*this); return i;

  1103 //     }

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

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

  1106     }

  1107 //    FIXME not tested

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

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

  1110     }

  1111     EdgeIt& first(EdgeIt& i) const {

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

  1113     }

  1115     using GraphWrapper<Graph>::next;

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

  1117     OutEdgeIt& next(OutEdgeIt& e) const {

  1118       if (!e.backward) {

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

  1120 	this->graph->next(e.out);

  1121 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) {

  1122 	  this->graph->next(e.out); }

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

  1124 	  e.backward=true;

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

  1126 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) {

  1127 	    this->graph->next(e.in); }

  1128 	}

  1129       } else {

  1130 	this->graph->next(e.in);

  1131 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) {

  1132 	  this->graph->next(e.in); }

  1133       }

  1134       return e;

  1135     }

  1136 //     FIXME Not tested

  1137     InEdgeIt& next(InEdgeIt& e) const {

  1138       if (!e.backward) {

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

  1140 	this->graph->next(e.in);

  1141 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) {

  1142 	  this->graph->next(e.in); }

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

  1144 	  e.backward=true;

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

  1146 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) {

  1147 	    this->graph->next(e.out); }

  1148 	}

  1149       } else {

  1150 	this->graph->next(e.out);

  1151 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) {

  1152 	  this->graph->next(e.out); }

  1153       }

  1154       return e;

  1155     }

  1156     EdgeIt& next(EdgeIt& e) const {

  1157       if (!e.backward) {

  1158 	this->graph->next(e.e);

  1159 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) {

  1160 	  this->graph->next(e.e); }

  1161 	if (!this->graph->valid(e.e)) {

  1162 	  e.backward=true;

  1163 	  this->graph->first(e.e);

  1164 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) {

  1165 	    this->graph->next(e.e); }

  1166 	}

  1167       } else {

  1168 	this->graph->next(e.e);

  1169 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) {

  1170 	  this->graph->next(e.e); }

  1171       }

  1172       return e;

  1173     }

  1175     Node tail(Edge e) const {

  1176       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }

  1177     Node head(Edge e) const {

  1178       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }

  1180     Node aNode(OutEdgeIt e) const {

  1181       return ((!e.backward) ? this->graph->aNode(e.out) :

  1182 	      this->graph->aNode(e.in)); }

  1183     Node bNode(OutEdgeIt e) const {

  1184       return ((!e.backward) ? this->graph->bNode(e.out) :

  1185 	      this->graph->bNode(e.in)); }

  1187     Node aNode(InEdgeIt e) const {

  1188       return ((!e.backward) ? this->graph->aNode(e.in) :

  1189 	      this->graph->aNode(e.out)); }

  1190     Node bNode(InEdgeIt e) const {

  1191       return ((!e.backward) ? this->graph->bNode(e.in) :

  1192 	      this->graph->bNode(e.out)); }

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

  1195     //FIXME

  1196     void edgeNum() const { }

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

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

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

  1203     bool valid(Edge e) const {

  1204       return this->graph->valid(e);

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

  1206     }

  1208     bool forward(const Edge& e) const { return !e.backward; }

  1209     bool backward(const Edge& e) const { return e.backward; }

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

  1212       if (!e.backward)

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

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

  1215       else

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

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

  1218     }

  1220     Number resCap(const Edge& e) const {

  1221       if (!e.backward)

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

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

  1224       else

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

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

  1227     }

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

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

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

  1232 //     }

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

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

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

  1237 //     }

  1239     template <typename T>

  1240     class EdgeMap {

  1241       typename Graph::template EdgeMap<T> forward_map, backward_map;

  1242     public:

  1243       typedef T ValueType;

  1244       typedef Edge KeyType;

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

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

  1247       void set(Edge e, T a) {

  1248 	if (!e.backward)

  1249 	  forward_map.set(e/*.out*/, a);

  1250 	else

  1251 	  backward_map.set(e/*.in*/, a);

  1252       }

  1253       T operator[](Edge e) const {

  1254 	if (!e.backward)

  1255 	  return forward_map[e/*.out*/];

  1256 	else

  1257 	  return backward_map[e/*.in*/];

  1258       }

  1259       void update() {

  1260 	forward_map.update();

  1261 	backward_map.update();

  1262       }

  1263 //       T get(Edge e) const {

  1264 // 	if (e.out_or_in)

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

  1266 // 	else

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

  1268 //       }

  1269     };

  1270   };

  1274   /// For blocking flows.

  1276   /// This graph wrapper is used for Dinits blocking flow computations.

  1277   /// For each node, an out-edge is stored which is used when the

  1278   /// \code

  1279   /// OutEdgeIt& first(OutEdgeIt&, const Node&)

  1280   /// \endcode

  1281   /// is called.

  1282   ///

  1283   ///\author Marton Makai

  1284   template<typename Graph, typename FirstOutEdgesMap>

  1285   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1286   protected:

  1287     FirstOutEdgesMap* first_out_edges;

  1288   public:

  1289     ErasingFirstGraphWrapper(Graph& _graph,

  1290 			     FirstOutEdgesMap& _first_out_edges) :

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

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

  1294 //     class NodeIt {

  1295 //       friend class GraphWrapper<Graph>;

  1296 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1297 //       typename Graph::NodeIt n;

  1298 //      public:

  1299 //       NodeIt() { }

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

  1301 //       NodeIt(const Invalid& i) : n(i) { }

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

  1303 // 	n(*(_G.graph)) { }

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

  1305 //     };

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

  1307     class OutEdgeIt {

  1308       friend class GraphWrapper<Graph>;

  1309       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1310 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

  1311       typename Graph::OutEdgeIt e;

  1312     public:

  1313       OutEdgeIt() { }

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

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

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

  1317 		const Node& _n) :

  1318 	e((*_G.first_out_edges)[_n]) { }

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

  1320     };

  1321     class InEdgeIt {

  1322       friend class GraphWrapper<Graph>;

  1323       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1324 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

  1325       typename Graph::InEdgeIt e;

  1326     public:

  1327       InEdgeIt() { }

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

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

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

  1331 	       const Node& _n) :

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

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

  1334     };

  1335     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1336     class EdgeIt {

  1337       friend class GraphWrapper<Graph>;

  1338       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1339 //      typedef typename Graph::EdgeIt GraphEdgeIt;

  1340       typename Graph::EdgeIt e;

  1341     public:

  1342       EdgeIt() { }

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

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

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

  1346 	e(*(_G.graph)) { }

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

  1348     };

  1350     using GraphWrapper<Graph>::first;

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

  1352 //       i=NodeIt(*this); return i;

  1353 //     }

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

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

  1356     }

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

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

  1359     }

  1360     EdgeIt& first(EdgeIt& i) const {

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

  1362     }

  1364     using GraphWrapper<Graph>::next;

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

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

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

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

  1370     Node aNode(const OutEdgeIt& e) const {

  1371       return Node(this->graph->aNode(e.e)); }

  1372     Node aNode(const InEdgeIt& e) const {

  1373       return Node(this->graph->aNode(e.e)); }

  1374     Node bNode(const OutEdgeIt& e) const {

  1375       return Node(this->graph->bNode(e.e)); }

  1376     Node bNode(const InEdgeIt& e) const {

  1377       return Node(this->graph->bNode(e.e)); }

  1379     void erase(const OutEdgeIt& e) const {

  1380       OutEdgeIt f=e;

  1381       this->next(f);

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

  1383     }

  1384   };

  1386   ///@}

  1388 } //namespace hugo

  1390 #endif //HUGO_GRAPH_WRAPPER_H

author	jacint
	Thu, 13 May 2004 10:29:13 +0000
changeset 629	6620dfc606af
parent 625	28634fadbf9a
child 650	588ff2ca55bd
permissions	-rw-r--r--