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

     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

    87   template<typename Graph>

    88   class GraphWrapper {

    89   protected:

    90     Graph* graph;

    91     GraphWrapper() : graph(0) { }

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

    94   public:

    95     typedef Graph BaseGraph;

    96     typedef Graph ParentGraph;

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

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

   101 //    typedef typename Graph::Node Node;

   102     class Node : public Graph::Node {

   103       friend class GraphWrapper<Graph>;

   104     public:

   105       Node() { }

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

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

   108     };

   109     class NodeIt {

   110       friend class GraphWrapper<Graph>;

   111       typename Graph::NodeIt n;

   112      public:

   113       NodeIt() { }

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

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

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

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

   118     };

   119 //    typedef typename Graph::Edge Edge;

   120     class Edge : public Graph::Edge {

   121       friend class GraphWrapper<Graph>;

   122     public:

   123       Edge() { }

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

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

   126     };

   127     class OutEdgeIt {

   128       friend class GraphWrapper<Graph>;

   129       typename Graph::OutEdgeIt e;

   130     public:

   131       OutEdgeIt() { }

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

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

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

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

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

   137     };

   138     class InEdgeIt {

   139       friend class GraphWrapper<Graph>;

   140       typename Graph::InEdgeIt e;

   141     public:

   142       InEdgeIt() { }

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

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

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

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

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

   148     };

   149     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   150     class EdgeIt {

   151       friend class GraphWrapper<Graph>;

   152       typename Graph::EdgeIt e;

   153     public:

   154       EdgeIt() { }

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

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

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

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

   159     };

   161     NodeIt& first(NodeIt& i) const {

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

   163     }

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

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

   166     }

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

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

   169     }

   170     EdgeIt& first(EdgeIt& i) const {

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

   172     }

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

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

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

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

   179     Node tail(const Edge& e) const {

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

   181     Node head(const Edge& e) const {

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

   184     bool valid(const Node& n) const {

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

   186     bool valid(const Edge& e) const {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   208     public:

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

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

   211     };

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

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

   215     public:

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

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

   218     };

   219   };

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

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

   226   ///

   227   ///\author Marton Makai

   228   template<typename Graph>

   229   class RevGraphWrapper : public GraphWrapper<Graph> {

   230   protected:

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

   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   /// 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>(0),

   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]; }

   468   };

   472   /// A wrapper for forgetting the orientation of a graph.

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

   475   /// the orientation of a directed one.

   476   ///

   477   ///\author Marton Makai

   478   template<typename Graph>

   479   class UndirGraphWrapper : public GraphWrapper<Graph> {

   480   protected:

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

   483   public:

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

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

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

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

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

   491     class OutEdgeIt {

   492       friend class UndirGraphWrapper<Graph>;

   493       bool out_or_in; //true iff out

   494       typename Graph::OutEdgeIt out;

   495       typename Graph::InEdgeIt in;

   496     public:

   497       OutEdgeIt() { }

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

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

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

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

   502       }

   503       operator Edge() const {

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

   505       }

   506     };

   508 //FIXME InEdgeIt

   509     typedef OutEdgeIt InEdgeIt;

   511     using GraphWrapper<Graph>::first;

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

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

   514 //     }

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

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

   517     }

   518 //FIXME

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

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

   521 //     }

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

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

   524 //     }

   526     using GraphWrapper<Graph>::next;

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

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

   529 //       return n;

   530 //     }

   531     OutEdgeIt& next(OutEdgeIt& e) const {

   532       if (e.out_or_in) {

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

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

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

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

   537       } else {

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

   539       }

   540       return e;

   541     }

   542     //FIXME InEdgeIt

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

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

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

   546 //       return e;

   547 //     }

   549     Node aNode(const OutEdgeIt& e) const {

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

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

   552     Node bNode(const OutEdgeIt& e) const {

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

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

   555   };

   559   /// An undirected graph template

   560   template<typename Graph>

   561   class UndirGraph : public UndirGraphWrapper<Graph> {

   562     typedef UndirGraphWrapper<Graph> Parent;

   563   protected:

   564     Graph gr;

   565   public:

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

   567       Parent::setGraph(gr);

   568     }

   569   };

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

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

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

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

   577   template<typename Graph>

   578   class BidirGraphWrapper : public GraphWrapper<Graph> {

   579   protected:

   580     //const CapacityMap* capacity;

   581     //FlowMap* flow;

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

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

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

   586 //       capacity=&_capacity;

   587 //     }

   588 //     void setFlowMap(FlowMap& _flow) {

   589 //       flow=&_flow;

   590 //     }

   592   public:

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

   595 				     FlowMap& _flow*/) :

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

   598     class Edge;

   599     class OutEdgeIt;

   600     friend class Edge;

   601     friend class OutEdgeIt;

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

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

   605     class Edge : public Graph::Edge {

   606       friend class BidirGraphWrapper<Graph>;

   607     protected:

   608       bool backward; //true, iff backward

   609 //      typename Graph::Edge e;

   610     public:

   611       Edge() { }

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

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

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

   615 //the unique invalid iterator

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

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

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

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

   620       }

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

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

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

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

   625       }

   626     };

   628     class OutEdgeIt {

   629       friend class BidirGraphWrapper<Graph>;

   630     protected:

   631       typename Graph::OutEdgeIt out;

   632       typename Graph::InEdgeIt in;

   633       bool backward;

   634     public:

   635       OutEdgeIt() { }

   636       //FIXME

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

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

   639 //the unique invalid iterator

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

   641 	backward=false;

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

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

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

   645 	  backward=true;

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

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

   648 	}

   649       }

   650       operator Edge() const {

   651 //	Edge e;

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

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

   654 //	return e;

   655 	if (this->backward)

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

   657 	else

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

   659       }

   660     };

   662     class InEdgeIt {

   663       friend class BidirGraphWrapper<Graph>;

   664     protected:

   665       typename Graph::OutEdgeIt out;

   666       typename Graph::InEdgeIt in;

   667       bool backward;

   668     public:

   669       InEdgeIt() { }

   670       //FIXME

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

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

   673 //the unique invalid iterator

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

   675 	backward=false;

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

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

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

   679 	  backward=true;

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

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

   682 	}

   683       }

   684       operator Edge() const {

   685 //	Edge e;

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

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

   688 //	return e;

   689 	if (this->backward)

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

   691 	else

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

   693       }

   694     };

   696     class EdgeIt {

   697       friend class BidirGraphWrapper<Graph>;

   698     protected:

   699       typename Graph::EdgeIt e;

   700       bool backward;

   701     public:

   702       EdgeIt() { }

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

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

   705 	backward=false;

   706 	_G.graph->first(e);

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

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

   709 	  backward=true;

   710 	  _G.graph->first(e);

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

   712 	}

   713       }

   714       operator Edge() const {

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

   716       }

   717     };

   719     using GraphWrapper<Graph>::first;

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

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

   722 //     }

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

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

   725     }

   726 //    FIXME not tested

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

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

   729     }

   730     EdgeIt& first(EdgeIt& i) const {

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

   732     }

   734     using GraphWrapper<Graph>::next;

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

   736     OutEdgeIt& next(OutEdgeIt& e) const {

   737       if (!e.backward) {

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

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

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

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

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

   743 	  e.backward=true;

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

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

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

   747 	}

   748       } else {

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

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

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

   752       }

   753       return e;

   754     }

   755 //     FIXME Not tested

   756     InEdgeIt& next(InEdgeIt& e) const {

   757       if (!e.backward) {

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

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

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

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

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

   763 	  e.backward=true;

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

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

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

   767 	}

   768       } else {

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

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

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

   772       }

   773       return e;

   774     }

   775     EdgeIt& next(EdgeIt& e) const {

   776       if (!e.backward) {

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

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

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

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

   781 	  e.backward=true;

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

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

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

   785 	}

   786       } else {

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

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

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

   790       }

   791       return e;

   792     }

   794     Node tail(Edge e) const {

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

   796     Node head(Edge e) const {

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

   799     Node aNode(OutEdgeIt e) const {

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

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

   802     Node bNode(OutEdgeIt e) const {

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

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

   806     Node aNode(InEdgeIt e) const {

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

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

   809     Node bNode(InEdgeIt e) const {

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

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

   813     /// Gives back the opposite edge.

   814     Edge opposite(const Edge& e) const {

   815       Edge f=e;

   816       f.backward=!f.backward;

   817       return f;

   818     }

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

   821     //FIXME

   822     void edgeNum() const { }

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

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

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

   829     bool valid(Edge e) const {

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

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

   832     }

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

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

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

   838 //       if (!e.backward)

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

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

   841 //       else

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

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

   844 //     }

   846     bool enabled(const Edge& e) const {

   847       if (!e.backward)

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

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

   850 	return true;

   851       else

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

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

   854 	return true;

   855     }

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

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

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

   860 //     }

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

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

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

   865 //     }

   867     template <typename T>

   868     class EdgeMap {

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

   870     public:

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

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

   873       void set(Edge e, T a) {

   874 	if (!e.backward)

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

   876 	else

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

   878       }

   879       T operator[](Edge e) const {

   880 	if (!e.backward)

   881 	  return forward_map[e.out];

   882 	else

   883 	  return backward_map[e.in];

   884       }

   885 //       T get(Edge e) const {

   886 // 	if (e.out_or_in)

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

   888 // 	else

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

   890 //       }

   891     };

   892   };

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

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

   899   template<typename Graph, typename Number,

   900 	   typename CapacityMap, typename FlowMap>

   901   class ResGraphWrapper : public GraphWrapper<Graph> {

   902   protected:

   903     const CapacityMap* capacity;

   904     FlowMap* flow;

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

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

   908     void setCapacityMap(const CapacityMap& _capacity) {

   909       capacity=&_capacity;

   910     }

   911     void setFlowMap(FlowMap& _flow) {

   912       flow=&_flow;

   913     }

   915   public:

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

   918 		    FlowMap& _flow) :

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

   921     class Edge;

   922     class OutEdgeIt;

   923     friend class Edge;

   924     friend class OutEdgeIt;

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

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

   928     class Edge : public Graph::Edge {

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

   930     protected:

   931       bool backward; //true, iff backward

   932 //      typename Graph::Edge e;

   933     public:

   934       Edge() { }

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

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

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

   938 //the unique invalid iterator

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

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

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

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

   943       }

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

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

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

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

   948       }

   949     };

   951     class OutEdgeIt {

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

   953     protected:

   954       typename Graph::OutEdgeIt out;

   955       typename Graph::InEdgeIt in;

   956       bool backward;

   957     public:

   958       OutEdgeIt() { }

   959       //FIXME

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

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

   962 //the unique invalid iterator

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

   964 	backward=false;

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

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

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

   968 	  backward=true;

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

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

   971 	}

   972       }

   973       operator Edge() const {

   974 //	Edge e;

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

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

   977 //	return e;

   978 	if (this->backward)

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

   980 	else

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

   982       }

   983     };

   985     class InEdgeIt {

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

   987     protected:

   988       typename Graph::OutEdgeIt out;

   989       typename Graph::InEdgeIt in;

   990       bool backward;

   991     public:

   992       InEdgeIt() { }

   993       //FIXME

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

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

   996 //the unique invalid iterator

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

   998 	backward=false;

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

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

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

  1002 	  backward=true;

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

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

  1005 	}

  1006       }

  1007       operator Edge() const {

  1008 //	Edge e;

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

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

  1011 //	return e;

  1012 	if (this->backward)

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

  1014 	else

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

  1016       }

  1017     };

  1019     class EdgeIt {

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

  1021     protected:

  1022       typename Graph::EdgeIt e;

  1023       bool backward;

  1024     public:

  1025       EdgeIt() { }

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

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

  1028 	backward=false;

  1029 	_G.graph->first(e);

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

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

  1032 	  backward=true;

  1033 	  _G.graph->first(e);

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

  1035 	}

  1036       }

  1037       operator Edge() const {

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

  1039       }

  1040     };

  1042     using GraphWrapper<Graph>::first;

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

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

  1045 //     }

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

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

  1048     }

  1049 //    FIXME not tested

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

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

  1052     }

  1053     EdgeIt& first(EdgeIt& i) const {

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

  1055     }

  1057     using GraphWrapper<Graph>::next;

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

  1059     OutEdgeIt& next(OutEdgeIt& e) const {

  1060       if (!e.backward) {

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

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

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

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

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

  1066 	  e.backward=true;

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

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

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

  1070 	}

  1071       } else {

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

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

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

  1075       }

  1076       return e;

  1077     }

  1078 //     FIXME Not tested

  1079     InEdgeIt& next(InEdgeIt& e) const {

  1080       if (!e.backward) {

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

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

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

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

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

  1086 	  e.backward=true;

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

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

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

  1090 	}

  1091       } else {

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

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

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

  1095       }

  1096       return e;

  1097     }

  1098     EdgeIt& next(EdgeIt& e) const {

  1099       if (!e.backward) {

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

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

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

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

  1104 	  e.backward=true;

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

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

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

  1108 	}

  1109       } else {

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

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

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

  1113       }

  1114       return e;

  1115     }

  1117     Node tail(Edge e) const {

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

  1119     Node head(Edge e) const {

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

  1122     Node aNode(OutEdgeIt e) const {

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

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

  1125     Node bNode(OutEdgeIt e) const {

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

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

  1129     Node aNode(InEdgeIt e) const {

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

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

  1132     Node bNode(InEdgeIt e) const {

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

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

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

  1137     //FIXME

  1138     void edgeNum() const { }

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

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

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

  1145     bool valid(Edge e) const {

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

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

  1148     }

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

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

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

  1154       if (!e.backward)

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

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

  1157       else

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

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

  1160     }

  1162     Number resCap(const Edge& e) const {

  1163       if (!e.backward)

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

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

  1166       else

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

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

  1169     }

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

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

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

  1174 //     }

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

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

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

  1179 //     }

  1181     template <typename T>

  1182     class EdgeMap {

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

  1184     public:

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

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

  1187       void set(Edge e, T a) {

  1188 	if (!e.backward)

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

  1190 	else

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

  1192       }

  1193       T operator[](Edge e) const {

  1194 	if (!e.backward)

  1195 	  return forward_map[e.out];

  1196 	else

  1197 	  return backward_map[e.in];

  1198       }

  1199 //       T get(Edge e) const {

  1200 // 	if (e.out_or_in)

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

  1202 // 	else

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

  1204 //       }

  1205     };

  1206   };

  1210   /// ErasingFirstGraphWrapper for blocking flows.

  1212   /// ErasingFirstGraphWrapper for blocking flows.

  1213   ///

  1214   ///\author Marton Makai

  1215   template<typename Graph, typename FirstOutEdgesMap>

  1216   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

  1217   protected:

  1218     FirstOutEdgesMap* first_out_edges;

  1219   public:

  1220     ErasingFirstGraphWrapper(Graph& _graph,

  1221 			     FirstOutEdgesMap& _first_out_edges) :

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

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

  1225 //     class NodeIt {

  1226 //       friend class GraphWrapper<Graph>;

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

  1228 //       typename Graph::NodeIt n;

  1229 //      public:

  1230 //       NodeIt() { }

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

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

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

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

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

  1236 //     };

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

  1238     class OutEdgeIt {

  1239       friend class GraphWrapper<Graph>;

  1240       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1241 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

  1242       typename Graph::OutEdgeIt e;

  1243     public:

  1244       OutEdgeIt() { }

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

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

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

  1248 		const Node& _n) :

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

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

  1251     };

  1252     class InEdgeIt {

  1253       friend class GraphWrapper<Graph>;

  1254       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1255 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

  1256       typename Graph::InEdgeIt e;

  1257     public:

  1258       InEdgeIt() { }

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

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

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

  1262 	       const Node& _n) :

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

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

  1265     };

  1266     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1267     class EdgeIt {

  1268       friend class GraphWrapper<Graph>;

  1269       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

  1270 //      typedef typename Graph::EdgeIt GraphEdgeIt;

  1271       typename Graph::EdgeIt e;

  1272     public:

  1273       EdgeIt() { }

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

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

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

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

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

  1279     };

  1281     using GraphWrapper<Graph>::first;

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

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

  1284 //     }

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

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

  1287     }

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

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

  1290     }

  1291     EdgeIt& first(EdgeIt& i) const {

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

  1293     }

  1295     using GraphWrapper<Graph>::next;

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

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

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

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

  1301     Node aNode(const OutEdgeIt& e) const {

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

  1303     Node aNode(const InEdgeIt& e) const {

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

  1305     Node bNode(const OutEdgeIt& e) const {

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

  1307     Node bNode(const InEdgeIt& e) const {

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

  1310     void erase(const OutEdgeIt& e) const {

  1311       OutEdgeIt f=e;

  1312       this->next(f);

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

  1314     }

  1315   };

  1317   ///@}

  1319 } //namespace hugo

  1322 #endif //HUGO_GRAPH_WRAPPER_H

author	alpar
	Sun, 09 May 2004 16:20:41 +0000
changeset 589	d89575370bcb
parent 576	d00c33d07114
child 593	b83b36ee7f10
permissions	-rw-r--r--