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

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

     2 #ifndef HUGO_GRAPH_WRAPPER_H

     3 #define HUGO_GRAPH_WRAPPER_H

     5 #include <invalid.h>

     6 #include <iter_map.h>

     8 namespace hugo {

    10   /// Graph wrappers

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

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

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

    15   /// latter notion needs further explanation.

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

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

    18   /// clearer.

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

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

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

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

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

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

    25   /// Thus, a wrapper class

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

    27   /// The code looks as follows

    28   /// \code

    29   /// ListGraph g;

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

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

    32   /// \endcode

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

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

    35   /// original graph with reverse orientation.

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

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

    38   /// implemented easily.

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

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

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

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

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

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

    45   /// wrappers.

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

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

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

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

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

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

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

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

    54   /// wrapper class

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

    56   /// has constructor

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

    58   /// This means that in a situation,

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

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

    61   /// \code

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

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

    64   ///   return algorithm2(rgw);

    65   /// }

    66   /// \endcode

    67   template<typename Graph>

    68   class GraphWrapper {

    69   protected:

    70     Graph* graph;

    72   public:

    73     typedef Graph BaseGraph;

    74     typedef Graph ParentGraph;

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

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

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

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

    81 //    typedef typename Graph::Node Node;

    82     class Node : public Graph::Node {

    83       friend class GraphWrapper<Graph>;

    84     public:

    85       Node() { }

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

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

    88     };

    89     class NodeIt {

    90       friend class GraphWrapper<Graph>;

    91       typename Graph::NodeIt n;

    92      public:

    93       NodeIt() { }

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

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

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

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

    98     };

    99 //    typedef typename Graph::Edge Edge;

   100     class Edge : public Graph::Edge {

   101       friend class GraphWrapper<Graph>;

   102     public:

   103       Edge() { }

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

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

   106     };

   107     class OutEdgeIt {

   108       friend class GraphWrapper<Graph>;

   109       typename Graph::OutEdgeIt e;

   110     public:

   111       OutEdgeIt() { }

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

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

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

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

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

   117     };

   118     class InEdgeIt {

   119       friend class GraphWrapper<Graph>;

   120       typename Graph::InEdgeIt e;

   121     public:

   122       InEdgeIt() { }

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

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

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

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

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

   128     };

   129     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   130     class EdgeIt {

   131       friend class GraphWrapper<Graph>;

   132       typename Graph::EdgeIt e;

   133     public:

   134       EdgeIt() { }

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

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

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

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

   139     };

   141     NodeIt& first(NodeIt& i) const {

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

   143     }

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

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

   146     }

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

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

   149     }

   150     EdgeIt& first(EdgeIt& i) const {

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

   152     }

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

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

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

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

   159     Node head(const Edge& e) const {

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

   161     Node tail(const Edge& e) const {

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

   164     bool valid(const Node& n) const {

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

   166     bool valid(const Edge& e) const {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   187     public:

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

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

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

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

   192     };

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

   195     public:

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

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

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

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

   200     };

   201   };

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

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

   206   template<typename Graph>

   207   class RevGraphWrapper : public GraphWrapper<Graph> {

   208   public:

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

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

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

   214     //If Graph::OutEdgeIt is not defined

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

   216     //the typdef techinque does not work.

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

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

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

   221     class OutEdgeIt {

   222       friend class GraphWrapper<Graph>;

   223       friend class RevGraphWrapper<Graph>;

   224       typename Graph::OutEdgeIt e;

   225     public:

   226       OutEdgeIt() { }

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

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

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

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

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

   232     };

   233     class InEdgeIt {

   234       friend class GraphWrapper<Graph>;

   235       friend class RevGraphWrapper<Graph>;

   236       typename Graph::InEdgeIt e;

   237     public:

   238       InEdgeIt() { }

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

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

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

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

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

   244     };

   246     using GraphWrapper<Graph>::first;

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

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

   249     }

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

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

   252     }

   254     using GraphWrapper<Graph>::next;

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

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

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

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

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

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

   262   };

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

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

   267   /// edge-set. The quick brown fox iterator jumps over

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

   269   /// in the bool maps.

   270   template<typename Graph, typename NodeFilterMap,

   271 	   typename EdgeFilterMap>

   272   class SubGraphWrapper : public GraphWrapper<Graph> {

   273   protected:

   274     NodeFilterMap* node_filter_map;

   275     EdgeFilterMap* edge_filter_map;

   276   public:

   278     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,

   279 		    EdgeFilterMap& _edge_filter_map) :

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

   281       edge_filter_map(&_edge_filter_map) { }

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

   284     class NodeIt {

   285       friend class GraphWrapper<Graph>;

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

   287       typename Graph::NodeIt n;

   288      public:

   289       NodeIt() { }

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

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

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

   293 	n(*(_G.graph)) {

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

   295 	  _G.graph->next(n);

   296       }

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

   298     };

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

   300     class OutEdgeIt {

   301       friend class GraphWrapper<Graph>;

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

   303       typename Graph::OutEdgeIt e;

   304     public:

   305       OutEdgeIt() { }

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

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

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

   309 		const Node& _n) :

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

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

   312 	  _G.graph->next(e);

   313       }

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

   315     };

   316     class InEdgeIt {

   317       friend class GraphWrapper<Graph>;

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

   319       typename Graph::InEdgeIt e;

   320     public:

   321       InEdgeIt() { }

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

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

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

   325 	       const Node& _n) :

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

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

   328 	  _G.graph->next(e);

   329       }

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

   331     };

   332     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   333     class EdgeIt {

   334       friend class GraphWrapper<Graph>;

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

   336       typename Graph::EdgeIt e;

   337     public:

   338       EdgeIt() { }

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

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

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

   342 	e(*(_G.graph)) {

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

   344 	  _G.graph->next(e);

   345       }

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

   347     };

   349     NodeIt& first(NodeIt& i) const {

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

   351     }

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

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

   354     }

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

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

   357     }

   358     EdgeIt& first(EdgeIt& i) const {

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

   360     }

   362     NodeIt& next(NodeIt& i) const {

   363       graph->next(i.n);

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

   365       return i;

   366     }

   367     OutEdgeIt& next(OutEdgeIt& i) const {

   368       graph->next(i.e);

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

   370       return i;

   371     }

   372     InEdgeIt& next(InEdgeIt& i) const {

   373       graph->next(i.e);

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

   375       return i;

   376     }

   377     EdgeIt& next(EdgeIt& i) const {

   378       graph->next(i.e);

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

   380       return i;

   381     }

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

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

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

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

   388     ///\todo

   389     ///Some doki, please.

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

   391     ///\todo

   392     ///Some doki, please.

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

   395     ///\todo

   396     ///Some doki, please.

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

   398     ///\todo

   399     ///Some doki, please.

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

   402     ///\todo

   403     ///Some doki, please.

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

   405     ///\todo

   406     ///Some doki, please.

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

   408   };

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

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

   413   /// the orientation of a directed one.

   414   template<typename Graph>

   415   class UndirGraphWrapper : public GraphWrapper<Graph> {

   416   public:

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

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

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

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

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

   424     class OutEdgeIt {

   425       friend class UndirGraphWrapper<Graph>;

   426       bool out_or_in; //true iff out

   427       typename Graph::OutEdgeIt out;

   428       typename Graph::InEdgeIt in;

   429     public:

   430       OutEdgeIt() { }

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

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

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

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

   435       }

   436       operator Edge() const {

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

   438       }

   439     };

   441 //FIXME InEdgeIt

   442     typedef OutEdgeIt InEdgeIt;

   444     using GraphWrapper<Graph>::first;

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

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

   447 //     }

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

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

   450     }

   451 //FIXME

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

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

   454 //     }

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

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

   457 //     }

   459     using GraphWrapper<Graph>::next;

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

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

   462 //       return n;

   463 //     }

   464     OutEdgeIt& next(OutEdgeIt& e) const {

   465       if (e.out_or_in) {

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

   467 	graph->next(e.out);

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

   469       } else {

   470 	graph->next(e.in);

   471       }

   472       return e;

   473     }

   474     //FIXME InEdgeIt

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

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

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

   478 //       return e;

   479 //     }

   481     Node aNode(const OutEdgeIt& e) const {

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

   483     Node bNode(const OutEdgeIt& e) const {

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

   485   };

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

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

   490   template<typename Graph, typename Number,

   491 	   typename CapacityMap, typename FlowMap>

   492   class ResGraphWrapper : public GraphWrapper<Graph> {

   493   protected:

   494     const CapacityMap* capacity;

   495     FlowMap* flow;

   496   public:

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

   499 		    FlowMap& _flow) :

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

   502     class Edge;

   503     class OutEdgeIt;

   504     friend class Edge;

   505     friend class OutEdgeIt;

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

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

   509     class Edge : public Graph::Edge {

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

   511     protected:

   512       bool forward; //true, iff forward

   513 //      typename Graph::Edge e;

   514     public:

   515       Edge() { }

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

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

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

   519 //the unique invalid iterator

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

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

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

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

   524       }

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

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

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

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

   529       }

   530     };

   532     class OutEdgeIt {

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

   534     protected:

   535       typename Graph::OutEdgeIt out;

   536       typename Graph::InEdgeIt in;

   537       bool forward;

   538     public:

   539       OutEdgeIt() { }

   540       //FIXME

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

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

   543 //the unique invalid iterator

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

   545 	forward=true;

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

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

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

   549 	  forward=false;

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

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

   552 	}

   553       }

   554       operator Edge() const {

   555 //	Edge e;

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

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

   558 //	return e;

   559 	if (this->forward)

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

   561 	else

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

   563       }

   564     };

   566     class InEdgeIt {

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

   568     protected:

   569       typename Graph::OutEdgeIt out;

   570       typename Graph::InEdgeIt in;

   571       bool forward;

   572     public:

   573       InEdgeIt() { }

   574       //FIXME

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

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

   577 //the unique invalid iterator

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

   579 	forward=true;

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

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

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

   583 	  forward=false;

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

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

   586 	}

   587       }

   588       operator Edge() const {

   589 //	Edge e;

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

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

   592 //	return e;

   593 	if (this->forward)

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

   595 	else

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

   597       }

   598     };

   600     class EdgeIt {

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

   602     protected:

   603       typename Graph::EdgeIt e;

   604       bool forward;

   605     public:

   606       EdgeIt() { }

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

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

   609 	forward=true;

   610 	resG.graph->first(e);

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

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

   613 	  forward=false;

   614 	  resG.graph->first(e);

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

   616 	}

   617       }

   618       operator Edge() const {

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

   620       }

   621     };

   623     using GraphWrapper<Graph>::first;

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

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

   626 //     }

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

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

   629     }

   630 //    FIXME not tested

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

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

   633     }

   634     EdgeIt& first(EdgeIt& i) const {

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

   636     }

   638     using GraphWrapper<Graph>::next;

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

   640     OutEdgeIt& next(OutEdgeIt& e) const {

   641       if (e.forward) {

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

   643 	graph->next(e.out);

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

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

   646 	  e.forward=false;

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

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

   649 	}

   650       } else {

   651 	graph->next(e.in);

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

   653       }

   654       return e;

   655     }

   656 //     FIXME Not tested

   657     InEdgeIt& next(InEdgeIt& e) const {

   658       if (e.forward) {

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

   660 	graph->next(e.in);

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

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

   663 	  e.forward=false;

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

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

   666 	}

   667       } else {

   668 	graph->next(e.out);

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

   670       }

   671       return e;

   672     }

   673     EdgeIt& next(EdgeIt& e) const {

   674       if (e.forward) {

   675 	graph->next(e.e);

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

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

   678 	  e.forward=false;

   679 	  graph->first(e.e);

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

   681 	}

   682       } else {

   683 	graph->next(e.e);

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

   685       }

   686       return e;

   687     }

   689     Node tail(Edge e) const {

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

   691     Node head(Edge e) const {

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

   694     Node aNode(OutEdgeIt e) const {

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

   696     Node bNode(OutEdgeIt e) const {

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

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

   700     //FIXME

   701     void edgeNum() const { }

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

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

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

   708     bool valid(Edge e) const {

   709       return graph->valid(e);

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

   711     }

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

   714       if (e.forward)

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

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

   717       else

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

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

   720     }

   722     Number resCap(const Edge& e) const {

   723       if (e.forward)

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

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

   726       else

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

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

   729     }

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

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

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

   734 //     }

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

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

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

   739 //     }

   741     template <typename T>

   742     class EdgeMap {

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

   744     public:

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

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

   747       void set(Edge e, T a) {

   748 	if (e.forward)

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

   750 	else

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

   752       }

   753       T operator[](Edge e) const {

   754 	if (e.forward)

   755 	  return forward_map[e.out];

   756 	else

   757 	  return backward_map[e.in];

   758       }

   759 //       T get(Edge e) const {

   760 // 	if (e.out_or_in)

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

   762 // 	else

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

   764 //       }

   765     };

   766   };

   768   /// ErasingFirstGraphWrapper for blocking flows.

   770   /// ErasingFirstGraphWrapper for blocking flows.

   771   template<typename Graph, typename FirstOutEdgesMap>

   772   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {

   773   protected:

   774     FirstOutEdgesMap* first_out_edges;

   775   public:

   776     ErasingFirstGraphWrapper(Graph& _graph,

   777 			     FirstOutEdgesMap& _first_out_edges) :

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

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

   781 //     class NodeIt {

   782 //       friend class GraphWrapper<Graph>;

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

   784 //       typename Graph::NodeIt n;

   785 //      public:

   786 //       NodeIt() { }

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

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

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

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

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

   792 //     };

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

   794     class OutEdgeIt {

   795       friend class GraphWrapper<Graph>;

   796       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   797 //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;

   798       typename Graph::OutEdgeIt e;

   799     public:

   800       OutEdgeIt() { }

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

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

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

   804 		const Node& _n) :

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

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

   807     };

   808     class InEdgeIt {

   809       friend class GraphWrapper<Graph>;

   810       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   811 //      typedef typename Graph::InEdgeIt GraphInEdgeIt;

   812       typename Graph::InEdgeIt e;

   813     public:

   814       InEdgeIt() { }

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

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

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

   818 	       const Node& _n) :

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

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

   821     };

   822     //typedef typename Graph::SymEdgeIt SymEdgeIt;

   823     class EdgeIt {

   824       friend class GraphWrapper<Graph>;

   825       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;

   826 //      typedef typename Graph::EdgeIt GraphEdgeIt;

   827       typename Graph::EdgeIt e;

   828     public:

   829       EdgeIt() { }

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

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

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

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

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

   835     };

   837     using GraphWrapper<Graph>::first;

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

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

   840 //     }

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

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

   843     }

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

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

   846     }

   847     EdgeIt& first(EdgeIt& i) const {

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

   849     }

   851     using GraphWrapper<Graph>::next;

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

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

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

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

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

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

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

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

   862     void erase(const OutEdgeIt& e) const {

   863       OutEdgeIt f=e;

   864       this->next(f);

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

   866     }

   867   };

   869   /// A wrapper for composing a bipartite graph.

   870   /// \c _graph have to be a reference to an undirected graph \c Graph

   871   /// and

   872   /// \c _s_false_t_true_map is an \c IterableBoolMap

   873   /// reference containing the elements for the

   874   /// color classes S and T.

   875   /// It results in a directed graph such that the edges are oriented from

   876   /// S to T.

   877   template<typename Graph>

   878   class BipartiteGraphWrapper : public GraphWrapper<Graph> {

   879     typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;

   880     SFalseTTrueMap* s_false_t_true_map;

   882   public:

   883     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)

   884       : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {

   885     }

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

   887     //using GraphWrapper<Graph>::NodeIt;

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

   889     //using GraphWrapper<Graph>::EdgeIt;

   890     class SNodeIt {

   891       Node n;

   892     public:

   893       SNodeIt() { }

   894       SNodeIt(const Invalid& i) : n(i) { }

   895       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {

   896 	_G.s_false_t_true_map->first(n, false);

   897       }

   898       operator Node() const { return n; }

   899     };

   900     class TNodeIt {

   901       Node n;

   902     public:

   903       TNodeIt() { }

   904       TNodeIt(const Invalid& i) : n(i) { }

   905       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {

   906 	_G.s_false_t_true_map->first(n, true);

   907       }

   908       operator Node() const { return n; }

   909     };

   910     class OutEdgeIt {

   911     public:

   912       typename Graph::OutEdgeIt e;

   913     public:

   914       OutEdgeIt() { }

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

   916       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

   917 	if (!(*(_G.s_false_t_true_map))[_n])

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

   919 	else

   920 	  e=INVALID;

   921       }

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

   923     };

   924     class InEdgeIt {

   925     public:

   926       typename Graph::InEdgeIt e;

   927     public:

   928       InEdgeIt() { }

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

   930       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

   931 	if ((*(_G.s_false_t_true_map))[_n])

   932 	  e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));

   933 	else

   934 	  e=INVALID;

   935       }

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

   937     };

   939     using GraphWrapper<Graph>::first;

   940     SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }

   941     TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }

   943     using GraphWrapper<Graph>::next;

   944     SNodeIt& next(SNodeIt& n) const {

   945       this->s_false_t_true_map->next(n); return n;

   946     }

   947     TNodeIt& next(TNodeIt& n) const {

   948       this->s_false_t_true_map->next(n); return n;

   949     }

   951     Node tail(const Edge& e) {

   952       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])

   953 	return Node(this->graph->tail(e));

   954       else

   955 	return Node(this->graph->head(e));

   956     }

   957     Node head(const Edge& e) {

   958       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])

   959 	return Node(this->graph->head(e));

   960       else

   961 	return Node(this->graph->tail(e));

   962     }

   964     Node aNode(const OutEdgeIt& e) const {

   965       return Node(this->graph->aNode(e.e));

   966     }

   967     Node aNode(const InEdgeIt& e) const {

   968       return Node(this->graph->aNode(e.e));

   969     }

   970     Node bNode(const OutEdgeIt& e) const {

   971       return Node(this->graph->bNode(e.e));

   972     }

   973     Node bNode(const InEdgeIt& e) const {

   974       return Node(this->graph->bNode(e.e));

   975     }

   976   };

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

   981 //   template<typename Graph>

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

   983 //   public:

   984 //     class Node;

   985 //     class NodeIt;

   986 //     class Edge;

   987 //     class OutEdgeIt;

   988 //     class InEdgeIt;

   989 //     class EdgeIt;

   991 //     const Node s;

   992 //     const Node t;

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

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

   997 //     class Node : public Graph::Node {

   998 //       friend class GraphWrapper<Graph>;

   999 //       friend class stGraphWrapper<Graph>;

  1000 //     protected:

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

  1002 //     public:

  1003 //       Node() { }

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

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

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

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

  1008 //     };

  1010 //     class NodeIt {

  1011 //       friend class GraphWrapper<Graph>;

  1012 //       friend class stGraphWrapper<Graph>;

  1013 //       typename Graph::NodeIt n;

  1014 //       int spec;

  1015 //      public:

  1016 //       NodeIt() { }

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

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

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

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

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

  1022 //       }

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

  1024 //     };

  1025 // //    typedef typename Graph::Edge Edge;

  1026 //     class Edge : public Graph::Edge {

  1027 //       friend class GraphWrapper<Graph>;

  1028 //       friend class stGraphWrapper<Graph>;

  1029 //       Node tail_spec;

  1030 //       Node head_spec;

  1031 //     public:

  1032 //       Edge() { }

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

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

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

  1036 //       }

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

  1038 //     };

  1039 //     class OutEdgeIt {

  1040 //       friend class GraphWrapper<Graph>;

  1041 //       friend class stGraphWrapper<Graph>;

  1042 //       typename Graph::OutEdgeIt e;

  1043 //       Node tail_spec;

  1044 //       Node head_spec;

  1045 //     public:

  1046 //       OutEdgeIt() { }

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

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

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

  1050 //       }

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

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

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

  1054 // 	switch (_n.spec) {

  1055 // 	case 0 :

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

  1057 // 	  _tail.spec=0;

  1058 // 	  _head.spec=0;

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

  1060 // 	  break;

  1061 // 	case 1:

  1062 // 	  e=INVALID;

  1063 // 	  _tail.spec=1;

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

  1065 // 	  if _head.spec==1

  1066 // 	  break;

  1067 // 	};

  1069 // 	  }

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

  1071 //     };

  1072 //     class InEdgeIt {

  1073 //       friend class GraphWrapper<Graph>;

  1074 //       typename Graph::InEdgeIt e;

  1075 //     public:

  1076 //       InEdgeIt() { }

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

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

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

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

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

  1082 //     };

  1083 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;

  1084 //     class EdgeIt {

  1085 //       friend class GraphWrapper<Graph>;

  1086 //       typename Graph::EdgeIt e;

  1087 //     public:

  1088 //       EdgeIt() { }

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

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

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

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

  1093 //     };

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

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

  1097 //     }

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

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

  1100 //     }

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

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

  1103 //     }

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

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

  1106 //     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1141 //     public:

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

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

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

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

  1146 //     };

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

  1149 //     public:

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

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

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

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

  1154 //     };

  1155 //   };

  1157 } //namespace hugo

  1159 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Wed, 21 Apr 2004 20:48:00 +0000
changeset 368	0beed7a49063
parent 363	7a05119c121a
child 371	b2acba449222
permissions	-rw-r--r--