COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1631:e15162d8eca1

Last change on this file since 1631:e15162d8eca1 was 1631:e15162d8eca1, checked in by Alpar Juttner, 19 years ago

Fixed most (but not all) of Doxygen warnings

File size: 49.4 KB
RevLine 
[906]1/* -*- C++ -*-
[1435]2 * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
[906]3 *
[1164]4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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 */
16
[1401]17#ifndef LEMON_GRAPH_ADAPTOR_H
18#define LEMON_GRAPH_ADAPTOR_H
[556]19
[1401]20///\ingroup graph_adaptors
[556]21///\file
[1401]22///\brief Several graph adaptors.
[556]23///
[1401]24///This file contains several useful graph adaptor functions.
[556]25///
26///\author Marton Makai
27
[921]28#include <lemon/invalid.h>
29#include <lemon/maps.h>
[1472]30#include <lemon/bits/erasable_graph_extender.h>
31#include <lemon/bits/clearable_graph_extender.h>
32#include <lemon/bits/extendable_graph_extender.h>
[1307]33#include <lemon/bits/iterable_graph_extender.h>
[1472]34#include <lemon/bits/alteration_notifier.h>
35#include <lemon/bits/default_map.h>
[1383]36#include <lemon/bits/undir_graph_extender.h>
[774]37#include <iostream>
[556]38
[921]39namespace lemon {
[556]40
[1401]41  // Graph adaptors
[556]42
[1172]43  /*!
[1401]44    \addtogroup graph_adaptors
[1004]45    @{
[1172]46   */
[556]47
[1172]48  /*!
[1401]49    Base type for the Graph Adaptors
[1242]50   
[1401]51    \warning Graph adaptors are in even more experimental state than the other
[1004]52    parts of the lib. Use them at you own risk.
[1242]53   
[1401]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
[1004]56    functions and types of the graph. The purpose of this class is to
[1401]57    make easier implementing graph adaptors. E.g. if an adaptor is
[1004]58    considered which differs from the wrapped graph only in some of its
[1401]59    functions or types, then it can be derived from GraphAdaptor, and only the
[1004]60    differences should be implemented.
61 
62    \author Marton Makai
63  */
[970]64  template<typename _Graph>
[1401]65  class GraphAdaptorBase {
[970]66  public:
67    typedef _Graph Graph;
68    /// \todo Is it needed?
69    typedef Graph BaseGraph;
70    typedef Graph ParentGraph;
71
[556]72  protected:
73    Graph* graph;
[1401]74    GraphAdaptorBase() : graph(0) { }
[556]75    void setGraph(Graph& _graph) { graph=&_graph; }
76
77  public:
[1401]78    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
[556]79 
[774]80    typedef typename Graph::Node Node;
81    typedef typename Graph::Edge Edge;
[556]82   
[970]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); }
[556]87
[970]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); }
92
[986]93    Node source(const Edge& e) const { return graph->source(e); }
94    Node target(const Edge& e) const { return graph->target(e); }
[556]95
96    int nodeNum() const { return graph->nodeNum(); }
97    int edgeNum() const { return graph->edgeNum(); }
98 
99    Node addNode() const { return Node(graph->addNode()); }
[986]100    Edge addEdge(const Node& source, const Node& target) const {
101      return Edge(graph->addEdge(source, target)); }
[556]102
103    void erase(const Node& i) const { graph->erase(i); }
104    void erase(const Edge& i) const { graph->erase(i); }
105 
106    void clear() const { graph->clear(); }
107   
[739]108    int id(const Node& v) const { return graph->id(v); }
109    int id(const Edge& e) const { return graph->id(e); }
[650]110   
[1627]111    Edge oppositeNode(const Edge& e) const {
112      return Edge(graph->opposite(e));
113    }
[650]114
[970]115    template <typename _Value>
116    class NodeMap : public _Graph::template NodeMap<_Value> {
117    public:
118      typedef typename _Graph::template NodeMap<_Value> Parent;
[1401]119      NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
120      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
[970]121      : Parent(*gw.graph, value) { }
122    };
[556]123
[970]124    template <typename _Value>
125    class EdgeMap : public _Graph::template EdgeMap<_Value> {
126    public:
127      typedef typename _Graph::template EdgeMap<_Value> Parent;
[1401]128      EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
129      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
[970]130      : Parent(*gw.graph, value) { }
131    };
[877]132
[556]133  };
134
[970]135  template <typename _Graph>
[1401]136  class GraphAdaptor :
137    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
[970]138  public:
139    typedef _Graph Graph;
[1401]140    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
[970]141  protected:
[1401]142    GraphAdaptor() : Parent() { }
[569]143
[970]144  public:
[1401]145    GraphAdaptor(Graph& _graph) { setGraph(_graph); }
[970]146  };
[569]147
[997]148  template <typename _Graph>
[1401]149  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[997]150  public:
151    typedef _Graph Graph;
[1401]152    typedef GraphAdaptorBase<_Graph> Parent;
[997]153  protected:
[1401]154    RevGraphAdaptorBase() : Parent() { }
[997]155  public:
156    typedef typename Parent::Node Node;
157    typedef typename Parent::Edge Edge;
158
[1383]159    //    using Parent::first;
[997]160    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
161    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
162
[1383]163    //    using Parent::next;
[997]164    void nextIn(Edge& i) const { Parent::nextOut(i); }
165    void nextOut(Edge& i) const { Parent::nextIn(i); }
166
167    Node source(const Edge& e) const { return Parent::target(e); }
168    Node target(const Edge& e) const { return Parent::source(e); }
169  };
170   
171
[1401]172  /// A graph adaptor which reverses the orientation of the edges.
[556]173
[1401]174  ///\warning Graph adaptors are in even more experimental state than the other
[879]175  ///parts of the lib. Use them at you own risk.
176  ///
[923]177  /// Let \f$G=(V, A)\f$ be a directed graph and
178  /// suppose that a graph instange \c g of type
179  /// \c ListGraph implements \f$G\f$.
180  /// \code
181  /// ListGraph g;
182  /// \endcode
183  /// For each directed edge
184  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
185  /// reversing its orientation.
[1401]186  /// Then RevGraphAdaptor implements the graph structure with node-set
[923]187  /// \f$V\f$ and edge-set
188  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
189  /// reversing the orientation of its edges. The following code shows how
190  /// such an instance can be constructed.
191  /// \code
[1401]192  /// RevGraphAdaptor<ListGraph> gw(g);
[923]193  /// \endcode
[556]194  ///\author Marton Makai
[997]195  template<typename _Graph>
[1401]196  class RevGraphAdaptor :
197    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
[650]198  public:
[997]199    typedef _Graph Graph;
200    typedef IterableGraphExtender<
[1401]201      RevGraphAdaptorBase<_Graph> > Parent;
[556]202  protected:
[1401]203    RevGraphAdaptor() { }
[556]204  public:
[1401]205    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
[997]206  };
[556]207
[992]208 
209  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
[1401]210  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[992]211  public:
212    typedef _Graph Graph;
[1401]213    typedef GraphAdaptorBase<_Graph> Parent;
[992]214  protected:
215    NodeFilterMap* node_filter_map;
216    EdgeFilterMap* edge_filter_map;
[1401]217    SubGraphAdaptorBase() : Parent(),
[992]218                            node_filter_map(0), edge_filter_map(0) { }
[775]219
[992]220    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
221      node_filter_map=&_node_filter_map;
222    }
223    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
224      edge_filter_map=&_edge_filter_map;
225    }
226
227  public:
[1401]228//     SubGraphAdaptorBase(Graph& _graph,
[992]229//                      NodeFilterMap& _node_filter_map,
230//                      EdgeFilterMap& _edge_filter_map) :
231//       Parent(&_graph),
232//       node_filter_map(&node_filter_map),
233//       edge_filter_map(&edge_filter_map) { }
234
235    typedef typename Parent::Node Node;
236    typedef typename Parent::Edge Edge;
237
238    void first(Node& i) const {
239      Parent::first(i);
240      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
241    }
242    void first(Edge& i) const {
243      Parent::first(i);
244      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
245    }
246    void firstIn(Edge& i, const Node& n) const {
247      Parent::firstIn(i, n);
248      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
249    }
250    void firstOut(Edge& i, const Node& n) const {
251      Parent::firstOut(i, n);
252      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
253    }
254
255    void next(Node& i) const {
256      Parent::next(i);
257      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
258    }
259    void next(Edge& i) const {
260      Parent::next(i);
261      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
262    }
263    void nextIn(Edge& i) const {
264      Parent::nextIn(i);
265      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
266    }
267    void nextOut(Edge& i) const {
268      Parent::nextOut(i);
269      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
270    }
271
272    /// This function hides \c n in the graph, i.e. the iteration
273    /// jumps over it. This is done by simply setting the value of \c n 
274    /// to be false in the corresponding node-map.
275    void hide(const Node& n) const { node_filter_map->set(n, false); }
276
277    /// This function hides \c e in the graph, i.e. the iteration
278    /// jumps over it. This is done by simply setting the value of \c e 
279    /// to be false in the corresponding edge-map.
280    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
281
282    /// The value of \c n is set to be true in the node-map which stores
283    /// hide information. If \c n was hidden previuosly, then it is shown
284    /// again
285     void unHide(const Node& n) const { node_filter_map->set(n, true); }
286
287    /// The value of \c e is set to be true in the edge-map which stores
288    /// hide information. If \c e was hidden previuosly, then it is shown
289    /// again
290    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
291
292    /// Returns true if \c n is hidden.
293    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
294
295    /// Returns true if \c n is hidden.
296    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
297
298    /// \warning This is a linear time operation and works only if s
299    /// \c Graph::NodeIt is defined.
300    /// \todo assign tags.
301    int nodeNum() const {
302      int i=0;
303      Node n;
304      for (first(n); n!=INVALID; next(n)) ++i;
305      return i;
306    }
307
308    /// \warning This is a linear time operation and works only if
309    /// \c Graph::EdgeIt is defined.
310    /// \todo assign tags.
311    int edgeNum() const {
312      int i=0;
313      Edge e;
314      for (first(e); e!=INVALID; next(e)) ++i;
315      return i;
316    }
317
318
319  };
[775]320
[1401]321  /*! \brief A graph adaptor for hiding nodes and edges from a graph.
[1242]322   
[1401]323  \warning Graph adaptors are in even more experimental state than the other
[930]324  parts of the lib. Use them at you own risk.
325 
[1401]326  SubGraphAdaptor shows the graph with filtered node-set and
[930]327  edge-set.
[1242]328  Let \f$G=(V, A)\f$ be a directed graph
329  and suppose that the graph instance \c g of type ListGraph implements
330  \f$G\f$.
331  Let moreover \f$b_V\f$ and
332  \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
[1401]333  SubGraphAdaptor<...>::NodeIt iterates
[1242]334  on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
[1401]335  SubGraphAdaptor<...>::EdgeIt iterates
[1242]336  on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
[1401]337  SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
[1242]338  only on edges leaving and entering a specific node which have true value.
339
340  We have to note that this does not mean that an
[930]341  induced subgraph is obtained, the node-iterator cares only the filter
342  on the node-set, and the edge-iterators care only the filter on the
[1242]343  edge-set.
[930]344  \code
[1242]345  typedef ListGraph Graph;
[930]346  Graph g;
347  typedef Graph::Node Node;
348  typedef Graph::Edge Edge;
349  Node u=g.addNode(); //node of id 0
350  Node v=g.addNode(); //node of id 1
351  Node e=g.addEdge(u, v); //edge of id 0
352  Node f=g.addEdge(v, u); //edge of id 1
353  Graph::NodeMap<bool> nm(g, true);
354  nm.set(u, false);
355  Graph::EdgeMap<bool> em(g, true);
356  em.set(e, false);
[1401]357  typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
[930]358  SubGW gw(g, nm, em);
359  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
360  std::cout << ":-)" << std::endl;
361  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
362  \endcode
363  The output of the above code is the following.
364  \code
365  1
366  :-)
367  1
368  \endcode
369  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
370  \c Graph::Node that is why \c g.id(n) can be applied.
371
[1401]372  For other examples see also the documentation of NodeSubGraphAdaptor and
373  EdgeSubGraphAdaptor.
[930]374
375  \author Marton Makai
376  */
[992]377  template<typename _Graph, typename NodeFilterMap,
[556]378           typename EdgeFilterMap>
[1401]379  class SubGraphAdaptor :
[992]380    public IterableGraphExtender<
[1401]381    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
[650]382  public:
[992]383    typedef _Graph Graph;
384    typedef IterableGraphExtender<
[1401]385      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
[556]386  protected:
[1401]387    SubGraphAdaptor() { }
[992]388  public:
[1401]389    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
[992]390                    EdgeFilterMap& _edge_filter_map) {
391      setGraph(_graph);
392      setNodeFilterMap(_node_filter_map);
393      setEdgeFilterMap(_edge_filter_map);
394    }
395  };
[556]396
397
[569]398
[1401]399  /*! \brief An adaptor for hiding nodes from a graph.
[933]400
[1401]401  \warning Graph adaptors are in even more experimental state than the other
[933]402  parts of the lib. Use them at you own risk.
403 
[1401]404  An adaptor for hiding nodes from a graph.
405  This adaptor specializes SubGraphAdaptor in the way that only the node-set
[933]406  can be filtered. Note that this does not mean of considering induced
407  subgraph, the edge-iterators consider the original edge-set.
408  \author Marton Makai
409  */
410  template<typename Graph, typename NodeFilterMap>
[1401]411  class NodeSubGraphAdaptor :
412    public SubGraphAdaptor<Graph, NodeFilterMap,
[933]413                           ConstMap<typename Graph::Edge,bool> > {
414  public:
[1401]415    typedef SubGraphAdaptor<Graph, NodeFilterMap,
[933]416                            ConstMap<typename Graph::Edge,bool> > Parent;
417  protected:
418    ConstMap<typename Graph::Edge, bool> const_true_map;
419  public:
[1401]420    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
[933]421      Parent(), const_true_map(true) {
422      Parent::setGraph(_graph);
423      Parent::setNodeFilterMap(_node_filter_map);
424      Parent::setEdgeFilterMap(const_true_map);
425    }
426  };
427
428
[1401]429  /*! \brief An adaptor for hiding edges from a graph.
[932]430
[1401]431  \warning Graph adaptors are in even more experimental state than the other
[932]432  parts of the lib. Use them at you own risk.
433 
[1401]434  An adaptor for hiding edges from a graph.
435  This adaptor specializes SubGraphAdaptor in the way that only the edge-set
436  can be filtered. The usefulness of this adaptor is demonstrated in the
[933]437  problem of searching a maximum number of edge-disjoint shortest paths
438  between
439  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
440  non-negative edge-lengths. Note that
441  the comprehension of the presented solution
[1252]442  need's some elementary knowledge from combinatorial optimization.
[933]443
444  If a single shortest path is to be
[1252]445  searched between \c s and \c t, then this can be done easily by
446  applying the Dijkstra algorithm. What happens, if a maximum number of
[933]447  edge-disjoint shortest paths is to be computed. It can be proved that an
448  edge can be in a shortest path if and only if it is tight with respect to
449  the potential function computed by Dijkstra. Moreover, any path containing
450  only such edges is a shortest one. Thus we have to compute a maximum number
451  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
452  all the tight edges. The computation will be demonstrated on the following
[1536]453  graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
[1425]454  The full source code is available in \ref sub_graph_adaptor_demo.cc.
455  If you are interested in more demo programs, you can use
456  \ref dim_to_dot.cc to generate .dot files from dimacs files.
[1576]457  The .dot file of the following figure was generated by 
[1425]458  the demo program \ref dim_to_dot.cc.
459
[933]460  \dot
461  digraph lemon_dot_example {
462  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
463  n0 [ label="0 (s)" ];
464  n1 [ label="1" ];
465  n2 [ label="2" ];
466  n3 [ label="3" ];
467  n4 [ label="4" ];
468  n5 [ label="5" ];
469  n6 [ label="6 (t)" ];
470  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
471  n5 ->  n6 [ label="9, length:4" ];
472  n4 ->  n6 [ label="8, length:2" ];
473  n3 ->  n5 [ label="7, length:1" ];
474  n2 ->  n5 [ label="6, length:3" ];
475  n2 ->  n6 [ label="5, length:5" ];
476  n2 ->  n4 [ label="4, length:2" ];
477  n1 ->  n4 [ label="3, length:3" ];
478  n0 ->  n3 [ label="2, length:1" ];
479  n0 ->  n2 [ label="1, length:2" ];
480  n0 ->  n1 [ label="0, length:3" ];
481  }
482  \enddot
483
484  \code
485  Graph g;
486  Node s, t;
487  LengthMap length(g);
488
489  readDimacs(std::cin, g, length, s, t);
490
[986]491  cout << "edges with lengths (of form id, source--length->target): " << endl;
[933]492  for(EdgeIt e(g); e!=INVALID; ++e)
[986]493    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
494         << length[e] << "->" << g.id(g.target(e)) << endl;
[933]495
496  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
497  \endcode
498  Next, the potential function is computed with Dijkstra.
499  \code
500  typedef Dijkstra<Graph, LengthMap> Dijkstra;
501  Dijkstra dijkstra(g, length);
502  dijkstra.run(s);
503  \endcode
504  Next, we consrtruct a map which filters the edge-set to the tight edges.
505  \code
506  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
507    TightEdgeFilter;
508  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
509 
[1401]510  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
[933]511  SubGW gw(g, tight_edge_filter);
512  \endcode
513  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
514  with a max flow algorithm Preflow.
515  \code
516  ConstMap<Edge, int> const_1_map(1);
517  Graph::EdgeMap<int> flow(g, 0);
518
519  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
520    preflow(gw, s, t, const_1_map, flow);
521  preflow.run();
522  \endcode
523  Last, the output is:
524  \code 
525  cout << "maximum number of edge-disjoint shortest path: "
526       << preflow.flowValue() << endl;
527  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
528       << endl;
529  for(EdgeIt e(g); e!=INVALID; ++e)
530    if (flow[e])
[986]531      cout << " " << g.id(g.source(e)) << "--"
532           << length[e] << "->" << g.id(g.target(e)) << endl;
[933]533  \endcode
534  The program has the following (expected :-)) output:
535  \code
[986]536  edges with lengths (of form id, source--length->target):
[933]537   9, 5--4->6
538   8, 4--2->6
539   7, 3--1->5
540   6, 2--3->5
541   5, 2--5->6
542   4, 2--2->4
543   3, 1--3->4
544   2, 0--1->3
545   1, 0--2->2
546   0, 0--3->1
547  s: 0 t: 6
548  maximum number of edge-disjoint shortest path: 2
549  edges of the maximum number of edge-disjoint shortest s-t paths:
550   9, 5--4->6
551   8, 4--2->6
552   7, 3--1->5
553   4, 2--2->4
554   2, 0--1->3
555   1, 0--2->2
556  \endcode
557
[932]558  \author Marton Makai
559  */
560  template<typename Graph, typename EdgeFilterMap>
[1401]561  class EdgeSubGraphAdaptor :
562    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[932]563                           EdgeFilterMap> {
564  public:
[1401]565    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[932]566                            EdgeFilterMap> Parent;
567  protected:
568    ConstMap<typename Graph::Node, bool> const_true_map;
569  public:
[1401]570    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
[932]571      Parent(), const_true_map(true) {
572      Parent::setGraph(_graph);
573      Parent::setNodeFilterMap(const_true_map);
574      Parent::setEdgeFilterMap(_edge_filter_map);
575    }
576  };
577
[1383]578  template <typename _Graph>
[1401]579  class UndirGraphAdaptorBase :
580    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
[1383]581  public:
582    typedef _Graph Graph;
[1401]583    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
[1383]584  protected:
[1401]585    UndirGraphAdaptorBase() : Parent() { }
[1383]586  public:
587    typedef typename Parent::UndirEdge UndirEdge;
588    typedef typename Parent::Edge Edge;
589   
590    /// \bug Why cant an edge say that it is forward or not???
591    /// By this, a pointer to the graph have to be stored
592    /// The implementation
593    template <typename T>
594    class EdgeMap {
595    protected:
[1401]596      const UndirGraphAdaptorBase<_Graph>* g;
[1383]597      template <typename TT> friend class EdgeMap;
598      typename _Graph::template EdgeMap<T> forward_map, backward_map;
599    public:
600      typedef T Value;
601      typedef Edge Key;
602     
[1401]603      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
[1383]604        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
[569]605
[1401]606      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
[1383]607        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
608     
609      void set(Edge e, T a) {
[1627]610        if (g->direction(e))
[1383]611          forward_map.set(e, a);
612        else
613          backward_map.set(e, a);
614      }
[556]615
[1383]616      T operator[](Edge e) const {
[1627]617        if (g->direction(e))
[1383]618          return forward_map[e];
619        else
620          return backward_map[e];
[556]621      }
622    };
[1383]623       
624    template <typename T>
625    class UndirEdgeMap {
626      template <typename TT> friend class UndirEdgeMap;
627      typename _Graph::template EdgeMap<T> map;
628    public:
629      typedef T Value;
630      typedef UndirEdge Key;
631     
[1401]632      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
[1383]633        map(*(g.graph)) { }
[556]634
[1401]635      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
[1383]636        map(*(g.graph), a) { }
637     
638      void set(UndirEdge e, T a) {
639        map.set(e, a);
640      }
[556]641
[1383]642      T operator[](UndirEdge e) const {
643        return map[e];
644      }
645    };
646     
647  };
648
[1401]649  /// \brief An undirected graph is made from a directed graph by an adaptor
[1383]650  ///
651  /// Undocumented, untested!!!
652  /// If somebody knows nice demo application, let's polulate it.
653  ///
654  /// \author Marton Makai
655  template<typename _Graph>
[1401]656  class UndirGraphAdaptor :
[1383]657    public IterableUndirGraphExtender<
[1401]658    UndirGraphAdaptorBase<_Graph> > {
[1383]659  public:
660    typedef _Graph Graph;
661    typedef IterableUndirGraphExtender<
[1401]662      UndirGraphAdaptorBase<_Graph> > Parent;
[1383]663  protected:
[1401]664    UndirGraphAdaptor() { }
[1383]665  public:
[1401]666    UndirGraphAdaptor(_Graph& _graph) {
[1383]667      setGraph(_graph);
[556]668    }
669  };
670
[992]671 
672  template <typename _Graph,
673            typename ForwardFilterMap, typename BackwardFilterMap>
[1401]674  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[992]675  public:
676    typedef _Graph Graph;
[1401]677    typedef GraphAdaptorBase<_Graph> Parent;
[992]678  protected:
679    ForwardFilterMap* forward_filter;
680    BackwardFilterMap* backward_filter;
[1401]681    SubBidirGraphAdaptorBase() : Parent(),
[992]682                                 forward_filter(0), backward_filter(0) { }
683
684    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
685      forward_filter=&_forward_filter;
686    }
687    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
688      backward_filter=&_backward_filter;
689    }
690
691  public:
[1401]692//     SubGraphAdaptorBase(Graph& _graph,
[992]693//                      NodeFilterMap& _node_filter_map,
694//                      EdgeFilterMap& _edge_filter_map) :
695//       Parent(&_graph),
696//       node_filter_map(&node_filter_map),
697//       edge_filter_map(&edge_filter_map) { }
698
699    typedef typename Parent::Node Node;
700    typedef typename _Graph::Edge GraphEdge;
701    template <typename T> class EdgeMap;
[1401]702    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
[992]703    /// _Graph::Edge. It contains an extra bool flag which is true
704    /// if and only if the
705    /// edge is the backward version of the original edge.
706    class Edge : public _Graph::Edge {
[1401]707      friend class SubBidirGraphAdaptorBase<
[992]708        Graph, ForwardFilterMap, BackwardFilterMap>;
709      template<typename T> friend class EdgeMap;
710    protected:
711      bool backward; //true, iff backward
712    public:
713      Edge() { }
714      /// \todo =false is needed, or causes problems?
715      /// If \c _backward is false, then we get an edge corresponding to the
716      /// original one, otherwise its oppositely directed pair is obtained.
717      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
718        _Graph::Edge(e), backward(_backward) { }
719      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
720      bool operator==(const Edge& v) const {
721        return (this->backward==v.backward &&
722                static_cast<typename _Graph::Edge>(*this)==
723                static_cast<typename _Graph::Edge>(v));
724      }
725      bool operator!=(const Edge& v) const {
726        return (this->backward!=v.backward ||
727                static_cast<typename _Graph::Edge>(*this)!=
728                static_cast<typename _Graph::Edge>(v));
729      }
730    };
731
732    void first(Node& i) const {
733      Parent::first(i);
734    }
735
736    void first(Edge& i) const {
737      Parent::first(i);
738      i.backward=false;
739      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
740             !(*forward_filter)[i]) Parent::next(i);
741      if (*static_cast<GraphEdge*>(&i)==INVALID) {
742        Parent::first(i);
743        i.backward=true;
744        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
745               !(*backward_filter)[i]) Parent::next(i);
746      }
747    }
748
749    void firstIn(Edge& i, const Node& n) const {
750      Parent::firstIn(i, n);
751      i.backward=false;
752      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
[1269]753             !(*forward_filter)[i]) Parent::nextIn(i);
[992]754      if (*static_cast<GraphEdge*>(&i)==INVALID) {
755        Parent::firstOut(i, n);
756        i.backward=true;
757        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
758               !(*backward_filter)[i]) Parent::nextOut(i);
759      }
760    }
761
762    void firstOut(Edge& i, const Node& n) const {
763      Parent::firstOut(i, n);
764      i.backward=false;
765      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
766             !(*forward_filter)[i]) Parent::nextOut(i);
767      if (*static_cast<GraphEdge*>(&i)==INVALID) {
768        Parent::firstIn(i, n);
769        i.backward=true;
770        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
771               !(*backward_filter)[i]) Parent::nextIn(i);
772      }
773    }
774
775    void next(Node& i) const {
776      Parent::next(i);
777    }
778
779    void next(Edge& i) const {
780      if (!(i.backward)) {
781        Parent::next(i);
782        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
783               !(*forward_filter)[i]) Parent::next(i);
784        if (*static_cast<GraphEdge*>(&i)==INVALID) {
785          Parent::first(i);
786          i.backward=true;
787          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
788                 !(*backward_filter)[i]) Parent::next(i);
789        }
790      } else {
791        Parent::next(i);
792        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
793               !(*backward_filter)[i]) Parent::next(i);
794      }
795    }
796
797    void nextIn(Edge& i) const {
798      if (!(i.backward)) {
799        Node n=Parent::target(i);
800        Parent::nextIn(i);
801        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
802               !(*forward_filter)[i]) Parent::nextIn(i);
803        if (*static_cast<GraphEdge*>(&i)==INVALID) {
804          Parent::firstOut(i, n);
805          i.backward=true;
806          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
807                 !(*backward_filter)[i]) Parent::nextOut(i);
808        }
809      } else {
810        Parent::nextOut(i);
811        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
812               !(*backward_filter)[i]) Parent::nextOut(i);
813      }
814    }
815
816    void nextOut(Edge& i) const {
817      if (!(i.backward)) {
818        Node n=Parent::source(i);
819        Parent::nextOut(i);
820        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
821               !(*forward_filter)[i]) Parent::nextOut(i);
822        if (*static_cast<GraphEdge*>(&i)==INVALID) {
823          Parent::firstIn(i, n);
824          i.backward=true;
825          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
826                 !(*backward_filter)[i]) Parent::nextIn(i);
827        }
828      } else {
829        Parent::nextIn(i);
830        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
831               !(*backward_filter)[i]) Parent::nextIn(i);
832      }
833    }
834
835    Node source(Edge e) const {
836      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
837    Node target(Edge e) const {
838      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
839
840    /// Gives back the opposite edge.
841    Edge opposite(const Edge& e) const {
842      Edge f=e;
843      f.backward=!f.backward;
844      return f;
845    }
846
847    /// \warning This is a linear time operation and works only if
848    /// \c Graph::EdgeIt is defined.
849    /// \todo hmm
850    int edgeNum() const {
851      int i=0;
852      Edge e;
853      for (first(e); e!=INVALID; next(e)) ++i;
854      return i;
855    }
856
857    bool forward(const Edge& e) const { return !e.backward; }
858    bool backward(const Edge& e) const { return e.backward; }
859
860    template <typename T>
[1401]861    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
[992]862    /// _Graph::EdgeMap one for the forward edges and
863    /// one for the backward edges.
864    class EdgeMap {
865      template <typename TT> friend class EdgeMap;
866      typename _Graph::template EdgeMap<T> forward_map, backward_map;
867    public:
868      typedef T Value;
869      typedef Edge Key;
870
[1401]871      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
[992]872              ForwardFilterMap, BackwardFilterMap>& g) :
873        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
874
[1401]875      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
[992]876              ForwardFilterMap, BackwardFilterMap>& g, T a) :
877        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
878     
879      void set(Edge e, T a) {
880        if (!e.backward)
881          forward_map.set(e, a);
882        else
883          backward_map.set(e, a);
884      }
885
886//       typename _Graph::template EdgeMap<T>::ConstReference
887//       operator[](Edge e) const {
888//      if (!e.backward)
889//        return forward_map[e];
890//      else
891//        return backward_map[e];
892//       }
893
894//      typename _Graph::template EdgeMap<T>::Reference
[1016]895      T operator[](Edge e) const {
[992]896        if (!e.backward)
897          return forward_map[e];
898        else
899          return backward_map[e];
900      }
901
902      void update() {
903        forward_map.update();
904        backward_map.update();
905      }
906    };
907
908  };
[569]909
[650]910
[1401]911  ///\brief An adaptor for composing a subgraph of a
[792]912  /// bidirected graph made from a directed one.
[612]913  ///
[1401]914  /// An adaptor for composing a subgraph of a
[911]915  /// bidirected graph made from a directed one.
916  ///
[1401]917  ///\warning Graph adaptors are in even more experimental state than the other
[879]918  ///parts of the lib. Use them at you own risk.
919  ///
[923]920  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
921  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
922  /// reversing its orientation. We are given moreover two bool valued
923  /// maps on the edge-set,
924  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
[1401]925  /// SubBidirGraphAdaptor implements the graph structure with node-set
[923]926  /// \f$V\f$ and edge-set
927  /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
[792]928  /// The purpose of writing + instead of union is because parallel
[923]929  /// edges can arise. (Similarly, antiparallel edges also can arise).
[792]930  /// In other words, a subgraph of the bidirected graph obtained, which
931  /// is given by orienting the edges of the original graph in both directions.
[923]932  /// As the oppositely directed edges are logically different,
933  /// the maps are able to attach different values for them.
934  ///
[1401]935  /// An example for such a construction is \c RevGraphAdaptor where the
[792]936  /// forward_filter is everywhere false and the backward_filter is
937  /// everywhere true. We note that for sake of efficiency,
[1401]938  /// \c RevGraphAdaptor is implemented in a different way.
939  /// But BidirGraphAdaptor is obtained from
940  /// SubBidirGraphAdaptor by considering everywhere true
[910]941  /// valued maps both for forward_filter and backward_filter.
[1252]942  ///
[1401]943  /// The most important application of SubBidirGraphAdaptor
944  /// is ResGraphAdaptor, which stands for the residual graph in directed
[792]945  /// flow and circulation problems.
[1401]946  /// As adaptors usually, the SubBidirGraphAdaptor implements the
[792]947  /// above mentioned graph structure without its physical storage,
[923]948  /// that is the whole stuff is stored in constant memory.
[992]949  template<typename _Graph,
[650]950           typename ForwardFilterMap, typename BackwardFilterMap>
[1401]951  class SubBidirGraphAdaptor :
[992]952    public IterableGraphExtender<
[1401]953    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
[650]954  public:
[992]955    typedef _Graph Graph;
956    typedef IterableGraphExtender<
[1401]957      SubBidirGraphAdaptorBase<
[992]958      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
[569]959  protected:
[1401]960    SubBidirGraphAdaptor() { }
[992]961  public:
[1401]962    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
[992]963                         BackwardFilterMap& _backward_filter) {
964      setGraph(_graph);
965      setForwardFilterMap(_forward_filter);
966      setBackwardFilterMap(_backward_filter);
967    }
968  };
[650]969
[569]970
[650]971
[1401]972  ///\brief An adaptor for composing bidirected graph from a directed one.
[650]973  ///
[1401]974  ///\warning Graph adaptors are in even more experimental state than the other
[879]975  ///parts of the lib. Use them at you own risk.
976  ///
[1401]977  /// An adaptor for composing bidirected graph from a directed one.
[650]978  /// A bidirected graph is composed over the directed one without physical
979  /// storage. As the oppositely directed edges are logically different ones
980  /// the maps are able to attach different values for them.
981  template<typename Graph>
[1401]982  class BidirGraphAdaptor :
983    public SubBidirGraphAdaptor<
[650]984    Graph,
985    ConstMap<typename Graph::Edge, bool>,
986    ConstMap<typename Graph::Edge, bool> > {
987  public:
[1401]988    typedef  SubBidirGraphAdaptor<
[650]989      Graph,
990      ConstMap<typename Graph::Edge, bool>,
991      ConstMap<typename Graph::Edge, bool> > Parent;
992  protected:
993    ConstMap<typename Graph::Edge, bool> cm;
994
[1401]995    BidirGraphAdaptor() : Parent(), cm(true) {
[655]996      Parent::setForwardFilterMap(cm);
997      Parent::setBackwardFilterMap(cm);
998    }
[650]999  public:
[1401]1000    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
[650]1001      Parent::setGraph(_graph);
1002      Parent::setForwardFilterMap(cm);
1003      Parent::setBackwardFilterMap(cm);
1004    }
[738]1005
1006    int edgeNum() const {
1007      return 2*this->graph->edgeNum();
1008    }
[1401]1009    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
[650]1010  };
1011
1012
1013  template<typename Graph, typename Number,
1014           typename CapacityMap, typename FlowMap>
[658]1015  class ResForwardFilter {
1016    //    const Graph* graph;
[650]1017    const CapacityMap* capacity;
1018    const FlowMap* flow;
1019  public:
[658]1020    ResForwardFilter(/*const Graph& _graph, */
1021                     const CapacityMap& _capacity, const FlowMap& _flow) :
1022      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1023    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
[656]1024    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1025    void setFlow(const FlowMap& _flow) { flow=&_flow; }
[650]1026    bool operator[](const typename Graph::Edge& e) const {
[738]1027      return (Number((*flow)[e]) < Number((*capacity)[e]));
[650]1028    }
1029  };
1030
1031  template<typename Graph, typename Number,
1032           typename CapacityMap, typename FlowMap>
[658]1033  class ResBackwardFilter {
[650]1034    const CapacityMap* capacity;
1035    const FlowMap* flow;
1036  public:
[658]1037    ResBackwardFilter(/*const Graph& _graph,*/
1038                      const CapacityMap& _capacity, const FlowMap& _flow) :
1039      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1040    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
[656]1041    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1042    void setFlow(const FlowMap& _flow) { flow=&_flow; }
[650]1043    bool operator[](const typename Graph::Edge& e) const {
[738]1044      return (Number(0) < Number((*flow)[e]));
[650]1045    }
1046  };
1047
[653]1048 
[1401]1049  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
[650]1050
[1401]1051  An adaptor for composing the residual graph for directed flow and circulation problems.
[1242]1052  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1053  number type. Let moreover
1054  \f$f,c:A\to F\f$, be functions on the edge-set.
[1401]1055  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
[1242]1056  and \f$c\f$ for a capacity function.   
1057  Suppose that a graph instange \c g of type
1058  \c ListGraph implements \f$G\f$.
1059  \code
1060  ListGraph g;
1061  \endcode
[1401]1062  Then RevGraphAdaptor implements the graph structure with node-set
[1242]1063  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1064  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1065  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1066  i.e. the so called residual graph.
1067  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1068  multilicities are counted, i.e. if an edge is in both
[1401]1069  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
[1242]1070  appears twice.
1071  The following code shows how
1072  such an instance can be constructed.
1073  \code
1074  typedef ListGraph Graph;
1075  Graph::EdgeMap<int> f(g);
1076  Graph::EdgeMap<int> c(g);
[1401]1077  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
[1242]1078  \endcode
1079  \author Marton Makai
1080  */
[650]1081  template<typename Graph, typename Number,
1082           typename CapacityMap, typename FlowMap>
[1401]1083  class ResGraphAdaptor :
1084    public SubBidirGraphAdaptor<
[650]1085    Graph,
[658]1086    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1087    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
[650]1088  public:
[1401]1089    typedef SubBidirGraphAdaptor<
[650]1090      Graph,
[658]1091      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1092      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
[650]1093  protected:
1094    const CapacityMap* capacity;
1095    FlowMap* flow;
[658]1096    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1097    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
[1401]1098    ResGraphAdaptor() : Parent(),
[658]1099                        capacity(0), flow(0) { }
1100    void setCapacityMap(const CapacityMap& _capacity) {
1101      capacity=&_capacity;
1102      forward_filter.setCapacity(_capacity);
1103      backward_filter.setCapacity(_capacity);
1104    }
1105    void setFlowMap(FlowMap& _flow) {
1106      flow=&_flow;
1107      forward_filter.setFlow(_flow);
1108      backward_filter.setFlow(_flow);
1109    }
[650]1110  public:
[1401]1111    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
[650]1112                       FlowMap& _flow) :
1113      Parent(), capacity(&_capacity), flow(&_flow),
[658]1114      forward_filter(/*_graph,*/ _capacity, _flow),
1115      backward_filter(/*_graph,*/ _capacity, _flow) {
[650]1116      Parent::setGraph(_graph);
1117      Parent::setForwardFilterMap(forward_filter);
1118      Parent::setBackwardFilterMap(backward_filter);
1119    }
1120
[660]1121    typedef typename Parent::Edge Edge;
1122
1123    void augment(const Edge& e, Number a) const {
[650]1124      if (Parent::forward(e)) 
1125        flow->set(e, (*flow)[e]+a);
1126      else 
1127        flow->set(e, (*flow)[e]-a);
1128    }
1129
[660]1130    /// \brief Residual capacity map.
1131    ///
[910]1132    /// In generic residual graphs the residual capacity can be obtained
1133    /// as a map.
[660]1134    class ResCap {
1135    protected:
[1401]1136      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
[660]1137    public:
[987]1138      typedef Number Value;
1139      typedef Edge Key;
[1401]1140      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
[888]1141             _res_graph) : res_graph(&_res_graph) { }
[660]1142      Number operator[](const Edge& e) const {
1143        if (res_graph->forward(e))
1144          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1145        else
1146          return (*(res_graph->flow))[e];
1147      }
1148    };
1149
[1401]1150    //    KEEP_MAPS(Parent, ResGraphAdaptor);
[650]1151  };
1152
1153
[998]1154
1155  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1156  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[998]1157  public:
1158    typedef _Graph Graph;
[1401]1159    typedef GraphAdaptorBase<_Graph> Parent;
[998]1160  protected:
1161    FirstOutEdgesMap* first_out_edges;
[1401]1162    ErasingFirstGraphAdaptorBase() : Parent(),
[998]1163                                     first_out_edges(0) { }
1164
1165    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1166      first_out_edges=&_first_out_edges;
1167    }
1168
1169  public:
1170
1171    typedef typename Parent::Node Node;
1172    typedef typename Parent::Edge Edge;
1173
1174    void firstOut(Edge& i, const Node& n) const {
1175      i=(*first_out_edges)[n];
1176    }
1177
1178    void erase(const Edge& e) const {
1179      Node n=source(e);
1180      Edge f=e;
1181      Parent::nextOut(f);
1182      first_out_edges->set(n, f);
1183    }   
1184  };
1185
1186
[612]1187  /// For blocking flows.
[556]1188
[1401]1189  ///\warning Graph adaptors are in even more experimental state than the other
[879]1190  ///parts of the lib. Use them at you own risk.
1191  ///
[1401]1192  /// This graph adaptor is used for on-the-fly
[792]1193  /// Dinits blocking flow computations.
[612]1194  /// For each node, an out-edge is stored which is used when the
1195  /// \code
1196  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1197  /// \endcode
1198  /// is called.
[556]1199  ///
[792]1200  /// \author Marton Makai
[998]1201  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1202  class ErasingFirstGraphAdaptor :
[998]1203    public IterableGraphExtender<
[1401]1204    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
[650]1205  public:
[998]1206    typedef _Graph Graph;
1207    typedef IterableGraphExtender<
[1401]1208      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1209    ErasingFirstGraphAdaptor(Graph& _graph,
[998]1210                             FirstOutEdgesMap& _first_out_edges) {
1211      setGraph(_graph);
1212      setFirstOutEdgesMap(_first_out_edges);
1213    }
[1019]1214
[998]1215  };
[556]1216
[1472]1217  template <typename _Graph>
1218  class NewEdgeSetAdaptorBase {
1219  public:
1220
1221    typedef _Graph Graph;
1222    typedef typename Graph::Node Node;
1223    typedef typename Graph::NodeIt NodeIt;
1224
1225  protected:
1226
1227    struct NodeT {
1228      int first_out, first_in;
1229      NodeT() : first_out(-1), first_in(-1) {}
1230    };
1231   
1232    class NodesImpl : protected Graph::template NodeMap<NodeT> {
1233
1234      typedef typename Graph::template NodeMap<NodeT> Parent;
1235      typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1236
1237      Adaptor& adaptor;
1238
1239    public:
1240
1241      NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1242        : Parent(_graph), adaptor(_adaptor) {}
1243
1244      virtual ~NodesImpl() {}
1245
1246      virtual void build() {
1247        Parent::build();
1248      }
1249
1250      virtual void clear() {
1251        adaptor._clear();
1252        Parent::clear();
1253      }
1254     
1255      virtual void add(const Node& node) {
1256        Parent::add(node);
1257        adaptor._add(node);
1258      }
1259     
1260      virtual void erase(const Node& node) {
1261        adaptor._erase(node);
1262        Parent::erase(node);
1263      }
1264
1265      NodeT& operator[](const Node& node) {
1266        return Parent::operator[](node);
1267      }
1268
1269      const NodeT& operator[](const Node& node) const {
1270        return Parent::operator[](node);
1271      }
1272     
1273    };
1274
1275    NodesImpl* nodes;
1276
1277    struct EdgeT {
1278      Node source, target;
1279      int next_out, next_in;
1280      int prev_out, prev_in;
1281      EdgeT() : prev_out(-1), prev_in(-1) {}
1282    };
1283
1284    std::vector<EdgeT> edges;
1285
1286    int first_edge;
1287    int first_free_edge;
1288
1289    virtual void _clear() = 0;
1290    virtual void _add(const Node& node) = 0;
1291    virtual void _erase(const Node& node) = 0;
1292   
1293    const Graph* graph;
1294
1295    void initalize(const Graph& _graph, NodesImpl& _nodes) {
1296      graph = &_graph;
1297      nodes = &_nodes;
1298    }
1299   
1300  public:
1301
1302    class Edge {
1303      friend class NewEdgeSetAdaptorBase<Graph>;
1304    protected:
1305      Edge(int _id) : id(_id) {}
1306      int id;
1307    public:
1308      Edge() {}
1309      Edge(Invalid) : id(-1) {}
1310      bool operator==(const Edge& edge) const { return id == edge.id; }
1311      bool operator!=(const Edge& edge) const { return id != edge.id; }
1312      bool operator<(const Edge& edge) const { return id < edge.id; }
1313    };
1314
1315    NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1316    virtual ~NewEdgeSetAdaptorBase() {}
1317
1318    Edge addEdge(const Node& source, const Node& target) {
1319      int n;
1320      if (first_free_edge == -1) {
1321        n = edges.size();
1322        edges.push_back(EdgeT());
1323      } else {
1324        n = first_free_edge;
1325        first_free_edge = edges[first_free_edge].next_in;
1326      }
1327      edges[n].next_in = (*nodes)[target].first_in;
1328      (*nodes)[target].first_in = n;
1329      edges[n].next_out = (*nodes)[source].first_out;
1330      (*nodes)[source].first_out = n;
1331      edges[n].source = source;
1332      edges[n].target = target;
1333      return Edge(n);
1334    }
1335
1336    void erase(const Edge& edge) {
1337      int n = edge.id;
1338      if (edges[n].prev_in != -1) {
1339        edges[edges[n].prev_in].next_in = edges[n].next_in;
1340      } else {
1341        (*nodes)[edges[n].target].first_in = edges[n].next_in;
1342      }
1343      if (edges[n].next_in != -1) {
1344        edges[edges[n].next_in].prev_in = edges[n].prev_in;
1345      }
1346
1347      if (edges[n].prev_out != -1) {
1348        edges[edges[n].prev_out].next_out = edges[n].next_out;
1349      } else {
1350        (*nodes)[edges[n].source].first_out = edges[n].next_out;
1351      }
1352      if (edges[n].next_out != -1) {
1353        edges[edges[n].next_out].prev_out = edges[n].prev_out;
1354      }
1355           
1356    }
1357
1358    void first(Node& node) const {
1359      graph->first(node);
1360    }
1361
1362    void next(Node& node) const {
1363      graph->next(node);
1364    }
1365
1366    void first(Edge& edge) const {
1367      Node node;
1368      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1369           next(node));
1370      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1371    }
1372
1373    void next(Edge& edge) const {
1374      if (edges[edge.id].next_in != -1) {
1375        edge.id = edges[edge.id].next_in;
1376      } else {
1377        Node node = edges[edge.id].target;
1378        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1379             next(node));
1380        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1381      }     
1382    }
1383
1384    void firstOut(Edge& edge, const Node& node) const {
1385      edge.id = (*nodes)[node].first_out;   
1386    }
1387   
1388    void nextOut(Edge& edge) const {
1389      edge.id = edges[edge.id].next_out;       
1390    }
1391
1392    void firstIn(Edge& edge, const Node& node) const {
1393      edge.id = (*nodes)[node].first_in;         
1394    }
1395
1396    void nextIn(Edge& edge) const {
1397      edge.id = edges[edge.id].next_in;   
1398    }
1399
1400    int id(const Node& node) const { return graph->id(node); }
1401    int id(const Edge& edge) const { return edge.id; }
1402
1403    Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
1404    Edge fromId(int id, Edge) const { return Edge(id); }
1405
1406    int maxId(Node) const { return graph->maxId(Node()); };
1407    int maxId(Edge) const { return edges.size() - 1; }
1408
1409    Node source(const Edge& edge) const { return edges[edge.id].source;}
1410    Node target(const Edge& edge) const { return edges[edge.id].target;}
1411
1412  };
1413
[1538]1414
1415  /// \brief Graph adaptor using a node set of another graph and an
1416  /// own edge set.
1417  ///
1418  /// This structure can be used to establish another graph over a node set
1419  /// of an existing one. The node iterator will go through the nodes of the
1420  /// original graph.
1421  ///
1422  /// \param _Graph The type of the graph which shares its node set with
[1631]1423  /// this class. Its interface must conform to the \ref concept::StaticGraph
[1538]1424  /// "StaticGraph" concept.
1425  ///
1426  /// In the edge extension and removing it conforms to the
[1631]1427  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
[1472]1428  template <typename _Graph>
1429  class NewEdgeSetAdaptor :
1430    public ErasableGraphExtender<
1431    ClearableGraphExtender<
1432    ExtendableGraphExtender<
1433    DefaultMappableGraphExtender<
1434    IterableGraphExtender<
1435    AlterableGraphExtender<
1436    NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1437
1438  public:
1439
1440    typedef ErasableGraphExtender<
1441      ClearableGraphExtender<
1442      ExtendableGraphExtender<
1443      DefaultMappableGraphExtender<
1444      IterableGraphExtender<
1445      AlterableGraphExtender<
1446      NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1447   
1448
1449    typedef typename Parent::Node Node;
1450    typedef typename Parent::Edge Edge;
1451
1452  private:
1453
1454    virtual void _clear() {
1455      Parent::edges.clear();
1456      Parent::first_edge = -1;
1457      Parent::first_free_edge = -1;
1458      Parent::getNotifier(Edge()).clear();
1459      Parent::getNotifier(Node()).clear();
1460    }
1461
1462    virtual void _add(const Node& node) {
1463      Parent::getNotifier(Node()).add(node);
1464    }
1465
1466    virtual void _erase(const Node& node) {
1467      Edge edge;
1468      Parent::firstOut(edge, node);
1469      while (edge != INVALID) {
1470        Parent::erase(edge);
1471        Parent::firstOut(edge, node);
1472      }
1473
1474      Parent::firstIn(edge, node);
1475      while (edge != INVALID) {
1476        Parent::erase(edge);
1477        Parent::firstIn(edge, node);
1478      }
1479     
1480      Parent::getNotifier(Node()).erase(node);
1481    }
1482
1483
1484    typedef typename Parent::NodesImpl NodesImpl;
1485
1486    NodesImpl nodes;
1487   
1488  public:
1489
[1538]1490    /// \brief Constructor of the adaptor.
1491    ///
1492    /// Constructor of the adaptor.
[1472]1493    NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1494      Parent::initalize(_graph, nodes);
1495    }
1496
1497    void clear() {
[1538]1498      Parent::getNotifier(Edge()).clear();     
1499
[1472]1500      Parent::edges.clear();
1501      Parent::first_edge = -1;
1502      Parent::first_free_edge = -1;
[1538]1503    }
1504   
1505  };
[1472]1506
[1538]1507  /// \brief Graph adaptor using a node set of another graph and an
1508  /// own undir edge set.
1509  ///
1510  /// This structure can be used to establish another undirected graph over
1511  /// a node set of an existing one. The node iterator will go through the
1512  /// nodes of the original graph.
1513  ///
1514  /// \param _Graph The type of the graph which shares its node set with
[1631]1515  /// this class. Its interface must conform to the \ref concept::StaticGraph
[1538]1516  /// "StaticGraph" concept.
1517  ///
1518  /// In the edge extension and removing it conforms to the
[1631]1519  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
[1538]1520  template <typename _Graph>
1521  class NewUndirEdgeSetAdaptor :
1522    public ErasableUndirGraphExtender<
1523    ClearableUndirGraphExtender<
1524    ExtendableUndirGraphExtender<
1525    MappableUndirGraphExtender<
1526    IterableUndirGraphExtender<
1527    AlterableUndirGraphExtender<
1528    UndirGraphExtender<
1529    NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1530
1531  public:
1532
1533    typedef ErasableUndirGraphExtender<
1534      ClearableUndirGraphExtender<
1535      ExtendableUndirGraphExtender<
1536      MappableUndirGraphExtender<
1537      IterableUndirGraphExtender<
1538      AlterableUndirGraphExtender<
1539      UndirGraphExtender<
1540      NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
1541   
1542
1543    typedef typename Parent::Node Node;
1544    typedef typename Parent::Edge Edge;
1545    typedef typename Parent::UndirEdge UndirEdge;
1546
1547  private:
1548
1549    virtual void _clear() {
1550      Parent::edges.clear();
1551      Parent::first_edge = -1;
1552      Parent::first_free_edge = -1;
1553      Parent::getNotifier(Edge()).clear();
1554      Parent::getNotifier(Node()).clear();
1555    }
1556
1557    virtual void _add(const Node& node) {
1558      Parent::getNotifier(Node()).add(node);
1559    }
1560
1561    virtual void _erase(const Node& node) {
1562      Edge edge;
1563      Parent::firstOut(edge, node);
1564      while (edge != INVALID) {
1565        Parent::erase(edge);
1566        Parent::firstOut(edge, node);
1567      }
1568
1569      Parent::firstIn(edge, node);
1570      while (edge != INVALID) {
1571        Parent::erase(edge);
1572        Parent::firstIn(edge, node);
1573      }
1574     
1575      Parent::getNotifier(Node()).erase(node);
1576    }
1577
1578    typedef typename Parent::NodesImpl NodesImpl;
1579
1580    NodesImpl nodes;
1581   
1582  public:
1583
1584
1585    /// \brief Constructor of the adaptor.
1586    ///
1587    /// Constructor of the adaptor.
1588    NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1589      Parent::initalize(_graph, nodes);
1590    }
1591
1592    void clear() {
[1472]1593      Parent::getNotifier(Edge()).clear();     
[1538]1594      Parent::getNotifier(UndirEdge()).clear();     
1595
1596      Parent::edges.clear();
1597      Parent::first_edge = -1;
1598      Parent::first_free_edge = -1;
[1472]1599    }
1600   
1601  };
1602
[556]1603  ///@}
1604
[921]1605} //namespace lemon
[556]1606
[1401]1607#endif //LEMON_GRAPH_ADAPTOR_H
[556]1608
Note: See TracBrowser for help on using the repository browser.