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

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

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

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

   224   ///

   225   ///\author Marton Makai

   226   template<typename Graph>

   227   class RevGraphWrapper : public GraphWrapper<Graph> {

   228   protected:

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

   230   public:

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

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

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

   235     //If Graph::OutEdgeIt is not defined

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

   237     //the typdef techinque does not work.

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

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

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

   242     class OutEdgeIt {

   243       friend class GraphWrapper<Graph>;

   244       friend class RevGraphWrapper<Graph>;

   245       typename Graph::InEdgeIt e;

   246     public:

   247       OutEdgeIt() { }

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

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

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

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

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

   253     };

   254     class InEdgeIt {

   255       friend class GraphWrapper<Graph>;

   256       friend class RevGraphWrapper<Graph>;

   257       typename Graph::OutEdgeIt e;

   258     public:

   259       InEdgeIt() { }

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

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

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

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

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

   265     };

   267     using GraphWrapper<Graph>::first;

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

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

   270     }

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

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

   273     }

   275     using GraphWrapper<Graph>::next;

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

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

   279     Node aNode(const OutEdgeIt& e) const {

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

   281     Node aNode(const InEdgeIt& e) const {

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

   283     Node bNode(const OutEdgeIt& e) const {

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

   285     Node bNode(const InEdgeIt& e) const {

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

   288     Node tail(const Edge& e) const {

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

   290     Node head(const Edge& e) const {

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

   293   };

   295   /// Wrapper for hiding nodes and edges from a graph.

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

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

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

   300   /// in the bool maps.

   301   ///

   302   ///\author Marton Makai

   303   template<typename Graph, typename NodeFilterMap,

   304 	   typename EdgeFilterMap>

   305   class SubGraphWrapper : public GraphWrapper<Graph> {

   306   protected:

   307     NodeFilterMap* node_filter_map;

   308     EdgeFilterMap* edge_filter_map;

   310     SubGraphWrapper() : GraphWrapper<Graph>(0),

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

   312     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   313       node_filter_map=&_node_filter_map;

   314     }

   315     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

   316       edge_filter_map=&_edge_filter_map;

   317     }

   319   public:

   321     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   322 		    EdgeFilterMap& _edge_filter_map) :

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

   324       edge_filter_map(&_edge_filter_map) { }

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

   327     class NodeIt {

   328       friend class GraphWrapper<Graph>;

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

   330       typename Graph::NodeIt n;

   331      public:

   332       NodeIt() { }

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

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

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

   336 	n(*(_G.graph)) {

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

   338 	  _G.graph->next(n);

   339       }

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

   341     };

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

   343     class OutEdgeIt {

   344       friend class GraphWrapper<Graph>;

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

   346       typename Graph::OutEdgeIt e;

   347     public:

   348       OutEdgeIt() { }

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

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

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

   352 		const Node& _n) :

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

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

   355 	  _G.graph->next(e);

   356       }

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

   358     };

   359     class InEdgeIt {

   360       friend class GraphWrapper<Graph>;

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

   362       typename Graph::InEdgeIt e;

   363     public:

   364       InEdgeIt() { }

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

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

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

   368 	       const Node& _n) :

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

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

   371 	  _G.graph->next(e);

   372       }

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

   374     };

   375     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   376     class EdgeIt {

   377       friend class GraphWrapper<Graph>;

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

   379       typename Graph::EdgeIt e;

   380     public:

   381       EdgeIt() { }

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

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

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

   385 	e(*(_G.graph)) {

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

   387 	  _G.graph->next(e);

   388       }

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

   390     };

   392     NodeIt& first(NodeIt& i) const {

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

   394     }

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

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

   397     }

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

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

   400     }

   401     EdgeIt& first(EdgeIt& i) const {

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

   403     }

   405     NodeIt& next(NodeIt& i) const {

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

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

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

   409       return i;

   410     }

   411     OutEdgeIt& next(OutEdgeIt& i) const {

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

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

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

   415       return i;

   416     }

   417     InEdgeIt& next(InEdgeIt& i) const {

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

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

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

   421       return i;

   422     }

   423     EdgeIt& next(EdgeIt& i) const {

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

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

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

   427       return i;

   428     }

   430     Node aNode(const OutEdgeIt& e) const {

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

   432     Node aNode(const InEdgeIt& e) const {

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

   434     Node bNode(const OutEdgeIt& e) const {

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

   436     Node bNode(const InEdgeIt& e) const {

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

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

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

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

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

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

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

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

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

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

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

   451     /// again

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

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

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

   456     /// again

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

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

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

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

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

   464   };

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

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

   469   /// the orientation of a directed one.

   470   template<typename Graph>

   471   class UndirGraphWrapper : public GraphWrapper<Graph> {

   472   protected:

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

   475   public:

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

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

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

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

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

   483     class OutEdgeIt {

   484       friend class UndirGraphWrapper<Graph>;

   485       bool out_or_in; //true iff out

   486       typename Graph::OutEdgeIt out;

   487       typename Graph::InEdgeIt in;

   488     public:

   489       OutEdgeIt() { }

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

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

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

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

   494       }

   495       operator Edge() const {

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

   497       }

   498     };

   500 //FIXME InEdgeIt

   501     typedef OutEdgeIt InEdgeIt;

   503     using GraphWrapper<Graph>::first;

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

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

   506 //     }

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

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

   509     }

   510 //FIXME

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

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

   513 //     }

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

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

   516 //     }

   518     using GraphWrapper<Graph>::next;

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

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

   521 //       return n;

   522 //     }

   523     OutEdgeIt& next(OutEdgeIt& e) const {

   524       if (e.out_or_in) {

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

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

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

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

   529       } else {

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

   531       }

   532       return e;

   533     }

   534     //FIXME InEdgeIt

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

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

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

   538 //       return e;

   539 //     }

   541     Node aNode(const OutEdgeIt& e) const {

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

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

   544     Node bNode(const OutEdgeIt& e) const {

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

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

   547   };

   551   /// An undirected graph template

   552   template<typename Graph>

   553   class UndirGraph : public UndirGraphWrapper<Graph> {

   554     typedef UndirGraphWrapper<Graph> Parent;

   555   protected:

   556     Graph gr;

   557   public:

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

   559       Parent::setGraph(gr);

   560     }

   561   };

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

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

   568   template<typename Graph, typename Number,

   569 	   typename CapacityMap, typename FlowMap>

   570   class ResGraphWrapper : public GraphWrapper<Graph> {

   571   protected:

   572     const CapacityMap* capacity;

   573     FlowMap* flow;

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

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

   577     void setCapacityMap(const CapacityMap& _capacity) {

   578       capacity=&_capacity;

   579     }

   580     void setFlowMap(FlowMap& _flow) {

   581       flow=&_flow;

   582     }

   584   public:

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

   587 		    FlowMap& _flow) :

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

   590     class Edge;

   591     class OutEdgeIt;

   592     friend class Edge;

   593     friend class OutEdgeIt;

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

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

   597     class Edge : public Graph::Edge {

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

   599     protected:

   600       bool backward; //true, iff backward

   601 //      typename Graph::Edge e;

   602     public:

   603       Edge() { }

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

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

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

   607 //the unique invalid iterator

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

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

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

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

   612       }

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

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

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

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

   617       }

   618     };

   620     class OutEdgeIt {

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

   622     protected:

   623       typename Graph::OutEdgeIt out;

   624       typename Graph::InEdgeIt in;

   625       bool backward;

   626     public:

   627       OutEdgeIt() { }

   628       //FIXME

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

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

   631 //the unique invalid iterator

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

   633 	backward=false;

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

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

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

   637 	  backward=true;

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

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

   640 	}

   641       }

   642       operator Edge() const {

   643 //	Edge e;

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

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

   646 //	return e;

   647 	if (this->backward)

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

   649 	else

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

   651       }

   652     };

   654     class InEdgeIt {

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

   656     protected:

   657       typename Graph::OutEdgeIt out;

   658       typename Graph::InEdgeIt in;

   659       bool backward;

   660     public:

   661       InEdgeIt() { }

   662       //FIXME

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

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

   665 //the unique invalid iterator

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

   667 	backward=false;

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

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

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

   671 	  backward=true;

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

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

   674 	}

   675       }

   676       operator Edge() const {

   677 //	Edge e;

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

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

   680 //	return e;

   681 	if (this->backward)

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

   683 	else

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

   685       }

   686     };

   688     class EdgeIt {

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

   690     protected:

   691       typename Graph::EdgeIt e;

   692       bool backward;

   693     public:

   694       EdgeIt() { }

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

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

   697 	backward=false;

   698 	resG.graph->first(e);

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

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

   701 	  backward=true;

   702 	  resG.graph->first(e);

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

   704 	}

   705       }

   706       operator Edge() const {

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

   708       }

   709     };

   711     using GraphWrapper<Graph>::first;

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

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

   714 //     }

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

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

   717     }

   718 //    FIXME not tested

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

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

   721     }

   722     EdgeIt& first(EdgeIt& i) const {

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

   724     }

   726     using GraphWrapper<Graph>::next;

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

   728     OutEdgeIt& next(OutEdgeIt& e) const {

   729       if (!e.backward) {

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

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

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

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

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

   735 	  e.backward=true;

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

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

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

   739 	}

   740       } else {

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

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

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

   744       }

   745       return e;

   746     }

   747 //     FIXME Not tested

   748     InEdgeIt& next(InEdgeIt& e) const {

   749       if (!e.backward) {

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

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

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

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

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

   755 	  e.backward=true;

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

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

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

   759 	}

   760       } else {

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

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

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

   764       }

   765       return e;

   766     }

   767     EdgeIt& next(EdgeIt& e) const {

   768       if (!e.backward) {

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

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

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

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

   773 	  e.backward=true;

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

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

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

   777 	}

   778       } else {

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

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

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

   782       }

   783       return e;

   784     }

   786     Node tail(Edge e) const {

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

   788     Node head(Edge e) const {

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

   791     Node aNode(OutEdgeIt e) const {

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

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

   794     Node bNode(OutEdgeIt e) const {

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

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

   798     Node aNode(InEdgeIt e) const {

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

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

   801     Node bNode(InEdgeIt e) const {

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

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

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

   806     //FIXME

   807     void edgeNum() const { }

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

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

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

   814     bool valid(Edge e) const {

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

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

   817     }

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

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

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

   823       if (!e.backward)

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

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

   826       else

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

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

   829     }

   831     Number resCap(const Edge& e) const {

   832       if (!e.backward)

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

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

   835       else

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

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

   838     }

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

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

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

   843 //     }

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

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

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

   848 //     }

   850     template <typename T>

   851     class EdgeMap {

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

   853     public:

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

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

   856       void set(Edge e, T a) {

   857 	if (!e.backward)

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

   859 	else

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

   861       }

   862       T operator[](Edge e) const {

   863 	if (!e.backward)

   864 	  return forward_map[e.out];

   865 	else

   866 	  return backward_map[e.in];

   867       }

   868 //       T get(Edge e) const {

   869 // 	if (e.out_or_in)

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

   871 // 	else

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

   873 //       }

   874     };

   875   };

   877   /// ErasingFirstGraphWrapper for blocking flows.

   879   /// ErasingFirstGraphWrapper for blocking flows.

   880   ///

   881   ///\author Marton Makai

   882   template<typename Graph, typename FirstOutEdgesMap>

   883   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

   884   protected:

   885     FirstOutEdgesMap* first_out_edges;

   886   public:

   887     ErasingFirstGraphWrapper(Graph& _graph,

   888 			     FirstOutEdgesMap& _first_out_edges) :

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

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

   892 //     class NodeIt {

   893 //       friend class GraphWrapper<Graph>;

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

   895 //       typename Graph::NodeIt n;

   896 //      public:

   897 //       NodeIt() { }

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

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

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

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

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

   903 //     };

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

   905     class OutEdgeIt {

   906       friend class GraphWrapper<Graph>;

   907       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   908 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   909       typename Graph::OutEdgeIt e;

   910     public:

   911       OutEdgeIt() { }

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

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

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

   915 		const Node& _n) :

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

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

   918     };

   919     class InEdgeIt {

   920       friend class GraphWrapper<Graph>;

   921       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   922 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   923       typename Graph::InEdgeIt e;

   924     public:

   925       InEdgeIt() { }

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

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

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

   929 	       const Node& _n) :

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

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

   932     };

   933     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   934     class EdgeIt {

   935       friend class GraphWrapper<Graph>;

   936       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   937 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   938       typename Graph::EdgeIt e;

   939     public:

   940       EdgeIt() { }

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

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

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

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

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

   946     };

   948     using GraphWrapper<Graph>::first;

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

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

   951 //     }

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

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

   954     }

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

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

   957     }

   958     EdgeIt& first(EdgeIt& i) const {

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

   960     }

   962     using GraphWrapper<Graph>::next;

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

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

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

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

   968     Node aNode(const OutEdgeIt& e) const {

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

   970     Node aNode(const InEdgeIt& e) const {

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

   972     Node bNode(const OutEdgeIt& e) const {

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

   974     Node bNode(const InEdgeIt& e) const {

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

   977     void erase(const OutEdgeIt& e) const {

   978       OutEdgeIt f=e;

   979       this->next(f);

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

   981     }

   982   };

   984   ///@}

   986 } //namespace hugo

   989 #endif //HUGO_GRAPH_WRAPPER_H

author	alpar
	Fri, 07 May 2004 06:57:50 +0000
changeset 567	efaa79ee8d14
parent 561	a10e6f1769e2
child 569	3b6afd33c221
permissions	-rw-r--r--