lemon-0.x: src/work/marci/graph_wrapper.h@5165a1c8633e

     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     ///\todo

   388     ///Some doki, please.

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

   390     ///\todo

   391     ///Some doki, please.

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

   394     ///\todo

   395     ///Some doki, please.

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

   397     ///\todo

   398     ///Some doki, please.

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

   401     ///\todo

   402     ///Some doki, please.

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

   404     ///\todo

   405     ///Some doki, please.

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

   407   };

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

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

   412   /// the orientation of a directed one.

   413   template<typename Graph>

   414   class UndirGraphWrapper : public GraphWrapper<Graph> {

   415   public:

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

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

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

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

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

   423     class OutEdgeIt {

   424       friend class UndirGraphWrapper<Graph>;

   425       bool out_or_in; //true iff out

   426       typename Graph::OutEdgeIt out;

   427       typename Graph::InEdgeIt in;

   428     public:

   429       OutEdgeIt() { }

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

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

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

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

   434       }

   435       operator Edge() const {

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

   437       }

   438     };

   440 //FIXME InEdgeIt

   441     typedef OutEdgeIt InEdgeIt;

   443     using GraphWrapper<Graph>::first;

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

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

   446 //     }

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

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

   449     }

   450 //FIXME

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

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

   453 //     }

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

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

   456 //     }

   458     using GraphWrapper<Graph>::next;

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

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

   461 //       return n;

   462 //     }

   463     OutEdgeIt& next(OutEdgeIt& e) const {

   464       if (e.out_or_in) {

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

   466 	graph->next(e.out);

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

   468       } else {

   469 	graph->next(e.in);

   470       }

   471       return e;

   472     }

   473     //FIXME InEdgeIt

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

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

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

   477 //       return e;

   478 //     }

   480     Node aNode(const OutEdgeIt& e) const {

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

   482     Node bNode(const OutEdgeIt& e) const {

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

   484   };

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

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

   489   template<typename Graph, typename Number,

   490 	   typename CapacityMap, typename FlowMap>

   491   class ResGraphWrapper : public GraphWrapper<Graph> {

   492   protected:

   493     const CapacityMap* capacity;

   494     FlowMap* flow;

   495   public:

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

   498 		    FlowMap& _flow) :

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

   501     class Edge;

   502     class OutEdgeIt;

   503     friend class Edge;

   504     friend class OutEdgeIt;

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

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

   508     class Edge : public Graph::Edge {

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

   510     protected:

   511       bool forward; //true, iff forward

   512 //      typename Graph::Edge e;

   513     public:

   514       Edge() { }

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

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

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

   518 //the unique invalid iterator

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

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

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

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

   523       }

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

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

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

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

   528       }

   529     };

   531     class OutEdgeIt {

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

   533     protected:

   534       typename Graph::OutEdgeIt out;

   535       typename Graph::InEdgeIt in;

   536       bool forward;

   537     public:

   538       OutEdgeIt() { }

   539       //FIXME

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

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

   542 //the unique invalid iterator

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

   544 	forward=true;

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

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

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

   548 	  forward=false;

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

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

   551 	}

   552       }

   553       operator Edge() const {

   554 //	Edge e;

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

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

   557 //	return e;

   558 	if (this->forward)

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

   560 	else

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

   562       }

   563     };

   565     class InEdgeIt {

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

   567     protected:

   568       typename Graph::OutEdgeIt out;

   569       typename Graph::InEdgeIt in;

   570       bool forward;

   571     public:

   572       InEdgeIt() { }

   573       //FIXME

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

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

   576 //the unique invalid iterator

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

   578 	forward=true;

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

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

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

   582 	  forward=false;

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

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

   585 	}

   586       }

   587       operator Edge() const {

   588 //	Edge e;

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

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

   591 //	return e;

   592 	if (this->forward)

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

   594 	else

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

   596       }

   597     };

   599     class EdgeIt {

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

   601     protected:

   602       typename Graph::EdgeIt e;

   603       bool forward;

   604     public:

   605       EdgeIt() { }

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

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

   608 	forward=true;

   609 	resG.graph->first(e);

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

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

   612 	  forward=false;

   613 	  resG.graph->first(e);

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

   615 	}

   616       }

   617       operator Edge() const {

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

   619       }

   620     };

   622     using GraphWrapper<Graph>::first;

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

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

   625 //     }

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

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

   628     }

   629 //    FIXME not tested

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

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

   632     }

   633     EdgeIt& first(EdgeIt& i) const {

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

   635     }

   637     using GraphWrapper<Graph>::next;

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

   639     OutEdgeIt& next(OutEdgeIt& e) const {

   640       if (e.forward) {

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

   642 	graph->next(e.out);

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

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

   645 	  e.forward=false;

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

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

   648 	}

   649       } else {

   650 	graph->next(e.in);

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

   652       }

   653       return e;

   654     }

   655 //     FIXME Not tested

   656     InEdgeIt& next(InEdgeIt& e) const {

   657       if (e.forward) {

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

   659 	graph->next(e.in);

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

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

   662 	  e.forward=false;

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

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

   665 	}

   666       } else {

   667 	graph->next(e.out);

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

   669       }

   670       return e;

   671     }

   672     EdgeIt& next(EdgeIt& e) const {

   673       if (e.forward) {

   674 	graph->next(e.e);

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

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

   677 	  e.forward=false;

   678 	  graph->first(e.e);

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

   680 	}

   681       } else {

   682 	graph->next(e.e);

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

   684       }

   685       return e;

   686     }

   688     Node tail(Edge e) const {

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

   690     Node head(Edge e) const {

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

   693     Node aNode(OutEdgeIt e) const {

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

   695     Node bNode(OutEdgeIt e) const {

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

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

   699     //FIXME

   700     void edgeNum() const { }

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

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

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

   707     bool valid(Edge e) const {

   708       return graph->valid(e);

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

   710     }

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

   713       if (e.forward)

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

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

   716       else

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

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

   719     }

   721     Number resCap(const Edge& e) const {

   722       if (e.forward)

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

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

   725       else

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

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

   728     }

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

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

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

   733 //     }

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

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

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

   738 //     }

   740     template <typename T>

   741     class EdgeMap {

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

   743     public:

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

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

   746       void set(Edge e, T a) {

   747 	if (e.forward)

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

   749 	else

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

   751       }

   752       T operator[](Edge e) const {

   753 	if (e.forward)

   754 	  return forward_map[e.out];

   755 	else

   756 	  return backward_map[e.in];

   757       }

   758 //       T get(Edge e) const {

   759 // 	if (e.out_or_in)

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

   761 // 	else

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

   763 //       }

   764     };

   765   };

   767   /// ErasingFirstGraphWrapper for blocking flows.

   769   /// ErasingFirstGraphWrapper for blocking flows.

   770   template<typename Graph, typename FirstOutEdgesMap>

   771   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

   772   protected:

   773     FirstOutEdgesMap* first_out_edges;

   774   public:

   775     ErasingFirstGraphWrapper(Graph& _graph,

   776 			     FirstOutEdgesMap& _first_out_edges) :

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

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

   780 //     class NodeIt {

   781 //       friend class GraphWrapper<Graph>;

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

   783 //       typename Graph::NodeIt n;

   784 //      public:

   785 //       NodeIt() { }

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

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

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

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

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

   791 //     };

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

   793     class OutEdgeIt {

   794       friend class GraphWrapper<Graph>;

   795       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   796 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   797       typename Graph::OutEdgeIt e;

   798     public:

   799       OutEdgeIt() { }

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

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

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

   803 		const Node& _n) :

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

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

   806     };

   807     class InEdgeIt {

   808       friend class GraphWrapper<Graph>;

   809       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   810 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   811       typename Graph::InEdgeIt e;

   812     public:

   813       InEdgeIt() { }

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

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

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

   817 	       const Node& _n) :

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

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

   820     };

   821     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   822     class EdgeIt {

   823       friend class GraphWrapper<Graph>;

   824       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   825 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   826       typename Graph::EdgeIt e;

   827     public:

   828       EdgeIt() { }

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

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

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

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

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

   834     };

   836     using GraphWrapper<Graph>::first;

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

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

   839 //     }

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

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

   842     }

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

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

   845     }

   846     EdgeIt& first(EdgeIt& i) const {

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

   848     }

   850     using GraphWrapper<Graph>::next;

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

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

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

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

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

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

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

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

   861     void erase(const OutEdgeIt& e) const {

   862       OutEdgeIt f=e;

   863       this->next(f);

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

   865     }

   866   };

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

   871 //   template<typename Graph>

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

   873 //   public:

   874 //     class Node;

   875 //     class NodeIt;

   876 //     class Edge;

   877 //     class OutEdgeIt;

   878 //     class InEdgeIt;

   879 //     class EdgeIt;

   881 //     const Node s;

   882 //     const Node t;

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

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

   887 //     class Node : public Graph::Node {

   888 //       friend class GraphWrapper<Graph>;

   889 //       friend class stGraphWrapper<Graph>;

   890 //     protected:

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

   892 //     public:

   893 //       Node() { }

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

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

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

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

   898 //     };

   900 //     class NodeIt {

   901 //       friend class GraphWrapper<Graph>;

   902 //       friend class stGraphWrapper<Graph>;

   903 //       typename Graph::NodeIt n;

   904 //       int spec;

   905 //      public:

   906 //       NodeIt() { }

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

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

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

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

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

   912 //       }

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

   914 //     };

   915 // //    typedef typename Graph::Edge Edge;

   916 //     class Edge : public Graph::Edge {

   917 //       friend class GraphWrapper<Graph>;

   918 //       friend class stGraphWrapper<Graph>;

   919 //       Node tail_spec;

   920 //       Node head_spec;

   921 //     public:

   922 //       Edge() { }

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

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

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

   926 //       }

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

   928 //     };

   929 //     class OutEdgeIt {

   930 //       friend class GraphWrapper<Graph>;

   931 //       friend class stGraphWrapper<Graph>;

   932 //       typename Graph::OutEdgeIt e;

   933 //       Node tail_spec;

   934 //       Node head_spec;

   935 //     public:

   936 //       OutEdgeIt() { }

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

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

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

   940 //       }

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

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

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

   944 // 	switch (_n.spec) {

   945 // 	case 0 :

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

   947 // 	  _tail.spec=0;

   948 // 	  _head.spec=0;

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

   950 // 	  break;

   951 // 	case 1:

   952 // 	  e=INVALID;

   953 // 	  _tail.spec=1;

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

   955 // 	  if _head.spec==1

   956 // 	  break;

   957 // 	};

   959 // 	  }

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

   961 //     };

   962 //     class InEdgeIt {

   963 //       friend class GraphWrapper<Graph>;

   964 //       typename Graph::InEdgeIt e;

   965 //     public:

   966 //       InEdgeIt() { }

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

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

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

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

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

   972 //     };

   973 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   974 //     class EdgeIt {

   975 //       friend class GraphWrapper<Graph>;

   976 //       typename Graph::EdgeIt e;

   977 //     public:

   978 //       EdgeIt() { }

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

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

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

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

   983 //     };

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

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

   987 //     }

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

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

   990 //     }

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

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

   993 //     }

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

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

   996 //     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1031 //     public:

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

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

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

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

  1036 //     };

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

  1039 //     public:

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

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

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

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

  1044 //     };

  1045 //   };

  1047 } //namespace hugo

  1049 #endif //HUGO_GRAPH_WRAPPER_H

author	alpar
	Wed, 21 Apr 2004 12:36:53 +0000
changeset 357	5165a1c8633e
parent 356	b4dcbe3e3b8f
child 363	7a05119c121a
permissions	-rw-r--r--