lemon-0.x: src/work/marci/graph_wrapper.h@42c660f58702

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

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_GRAPH_WRAPPER_H

     5 #include <invalid.h>

     7 namespace hugo {

     9   /// Graph wrappers

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

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

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

    14   /// latter notion needs further explanation.

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

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

    17   /// clearer.

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

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

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

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

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

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

    24   /// Thus, a wrapper class

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

    26   /// The code looks as follows

    27   /// \code

    28   /// ListGraph g;

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

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

    31   /// \endcode

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

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

    34   /// original graph with reverse orientation.

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

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

    37   /// implemented easily.

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

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

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

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

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

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

    44   /// wrappers.

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

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

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

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

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

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

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

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

    53   /// wrapper class

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

    55   /// has constructor

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

    57   /// This means that in a situation,

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

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

    60   /// \code

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

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

    63   ///   return algorithm2(rgw);

    64   /// }

    65   /// \endcode

    66   template<typename Graph>

    67   class GraphWrapper {

    68   protected:

    69     Graph* graph;

    71   public:

    72     typedef Graph BaseGraph;

    73     typedef Graph ParentGraph;

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

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

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

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

    80 //    typedef typename Graph::Node Node;

    81     class Node : public Graph::Node {

    82       friend class GraphWrapper<Graph>;

    83     public:

    84       Node() { }

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

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

    87     };

    88     class NodeIt {

    89       friend class GraphWrapper<Graph>;

    90       typename Graph::NodeIt n;

    91      public:

    92       NodeIt() { }

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

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

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

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

    97     };

    98 //    typedef typename Graph::Edge Edge;

    99     class Edge : public Graph::Edge {

   100       friend class GraphWrapper<Graph>;

   101     public:

   102       Edge() { }

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

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

   105     };

   106     class OutEdgeIt {

   107       friend class GraphWrapper<Graph>;

   108       typename Graph::OutEdgeIt e;

   109     public:

   110       OutEdgeIt() { }

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

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

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

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

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

   116     };

   117     class InEdgeIt {

   118       friend class GraphWrapper<Graph>;

   119       typename Graph::InEdgeIt e;

   120     public:

   121       InEdgeIt() { }

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

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

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

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

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

   127     };

   128     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   129     class EdgeIt {

   130       friend class GraphWrapper<Graph>;

   131       typename Graph::EdgeIt e;

   132     public:

   133       EdgeIt() { }

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

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

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

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

   138     };

   140     NodeIt& first(NodeIt& i) const {

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

   142     }

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

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

   145     }

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

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

   148     }

   149     EdgeIt& first(EdgeIt& i) const {

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

   151     }

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

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

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

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

   158     Node head(const Edge& e) const {

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

   160     Node tail(const Edge& e) const {

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

   163     bool valid(const Node& n) const {

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

   165     bool valid(const Edge& e) const {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   186     public:

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

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

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

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

   191     };

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

   194     public:

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

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

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

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

   199     };

   200   };

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

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

   205   template<typename Graph>

   206   class RevGraphWrapper : public GraphWrapper<Graph> {

   207   public:

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

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

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

   213     //If Graph::OutEdgeIt is not defined

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

   215     //the typdef techinque does not work.

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

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

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

   220     class OutEdgeIt {

   221       friend class GraphWrapper<Graph>;

   222       friend class RevGraphWrapper<Graph>;

   223       typename Graph::OutEdgeIt e;

   224     public:

   225       OutEdgeIt() { }

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

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

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

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

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

   231     };

   232     class InEdgeIt {

   233       friend class GraphWrapper<Graph>;

   234       friend class RevGraphWrapper<Graph>;

   235       typename Graph::InEdgeIt e;

   236     public:

   237       InEdgeIt() { }

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

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

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

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

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

   243     };

   245     using GraphWrapper<Graph>::first;

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

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

   248     }

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

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

   251     }

   253     using GraphWrapper<Graph>::next;

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

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

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

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

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

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

   261   };

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

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

   266   /// edge-set. The quick brown fox iterators jumps over

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

   268   /// in the bool maps.

   269   template<typename Graph, typename NodeFilterMap,

   270 	   typename EdgeFilterMap>

   271   class SubGraphWrapper : public GraphWrapper<Graph> {

   272   protected:

   273     NodeFilterMap* node_filter_map;

   274     EdgeFilterMap* edge_filter_map;

   275   public:

   277     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   278 		    EdgeFilterMap& _edge_filter_map) :

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

   280       edge_filter_map(&_edge_filter_map) { }

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

   283     class NodeIt {

   284       friend class GraphWrapper<Graph>;

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

   286       typename Graph::NodeIt n;

   287      public:

   288       NodeIt() { }

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

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

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

   292 	n(*(_G.graph)) {

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

   294 	  _G.graph->next(n);

   295       }

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

   297     };

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

   299     class OutEdgeIt {

   300       friend class GraphWrapper<Graph>;

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

   302       typename Graph::OutEdgeIt e;

   303     public:

   304       OutEdgeIt() { }

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

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

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

   308 		const Node& _n) :

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

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

   311 	  _G.graph->next(e);

   312       }

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

   314     };

   315     class InEdgeIt {

   316       friend class GraphWrapper<Graph>;

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

   318       typename Graph::InEdgeIt e;

   319     public:

   320       InEdgeIt() { }

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

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

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

   324 	       const Node& _n) :

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

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

   327 	  _G.graph->next(e);

   328       }

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

   330     };

   331     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   332     class EdgeIt {

   333       friend class GraphWrapper<Graph>;

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

   335       typename Graph::EdgeIt e;

   336     public:

   337       EdgeIt() { }

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

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

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

   341 	e(*(_G.graph)) {

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

   343 	  _G.graph->next(e);

   344       }

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

   346     };

   348     NodeIt& first(NodeIt& i) const {

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

   350     }

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

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

   353     }

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

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

   356     }

   357     EdgeIt& first(EdgeIt& i) const {

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

   359     }

   361     NodeIt& next(NodeIt& i) const {

   362       graph->next(i.n);

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

   364       return i;

   365     }

   366     OutEdgeIt& next(OutEdgeIt& i) const {

   367       graph->next(i.e);

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

   369       return i;

   370     }

   371     InEdgeIt& next(InEdgeIt& i) const {

   372       graph->next(i.e);

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

   374       return i;

   375     }

   376     EdgeIt& next(EdgeIt& i) const {

   377       graph->next(i.e);

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

   379       return i;

   380     }

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

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

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

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

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

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

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

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

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

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

   395   };

   397   /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one.

   399   /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one.

   400   template<typename Graph>

   401   class UndirGraphWrapper : public GraphWrapper<Graph> {

   402   public:

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

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

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

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

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

   410     class OutEdgeIt {

   411       friend class UndirGraphWrapper<Graph>;

   412       bool out_or_in; //true iff out

   413       typename Graph::OutEdgeIt out;

   414       typename Graph::InEdgeIt in;

   415     public:

   416       OutEdgeIt() { }

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

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

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

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

   421       }

   422       operator Edge() const {

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

   424       }

   425     };

   427 //FIXME InEdgeIt

   428     typedef OutEdgeIt InEdgeIt;

   430     using GraphWrapper<Graph>::first;

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

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

   433 //     }

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

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

   436     }

   437 //FIXME

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

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

   440 //     }

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

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

   443 //     }

   445     using GraphWrapper<Graph>::next;

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

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

   448 //       return n;

   449 //     }

   450     OutEdgeIt& next(OutEdgeIt& e) const {

   451       if (e.out_or_in) {

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

   453 	graph->next(e.out);

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

   455       } else {

   456 	graph->next(e.in);

   457       }

   458       return e;

   459     }

   460     //FIXME InEdgeIt

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

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

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

   464 //       return e;

   465 //     }

   467     Node aNode(const OutEdgeIt& e) const {

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

   469     Node bNode(const OutEdgeIt& e) const {

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

   471   };

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

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

   476   template<typename Graph, typename Number,

   477 	   typename CapacityMap, typename FlowMap>

   478   class ResGraphWrapper : public GraphWrapper<Graph> {

   479   protected:

   480     const CapacityMap* capacity;

   481     FlowMap* flow;

   482   public:

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

   485 		    FlowMap& _flow) :

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

   488     class Edge;

   489     class OutEdgeIt;

   490     friend class Edge;

   491     friend class OutEdgeIt;

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

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

   495     class Edge : public Graph::Edge {

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

   497     protected:

   498       bool forward; //true, iff forward

   499 //      typename Graph::Edge e;

   500     public:

   501       Edge() { }

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

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

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

   505 //the unique invalid iterator

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

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

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

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

   510       }

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

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

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

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

   515       }

   516     };

   518     class OutEdgeIt {

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

   520     protected:

   521       typename Graph::OutEdgeIt out;

   522       typename Graph::InEdgeIt in;

   523       bool forward;

   524     public:

   525       OutEdgeIt() { }

   526       //FIXME

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

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

   529 //the unique invalid iterator

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

   531 	forward=true;

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

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

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

   535 	  forward=false;

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

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

   538 	}

   539       }

   540       operator Edge() const {

   541 //	Edge e;

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

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

   544 //	return e;

   545 	if (this->forward)

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

   547 	else

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

   549       }

   550     };

   552     class InEdgeIt {

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

   554     protected:

   555       typename Graph::OutEdgeIt out;

   556       typename Graph::InEdgeIt in;

   557       bool forward;

   558     public:

   559       InEdgeIt() { }

   560       //FIXME

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

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

   563 //the unique invalid iterator

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

   565 	forward=true;

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

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

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

   569 	  forward=false;

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

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

   572 	}

   573       }

   574       operator Edge() const {

   575 //	Edge e;

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

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

   578 //	return e;

   579 	if (this->forward)

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

   581 	else

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

   583       }

   584     };

   586     class EdgeIt {

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

   588     protected:

   589       typename Graph::EdgeIt e;

   590       bool forward;

   591     public:

   592       EdgeIt() { }

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

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

   595 	forward=true;

   596 	resG.graph->first(e);

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

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

   599 	  forward=false;

   600 	  resG.graph->first(e);

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

   602 	}

   603       }

   604       operator Edge() const {

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

   606       }

   607     };

   609     using GraphWrapper<Graph>::first;

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

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

   612 //     }

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

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

   615     }

   616 //    FIXME not tested

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

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

   619     }

   620     EdgeIt& first(EdgeIt& i) const {

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

   622     }

   624     using GraphWrapper<Graph>::next;

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

   626     OutEdgeIt& next(OutEdgeIt& e) const {

   627       if (e.forward) {

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

   629 	graph->next(e.out);

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

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

   632 	  e.forward=false;

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

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

   635 	}

   636       } else {

   637 	graph->next(e.in);

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

   639       }

   640       return e;

   641     }

   642 //     FIXME Not tested

   643     InEdgeIt& next(InEdgeIt& e) const {

   644       if (e.forward) {

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

   646 	graph->next(e.in);

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

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

   649 	  e.forward=false;

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

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

   652 	}

   653       } else {

   654 	graph->next(e.out);

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

   656       }

   657       return e;

   658     }

   659     EdgeIt& next(EdgeIt& e) const {

   660       if (e.forward) {

   661 	graph->next(e.e);

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

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

   664 	  e.forward=false;

   665 	  graph->first(e.e);

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

   667 	}

   668       } else {

   669 	graph->next(e.e);

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

   671       }

   672       return e;

   673     }

   675     Node tail(Edge e) const {

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

   677     Node head(Edge e) const {

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

   680     Node aNode(OutEdgeIt e) const {

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

   682     Node bNode(OutEdgeIt e) const {

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

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

   686     //FIXME

   687     void edgeNum() const { }

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

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

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

   694     bool valid(Edge e) const {

   695       return graph->valid(e);

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

   697     }

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

   700       if (e.forward)

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

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

   703       else

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

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

   706     }

   708     Number resCap(const Edge& e) const {

   709       if (e.forward)

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

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

   712       else

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

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

   715     }

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

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

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

   720 //     }

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

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

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

   725 //     }

   727     template <typename T>

   728     class EdgeMap {

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

   730     public:

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

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

   733       void set(Edge e, T a) {

   734 	if (e.forward)

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

   736 	else

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

   738       }

   739       T operator[](Edge e) const {

   740 	if (e.forward)

   741 	  return forward_map[e.out];

   742 	else

   743 	  return backward_map[e.in];

   744       }

   745 //       T get(Edge e) const {

   746 // 	if (e.out_or_in)

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

   748 // 	else

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

   750 //       }

   751     };

   752   };

   754   /// ErasingFirstGraphWrapper for blocking flows.

   756   /// ErasingFirstGraphWrapper for blocking flows.

   757   template<typename Graph, typename FirstOutEdgesMap>

   758   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

   759   protected:

   760     FirstOutEdgesMap* first_out_edges;

   761   public:

   762     ErasingFirstGraphWrapper(Graph& _graph,

   763 			     FirstOutEdgesMap& _first_out_edges) :

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

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

   767 //     class NodeIt {

   768 //       friend class GraphWrapper<Graph>;

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

   770 //       typename Graph::NodeIt n;

   771 //      public:

   772 //       NodeIt() { }

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

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

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

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

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

   778 //     };

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

   780     class OutEdgeIt {

   781       friend class GraphWrapper<Graph>;

   782       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   783 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   784       typename Graph::OutEdgeIt e;

   785     public:

   786       OutEdgeIt() { }

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

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

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

   790 		const Node& _n) :

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

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

   793     };

   794     class InEdgeIt {

   795       friend class GraphWrapper<Graph>;

   796       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   797 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   798       typename Graph::InEdgeIt e;

   799     public:

   800       InEdgeIt() { }

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

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

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

   804 	       const Node& _n) :

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

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

   807     };

   808     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   809     class EdgeIt {

   810       friend class GraphWrapper<Graph>;

   811       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   812 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   813       typename Graph::EdgeIt e;

   814     public:

   815       EdgeIt() { }

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

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

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

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

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

   821     };

   823     using GraphWrapper<Graph>::first;

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

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

   826 //     }

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

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

   829     }

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

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

   832     }

   833     EdgeIt& first(EdgeIt& i) const {

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

   835     }

   837     using GraphWrapper<Graph>::next;

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

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

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

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

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

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

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

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

   848     void erase(const OutEdgeIt& e) const {

   849       OutEdgeIt f=e;

   850       this->next(f);

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

   852     }

   853   };

   857 //   /// experimentral, do not try it.

   858 //   template<typename Graph>

   859 //   class stGraphWrapper : public GraphWrapper<Graph> {

   860 //   public:

   861 //     class Node;

   862 //     class NodeIt;

   863 //     class Edge;

   864 //     class OutEdgeIt;

   865 //     class InEdgeIt;

   866 //     class EdgeIt;

   868 //     const Node s;

   869 //     const Node t;

   871 //     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph),

   872 // 				    s(INVALID, 1), t(INVALID, 2) { }

   874 //     class Node : public Graph::Node {

   875 //       friend class GraphWrapper<Graph>;

   876 //       friend class stGraphWrapper<Graph>;

   877 //     protected:

   878 //       int spec; //0 if real node, 1 iff s, 2 iff t

   879 //     public:

   880 //       Node() { }

   881 //       Node(const typename Graph::Node& _n, int _spec=0) :

   882 // 	Graph::Node(_n), spec(_spec) { }

   883 //       Node(const Invalid& i) : Graph::Node(i), spec(2) { }

   884 //       //invalid: (invalid, 2);

   885 //     };

   887 //     class NodeIt {

   888 //       friend class GraphWrapper<Graph>;

   889 //       friend class stGraphWrapper<Graph>;

   890 //       typename Graph::NodeIt n;

   891 //       int spec;

   892 //      public:

   893 //       NodeIt() { }

   894 //       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) :

   895 // 	n(_n), spec(_spec) { }

   896 //       NodeIt(const Invalid& i) : n(i), spec(2) { }

   897 //       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {

   898 // 	if (!_G->valid(n)) spec=1;

   899 //       }

   900 //       operator Node() const { return Node(n, spec); }

   901 //     };

   902 // //    typedef typename Graph::Edge Edge;

   903 //     class Edge : public Graph::Edge {

   904 //       friend class GraphWrapper<Graph>;

   905 //       friend class stGraphWrapper<Graph>;

   906 //       Node tail_spec;

   907 //       Node head_spec;

   908 //     public:

   909 //       Edge() { }

   910 //       Edge(const typename Graph::Edge& _e) :

   911 // 	Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) {

   912 // 	//a tail-t es a head-et real node-ra csinaljuk

   913 //       }

   914 //       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }

   915 //     };

   916 //     class OutEdgeIt {

   917 //       friend class GraphWrapper<Graph>;

   918 //       friend class stGraphWrapper<Graph>;

   919 //       typename Graph::OutEdgeIt e;

   920 //       Node tail_spec;

   921 //       Node head_spec;

   922 //     public:

   923 //       OutEdgeIt() { }

   924 //       OutEdgeIt(const typename Graph::OutEdgeIt& _e) :

   925 // 	e(_e), tail_spec(i, 0), head_spec(i, 0) {

   926 // 	//a tail-t es a head-et real node-ra csinaljuk

   927 //       }

   928 //       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }

   929 //       //invalid: (barmi, 0, 2)

   930 //       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {

   931 // 	switch (_n.spec) {

   932 // 	case 0 :

   933 // 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));

   934 // 	  _tail.spec=0;

   935 // 	  _head.spec=0;

   936 // 	  if (!_G.graph->valid(e)) spec=1;

   937 // 	  break;

   938 // 	case 1:

   939 // 	  e=INVALID;

   940 // 	  _tail.spec=1;

   941 // 	  _head(_G.graph->first(typename Graph::NodeIt()));

   942 // 	  if _head.spec==1

   943 // 	  break;

   944 // 	};

   946 // 	  }

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

   948 //     };

   949 //     class InEdgeIt {

   950 //       friend class GraphWrapper<Graph>;

   951 //       typename Graph::InEdgeIt e;

   952 //     public:

   953 //       InEdgeIt() { }

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

   955 //       InEdgeIt(const Invalid& i) : e(i) { }

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

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

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

   959 //     };

   960 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   961 //     class EdgeIt {

   962 //       friend class GraphWrapper<Graph>;

   963 //       typename Graph::EdgeIt e;

   964 //     public:

   965 //       EdgeIt() { }

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

   967 //       EdgeIt(const Invalid& i) : e(i) { }

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

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

   970 //     };

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

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

   974 //     }

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

   976 //       i=OutEdgeIt(*this, p); return i;

   977 //     }

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

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

   980 //     }

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

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

   983 //     }

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

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

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

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

   990 //     Node head(const Edge& e) const {

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

   992 //     Node tail(const Edge& e) const {

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

   995 //     bool valid(const Node& n) const {

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

   997 //     bool valid(const Edge& e) const {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1018 //     public:

  1019 //       NodeMap(const GraphWrapper<Graph>& _G) :

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

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

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

  1023 //     };

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

  1026 //     public:

  1027 //       EdgeMap(const GraphWrapper<Graph>& _G) :

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

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

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

  1031 //     };

  1032 //   };

  1034 } //namespace hugo

  1036 #endif //HUGO_GRAPH_WRAPPER_H

author	beckerjc
	Sat, 17 Apr 2004 19:19:57 +0000
changeset 349	42c660f58702
parent 341	6046b1d0f267
child 356	b4dcbe3e3b8f
permissions	-rw-r--r--