lemon-0.x: src/lemon/graph_wrapper.h@2414b5ab7684

     1 /* -*- C++ -*-

     2  * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Combinatorial Optimization Research Group, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_GRAPH_WRAPPER_H

    18 #define LEMON_GRAPH_WRAPPER_H

    20 ///\ingroup gwrappers

    21 ///\file

    22 ///\brief Several graph wrappers.

    23 ///

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

    25 ///

    26 ///\author Marton Makai

    28 #include <lemon/invalid.h>

    29 #include <lemon/maps.h>

    30 #include <lemon/iterable_graph_extender.h>

    31 #include <iostream>

    33 namespace lemon {

    35   // Graph wrappers

    37   /*!

    38     \addtogroup gwrappers

    39     @{

    40    */

    42   /*!

    43     Base type for the Graph Wrappers

    45     \warning Graph wrappers are in even more experimental state than the other

    46     parts of the lib. Use them at you own risk.

    48     This is the base type for most of LEMON graph wrappers.

    49     This class implements a trivial graph wrapper i.e. it only wraps the

    50     functions and types of the graph. The purpose of this class is to

    51     make easier implementing graph wrappers. E.g. if a wrapper is

    52     considered which differs from the wrapped graph only in some of its

    53     functions or types, then it can be derived from GraphWrapper, and only the

    54     differences should be implemented.

    56     \author Marton Makai

    57   */

    58   template<typename _Graph>

    59   class GraphWrapperBase {

    60   public:

    61     typedef _Graph Graph;

    62     /// \todo Is it needed?

    63     typedef Graph BaseGraph;

    64     typedef Graph ParentGraph;

    66   protected:

    67     Graph* graph;

    68     GraphWrapperBase() : graph(0) { }

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

    71   public:

    72     GraphWrapperBase(Graph& _graph) : graph(&_graph) { }

    74     typedef typename Graph::Node Node;

    75     typedef typename Graph::Edge Edge;

    77     void first(Node& i) const { graph->first(i); }

    78     void first(Edge& i) const { graph->first(i); }

    79     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }

    80     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

    82     void next(Node& i) const { graph->next(i); }

    83     void next(Edge& i) const { graph->next(i); }

    84     void nextIn(Edge& i) const { graph->nextIn(i); }

    85     void nextOut(Edge& i) const { graph->nextOut(i); }

    87     Node source(const Edge& e) const { return graph->source(e); }

    88     Node target(const Edge& e) const { return graph->target(e); }

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

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

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

    94     Edge addEdge(const Node& source, const Node& target) const {

    95       return Edge(graph->addEdge(source, target)); }

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

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

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

   102     bool forward(const Edge& e) const { return graph->forward(e); }

   103     bool backward(const Edge& e) const { return graph->backward(e); }

   105     int id(const Node& v) const { return graph->id(v); }

   106     int id(const Edge& e) const { return graph->id(e); }

   108     Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }

   110     template <typename _Value>

   111     class NodeMap : public _Graph::template NodeMap<_Value> {

   112     public:

   113       typedef typename _Graph::template NodeMap<_Value> Parent;

   114       NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }

   115       NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)

   116       : Parent(*gw.graph, value) { }

   117     };

   119     template <typename _Value>

   120     class EdgeMap : public _Graph::template EdgeMap<_Value> {

   121     public:

   122       typedef typename _Graph::template EdgeMap<_Value> Parent;

   123       EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }

   124       EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)

   125       : Parent(*gw.graph, value) { }

   126     };

   128   };

   130   template <typename _Graph>

   131   class GraphWrapper :

   132     public IterableGraphExtender<GraphWrapperBase<_Graph> > {

   133   public:

   134     typedef _Graph Graph;

   135     typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;

   136   protected:

   137     GraphWrapper() : Parent() { }

   139   public:

   140     GraphWrapper(Graph& _graph) { setGraph(_graph); }

   141   };

   143   template <typename _Graph>

   144   class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {

   145   public:

   146     typedef _Graph Graph;

   147     typedef GraphWrapperBase<_Graph> Parent;

   148   protected:

   149     RevGraphWrapperBase() : Parent() { }

   150   public:

   151     typedef typename Parent::Node Node;

   152     typedef typename Parent::Edge Edge;

   154     using Parent::first;

   155     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }

   156     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }

   158     using Parent::next;

   159     void nextIn(Edge& i) const { Parent::nextOut(i); }

   160     void nextOut(Edge& i) const { Parent::nextIn(i); }

   162     Node source(const Edge& e) const { return Parent::target(e); }

   163     Node target(const Edge& e) const { return Parent::source(e); }

   164   };

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

   169   ///\warning Graph wrappers are in even more experimental state than the other

   170   ///parts of the lib. Use them at you own risk.

   171   ///

   172   /// Let \f$G=(V, A)\f$ be a directed graph and

   173   /// suppose that a graph instange \c g of type

   174   /// \c ListGraph implements \f$G\f$.

   175   /// \code

   176   /// ListGraph g;

   177   /// \endcode

   178   /// For each directed edge

   179   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by

   180   /// reversing its orientation.

   181   /// Then RevGraphWrapper implements the graph structure with node-set

   182   /// \f$V\f$ and edge-set

   183   /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be

   184   /// reversing the orientation of its edges. The following code shows how

   185   /// such an instance can be constructed.

   186   /// \code

   187   /// RevGraphWrapper<ListGraph> gw(g);

   188   /// \endcode

   189   ///\author Marton Makai

   190   template<typename _Graph>

   191   class RevGraphWrapper :

   192     public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {

   193   public:

   194     typedef _Graph Graph;

   195     typedef IterableGraphExtender<

   196       RevGraphWrapperBase<_Graph> > Parent;

   197   protected:

   198     RevGraphWrapper() { }

   199   public:

   200     RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }

   201   };

   204   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>

   205   class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {

   206   public:

   207     typedef _Graph Graph;

   208     typedef GraphWrapperBase<_Graph> Parent;

   209   protected:

   210     NodeFilterMap* node_filter_map;

   211     EdgeFilterMap* edge_filter_map;

   212     SubGraphWrapperBase() : Parent(),

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

   215     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   216       node_filter_map=&_node_filter_map;

   217     }

   218     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

   219       edge_filter_map=&_edge_filter_map;

   220     }

   222   public:

   223 //     SubGraphWrapperBase(Graph& _graph,

   224 // 			NodeFilterMap& _node_filter_map,

   225 // 			EdgeFilterMap& _edge_filter_map) :

   226 //       Parent(&_graph),

   227 //       node_filter_map(&node_filter_map),

   228 //       edge_filter_map(&edge_filter_map) { }

   230     typedef typename Parent::Node Node;

   231     typedef typename Parent::Edge Edge;

   233     void first(Node& i) const {

   234       Parent::first(i);

   235       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   236     }

   237     void first(Edge& i) const {

   238       Parent::first(i);

   239       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);

   240     }

   241     void firstIn(Edge& i, const Node& n) const {

   242       Parent::firstIn(i, n);

   243       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);

   244     }

   245     void firstOut(Edge& i, const Node& n) const {

   246       Parent::firstOut(i, n);

   247       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);

   248     }

   250     void next(Node& i) const {

   251       Parent::next(i);

   252       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   253     }

   254     void next(Edge& i) const {

   255       Parent::next(i);

   256       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);

   257     }

   258     void nextIn(Edge& i) const {

   259       Parent::nextIn(i);

   260       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);

   261     }

   262     void nextOut(Edge& i) const {

   263       Parent::nextOut(i);

   264       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);

   265     }

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

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

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

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

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

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

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

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

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

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

   279     /// again

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

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

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

   284     /// again

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

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

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

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

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

   293     /// \warning This is a linear time operation and works only if s

   294     /// \c Graph::NodeIt is defined.

   295     /// \todo assign tags.

   296     int nodeNum() const {

   297       int i=0;

   298       Node n;

   299       for (first(n); n!=INVALID; next(n)) ++i;

   300       return i;

   301     }

   303     /// \warning This is a linear time operation and works only if

   304     /// \c Graph::EdgeIt is defined.

   305     /// \todo assign tags.

   306     int edgeNum() const {

   307       int i=0;

   308       Edge e;

   309       for (first(e); e!=INVALID; next(e)) ++i;

   310       return i;

   311     }

   314   };

   316   /*! \brief A graph wrapper for hiding nodes and edges from a graph.

   318   \warning Graph wrappers are in even more experimental state than the other

   319   parts of the lib. Use them at you own risk.

   321   This wrapper shows a graph with filtered node-set and

   322   edge-set.

   323   Given a bool-valued map on the node-set and one on

   324   the edge-set of the graph, the iterators show only the objects

   325   having true value. We have to note that this does not mean that an

   326   induced subgraph is obtained, the node-iterator cares only the filter

   327   on the node-set, and the edge-iterators care only the filter on the

   328   edge-set.

   329   \code

   330   typedef SmartGraph Graph;

   331   Graph g;

   332   typedef Graph::Node Node;

   333   typedef Graph::Edge Edge;

   334   Node u=g.addNode(); //node of id 0

   335   Node v=g.addNode(); //node of id 1

   336   Node e=g.addEdge(u, v); //edge of id 0

   337   Node f=g.addEdge(v, u); //edge of id 1

   338   Graph::NodeMap<bool> nm(g, true);

   339   nm.set(u, false);

   340   Graph::EdgeMap<bool> em(g, true);

   341   em.set(e, false);

   342   typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;

   343   SubGW gw(g, nm, em);

   344   for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;

   345   std::cout << ":-)" << std::endl;

   346   for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;

   347   \endcode

   348   The output of the above code is the following.

   349   \code

   350   1

   351   :-)

   352   1

   353   \endcode

   354   Note that \c n is of type \c SubGW::NodeIt, but it can be converted to

   355   \c Graph::Node that is why \c g.id(n) can be applied.

   357   For other examples see also the documentation of NodeSubGraphWrapper and

   358   EdgeSubGraphWrapper.

   360   \author Marton Makai

   361   */

   362   template<typename _Graph, typename NodeFilterMap,

   363 	   typename EdgeFilterMap>

   364   class SubGraphWrapper :

   365     public IterableGraphExtender<

   366     SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {

   367   public:

   368     typedef _Graph Graph;

   369     typedef IterableGraphExtender<

   370       SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

   371   protected:

   372     SubGraphWrapper() { }

   373   public:

   374     SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,

   375 		    EdgeFilterMap& _edge_filter_map) {

   376       setGraph(_graph);

   377       setNodeFilterMap(_node_filter_map);

   378       setEdgeFilterMap(_edge_filter_map);

   379     }

   380   };

   384   /*! \brief A wrapper for hiding nodes from a graph.

   386   \warning Graph wrappers are in even more experimental state than the other

   387   parts of the lib. Use them at you own risk.

   389   A wrapper for hiding nodes from a graph.

   390   This wrapper specializes SubGraphWrapper in the way that only the node-set

   391   can be filtered. Note that this does not mean of considering induced

   392   subgraph, the edge-iterators consider the original edge-set.

   393   \author Marton Makai

   394   */

   395   template<typename Graph, typename NodeFilterMap>

   396   class NodeSubGraphWrapper :

   397     public SubGraphWrapper<Graph, NodeFilterMap,

   398 			   ConstMap<typename Graph::Edge,bool> > {

   399   public:

   400     typedef SubGraphWrapper<Graph, NodeFilterMap,

   401 			    ConstMap<typename Graph::Edge,bool> > Parent;

   402   protected:

   403     ConstMap<typename Graph::Edge, bool> const_true_map;

   404   public:

   405     NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :

   406       Parent(), const_true_map(true) {

   407       Parent::setGraph(_graph);

   408       Parent::setNodeFilterMap(_node_filter_map);

   409       Parent::setEdgeFilterMap(const_true_map);

   410     }

   411   };

   414   /*! \brief A wrapper for hiding edges from a graph.

   416   \warning Graph wrappers are in even more experimental state than the other

   417   parts of the lib. Use them at you own risk.

   419   A wrapper for hiding edges from a graph.

   420   This wrapper specializes SubGraphWrapper in the way that only the edge-set

   421   can be filtered. The usefulness of this wrapper is demonstrated in the

   422   problem of searching a maximum number of edge-disjoint shortest paths

   423   between

   424   two nodes \c s and \c t. Shortest here means being shortest w.r.t.

   425   non-negative edge-lengths. Note that

   426   the comprehension of the presented solution

   427   need's some knowledge from elementary combinatorial optimization.

   429   If a single shortest path is to be

   430   searched between two nodes \c s and \c t, then this can be done easily by

   431   applying the Dijkstra algorithm class. What happens, if a maximum number of

   432   edge-disjoint shortest paths is to be computed. It can be proved that an

   433   edge can be in a shortest path if and only if it is tight with respect to

   434   the potential function computed by Dijkstra. Moreover, any path containing

   435   only such edges is a shortest one. Thus we have to compute a maximum number

   436   of edge-disjoint paths between \c s and \c t in the graph which has edge-set

   437   all the tight edges. The computation will be demonstrated on the following

   438   graph, which is read from a dimacs file.

   440   \dot

   441   digraph lemon_dot_example {

   442   node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   443   n0 [ label="0 (s)" ];

   444   n1 [ label="1" ];

   445   n2 [ label="2" ];

   446   n3 [ label="3" ];

   447   n4 [ label="4" ];

   448   n5 [ label="5" ];

   449   n6 [ label="6 (t)" ];

   450   edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

   451   n5 ->  n6 [ label="9, length:4" ];

   452   n4 ->  n6 [ label="8, length:2" ];

   453   n3 ->  n5 [ label="7, length:1" ];

   454   n2 ->  n5 [ label="6, length:3" ];

   455   n2 ->  n6 [ label="5, length:5" ];

   456   n2 ->  n4 [ label="4, length:2" ];

   457   n1 ->  n4 [ label="3, length:3" ];

   458   n0 ->  n3 [ label="2, length:1" ];

   459   n0 ->  n2 [ label="1, length:2" ];

   460   n0 ->  n1 [ label="0, length:3" ];

   461   }

   462   \enddot

   464   \code

   465   Graph g;

   466   Node s, t;

   467   LengthMap length(g);

   469   readDimacs(std::cin, g, length, s, t);

   471   cout << "edges with lengths (of form id, source--length->target): " << endl;

   472   for(EdgeIt e(g); e!=INVALID; ++e)

   473     cout << g.id(e) << ", " << g.id(g.source(e)) << "--"

   474          << length[e] << "->" << g.id(g.target(e)) << endl;

   476   cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;

   477   \endcode

   478   Next, the potential function is computed with Dijkstra.

   479   \code

   480   typedef Dijkstra<Graph, LengthMap> Dijkstra;

   481   Dijkstra dijkstra(g, length);

   482   dijkstra.run(s);

   483   \endcode

   484   Next, we consrtruct a map which filters the edge-set to the tight edges.

   485   \code

   486   typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>

   487     TightEdgeFilter;

   488   TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);

   490   typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;

   491   SubGW gw(g, tight_edge_filter);

   492   \endcode

   493   Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed

   494   with a max flow algorithm Preflow.

   495   \code

   496   ConstMap<Edge, int> const_1_map(1);

   497   Graph::EdgeMap<int> flow(g, 0);

   499   Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >

   500     preflow(gw, s, t, const_1_map, flow);

   501   preflow.run();

   502   \endcode

   503   Last, the output is:

   504   \code

   505   cout << "maximum number of edge-disjoint shortest path: "

   506        << preflow.flowValue() << endl;

   507   cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "

   508        << endl;

   509   for(EdgeIt e(g); e!=INVALID; ++e)

   510     if (flow[e])

   511       cout << " " << g.id(g.source(e)) << "--"

   512 	   << length[e] << "->" << g.id(g.target(e)) << endl;

   513   \endcode

   514   The program has the following (expected :-)) output:

   515   \code

   516   edges with lengths (of form id, source--length->target):

   517    9, 5--4->6

   518    8, 4--2->6

   519    7, 3--1->5

   520    6, 2--3->5

   521    5, 2--5->6

   522    4, 2--2->4

   523    3, 1--3->4

   524    2, 0--1->3

   525    1, 0--2->2

   526    0, 0--3->1

   527   s: 0 t: 6

   528   maximum number of edge-disjoint shortest path: 2

   529   edges of the maximum number of edge-disjoint shortest s-t paths:

   530    9, 5--4->6

   531    8, 4--2->6

   532    7, 3--1->5

   533    4, 2--2->4

   534    2, 0--1->3

   535    1, 0--2->2

   536   \endcode

   538   \author Marton Makai

   539   */

   540   template<typename Graph, typename EdgeFilterMap>

   541   class EdgeSubGraphWrapper :

   542     public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,

   543 			   EdgeFilterMap> {

   544   public:

   545     typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,

   546 			    EdgeFilterMap> Parent;

   547   protected:

   548     ConstMap<typename Graph::Node, bool> const_true_map;

   549   public:

   550     EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :

   551       Parent(), const_true_map(true) {

   552       Parent::setGraph(_graph);

   553       Parent::setNodeFilterMap(const_true_map);

   554       Parent::setEdgeFilterMap(_edge_filter_map);

   555     }

   556   };

   559   template<typename Graph>

   560   class UndirGraphWrapper : public GraphWrapper<Graph> {

   561   public:

   562     typedef GraphWrapper<Graph> Parent;

   563   protected:

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

   566   public:

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

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

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

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

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

   574     class OutEdgeIt {

   575       friend class UndirGraphWrapper<Graph>;

   576       bool out_or_in; //true iff out

   577       typename Graph::OutEdgeIt out;

   578       typename Graph::InEdgeIt in;

   579     public:

   580       OutEdgeIt() { }

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

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

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

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

   585       }

   586       operator Edge() const {

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

   588       }

   589     };

   591     typedef OutEdgeIt InEdgeIt;

   593     using GraphWrapper<Graph>::first;

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

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

   596     }

   598     using GraphWrapper<Graph>::next;

   600     OutEdgeIt& next(OutEdgeIt& e) const {

   601       if (e.out_or_in) {

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

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

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

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

   606       } else {

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

   608       }

   609       return e;

   610     }

   612     Node aNode(const OutEdgeIt& e) const {

   613       if (e.out_or_in) return this->graph->source(e); else

   614 	return this->graph->target(e); }

   615     Node bNode(const OutEdgeIt& e) const {

   616       if (e.out_or_in) return this->graph->target(e); else

   617 	return this->graph->source(e); }

   619     //    KEEP_MAPS(Parent, UndirGraphWrapper);

   621   };

   623 //   /// \brief An undirected graph template.

   624 //   ///

   625 //   ///\warning Graph wrappers are in even more experimental state than the other

   626 //   ///parts of the lib. Use them at your own risk.

   627 //   ///

   628 //   /// An undirected graph template.

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

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

   631 //   /// \ingroup graphs

   632   template<typename Graph>

   633   class UndirGraph : public UndirGraphWrapper<Graph> {

   634     typedef UndirGraphWrapper<Graph> Parent;

   635   protected:

   636     Graph gr;

   637   public:

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

   639       Parent::setGraph(gr);

   640     }

   642     //    KEEP_MAPS(Parent, UndirGraph);

   643   };

   646   template <typename _Graph,

   647 	    typename ForwardFilterMap, typename BackwardFilterMap>

   648   class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {

   649   public:

   650     typedef _Graph Graph;

   651     typedef GraphWrapperBase<_Graph> Parent;

   652   protected:

   653     ForwardFilterMap* forward_filter;

   654     BackwardFilterMap* backward_filter;

   655     SubBidirGraphWrapperBase() : Parent(),

   656 				 forward_filter(0), backward_filter(0) { }

   658     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

   659       forward_filter=&_forward_filter;

   660     }

   661     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

   662       backward_filter=&_backward_filter;

   663     }

   665   public:

   666 //     SubGraphWrapperBase(Graph& _graph,

   667 // 			NodeFilterMap& _node_filter_map,

   668 // 			EdgeFilterMap& _edge_filter_map) :

   669 //       Parent(&_graph),

   670 //       node_filter_map(&node_filter_map),

   671 //       edge_filter_map(&edge_filter_map) { }

   673     typedef typename Parent::Node Node;

   674     typedef typename _Graph::Edge GraphEdge;

   675     template <typename T> class EdgeMap;

   676     /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from

   677     /// _Graph::Edge. It contains an extra bool flag which is true

   678     /// if and only if the

   679     /// edge is the backward version of the original edge.

   680     class Edge : public _Graph::Edge {

   681       friend class SubBidirGraphWrapperBase<

   682 	Graph, ForwardFilterMap, BackwardFilterMap>;

   683       template<typename T> friend class EdgeMap;

   684     protected:

   685       bool backward; //true, iff backward

   686     public:

   687       Edge() { }

   688       /// \todo =false is needed, or causes problems?

   689       /// If \c _backward is false, then we get an edge corresponding to the

   690       /// original one, otherwise its oppositely directed pair is obtained.

   691       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :

   692 	_Graph::Edge(e), backward(_backward) { }

   693       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }

   694       bool operator==(const Edge& v) const {

   695 	return (this->backward==v.backward &&

   696 		static_cast<typename _Graph::Edge>(*this)==

   697 		static_cast<typename _Graph::Edge>(v));

   698       }

   699       bool operator!=(const Edge& v) const {

   700 	return (this->backward!=v.backward ||

   701 		static_cast<typename _Graph::Edge>(*this)!=

   702 		static_cast<typename _Graph::Edge>(v));

   703       }

   704     };

   706     void first(Node& i) const {

   707       Parent::first(i);

   708     }

   710     void first(Edge& i) const {

   711       Parent::first(i);

   712       i.backward=false;

   713       while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   714 	     !(*forward_filter)[i]) Parent::next(i);

   715       if (*static_cast<GraphEdge*>(&i)==INVALID) {

   716 	Parent::first(i);

   717 	i.backward=true;

   718 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   719 	       !(*backward_filter)[i]) Parent::next(i);

   720       }

   721     }

   723     void firstIn(Edge& i, const Node& n) const {

   724       Parent::firstIn(i, n);

   725       i.backward=false;

   726       while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   727 	     !(*forward_filter)[i]) Parent::nextOut(i);

   728       if (*static_cast<GraphEdge*>(&i)==INVALID) {

   729 	Parent::firstOut(i, n);

   730 	i.backward=true;

   731 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   732 	       !(*backward_filter)[i]) Parent::nextOut(i);

   733       }

   734     }

   736     void firstOut(Edge& i, const Node& n) const {

   737       Parent::firstOut(i, n);

   738       i.backward=false;

   739       while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   740 	     !(*forward_filter)[i]) Parent::nextOut(i);

   741       if (*static_cast<GraphEdge*>(&i)==INVALID) {

   742 	Parent::firstIn(i, n);

   743 	i.backward=true;

   744 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   745 	       !(*backward_filter)[i]) Parent::nextIn(i);

   746       }

   747     }

   749     void next(Node& i) const {

   750       Parent::next(i);

   751     }

   753     void next(Edge& i) const {

   754       if (!(i.backward)) {

   755 	Parent::next(i);

   756 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   757 	       !(*forward_filter)[i]) Parent::next(i);

   758 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

   759 	  Parent::first(i);

   760 	  i.backward=true;

   761 	  while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   762 		 !(*backward_filter)[i]) Parent::next(i);

   763 	}

   764       } else {

   765 	Parent::next(i);

   766 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   767 	       !(*backward_filter)[i]) Parent::next(i);

   768       }

   769     }

   771     void nextIn(Edge& i) const {

   772       if (!(i.backward)) {

   773 	Node n=Parent::target(i);

   774 	Parent::nextIn(i);

   775 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   776 	       !(*forward_filter)[i]) Parent::nextIn(i);

   777 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

   778 	  Parent::firstOut(i, n);

   779 	  i.backward=true;

   780 	  while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   781 		 !(*backward_filter)[i]) Parent::nextOut(i);

   782 	}

   783       } else {

   784 	Parent::nextOut(i);

   785 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   786 	       !(*backward_filter)[i]) Parent::nextOut(i);

   787       }

   788     }

   790     void nextOut(Edge& i) const {

   791       if (!(i.backward)) {

   792 	Node n=Parent::source(i);

   793 	Parent::nextOut(i);

   794 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   795 	       !(*forward_filter)[i]) Parent::nextOut(i);

   796 	if (*static_cast<GraphEdge*>(&i)==INVALID) {

   797 	  Parent::firstIn(i, n);

   798 	  i.backward=true;

   799 	  while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   800 		 !(*backward_filter)[i]) Parent::nextIn(i);

   801 	}

   802       } else {

   803 	Parent::nextIn(i);

   804 	while (*static_cast<GraphEdge*>(&i)!=INVALID &&

   805 	       !(*backward_filter)[i]) Parent::nextIn(i);

   806       }

   807     }

   809     Node source(Edge e) const {

   810       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }

   811     Node target(Edge e) const {

   812       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }

   814     /// Gives back the opposite edge.

   815     Edge opposite(const Edge& e) const {

   816       Edge f=e;

   817       f.backward=!f.backward;

   818       return f;

   819     }

   821     /// \warning This is a linear time operation and works only if

   822     /// \c Graph::EdgeIt is defined.

   823     /// \todo hmm

   824     int edgeNum() const {

   825       int i=0;

   826       Edge e;

   827       for (first(e); e!=INVALID; next(e)) ++i;

   828       return i;

   829     }

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

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

   834     template <typename T>

   835     /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two

   836     /// _Graph::EdgeMap one for the forward edges and

   837     /// one for the backward edges.

   838     class EdgeMap {

   839       template <typename TT> friend class EdgeMap;

   840       typename _Graph::template EdgeMap<T> forward_map, backward_map;

   841     public:

   842       typedef T Value;

   843       typedef Edge Key;

   845       EdgeMap(const SubBidirGraphWrapperBase<_Graph,

   846 	      ForwardFilterMap, BackwardFilterMap>& g) :

   847 	forward_map(*(g.graph)), backward_map(*(g.graph)) { }

   849       EdgeMap(const SubBidirGraphWrapperBase<_Graph,

   850 	      ForwardFilterMap, BackwardFilterMap>& g, T a) :

   851 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }

   853       void set(Edge e, T a) {

   854 	if (!e.backward)

   855 	  forward_map.set(e, a);

   856 	else

   857 	  backward_map.set(e, a);

   858       }

   860 //       typename _Graph::template EdgeMap<T>::ConstReference

   861 //       operator[](Edge e) const {

   862 // 	if (!e.backward)

   863 // 	  return forward_map[e];

   864 // 	else

   865 // 	  return backward_map[e];

   866 //       }

   868 //      typename _Graph::template EdgeMap<T>::Reference

   869       T operator[](Edge e) const {

   870 	if (!e.backward)

   871 	  return forward_map[e];

   872 	else

   873 	  return backward_map[e];

   874       }

   876       void update() {

   877 	forward_map.update();

   878 	backward_map.update();

   879       }

   880     };

   882   };

   885   ///\brief A wrapper for composing a subgraph of a

   886   /// bidirected graph made from a directed one.

   887   ///

   888   /// A wrapper for composing a subgraph of a

   889   /// bidirected graph made from a directed one.

   890   ///

   891   ///\warning Graph wrappers are in even more experimental state than the other

   892   ///parts of the lib. Use them at you own risk.

   893   ///

   894   /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge

   895   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by

   896   /// reversing its orientation. We are given moreover two bool valued

   897   /// maps on the edge-set,

   898   /// \f$forward\_filter\f$, and \f$backward\_filter\f$.

   899   /// SubBidirGraphWrapper implements the graph structure with node-set

   900   /// \f$V\f$ and edge-set

   901   /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.

   902   /// The purpose of writing + instead of union is because parallel

   903   /// edges can arise. (Similarly, antiparallel edges also can arise).

   904   /// In other words, a subgraph of the bidirected graph obtained, which

   905   /// is given by orienting the edges of the original graph in both directions.

   906   /// As the oppositely directed edges are logically different,

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

   908   ///

   909   /// An example for such a construction is \c RevGraphWrapper where the

   910   /// forward_filter is everywhere false and the backward_filter is

   911   /// everywhere true. We note that for sake of efficiency,

   912   /// \c RevGraphWrapper is implemented in a different way.

   913   /// But BidirGraphWrapper is obtained from

   914   /// SubBidirGraphWrapper by considering everywhere true

   915   /// valued maps both for forward_filter and backward_filter.

   916   /// Finally, one of the most important applications of SubBidirGraphWrapper

   917   /// is ResGraphWrapper, which stands for the residual graph in directed

   918   /// flow and circulation problems.

   919   /// As wrappers usually, the SubBidirGraphWrapper implements the

   920   /// above mentioned graph structure without its physical storage,

   921   /// that is the whole stuff is stored in constant memory.

   922   template<typename _Graph,

   923 	   typename ForwardFilterMap, typename BackwardFilterMap>

   924   class SubBidirGraphWrapper :

   925     public IterableGraphExtender<

   926     SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   927   public:

   928     typedef _Graph Graph;

   929     typedef IterableGraphExtender<

   930       SubBidirGraphWrapperBase<

   931       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   932   protected:

   933     SubBidirGraphWrapper() { }

   934   public:

   935     SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,

   936 			 BackwardFilterMap& _backward_filter) {

   937       setGraph(_graph);

   938       setForwardFilterMap(_forward_filter);

   939       setBackwardFilterMap(_backward_filter);

   940     }

   941   };

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

   946   ///

   947   ///\warning Graph wrappers are in even more experimental state than the other

   948   ///parts of the lib. Use them at you own risk.

   949   ///

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

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

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

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

   954   template<typename Graph>

   955   class BidirGraphWrapper :

   956     public SubBidirGraphWrapper<

   957     Graph,

   958     ConstMap<typename Graph::Edge, bool>,

   959     ConstMap<typename Graph::Edge, bool> > {

   960   public:

   961     typedef  SubBidirGraphWrapper<

   962       Graph,

   963       ConstMap<typename Graph::Edge, bool>,

   964       ConstMap<typename Graph::Edge, bool> > Parent;

   965   protected:

   966     ConstMap<typename Graph::Edge, bool> cm;

   968     BidirGraphWrapper() : Parent(), cm(true) {

   969       Parent::setForwardFilterMap(cm);

   970       Parent::setBackwardFilterMap(cm);

   971     }

   972   public:

   973     BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {

   974       Parent::setGraph(_graph);

   975       Parent::setForwardFilterMap(cm);

   976       Parent::setBackwardFilterMap(cm);

   977     }

   979     int edgeNum() const {

   980       return 2*this->graph->edgeNum();

   981     }

   982     //    KEEP_MAPS(Parent, BidirGraphWrapper);

   983   };

   986   template<typename Graph, typename Number,

   987 	   typename CapacityMap, typename FlowMap>

   988   class ResForwardFilter {

   989     //    const Graph* graph;

   990     const CapacityMap* capacity;

   991     const FlowMap* flow;

   992   public:

   993     ResForwardFilter(/*const Graph& _graph, */

   994 		     const CapacityMap& _capacity, const FlowMap& _flow) :

   995       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }

   996     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }

   997     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }

   998     void setFlow(const FlowMap& _flow) { flow=&_flow; }

   999     bool operator[](const typename Graph::Edge& e) const {

  1000       return (Number((*flow)[e]) < Number((*capacity)[e]));

  1001     }

  1002   };

  1004   template<typename Graph, typename Number,

  1005 	   typename CapacityMap, typename FlowMap>

  1006   class ResBackwardFilter {

  1007     const CapacityMap* capacity;

  1008     const FlowMap* flow;

  1009   public:

  1010     ResBackwardFilter(/*const Graph& _graph,*/

  1011 		      const CapacityMap& _capacity, const FlowMap& _flow) :

  1012       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }

  1013     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }

  1014     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }

  1015     void setFlow(const FlowMap& _flow) { flow=&_flow; }

  1016     bool operator[](const typename Graph::Edge& e) const {

  1017       return (Number(0) < Number((*flow)[e]));

  1018     }

  1019   };

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

  1024   ///\warning Graph wrappers are in even more experimental state than the other

  1025   ///parts of the lib. Use them at you own risk.

  1026   ///

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

  1028   template<typename Graph, typename Number,

  1029 	   typename CapacityMap, typename FlowMap>

  1030   class ResGraphWrapper :

  1031     public SubBidirGraphWrapper<

  1032     Graph,

  1033     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,

  1034     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {

  1035   public:

  1036     typedef SubBidirGraphWrapper<

  1037       Graph,

  1038       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,

  1039       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;

  1040   protected:

  1041     const CapacityMap* capacity;

  1042     FlowMap* flow;

  1043     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;

  1044     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;

  1045     ResGraphWrapper() : Parent(),

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

  1047     void setCapacityMap(const CapacityMap& _capacity) {

  1048       capacity=&_capacity;

  1049       forward_filter.setCapacity(_capacity);

  1050       backward_filter.setCapacity(_capacity);

  1051     }

  1052     void setFlowMap(FlowMap& _flow) {

  1053       flow=&_flow;

  1054       forward_filter.setFlow(_flow);

  1055       backward_filter.setFlow(_flow);

  1056     }

  1057   public:

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

  1059 		       FlowMap& _flow) :

  1060       Parent(), capacity(&_capacity), flow(&_flow),

  1061       forward_filter(/*_graph,*/ _capacity, _flow),

  1062       backward_filter(/*_graph,*/ _capacity, _flow) {

  1063       Parent::setGraph(_graph);

  1064       Parent::setForwardFilterMap(forward_filter);

  1065       Parent::setBackwardFilterMap(backward_filter);

  1066     }

  1068     typedef typename Parent::Edge Edge;

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

  1071       if (Parent::forward(e))

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

  1073       else

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

  1075     }

  1077     /// \brief Residual capacity map.

  1078     ///

  1079     /// In generic residual graphs the residual capacity can be obtained

  1080     /// as a map.

  1081     class ResCap {

  1082     protected:

  1083       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;

  1084     public:

  1085       typedef Number Value;

  1086       typedef Edge Key;

  1087       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&

  1088 	     _res_graph) : res_graph(&_res_graph) { }

  1089       Number operator[](const Edge& e) const {

  1090 	if (res_graph->forward(e))

  1091 	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];

  1092 	else

  1093 	  return (*(res_graph->flow))[e];

  1094       }

  1095     };

  1097     //    KEEP_MAPS(Parent, ResGraphWrapper);

  1098   };

  1102   template <typename _Graph, typename FirstOutEdgesMap>

  1103   class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {

  1104   public:

  1105     typedef _Graph Graph;

  1106     typedef GraphWrapperBase<_Graph> Parent;

  1107   protected:

  1108     FirstOutEdgesMap* first_out_edges;

  1109     ErasingFirstGraphWrapperBase() : Parent(),

  1110 				     first_out_edges(0) { }

  1112     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

  1113       first_out_edges=&_first_out_edges;

  1114     }

  1116   public:

  1118     typedef typename Parent::Node Node;

  1119     typedef typename Parent::Edge Edge;

  1121     void firstOut(Edge& i, const Node& n) const {

  1122       i=(*first_out_edges)[n];

  1123     }

  1125     void erase(const Edge& e) const {

  1126       Node n=source(e);

  1127       Edge f=e;

  1128       Parent::nextOut(f);

  1129       first_out_edges->set(n, f);

  1130     }

  1131   };

  1134   /// For blocking flows.

  1136   ///\warning Graph wrappers are in even more experimental state than the other

  1137   ///parts of the lib. Use them at you own risk.

  1138   ///

  1139   /// This graph wrapper is used for on-the-fly

  1140   /// Dinits blocking flow computations.

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

  1142   /// \code

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

  1144   /// \endcode

  1145   /// is called.

  1146   ///

  1147   /// \author Marton Makai

  1148   template <typename _Graph, typename FirstOutEdgesMap>

  1149   class ErasingFirstGraphWrapper :

  1150     public IterableGraphExtender<

  1151     ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {

  1152   public:

  1153     typedef _Graph Graph;

  1154     typedef IterableGraphExtender<

  1155       ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;

  1156     ErasingFirstGraphWrapper(Graph& _graph,

  1157 			     FirstOutEdgesMap& _first_out_edges) {

  1158       setGraph(_graph);

  1159       setFirstOutEdgesMap(_first_out_edges);

  1160     }

  1162   };

  1164   ///@}

  1166 } //namespace lemon

  1168 #endif //LEMON_GRAPH_WRAPPER_H

author	alpar
	Mon, 21 Mar 2005 16:16:52 +0000
changeset 1237	2414b5ab7684
parent 1172	37338ae42a2b
child 1242	e48c4fe47aaf
permissions	-rw-r--r--