lemon-0.x: lemon/graph_adaptor.h@955e8e83f6b1

     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     bool forward(const Edge& e) const { return graph->forward(e); }

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

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

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

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

   116     template <typename _Value>

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

   118     public:

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

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

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

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

   123     };

   125     template <typename _Value>

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

   127     public:

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

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

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

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

   132     };

   134   };

   136   template <typename _Graph>

   137   class GraphAdaptor :

   138     public IterableGraphExtender<GraphAdaptorBase<_Graph> > {

   139   public:

   140     typedef _Graph Graph;

   141     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   142   protected:

   143     GraphAdaptor() : Parent() { }

   145   public:

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

   147   };

   149   template <typename _Graph>

   150   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   151   public:

   152     typedef _Graph Graph;

   153     typedef GraphAdaptorBase<_Graph> Parent;

   154   protected:

   155     RevGraphAdaptorBase() : Parent() { }

   156   public:

   157     typedef typename Parent::Node Node;

   158     typedef typename Parent::Edge Edge;

   160     //    using Parent::first;

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

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

   164     //    using Parent::next;

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

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

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

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

   170   };

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

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

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

   177   ///

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

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

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

   181   /// \code

   182   /// ListGraph g;

   183   /// \endcode

   184   /// For each directed edge

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

   186   /// reversing its orientation.

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

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

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

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

   191   /// such an instance can be constructed.

   192   /// \code

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

   194   /// \endcode

   195   ///\author Marton Makai

   196   template<typename _Graph>

   197   class RevGraphAdaptor :

   198     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {

   199   public:

   200     typedef _Graph Graph;

   201     typedef IterableGraphExtender<

   202       RevGraphAdaptorBase<_Graph> > Parent;

   203   protected:

   204     RevGraphAdaptor() { }

   205   public:

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

   207   };

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

   211   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   212   public:

   213     typedef _Graph Graph;

   214     typedef GraphAdaptorBase<_Graph> Parent;

   215   protected:

   216     NodeFilterMap* node_filter_map;

   217     EdgeFilterMap* edge_filter_map;

   218     SubGraphAdaptorBase() : Parent(),

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

   221     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   222       node_filter_map=&_node_filter_map;

   223     }

   224     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {

   225       edge_filter_map=&_edge_filter_map;

   226     }

   228   public:

   229 //     SubGraphAdaptorBase(Graph& _graph,

   230 // 			NodeFilterMap& _node_filter_map,

   231 // 			EdgeFilterMap& _edge_filter_map) :

   232 //       Parent(&_graph),

   233 //       node_filter_map(&node_filter_map),

   234 //       edge_filter_map(&edge_filter_map) { }

   236     typedef typename Parent::Node Node;

   237     typedef typename Parent::Edge Edge;

   239     void first(Node& i) const {

   240       Parent::first(i);

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

   242     }

   243     void first(Edge& i) const {

   244       Parent::first(i);

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

   246     }

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

   248       Parent::firstIn(i, n);

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

   250     }

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

   252       Parent::firstOut(i, n);

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

   254     }

   256     void next(Node& i) const {

   257       Parent::next(i);

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

   259     }

   260     void next(Edge& i) const {

   261       Parent::next(i);

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

   263     }

   264     void nextIn(Edge& i) const {

   265       Parent::nextIn(i);

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

   267     }

   268     void nextOut(Edge& i) const {

   269       Parent::nextOut(i);

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

   271     }

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

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

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

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

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

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

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

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

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

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

   285     /// again

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

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

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

   290     /// again

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

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

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

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

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

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

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

   301     /// \todo assign tags.

   302     int nodeNum() const {

   303       int i=0;

   304       Node n;

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

   306       return i;

   307     }

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

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

   311     /// \todo assign tags.

   312     int edgeNum() const {

   313       int i=0;

   314       Edge e;

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

   316       return i;

   317     }

   320   };

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

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

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

   327   SubGraphAdaptor shows the graph with filtered node-set and

   328   edge-set.

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

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

   331   \f$G\f$.

   332   Let moreover \f$b_V\f$ and

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

   334   SubGraphAdaptor<...>::NodeIt iterates

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

   336   SubGraphAdaptor<...>::EdgeIt iterates

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

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

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

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

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

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

   344   edge-set.

   345   \code

   346   typedef ListGraph Graph;

   347   Graph g;

   348   typedef Graph::Node Node;

   349   typedef Graph::Edge Edge;

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

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

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

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

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

   355   nm.set(u, false);

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

   357   em.set(e, false);

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

   359   SubGW gw(g, nm, em);

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

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

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

   363   \endcode

   364   The output of the above code is the following.

   365   \code

   366   1

   367   :-)

   368   1

   369   \endcode

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

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

   373   For other examples see also the documentation of NodeSubGraphAdaptor and

   374   EdgeSubGraphAdaptor.

   376   \author Marton Makai

   377   */

   378   template<typename _Graph, typename NodeFilterMap,

   379 	   typename EdgeFilterMap>

   380   class SubGraphAdaptor :

   381     public IterableGraphExtender<

   382     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {

   383   public:

   384     typedef _Graph Graph;

   385     typedef IterableGraphExtender<

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

   387   protected:

   388     SubGraphAdaptor() { }

   389   public:

   390     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,

   391 		    EdgeFilterMap& _edge_filter_map) {

   392       setGraph(_graph);

   393       setNodeFilterMap(_node_filter_map);

   394       setEdgeFilterMap(_edge_filter_map);

   395     }

   396   };

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

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

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

   405   An adaptor for hiding nodes from a graph.

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

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

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

   409   \author Marton Makai

   410   */

   411   template<typename Graph, typename NodeFilterMap>

   412   class NodeSubGraphAdaptor :

   413     public SubGraphAdaptor<Graph, NodeFilterMap,

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

   415   public:

   416     typedef SubGraphAdaptor<Graph, NodeFilterMap,

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

   418   protected:

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

   420   public:

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

   422       Parent(), const_true_map(true) {

   423       Parent::setGraph(_graph);

   424       Parent::setNodeFilterMap(_node_filter_map);

   425       Parent::setEdgeFilterMap(const_true_map);

   426     }

   427   };

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

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

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

   435   An adaptor for hiding edges from a graph.

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

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

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

   439   between

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

   441   non-negative edge-lengths. Note that

   442   the comprehension of the presented solution

   443   need's some elementary knowledge from combinatorial optimization.

   445   If a single shortest path is to be

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

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

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

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

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

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

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

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

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

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

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

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

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

   459   the demo program \ref dim_to_dot.cc.

   461   \dot

   462   digraph lemon_dot_example {

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

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

   465   n1 [ label="1" ];

   466   n2 [ label="2" ];

   467   n3 [ label="3" ];

   468   n4 [ label="4" ];

   469   n5 [ label="5" ];

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

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

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

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

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

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

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

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

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

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

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

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

   482   }

   483   \enddot

   485   \code

   486   Graph g;

   487   Node s, t;

   488   LengthMap length(g);

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

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

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

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

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

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

   498   \endcode

   499   Next, the potential function is computed with Dijkstra.

   500   \code

   501   typedef Dijkstra<Graph, LengthMap> Dijkstra;

   502   Dijkstra dijkstra(g, length);

   503   dijkstra.run(s);

   504   \endcode

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

   506   \code

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

   508     TightEdgeFilter;

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

   511   typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;

   512   SubGW gw(g, tight_edge_filter);

   513   \endcode

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

   515   with a max flow algorithm Preflow.

   516   \code

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

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

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

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

   522   preflow.run();

   523   \endcode

   524   Last, the output is:

   525   \code

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

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

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

   529        << endl;

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

   531     if (flow[e])

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

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

   534   \endcode

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

   536   \code

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

   538    9, 5--4->6

   539    8, 4--2->6

   540    7, 3--1->5

   541    6, 2--3->5

   542    5, 2--5->6

   543    4, 2--2->4

   544    3, 1--3->4

   545    2, 0--1->3

   546    1, 0--2->2

   547    0, 0--3->1

   548   s: 0 t: 6

   549   maximum number of edge-disjoint shortest path: 2

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

   551    9, 5--4->6

   552    8, 4--2->6

   553    7, 3--1->5

   554    4, 2--2->4

   555    2, 0--1->3

   556    1, 0--2->2

   557   \endcode

   559   \author Marton Makai

   560   */

   561   template<typename Graph, typename EdgeFilterMap>

   562   class EdgeSubGraphAdaptor :

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

   564 			   EdgeFilterMap> {

   565   public:

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

   567 			    EdgeFilterMap> Parent;

   568   protected:

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

   570   public:

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

   572       Parent(), const_true_map(true) {

   573       Parent::setGraph(_graph);

   574       Parent::setNodeFilterMap(const_true_map);

   575       Parent::setEdgeFilterMap(_edge_filter_map);

   576     }

   577   };

   579   template <typename _Graph>

   580   class UndirGraphAdaptorBase :

   581     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {

   582   public:

   583     typedef _Graph Graph;

   584     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;

   585   protected:

   586     UndirGraphAdaptorBase() : Parent() { }

   587   public:

   588     typedef typename Parent::UndirEdge UndirEdge;

   589     typedef typename Parent::Edge Edge;

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

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

   593     /// The implementation

   594     template <typename T>

   595     class EdgeMap {

   596     protected:

   597       const UndirGraphAdaptorBase<_Graph>* g;

   598       template <typename TT> friend class EdgeMap;

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

   600     public:

   601       typedef T Value;

   602       typedef Edge Key;

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

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

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

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

   610       void set(Edge e, T a) {

   611 	if (g->forward(e))

   612 	  forward_map.set(e, a);

   613 	else

   614 	  backward_map.set(e, a);

   615       }

   617       T operator[](Edge e) const {

   618 	if (g->forward(e))

   619 	  return forward_map[e];

   620 	else

   621 	  return backward_map[e];

   622       }

   623     };

   625     template <typename T>

   626     class UndirEdgeMap {

   627       template <typename TT> friend class UndirEdgeMap;

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

   629     public:

   630       typedef T Value;

   631       typedef UndirEdge Key;

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

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

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

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

   639       void set(UndirEdge e, T a) {

   640 	map.set(e, a);

   641       }

   643       T operator[](UndirEdge e) const {

   644 	return map[e];

   645       }

   646     };

   648   };

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

   651   ///

   652   /// Undocumented, untested!!!

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

   654   ///

   655   /// \author Marton Makai

   656   template<typename _Graph>

   657   class UndirGraphAdaptor :

   658     public IterableUndirGraphExtender<

   659     UndirGraphAdaptorBase<_Graph> > {

   660   public:

   661     typedef _Graph Graph;

   662     typedef IterableUndirGraphExtender<

   663       UndirGraphAdaptorBase<_Graph> > Parent;

   664   protected:

   665     UndirGraphAdaptor() { }

   666   public:

   667     UndirGraphAdaptor(_Graph& _graph) {

   668       setGraph(_graph);

   669     }

   670   };

   673   template <typename _Graph,

   674 	    typename ForwardFilterMap, typename BackwardFilterMap>

   675   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

   676   public:

   677     typedef _Graph Graph;

   678     typedef GraphAdaptorBase<_Graph> Parent;

   679   protected:

   680     ForwardFilterMap* forward_filter;

   681     BackwardFilterMap* backward_filter;

   682     SubBidirGraphAdaptorBase() : Parent(),

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

   685     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {

   686       forward_filter=&_forward_filter;

   687     }

   688     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {

   689       backward_filter=&_backward_filter;

   690     }

   692   public:

   693 //     SubGraphAdaptorBase(Graph& _graph,

   694 // 			NodeFilterMap& _node_filter_map,

   695 // 			EdgeFilterMap& _edge_filter_map) :

   696 //       Parent(&_graph),

   697 //       node_filter_map(&node_filter_map),

   698 //       edge_filter_map(&edge_filter_map) { }

   700     typedef typename Parent::Node Node;

   701     typedef typename _Graph::Edge GraphEdge;

   702     template <typename T> class EdgeMap;

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

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

   705     /// if and only if the

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

   707     class Edge : public _Graph::Edge {

   708       friend class SubBidirGraphAdaptorBase<

   709 	Graph, ForwardFilterMap, BackwardFilterMap>;

   710       template<typename T> friend class EdgeMap;

   711     protected:

   712       bool backward; //true, iff backward

   713     public:

   714       Edge() { }

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

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

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

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

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

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

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

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

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

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

   725       }

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

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

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

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

   730       }

   731     };

   733     void first(Node& i) const {

   734       Parent::first(i);

   735     }

   737     void first(Edge& i) const {

   738       Parent::first(i);

   739       i.backward=false;

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

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

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

   743 	Parent::first(i);

   744 	i.backward=true;

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

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

   747       }

   748     }

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

   751       Parent::firstIn(i, n);

   752       i.backward=false;

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

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

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

   756 	Parent::firstOut(i, n);

   757 	i.backward=true;

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

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

   760       }

   761     }

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

   764       Parent::firstOut(i, n);

   765       i.backward=false;

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

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

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

   769 	Parent::firstIn(i, n);

   770 	i.backward=true;

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

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

   773       }

   774     }

   776     void next(Node& i) const {

   777       Parent::next(i);

   778     }

   780     void next(Edge& i) const {

   781       if (!(i.backward)) {

   782 	Parent::next(i);

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

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

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

   786 	  Parent::first(i);

   787 	  i.backward=true;

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

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

   790 	}

   791       } else {

   792 	Parent::next(i);

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

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

   795       }

   796     }

   798     void nextIn(Edge& i) const {

   799       if (!(i.backward)) {

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

   801 	Parent::nextIn(i);

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

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

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

   805 	  Parent::firstOut(i, n);

   806 	  i.backward=true;

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

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

   809 	}

   810       } else {

   811 	Parent::nextOut(i);

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

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

   814       }

   815     }

   817     void nextOut(Edge& i) const {

   818       if (!(i.backward)) {

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

   820 	Parent::nextOut(i);

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

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

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

   824 	  Parent::firstIn(i, n);

   825 	  i.backward=true;

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

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

   828 	}

   829       } else {

   830 	Parent::nextIn(i);

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

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

   833       }

   834     }

   836     Node source(Edge e) const {

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

   838     Node target(Edge e) const {

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

   841     /// Gives back the opposite edge.

   842     Edge opposite(const Edge& e) const {

   843       Edge f=e;

   844       f.backward=!f.backward;

   845       return f;

   846     }

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

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

   850     /// \todo hmm

   851     int edgeNum() const {

   852       int i=0;

   853       Edge e;

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

   855       return i;

   856     }

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

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

   861     template <typename T>

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

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

   864     /// one for the backward edges.

   865     class EdgeMap {

   866       template <typename TT> friend class EdgeMap;

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

   868     public:

   869       typedef T Value;

   870       typedef Edge Key;

   872       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

   873 	      ForwardFilterMap, BackwardFilterMap>& g) :

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

   876       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,

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

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

   880       void set(Edge e, T a) {

   881 	if (!e.backward)

   882 	  forward_map.set(e, a);

   883 	else

   884 	  backward_map.set(e, a);

   885       }

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

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

   889 // 	if (!e.backward)

   890 // 	  return forward_map[e];

   891 // 	else

   892 // 	  return backward_map[e];

   893 //       }

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

   896       T operator[](Edge e) const {

   897 	if (!e.backward)

   898 	  return forward_map[e];

   899 	else

   900 	  return backward_map[e];

   901       }

   903       void update() {

   904 	forward_map.update();

   905 	backward_map.update();

   906       }

   907     };

   909   };

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

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

   914   ///

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

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

   917   ///

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

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

   920   ///

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

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

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

   924   /// maps on the edge-set,

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

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

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

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

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

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

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

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

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

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

   935   ///

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

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

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

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

   940   /// But BidirGraphAdaptor is obtained from

   941   /// SubBidirGraphAdaptor by considering everywhere true

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

   943   ///

   944   /// The most important application of SubBidirGraphAdaptor

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

   946   /// flow and circulation problems.

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

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

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

   950   template<typename _Graph,

   951 	   typename ForwardFilterMap, typename BackwardFilterMap>

   952   class SubBidirGraphAdaptor :

   953     public IterableGraphExtender<

   954     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {

   955   public:

   956     typedef _Graph Graph;

   957     typedef IterableGraphExtender<

   958       SubBidirGraphAdaptorBase<

   959       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;

   960   protected:

   961     SubBidirGraphAdaptor() { }

   962   public:

   963     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,

   964 			 BackwardFilterMap& _backward_filter) {

   965       setGraph(_graph);

   966       setForwardFilterMap(_forward_filter);

   967       setBackwardFilterMap(_backward_filter);

   968     }

   969   };

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

   974   ///

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

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

   977   ///

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

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

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

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

   982   template<typename Graph>

   983   class BidirGraphAdaptor :

   984     public SubBidirGraphAdaptor<

   985     Graph,

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

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

   988   public:

   989     typedef  SubBidirGraphAdaptor<

   990       Graph,

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

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

   993   protected:

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

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

   997       Parent::setForwardFilterMap(cm);

   998       Parent::setBackwardFilterMap(cm);

   999     }

  1000   public:

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

  1002       Parent::setGraph(_graph);

  1003       Parent::setForwardFilterMap(cm);

  1004       Parent::setBackwardFilterMap(cm);

  1005     }

  1007     int edgeNum() const {

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

  1009     }

  1010     //    KEEP_MAPS(Parent, BidirGraphAdaptor);

  1011   };

  1014   template<typename Graph, typename Number,

  1015 	   typename CapacityMap, typename FlowMap>

  1016   class ResForwardFilter {

  1017     //    const Graph* graph;

  1018     const CapacityMap* capacity;

  1019     const FlowMap* flow;

  1020   public:

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

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

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

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

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

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

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

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

  1029     }

  1030   };

  1032   template<typename Graph, typename Number,

  1033 	   typename CapacityMap, typename FlowMap>

  1034   class ResBackwardFilter {

  1035     const CapacityMap* capacity;

  1036     const FlowMap* flow;

  1037   public:

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

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

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

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

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

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

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

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

  1046     }

  1047   };

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

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

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

  1054   number type. Let moreover

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

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

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

  1058   Suppose that a graph instange \c g of type

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

  1060   \code

  1061   ListGraph g;

  1062   \endcode

  1063   Then RevGraphAdaptor implements the graph structure with node-set

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

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

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

  1067   i.e. the so called residual graph.

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

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

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

  1071   appears twice.

  1072   The following code shows how

  1073   such an instance can be constructed.

  1074   \code

  1075   typedef ListGraph Graph;

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

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

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

  1079   \endcode

  1080   \author Marton Makai

  1081   */

  1082   template<typename Graph, typename Number,

  1083 	   typename CapacityMap, typename FlowMap>

  1084   class ResGraphAdaptor :

  1085     public SubBidirGraphAdaptor<

  1086     Graph,

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

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

  1089   public:

  1090     typedef SubBidirGraphAdaptor<

  1091       Graph,

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

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

  1094   protected:

  1095     const CapacityMap* capacity;

  1096     FlowMap* flow;

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

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

  1099     ResGraphAdaptor() : Parent(),

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

  1101     void setCapacityMap(const CapacityMap& _capacity) {

  1102       capacity=&_capacity;

  1103       forward_filter.setCapacity(_capacity);

  1104       backward_filter.setCapacity(_capacity);

  1105     }

  1106     void setFlowMap(FlowMap& _flow) {

  1107       flow=&_flow;

  1108       forward_filter.setFlow(_flow);

  1109       backward_filter.setFlow(_flow);

  1110     }

  1111   public:

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

  1113 		       FlowMap& _flow) :

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

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

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

  1117       Parent::setGraph(_graph);

  1118       Parent::setForwardFilterMap(forward_filter);

  1119       Parent::setBackwardFilterMap(backward_filter);

  1120     }

  1122     typedef typename Parent::Edge Edge;

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

  1125       if (Parent::forward(e))

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

  1127       else

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

  1129     }

  1131     /// \brief Residual capacity map.

  1132     ///

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

  1134     /// as a map.

  1135     class ResCap {

  1136     protected:

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

  1138     public:

  1139       typedef Number Value;

  1140       typedef Edge Key;

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

  1142 	     _res_graph) : res_graph(&_res_graph) { }

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

  1144 	if (res_graph->forward(e))

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

  1146 	else

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

  1148       }

  1149     };

  1151     //    KEEP_MAPS(Parent, ResGraphAdaptor);

  1152   };

  1156   template <typename _Graph, typename FirstOutEdgesMap>

  1157   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  1158   public:

  1159     typedef _Graph Graph;

  1160     typedef GraphAdaptorBase<_Graph> Parent;

  1161   protected:

  1162     FirstOutEdgesMap* first_out_edges;

  1163     ErasingFirstGraphAdaptorBase() : Parent(),

  1164 				     first_out_edges(0) { }

  1166     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {

  1167       first_out_edges=&_first_out_edges;

  1168     }

  1170   public:

  1172     typedef typename Parent::Node Node;

  1173     typedef typename Parent::Edge Edge;

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

  1176       i=(*first_out_edges)[n];

  1177     }

  1179     void erase(const Edge& e) const {

  1180       Node n=source(e);

  1181       Edge f=e;

  1182       Parent::nextOut(f);

  1183       first_out_edges->set(n, f);

  1184     }

  1185   };

  1188   /// For blocking flows.

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

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

  1192   ///

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

  1194   /// Dinits blocking flow computations.

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

  1196   /// \code

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

  1198   /// \endcode

  1199   /// is called.

  1200   ///

  1201   /// \author Marton Makai

  1202   template <typename _Graph, typename FirstOutEdgesMap>

  1203   class ErasingFirstGraphAdaptor :

  1204     public IterableGraphExtender<

  1205     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {

  1206   public:

  1207     typedef _Graph Graph;

  1208     typedef IterableGraphExtender<

  1209       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;

  1210     ErasingFirstGraphAdaptor(Graph& _graph,

  1211 			     FirstOutEdgesMap& _first_out_edges) {

  1212       setGraph(_graph);

  1213       setFirstOutEdgesMap(_first_out_edges);

  1214     }

  1216   };

  1218   template <typename _Graph>

  1219   class NewEdgeSetAdaptorBase {

  1220   public:

  1222     typedef _Graph Graph;

  1223     typedef typename Graph::Node Node;

  1224     typedef typename Graph::NodeIt NodeIt;

  1226   protected:

  1228     struct NodeT {

  1229       int first_out, first_in;

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

  1231     };

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

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

  1236       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;

  1238       Adaptor& adaptor;

  1240     public:

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

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

  1245       virtual ~NodesImpl() {}

  1247       virtual void build() {

  1248 	Parent::build();

  1249       }

  1251       virtual void clear() {

  1252 	adaptor._clear();

  1253 	Parent::clear();

  1254       }

  1256       virtual void add(const Node& node) {

  1257 	Parent::add(node);

  1258 	adaptor._add(node);

  1259       }

  1261       virtual void erase(const Node& node) {

  1262 	adaptor._erase(node);

  1263 	Parent::erase(node);

  1264       }

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

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

  1268       }

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

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

  1272       }

  1274     };

  1276     NodesImpl* nodes;

  1278     struct EdgeT {

  1279       Node source, target;

  1280       int next_out, next_in;

  1281       int prev_out, prev_in;

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

  1283     };

  1285     std::vector<EdgeT> edges;

  1287     int first_edge;

  1288     int first_free_edge;

  1290     virtual void _clear() = 0;

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

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

  1294     const Graph* graph;

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

  1297       graph = &_graph;

  1298       nodes = &_nodes;

  1299     }

  1301   public:

  1303     class Edge {

  1304       friend class NewEdgeSetAdaptorBase<Graph>;

  1305     protected:

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

  1307       int id;

  1308     public:

  1309       Edge() {}

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

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

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

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

  1314     };

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

  1317     virtual ~NewEdgeSetAdaptorBase() {}

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

  1320       int n;

  1321       if (first_free_edge == -1) {

  1322 	n = edges.size();

  1323 	edges.push_back(EdgeT());

  1324       } else {

  1325 	n = first_free_edge;

  1326 	first_free_edge = edges[first_free_edge].next_in;

  1327       }

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

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

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

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

  1332       edges[n].source = source;

  1333       edges[n].target = target;

  1334       return Edge(n);

  1335     }

  1337     void erase(const Edge& edge) {

  1338       int n = edge.id;

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

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

  1341       } else {

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

  1343       }

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

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

  1346       }

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

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

  1350       } else {

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

  1352       }

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

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

  1355       }

  1357     }

  1359     void first(Node& node) const {

  1360       graph->first(node);

  1361     }

  1363     void next(Node& node) const {

  1364       graph->next(node);

  1365     }

  1367     void first(Edge& edge) const {

  1368       Node node;

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

  1370 	   next(node));

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

  1372     }

  1374     void next(Edge& edge) const {

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

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

  1377       } else {

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

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

  1380 	     next(node));

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

  1382       }

  1383     }

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

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

  1387     }

  1389     void nextOut(Edge& edge) const {

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

  1391     }

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

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

  1395     }

  1397     void nextIn(Edge& edge) const {

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

  1399     }

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

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

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

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

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

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

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

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

  1413   };

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

  1417   /// own edge set.

  1418   ///

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

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

  1421   /// original graph.

  1422   ///

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

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

  1425   /// "StaticGraph" concept.

  1426   ///

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

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

  1429   template <typename _Graph>

  1430   class NewEdgeSetAdaptor :

  1431     public ErasableGraphExtender<

  1432     ClearableGraphExtender<

  1433     ExtendableGraphExtender<

  1434     DefaultMappableGraphExtender<

  1435     IterableGraphExtender<

  1436     AlterableGraphExtender<

  1437     NewEdgeSetAdaptorBase<_Graph> > > > > > > {

  1439   public:

  1441     typedef ErasableGraphExtender<

  1442       ClearableGraphExtender<

  1443       ExtendableGraphExtender<

  1444       DefaultMappableGraphExtender<

  1445       IterableGraphExtender<

  1446       AlterableGraphExtender<

  1447       NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;

  1450     typedef typename Parent::Node Node;

  1451     typedef typename Parent::Edge Edge;

  1453   private:

  1455     virtual void _clear() {

  1456       Parent::edges.clear();

  1457       Parent::first_edge = -1;

  1458       Parent::first_free_edge = -1;

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

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

  1461     }

  1463     virtual void _add(const Node& node) {

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

  1465     }

  1467     virtual void _erase(const Node& node) {

  1468       Edge edge;

  1469       Parent::firstOut(edge, node);

  1470       while (edge != INVALID) {

  1471 	Parent::erase(edge);

  1472 	Parent::firstOut(edge, node);

  1473       }

  1475       Parent::firstIn(edge, node);

  1476       while (edge != INVALID) {

  1477 	Parent::erase(edge);

  1478 	Parent::firstIn(edge, node);

  1479       }

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

  1482     }

  1485     typedef typename Parent::NodesImpl NodesImpl;

  1487     NodesImpl nodes;

  1489   public:

  1491     /// \brief Constructor of the adaptor.

  1492     ///

  1493     /// Constructor of the adaptor.

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

  1495       Parent::initalize(_graph, nodes);

  1496     }

  1498     void clear() {

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

  1501       Parent::edges.clear();

  1502       Parent::first_edge = -1;

  1503       Parent::first_free_edge = -1;

  1504     }

  1506   };

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

  1509   /// own undir edge set.

  1510   ///

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

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

  1513   /// nodes of the original graph.

  1514   ///

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

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

  1517   /// "StaticGraph" concept.

  1518   ///

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

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

  1521   template <typename _Graph>

  1522   class NewUndirEdgeSetAdaptor :

  1523     public ErasableUndirGraphExtender<

  1524     ClearableUndirGraphExtender<

  1525     ExtendableUndirGraphExtender<

  1526     MappableUndirGraphExtender<

  1527     IterableUndirGraphExtender<

  1528     AlterableUndirGraphExtender<

  1529     UndirGraphExtender<

  1530     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {

  1532   public:

  1534     typedef ErasableUndirGraphExtender<

  1535       ClearableUndirGraphExtender<

  1536       ExtendableUndirGraphExtender<

  1537       MappableUndirGraphExtender<

  1538       IterableUndirGraphExtender<

  1539       AlterableUndirGraphExtender<

  1540       UndirGraphExtender<

  1541       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;

  1544     typedef typename Parent::Node Node;

  1545     typedef typename Parent::Edge Edge;

  1546     typedef typename Parent::UndirEdge UndirEdge;

  1548   private:

  1550     virtual void _clear() {

  1551       Parent::edges.clear();

  1552       Parent::first_edge = -1;

  1553       Parent::first_free_edge = -1;

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

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

  1556     }

  1558     virtual void _add(const Node& node) {

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

  1560     }

  1562     virtual void _erase(const Node& node) {

  1563       Edge edge;

  1564       Parent::firstOut(edge, node);

  1565       while (edge != INVALID) {

  1566 	Parent::erase(edge);

  1567 	Parent::firstOut(edge, node);

  1568       }

  1570       Parent::firstIn(edge, node);

  1571       while (edge != INVALID) {

  1572 	Parent::erase(edge);

  1573 	Parent::firstIn(edge, node);

  1574       }

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

  1577     }

  1579     typedef typename Parent::NodesImpl NodesImpl;

  1581     NodesImpl nodes;

  1583   public:

  1586     /// \brief Constructor of the adaptor.

  1587     ///

  1588     /// Constructor of the adaptor.

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

  1590       Parent::initalize(_graph, nodes);

  1591     }

  1593     void clear() {

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

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

  1597       Parent::edges.clear();

  1598       Parent::first_edge = -1;

  1599       Parent::first_free_edge = -1;

  1600     }

  1602   };

  1604   ///@}

  1606 } //namespace lemon

  1608 #endif //LEMON_GRAPH_ADAPTOR_H

author	athos
	Mon, 11 Jul 2005 08:54:31 +0000
changeset 1544	955e8e83f6b1
parent 1536	308150155bb5
child 1576	e5957f8866e6
permissions	-rw-r--r--