lemon-0.x: lemon/graph_adaptor.h@a245eff568a6

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

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

     3  *

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

     5  * (Egervary Research Group on Combinatorial Optimization, 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_ADAPTOR_H

    18 #define LEMON_GRAPH_ADAPTOR_H

    20 ///\ingroup graph_adaptors

    21 ///\file

    22 ///\brief Several graph adaptors.

    23 ///

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

    25 ///

    26 ///\author Marton Makai

    28 #include <lemon/invalid.h>

    29 #include <lemon/maps.h>

    30 #include <lemon/bits/erasable_graph_extender.h>

    31 #include <lemon/bits/clearable_graph_extender.h>

    32 #include <lemon/bits/extendable_graph_extender.h>

    33 #include <lemon/bits/iterable_graph_extender.h>

    34 #include <lemon/bits/alteration_notifier.h>

    35 #include <lemon/bits/default_map.h>

    36 #include <lemon/bits/undir_graph_extender.h>

    37 #include <iostream>

    39 namespace lemon {

    41   // Graph adaptors

    43   /*!

    44     \addtogroup graph_adaptors

    45     @{

    46    */

    48   /*!

    49     Base type for the Graph Adaptors

    51     \warning Graph adaptors are in even more experimental state than the other

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

    54     This is the base type for most of LEMON graph adaptors.

    55     This class implements a trivial graph adaptor i.e. it only wraps the

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

    57     make easier implementing graph adaptors. E.g. if an adaptor is

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

    59     functions or types, then it can be derived from GraphAdaptor, and only the

    60     differences should be implemented.

    62     \author Marton Makai

    63   */

    64   template<typename _Graph>

    65   class GraphAdaptorBase {

    66   public:

    67     typedef _Graph Graph;

    68     /// \todo Is it needed?

    69     typedef Graph BaseGraph;

    70     typedef Graph ParentGraph;

    72   protected:

    73     Graph* graph;

    74     GraphAdaptorBase() : graph(0) { }

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

    77   public:

    78     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }

    80     typedef typename Graph::Node Node;

    81     typedef typename Graph::Edge Edge;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   111     Edge oppositeNode(const Edge& e) const {

   112       return Edge(graph->opposite(e));

   113     }

   115     template <typename _Value>

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

   117     public:

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

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

   120       NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)

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

   122     };

   124     template <typename _Value>

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

   126     public:

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

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

   129       EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)

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

   131     };

   133   };

   135   template <typename _Graph>

   136   class GraphAdaptor :

   137     public IterableGraphExtender<GraphAdaptorBase<_Graph> > {

   138   public:

   139     typedef _Graph Graph;

   140     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   141   protected:

   142     GraphAdaptor() : Parent() { }

   144   public:

   145     GraphAdaptor(Graph& _graph) { setGraph(_graph); }

   146   };

   148   template <typename _Graph>

   149   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   150   public:

   151     typedef _Graph Graph;

   152     typedef GraphAdaptorBase<_Graph> Parent;

   153   protected:

   154     RevGraphAdaptorBase() : Parent() { }

   155   public:

   156     typedef typename Parent::Node Node;

   157     typedef typename Parent::Edge Edge;

   159     //    using Parent::first;

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

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

   163     //    using Parent::next;

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

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

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

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

   169   };

   172   /// A graph adaptor which reverses the orientation of the edges.

   174   ///\warning Graph adaptors are in even more experimental state than the other

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

   176   ///

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

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

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

   180   /// \code

   181   /// ListGraph g;

   182   /// \endcode

   183   /// For each directed edge

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

   185   /// reversing its orientation.

   186   /// Then RevGraphAdaptor implements the graph structure with node-set

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

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

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

   190   /// such an instance can be constructed.

   191   /// \code

   192   /// RevGraphAdaptor<ListGraph> gw(g);

   193   /// \endcode

   194   ///\author Marton Makai

   195   template<typename _Graph>

   196   class RevGraphAdaptor :

   197     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {

   198   public:

   199     typedef _Graph Graph;

   200     typedef IterableGraphExtender<

   201       RevGraphAdaptorBase<_Graph> > Parent;

   202   protected:

   203     RevGraphAdaptor() { }

   204   public:

   205     RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }

   206   };

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

   210   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   211   public:

   212     typedef _Graph Graph;

   213     typedef GraphAdaptorBase<_Graph> Parent;

   214   protected:

   215     NodeFilterMap* node_filter_map;

   216     EdgeFilterMap* edge_filter_map;

   217     SubGraphAdaptorBase() : Parent(),

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

   220     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   221       node_filter_map=&_node_filter_map;

   222     }

   223     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

   224       edge_filter_map=&_edge_filter_map;

   225     }

   227   public:

   228 //     SubGraphAdaptorBase(Graph& _graph,

   229 // 			NodeFilterMap& _node_filter_map,

   230 // 			EdgeFilterMap& _edge_filter_map) :

   231 //       Parent(&_graph),

   232 //       node_filter_map(&node_filter_map),

   233 //       edge_filter_map(&edge_filter_map) { }

   235     typedef typename Parent::Node Node;

   236     typedef typename Parent::Edge Edge;

   238     void first(Node& i) const {

   239       Parent::first(i);

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

   241     }

   242     void first(Edge& i) const {

   243       Parent::first(i);

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

   245     }

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

   247       Parent::firstIn(i, n);

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

   249     }

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

   251       Parent::firstOut(i, n);

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

   253     }

   255     void next(Node& i) const {

   256       Parent::next(i);

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

   258     }

   259     void next(Edge& i) const {

   260       Parent::next(i);

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

   262     }

   263     void nextIn(Edge& i) const {

   264       Parent::nextIn(i);

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

   266     }

   267     void nextOut(Edge& i) const {

   268       Parent::nextOut(i);

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

   270     }

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

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

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

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

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

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

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

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

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

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

   284     /// again

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

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

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

   289     /// again

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

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

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

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

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

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

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

   300     /// \todo assign tags.

   301     int nodeNum() const {

   302       int i=0;

   303       Node n;

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

   305       return i;

   306     }

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

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

   310     /// \todo assign tags.

   311     int edgeNum() const {

   312       int i=0;

   313       Edge e;

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

   315       return i;

   316     }

   319   };

   321   /*! \brief A graph adaptor for hiding nodes and edges from a graph.

   323   \warning Graph adaptors are in even more experimental state than the other

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

   326   SubGraphAdaptor shows the graph with filtered node-set and

   327   edge-set.

   328   Let \f$G=(V, A)\f$ be a directed graph

   329   and suppose that the graph instance \c g of type ListGraph implements

   330   \f$G\f$.

   331   Let moreover \f$b_V\f$ and

   332   \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.

   333   SubGraphAdaptor<...>::NodeIt iterates

   334   on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and

   335   SubGraphAdaptor<...>::EdgeIt iterates

   336   on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,

   337   SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates

   338   only on edges leaving and entering a specific node which have true value.

   340   We have to note that this does not mean that an

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

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

   343   edge-set.

   344   \code

   345   typedef ListGraph Graph;

   346   Graph g;

   347   typedef Graph::Node Node;

   348   typedef Graph::Edge Edge;

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

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

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

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

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

   354   nm.set(u, false);

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

   356   em.set(e, false);

   357   typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;

   358   SubGW gw(g, nm, em);

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

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

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

   362   \endcode

   363   The output of the above code is the following.

   364   \code

   365   1

   366   :-)

   367   1

   368   \endcode

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

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

   372   For other examples see also the documentation of NodeSubGraphAdaptor and

   373   EdgeSubGraphAdaptor.

   375   \author Marton Makai

   376   */

   377   template<typename _Graph, typename NodeFilterMap,

   378 	   typename EdgeFilterMap>

   379   class SubGraphAdaptor :

   380     public IterableGraphExtender<

   381     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {

   382   public:

   383     typedef _Graph Graph;

   384     typedef IterableGraphExtender<

   385       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

   386   protected:

   387     SubGraphAdaptor() { }

   388   public:

   389     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,

   390 		    EdgeFilterMap& _edge_filter_map) {

   391       setGraph(_graph);

   392       setNodeFilterMap(_node_filter_map);

   393       setEdgeFilterMap(_edge_filter_map);

   394     }

   395   };

   399   /*! \brief An adaptor for hiding nodes from a graph.

   401   \warning Graph adaptors are in even more experimental state than the other

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

   404   An adaptor for hiding nodes from a graph.

   405   This adaptor specializes SubGraphAdaptor in the way that only the node-set

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

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

   408   \author Marton Makai

   409   */

   410   template<typename Graph, typename NodeFilterMap>

   411   class NodeSubGraphAdaptor :

   412     public SubGraphAdaptor<Graph, NodeFilterMap,

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

   414   public:

   415     typedef SubGraphAdaptor<Graph, NodeFilterMap,

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

   417   protected:

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

   419   public:

   420     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :

   421       Parent(), const_true_map(true) {

   422       Parent::setGraph(_graph);

   423       Parent::setNodeFilterMap(_node_filter_map);

   424       Parent::setEdgeFilterMap(const_true_map);

   425     }

   426   };

   429   /*! \brief An adaptor for hiding edges from a graph.

   431   \warning Graph adaptors are in even more experimental state than the other

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

   434   An adaptor for hiding edges from a graph.

   435   This adaptor specializes SubGraphAdaptor in the way that only the edge-set

   436   can be filtered. The usefulness of this adaptor is demonstrated in the

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

   438   between

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

   440   non-negative edge-lengths. Note that

   441   the comprehension of the presented solution

   442   need's some elementary knowledge from combinatorial optimization.

   444   If a single shortest path is to be

   445   searched between \c s and \c t, then this can be done easily by

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

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

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

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

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

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

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

   453   graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.

   454   The full source code is available in \ref sub_graph_adaptor_demo.cc.

   455   If you are interested in more demo programs, you can use

   456   \ref dim_to_dot.cc to generate .dot files from dimacs files.

   457   The .dot file of the following figure was generated by

   458   the demo program \ref dim_to_dot.cc.

   460   \dot

   461   digraph lemon_dot_example {

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

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

   464   n1 [ label="1" ];

   465   n2 [ label="2" ];

   466   n3 [ label="3" ];

   467   n4 [ label="4" ];

   468   n5 [ label="5" ];

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

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

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

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

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

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

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

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

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

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

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

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

   481   }

   482   \enddot

   484   \code

   485   Graph g;

   486   Node s, t;

   487   LengthMap length(g);

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

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

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

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

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

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

   497   \endcode

   498   Next, the potential function is computed with Dijkstra.

   499   \code

   500   typedef Dijkstra<Graph, LengthMap> Dijkstra;

   501   Dijkstra dijkstra(g, length);

   502   dijkstra.run(s);

   503   \endcode

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

   505   \code

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

   507     TightEdgeFilter;

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

   510   typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;

   511   SubGW gw(g, tight_edge_filter);

   512   \endcode

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

   514   with a max flow algorithm Preflow.

   515   \code

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

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

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

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

   521   preflow.run();

   522   \endcode

   523   Last, the output is:

   524   \code

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

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

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

   528        << endl;

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

   530     if (flow[e])

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

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

   533   \endcode

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

   535   \code

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

   537    9, 5--4->6

   538    8, 4--2->6

   539    7, 3--1->5

   540    6, 2--3->5

   541    5, 2--5->6

   542    4, 2--2->4

   543    3, 1--3->4

   544    2, 0--1->3

   545    1, 0--2->2

   546    0, 0--3->1

   547   s: 0 t: 6

   548   maximum number of edge-disjoint shortest path: 2

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

   550    9, 5--4->6

   551    8, 4--2->6

   552    7, 3--1->5

   553    4, 2--2->4

   554    2, 0--1->3

   555    1, 0--2->2

   556   \endcode

   558   \author Marton Makai

   559   */

   560   template<typename Graph, typename EdgeFilterMap>

   561   class EdgeSubGraphAdaptor :

   562     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,

   563 			   EdgeFilterMap> {

   564   public:

   565     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,

   566 			    EdgeFilterMap> Parent;

   567   protected:

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

   569   public:

   570     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :

   571       Parent(), const_true_map(true) {

   572       Parent::setGraph(_graph);

   573       Parent::setNodeFilterMap(const_true_map);

   574       Parent::setEdgeFilterMap(_edge_filter_map);

   575     }

   576   };

   578   template <typename _Graph>

   579   class UndirGraphAdaptorBase :

   580     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {

   581   public:

   582     typedef _Graph Graph;

   583     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   584   protected:

   585     UndirGraphAdaptorBase() : Parent() { }

   586   public:

   587     typedef typename Parent::UndirEdge UndirEdge;

   588     typedef typename Parent::Edge Edge;

   590     /// \bug Why cant an edge say that it is forward or not???

   591     /// By this, a pointer to the graph have to be stored

   592     /// The implementation

   593     template <typename T>

   594     class EdgeMap {

   595     protected:

   596       const UndirGraphAdaptorBase<_Graph>* g;

   597       template <typename TT> friend class EdgeMap;

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

   599     public:

   600       typedef T Value;

   601       typedef Edge Key;

   603       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),

   604 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }

   606       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),

   607 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }

   609       void set(Edge e, T a) {

   610 	if (g->direction(e))

   611 	  forward_map.set(e, a);

   612 	else

   613 	  backward_map.set(e, a);

   614       }

   616       T operator[](Edge e) const {

   617 	if (g->direction(e))

   618 	  return forward_map[e];

   619 	else

   620 	  return backward_map[e];

   621       }

   622     };

   624     template <typename T>

   625     class UndirEdgeMap {

   626       template <typename TT> friend class UndirEdgeMap;

   627       typename _Graph::template EdgeMap<T> map;

   628     public:

   629       typedef T Value;

   630       typedef UndirEdge Key;

   632       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :

   633 	map(*(g.graph)) { }

   635       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :

   636 	map(*(g.graph), a) { }

   638       void set(UndirEdge e, T a) {

   639 	map.set(e, a);

   640       }

   642       T operator[](UndirEdge e) const {

   643 	return map[e];

   644       }

   645     };

   647   };

   649   /// \brief An undirected graph is made from a directed graph by an adaptor

   650   ///

   651   /// Undocumented, untested!!!

   652   /// If somebody knows nice demo application, let's polulate it.

   653   ///

   654   /// \author Marton Makai

   655   template<typename _Graph>

   656   class UndirGraphAdaptor :

   657     public IterableUndirGraphExtender<

   658     UndirGraphAdaptorBase<_Graph> > {

   659   public:

   660     typedef _Graph Graph;

   661     typedef IterableUndirGraphExtender<

   662       UndirGraphAdaptorBase<_Graph> > Parent;

   663   protected:

   664     UndirGraphAdaptor() { }

   665   public:

   666     UndirGraphAdaptor(_Graph& _graph) {

   667       setGraph(_graph);

   668     }

   669   };

   672   template <typename _Graph,

   673 	    typename ForwardFilterMap, typename BackwardFilterMap>

   674   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   675   public:

   676     typedef _Graph Graph;

   677     typedef GraphAdaptorBase<_Graph> Parent;

   678   protected:

   679     ForwardFilterMap* forward_filter;

   680     BackwardFilterMap* backward_filter;

   681     SubBidirGraphAdaptorBase() : Parent(),

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

   684     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

   685       forward_filter=&_forward_filter;

   686     }

   687     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

   688       backward_filter=&_backward_filter;

   689     }

   691   public:

   692 //     SubGraphAdaptorBase(Graph& _graph,

   693 // 			NodeFilterMap& _node_filter_map,

   694 // 			EdgeFilterMap& _edge_filter_map) :

   695 //       Parent(&_graph),

   696 //       node_filter_map(&node_filter_map),

   697 //       edge_filter_map(&edge_filter_map) { }

   699     typedef typename Parent::Node Node;

   700     typedef typename _Graph::Edge GraphEdge;

   701     template <typename T> class EdgeMap;

   702     /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from

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

   704     /// if and only if the

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

   706     class Edge : public _Graph::Edge {

   707       friend class SubBidirGraphAdaptorBase<

   708 	Graph, ForwardFilterMap, BackwardFilterMap>;

   709       template<typename T> friend class EdgeMap;

   710     protected:

   711       bool backward; //true, iff backward

   712     public:

   713       Edge() { }

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

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

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

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

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

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

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

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

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

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

   724       }

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

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

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

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

   729       }

   730     };

   732     void first(Node& i) const {

   733       Parent::first(i);

   734     }

   736     void first(Edge& i) const {

   737       Parent::first(i);

   738       i.backward=false;

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

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

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

   742 	Parent::first(i);

   743 	i.backward=true;

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

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

   746       }

   747     }

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

   750       Parent::firstIn(i, n);

   751       i.backward=false;

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

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

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

   755 	Parent::firstOut(i, n);

   756 	i.backward=true;

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

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

   759       }

   760     }

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

   763       Parent::firstOut(i, n);

   764       i.backward=false;

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

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

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

   768 	Parent::firstIn(i, n);

   769 	i.backward=true;

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

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

   772       }

   773     }

   775     void next(Node& i) const {

   776       Parent::next(i);

   777     }

   779     void next(Edge& i) const {

   780       if (!(i.backward)) {

   781 	Parent::next(i);

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

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

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

   785 	  Parent::first(i);

   786 	  i.backward=true;

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

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

   789 	}

   790       } else {

   791 	Parent::next(i);

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

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

   794       }

   795     }

   797     void nextIn(Edge& i) const {

   798       if (!(i.backward)) {

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

   800 	Parent::nextIn(i);

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

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

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

   804 	  Parent::firstOut(i, n);

   805 	  i.backward=true;

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

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

   808 	}

   809       } else {

   810 	Parent::nextOut(i);

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

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

   813       }

   814     }

   816     void nextOut(Edge& i) const {

   817       if (!(i.backward)) {

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

   819 	Parent::nextOut(i);

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

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

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

   823 	  Parent::firstIn(i, n);

   824 	  i.backward=true;

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

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

   827 	}

   828       } else {

   829 	Parent::nextIn(i);

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

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

   832       }

   833     }

   835     Node source(Edge e) const {

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

   837     Node target(Edge e) const {

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

   840     /// Gives back the opposite edge.

   841     Edge opposite(const Edge& e) const {

   842       Edge f=e;

   843       f.backward=!f.backward;

   844       return f;

   845     }

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

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

   849     /// \todo hmm

   850     int edgeNum() const {

   851       int i=0;

   852       Edge e;

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

   854       return i;

   855     }

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

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

   860     template <typename T>

   861     /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two

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

   863     /// one for the backward edges.

   864     class EdgeMap {

   865       template <typename TT> friend class EdgeMap;

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

   867     public:

   868       typedef T Value;

   869       typedef Edge Key;

   871       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

   872 	      ForwardFilterMap, BackwardFilterMap>& g) :

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

   875       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

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

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

   879       void set(Edge e, T a) {

   880 	if (!e.backward)

   881 	  forward_map.set(e, a);

   882 	else

   883 	  backward_map.set(e, a);

   884       }

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

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

   888 // 	if (!e.backward)

   889 // 	  return forward_map[e];

   890 // 	else

   891 // 	  return backward_map[e];

   892 //       }

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

   895       T operator[](Edge e) const {

   896 	if (!e.backward)

   897 	  return forward_map[e];

   898 	else

   899 	  return backward_map[e];

   900       }

   902       void update() {

   903 	forward_map.update();

   904 	backward_map.update();

   905       }

   906     };

   908   };

   911   ///\brief An adaptor for composing a subgraph of a

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

   913   ///

   914   /// An adaptor for composing a subgraph of a

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

   916   ///

   917   ///\warning Graph adaptors are in even more experimental state than the other

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

   919   ///

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

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

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

   923   /// maps on the edge-set,

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

   925   /// SubBidirGraphAdaptor implements the graph structure with node-set

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

   927   /// \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$.

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

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

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

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

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

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

   934   ///

   935   /// An example for such a construction is \c RevGraphAdaptor where the

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

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

   938   /// \c RevGraphAdaptor is implemented in a different way.

   939   /// But BidirGraphAdaptor is obtained from

   940   /// SubBidirGraphAdaptor by considering everywhere true

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

   942   ///

   943   /// The most important application of SubBidirGraphAdaptor

   944   /// is ResGraphAdaptor, which stands for the residual graph in directed

   945   /// flow and circulation problems.

   946   /// As adaptors usually, the SubBidirGraphAdaptor implements the

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

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

   949   template<typename _Graph,

   950 	   typename ForwardFilterMap, typename BackwardFilterMap>

   951   class SubBidirGraphAdaptor :

   952     public IterableGraphExtender<

   953     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   954   public:

   955     typedef _Graph Graph;

   956     typedef IterableGraphExtender<

   957       SubBidirGraphAdaptorBase<

   958       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   959   protected:

   960     SubBidirGraphAdaptor() { }

   961   public:

   962     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,

   963 			 BackwardFilterMap& _backward_filter) {

   964       setGraph(_graph);

   965       setForwardFilterMap(_forward_filter);

   966       setBackwardFilterMap(_backward_filter);

   967     }

   968   };

   972   ///\brief An adaptor for composing bidirected graph from a directed one.

   973   ///

   974   ///\warning Graph adaptors are in even more experimental state than the other

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

   976   ///

   977   /// An adaptor for composing bidirected graph from a directed one.

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

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

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

   981   template<typename Graph>

   982   class BidirGraphAdaptor :

   983     public SubBidirGraphAdaptor<

   984     Graph,

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

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

   987   public:

   988     typedef  SubBidirGraphAdaptor<

   989       Graph,

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

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

   992   protected:

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

   995     BidirGraphAdaptor() : Parent(), cm(true) {

   996       Parent::setForwardFilterMap(cm);

   997       Parent::setBackwardFilterMap(cm);

   998     }

   999   public:

  1000     BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {

  1001       Parent::setGraph(_graph);

  1002       Parent::setForwardFilterMap(cm);

  1003       Parent::setBackwardFilterMap(cm);

  1004     }

  1006     int edgeNum() const {

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

  1008     }

  1009     //    KEEP_MAPS(Parent, BidirGraphAdaptor);

  1010   };

  1013   template<typename Graph, typename Number,

  1014 	   typename CapacityMap, typename FlowMap>

  1015   class ResForwardFilter {

  1016     //    const Graph* graph;

  1017     const CapacityMap* capacity;

  1018     const FlowMap* flow;

  1019   public:

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

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

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

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

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

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

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

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

  1028     }

  1029   };

  1031   template<typename Graph, typename Number,

  1032 	   typename CapacityMap, typename FlowMap>

  1033   class ResBackwardFilter {

  1034     const CapacityMap* capacity;

  1035     const FlowMap* flow;

  1036   public:

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

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

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

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

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

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

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

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

  1045     }

  1046   };

  1049   /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.

  1051   An adaptor for composing the residual graph for directed flow and circulation problems.

  1052   Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a

  1053   number type. Let moreover

  1054   \f$f,c:A\to F\f$, be functions on the edge-set.

  1055   In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow

  1056   and \f$c\f$ for a capacity function.

  1057   Suppose that a graph instange \c g of type

  1058   \c ListGraph implements \f$G\f$.

  1059   \code

  1060   ListGraph g;

  1061   \endcode

  1062   Then RevGraphAdaptor implements the graph structure with node-set

  1063   \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where

  1064   \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and

  1065   \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,

  1066   i.e. the so called residual graph.

  1067   When we take the union \f$A_{forward}\cup A_{backward}\f$,

  1068   multilicities are counted, i.e. if an edge is in both

  1069   \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it

  1070   appears twice.

  1071   The following code shows how

  1072   such an instance can be constructed.

  1073   \code

  1074   typedef ListGraph Graph;

  1075   Graph::EdgeMap<int> f(g);

  1076   Graph::EdgeMap<int> c(g);

  1077   ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);

  1078   \endcode

  1079   \author Marton Makai

  1080   */

  1081   template<typename Graph, typename Number,

  1082 	   typename CapacityMap, typename FlowMap>

  1083   class ResGraphAdaptor :

  1084     public SubBidirGraphAdaptor<

  1085     Graph,

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

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

  1088   public:

  1089     typedef SubBidirGraphAdaptor<

  1090       Graph,

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

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

  1093   protected:

  1094     const CapacityMap* capacity;

  1095     FlowMap* flow;

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

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

  1098     ResGraphAdaptor() : Parent(),

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

  1100     void setCapacityMap(const CapacityMap& _capacity) {

  1101       capacity=&_capacity;

  1102       forward_filter.setCapacity(_capacity);

  1103       backward_filter.setCapacity(_capacity);

  1104     }

  1105     void setFlowMap(FlowMap& _flow) {

  1106       flow=&_flow;

  1107       forward_filter.setFlow(_flow);

  1108       backward_filter.setFlow(_flow);

  1109     }

  1110   public:

  1111     ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,

  1112 		       FlowMap& _flow) :

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

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

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

  1116       Parent::setGraph(_graph);

  1117       Parent::setForwardFilterMap(forward_filter);

  1118       Parent::setBackwardFilterMap(backward_filter);

  1119     }

  1121     typedef typename Parent::Edge Edge;

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

  1124       if (Parent::forward(e))

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

  1126       else

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

  1128     }

  1130     /// \brief Residual capacity map.

  1131     ///

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

  1133     /// as a map.

  1134     class ResCap {

  1135     protected:

  1136       const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;

  1137     public:

  1138       typedef Number Value;

  1139       typedef Edge Key;

  1140       ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&

  1141 	     _res_graph) : res_graph(&_res_graph) { }

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

  1143 	if (res_graph->forward(e))

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

  1145 	else

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

  1147       }

  1148     };

  1150     //    KEEP_MAPS(Parent, ResGraphAdaptor);

  1151   };

  1155   template <typename _Graph, typename FirstOutEdgesMap>

  1156   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  1157   public:

  1158     typedef _Graph Graph;

  1159     typedef GraphAdaptorBase<_Graph> Parent;

  1160   protected:

  1161     FirstOutEdgesMap* first_out_edges;

  1162     ErasingFirstGraphAdaptorBase() : Parent(),

  1163 				     first_out_edges(0) { }

  1165     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

  1166       first_out_edges=&_first_out_edges;

  1167     }

  1169   public:

  1171     typedef typename Parent::Node Node;

  1172     typedef typename Parent::Edge Edge;

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

  1175       i=(*first_out_edges)[n];

  1176     }

  1178     void erase(const Edge& e) const {

  1179       Node n=source(e);

  1180       Edge f=e;

  1181       Parent::nextOut(f);

  1182       first_out_edges->set(n, f);

  1183     }

  1184   };

  1187   /// For blocking flows.

  1189   ///\warning Graph adaptors are in even more experimental state than the other

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

  1191   ///

  1192   /// This graph adaptor is used for on-the-fly

  1193   /// Dinits blocking flow computations.

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

  1195   /// \code

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

  1197   /// \endcode

  1198   /// is called.

  1199   ///

  1200   /// \author Marton Makai

  1201   template <typename _Graph, typename FirstOutEdgesMap>

  1202   class ErasingFirstGraphAdaptor :

  1203     public IterableGraphExtender<

  1204     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {

  1205   public:

  1206     typedef _Graph Graph;

  1207     typedef IterableGraphExtender<

  1208       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;

  1209     ErasingFirstGraphAdaptor(Graph& _graph,

  1210 			     FirstOutEdgesMap& _first_out_edges) {

  1211       setGraph(_graph);

  1212       setFirstOutEdgesMap(_first_out_edges);

  1213     }

  1215   };

  1217   template <typename _Graph>

  1218   class NewEdgeSetAdaptorBase {

  1219   public:

  1221     typedef _Graph Graph;

  1222     typedef typename Graph::Node Node;

  1223     typedef typename Graph::NodeIt NodeIt;

  1225   protected:

  1227     struct NodeT {

  1228       int first_out, first_in;

  1229       NodeT() : first_out(-1), first_in(-1) {}

  1230     };

  1232     class NodesImpl : protected Graph::template NodeMap<NodeT> {

  1234       typedef typename Graph::template NodeMap<NodeT> Parent;

  1235       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;

  1237       Adaptor& adaptor;

  1239     public:

  1241       NodesImpl(Adaptor& _adaptor, const Graph& _graph)

  1242 	: Parent(_graph), adaptor(_adaptor) {}

  1244       virtual ~NodesImpl() {}

  1246       virtual void build() {

  1247 	Parent::build();

  1248       }

  1250       virtual void clear() {

  1251 	adaptor._clear();

  1252 	Parent::clear();

  1253       }

  1255       virtual void add(const Node& node) {

  1256 	Parent::add(node);

  1257 	adaptor._add(node);

  1258       }

  1260       virtual void erase(const Node& node) {

  1261 	adaptor._erase(node);

  1262 	Parent::erase(node);

  1263       }

  1265       NodeT& operator[](const Node& node) {

  1266 	return Parent::operator[](node);

  1267       }

  1269       const NodeT& operator[](const Node& node) const {

  1270 	return Parent::operator[](node);

  1271       }

  1273     };

  1275     NodesImpl* nodes;

  1277     struct EdgeT {

  1278       Node source, target;

  1279       int next_out, next_in;

  1280       int prev_out, prev_in;

  1281       EdgeT() : prev_out(-1), prev_in(-1) {}

  1282     };

  1284     std::vector<EdgeT> edges;

  1286     int first_edge;

  1287     int first_free_edge;

  1289     virtual void _clear() = 0;

  1290     virtual void _add(const Node& node) = 0;

  1291     virtual void _erase(const Node& node) = 0;

  1293     const Graph* graph;

  1295     void initalize(const Graph& _graph, NodesImpl& _nodes) {

  1296       graph = &_graph;

  1297       nodes = &_nodes;

  1298     }

  1300   public:

  1302     class Edge {

  1303       friend class NewEdgeSetAdaptorBase<Graph>;

  1304     protected:

  1305       Edge(int _id) : id(_id) {}

  1306       int id;

  1307     public:

  1308       Edge() {}

  1309       Edge(Invalid) : id(-1) {}

  1310       bool operator==(const Edge& edge) const { return id == edge.id; }

  1311       bool operator!=(const Edge& edge) const { return id != edge.id; }

  1312       bool operator<(const Edge& edge) const { return id < edge.id; }

  1313     };

  1315     NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}

  1316     virtual ~NewEdgeSetAdaptorBase() {}

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

  1319       int n;

  1320       if (first_free_edge == -1) {

  1321 	n = edges.size();

  1322 	edges.push_back(EdgeT());

  1323       } else {

  1324 	n = first_free_edge;

  1325 	first_free_edge = edges[first_free_edge].next_in;

  1326       }

  1327       edges[n].next_in = (*nodes)[target].first_in;

  1328       (*nodes)[target].first_in = n;

  1329       edges[n].next_out = (*nodes)[source].first_out;

  1330       (*nodes)[source].first_out = n;

  1331       edges[n].source = source;

  1332       edges[n].target = target;

  1333       return Edge(n);

  1334     }

  1336     void erase(const Edge& edge) {

  1337       int n = edge.id;

  1338       if (edges[n].prev_in != -1) {

  1339 	edges[edges[n].prev_in].next_in = edges[n].next_in;

  1340       } else {

  1341 	(*nodes)[edges[n].target].first_in = edges[n].next_in;

  1342       }

  1343       if (edges[n].next_in != -1) {

  1344 	edges[edges[n].next_in].prev_in = edges[n].prev_in;

  1345       }

  1347       if (edges[n].prev_out != -1) {

  1348 	edges[edges[n].prev_out].next_out = edges[n].next_out;

  1349       } else {

  1350 	(*nodes)[edges[n].source].first_out = edges[n].next_out;

  1351       }

  1352       if (edges[n].next_out != -1) {

  1353 	edges[edges[n].next_out].prev_out = edges[n].prev_out;

  1354       }

  1356     }

  1358     void first(Node& node) const {

  1359       graph->first(node);

  1360     }

  1362     void next(Node& node) const {

  1363       graph->next(node);

  1364     }

  1366     void first(Edge& edge) const {

  1367       Node node;

  1368       for (first(node); node != INVALID && (*nodes)[node].first_in == -1;

  1369 	   next(node));

  1370       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

  1371     }

  1373     void next(Edge& edge) const {

  1374       if (edges[edge.id].next_in != -1) {

  1375 	edge.id = edges[edge.id].next_in;

  1376       } else {

  1377 	Node node = edges[edge.id].target;

  1378 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1;

  1379 	     next(node));

  1380 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;

  1381       }

  1382     }

  1384     void firstOut(Edge& edge, const Node& node) const {

  1385       edge.id = (*nodes)[node].first_out;

  1386     }

  1388     void nextOut(Edge& edge) const {

  1389       edge.id = edges[edge.id].next_out;

  1390     }

  1392     void firstIn(Edge& edge, const Node& node) const {

  1393       edge.id = (*nodes)[node].first_in;

  1394     }

  1396     void nextIn(Edge& edge) const {

  1397       edge.id = edges[edge.id].next_in;

  1398     }

  1400     int id(const Node& node) const { return graph->id(node); }

  1401     int id(const Edge& edge) const { return edge.id; }

  1403     Node fromId(int id, Node) const { return graph->fromId(id, Node()); }

  1404     Edge fromId(int id, Edge) const { return Edge(id); }

  1406     int maxId(Node) const { return graph->maxId(Node()); };

  1407     int maxId(Edge) const { return edges.size() - 1; }

  1409     Node source(const Edge& edge) const { return edges[edge.id].source;}

  1410     Node target(const Edge& edge) const { return edges[edge.id].target;}

  1412   };

  1415   /// \brief Graph adaptor using a node set of another graph and an

  1416   /// own edge set.

  1417   ///

  1418   /// This structure can be used to establish another graph over a node set

  1419   /// of an existing one. The node iterator will go through the nodes of the

  1420   /// original graph.

  1421   ///

  1422   /// \param _Graph The type of the graph which shares its node set with

  1423   /// this class. Its interface must conform to the \ref skeleton::StaticGraph

  1424   /// "StaticGraph" concept.

  1425   ///

  1426   /// In the edge extension and removing it conforms to the

  1427   /// \ref skeleton::ExtendableGraph "ExtendableGraph" concept.

  1428   template <typename _Graph>

  1429   class NewEdgeSetAdaptor :

  1430     public ErasableGraphExtender<

  1431     ClearableGraphExtender<

  1432     ExtendableGraphExtender<

  1433     DefaultMappableGraphExtender<

  1434     IterableGraphExtender<

  1435     AlterableGraphExtender<

  1436     NewEdgeSetAdaptorBase<_Graph> > > > > > > {

  1438   public:

  1440     typedef ErasableGraphExtender<

  1441       ClearableGraphExtender<

  1442       ExtendableGraphExtender<

  1443       DefaultMappableGraphExtender<

  1444       IterableGraphExtender<

  1445       AlterableGraphExtender<

  1446       NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;

  1449     typedef typename Parent::Node Node;

  1450     typedef typename Parent::Edge Edge;

  1452   private:

  1454     virtual void _clear() {

  1455       Parent::edges.clear();

  1456       Parent::first_edge = -1;

  1457       Parent::first_free_edge = -1;

  1458       Parent::getNotifier(Edge()).clear();

  1459       Parent::getNotifier(Node()).clear();

  1460     }

  1462     virtual void _add(const Node& node) {

  1463       Parent::getNotifier(Node()).add(node);

  1464     }

  1466     virtual void _erase(const Node& node) {

  1467       Edge edge;

  1468       Parent::firstOut(edge, node);

  1469       while (edge != INVALID) {

  1470 	Parent::erase(edge);

  1471 	Parent::firstOut(edge, node);

  1472       }

  1474       Parent::firstIn(edge, node);

  1475       while (edge != INVALID) {

  1476 	Parent::erase(edge);

  1477 	Parent::firstIn(edge, node);

  1478       }

  1480       Parent::getNotifier(Node()).erase(node);

  1481     }

  1484     typedef typename Parent::NodesImpl NodesImpl;

  1486     NodesImpl nodes;

  1488   public:

  1490     /// \brief Constructor of the adaptor.

  1491     ///

  1492     /// Constructor of the adaptor.

  1493     NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {

  1494       Parent::initalize(_graph, nodes);

  1495     }

  1497     void clear() {

  1498       Parent::getNotifier(Edge()).clear();

  1500       Parent::edges.clear();

  1501       Parent::first_edge = -1;

  1502       Parent::first_free_edge = -1;

  1503     }

  1505   };

  1507   /// \brief Graph adaptor using a node set of another graph and an

  1508   /// own undir edge set.

  1509   ///

  1510   /// This structure can be used to establish another undirected graph over

  1511   /// a node set of an existing one. The node iterator will go through the

  1512   /// nodes of the original graph.

  1513   ///

  1514   /// \param _Graph The type of the graph which shares its node set with

  1515   /// this class. Its interface must conform to the \ref skeleton::StaticGraph

  1516   /// "StaticGraph" concept.

  1517   ///

  1518   /// In the edge extension and removing it conforms to the

  1519   /// \ref skeleton::ExtendableGraph "ExtendableGraph" concept.

  1520   template <typename _Graph>

  1521   class NewUndirEdgeSetAdaptor :

  1522     public ErasableUndirGraphExtender<

  1523     ClearableUndirGraphExtender<

  1524     ExtendableUndirGraphExtender<

  1525     MappableUndirGraphExtender<

  1526     IterableUndirGraphExtender<

  1527     AlterableUndirGraphExtender<

  1528     UndirGraphExtender<

  1529     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {

  1531   public:

  1533     typedef ErasableUndirGraphExtender<

  1534       ClearableUndirGraphExtender<

  1535       ExtendableUndirGraphExtender<

  1536       MappableUndirGraphExtender<

  1537       IterableUndirGraphExtender<

  1538       AlterableUndirGraphExtender<

  1539       UndirGraphExtender<

  1540       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;

  1543     typedef typename Parent::Node Node;

  1544     typedef typename Parent::Edge Edge;

  1545     typedef typename Parent::UndirEdge UndirEdge;

  1547   private:

  1549     virtual void _clear() {

  1550       Parent::edges.clear();

  1551       Parent::first_edge = -1;

  1552       Parent::first_free_edge = -1;

  1553       Parent::getNotifier(Edge()).clear();

  1554       Parent::getNotifier(Node()).clear();

  1555     }

  1557     virtual void _add(const Node& node) {

  1558       Parent::getNotifier(Node()).add(node);

  1559     }

  1561     virtual void _erase(const Node& node) {

  1562       Edge edge;

  1563       Parent::firstOut(edge, node);

  1564       while (edge != INVALID) {

  1565 	Parent::erase(edge);

  1566 	Parent::firstOut(edge, node);

  1567       }

  1569       Parent::firstIn(edge, node);

  1570       while (edge != INVALID) {

  1571 	Parent::erase(edge);

  1572 	Parent::firstIn(edge, node);

  1573       }

  1575       Parent::getNotifier(Node()).erase(node);

  1576     }

  1578     typedef typename Parent::NodesImpl NodesImpl;

  1580     NodesImpl nodes;

  1582   public:

  1585     /// \brief Constructor of the adaptor.

  1586     ///

  1587     /// Constructor of the adaptor.

  1588     NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {

  1589       Parent::initalize(_graph, nodes);

  1590     }

  1592     void clear() {

  1593       Parent::getNotifier(Edge()).clear();

  1594       Parent::getNotifier(UndirEdge()).clear();

  1596       Parent::edges.clear();

  1597       Parent::first_edge = -1;

  1598       Parent::first_free_edge = -1;

  1599     }

  1601   };

  1603   ///@}

  1605 } //namespace lemon

  1607 #endif //LEMON_GRAPH_ADAPTOR_H

author	alpar
	Tue, 16 Aug 2005 16:42:04 +0000
changeset 1629	a245eff568a6
parent 1576	e5957f8866e6
child 1631	e15162d8eca1
permissions	-rw-r--r--