COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_adaptor.h @ 1401:9588dcef6793

Last change on this file since 1401:9588dcef6793 was 1401:9588dcef6793, checked in by Alpar Juttner, 14 years ago

wrapper -> adaptor

File size: 39.2 KB
RevLine 
[906]1/* -*- C++ -*-
[1401]2 * src/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>
[1307]30#include <lemon/bits/iterable_graph_extender.h>
[1383]31#include <lemon/bits/undir_graph_extender.h>
[774]32#include <iostream>
[556]33
[921]34namespace lemon {
[556]35
[1401]36  // Graph adaptors
[556]37
[1172]38  /*!
[1401]39    \addtogroup graph_adaptors
[1004]40    @{
[1172]41   */
[556]42
[1172]43  /*!
[1401]44    Base type for the Graph Adaptors
[1242]45   
[1401]46    \warning Graph adaptors are in even more experimental state than the other
[1004]47    parts of the lib. Use them at you own risk.
[1242]48   
[1401]49    This is the base type for most of LEMON graph adaptors.
50    This class implements a trivial graph adaptor i.e. it only wraps the
[1004]51    functions and types of the graph. The purpose of this class is to
[1401]52    make easier implementing graph adaptors. E.g. if an adaptor is
[1004]53    considered which differs from the wrapped graph only in some of its
[1401]54    functions or types, then it can be derived from GraphAdaptor, and only the
[1004]55    differences should be implemented.
56 
57    \author Marton Makai
58  */
[970]59  template<typename _Graph>
[1401]60  class GraphAdaptorBase {
[970]61  public:
62    typedef _Graph Graph;
63    /// \todo Is it needed?
64    typedef Graph BaseGraph;
65    typedef Graph ParentGraph;
66
[556]67  protected:
68    Graph* graph;
[1401]69    GraphAdaptorBase() : graph(0) { }
[556]70    void setGraph(Graph& _graph) { graph=&_graph; }
71
72  public:
[1401]73    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
[556]74 
[774]75    typedef typename Graph::Node Node;
76    typedef typename Graph::Edge Edge;
[556]77   
[970]78    void first(Node& i) const { graph->first(i); }
79    void first(Edge& i) const { graph->first(i); }
80    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
81    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
[556]82
[970]83    void next(Node& i) const { graph->next(i); }
84    void next(Edge& i) const { graph->next(i); }
85    void nextIn(Edge& i) const { graph->nextIn(i); }
86    void nextOut(Edge& i) const { graph->nextOut(i); }
87
[986]88    Node source(const Edge& e) const { return graph->source(e); }
89    Node target(const Edge& e) const { return graph->target(e); }
[556]90
91    int nodeNum() const { return graph->nodeNum(); }
92    int edgeNum() const { return graph->edgeNum(); }
93 
94    Node addNode() const { return Node(graph->addNode()); }
[986]95    Edge addEdge(const Node& source, const Node& target) const {
96      return Edge(graph->addEdge(source, target)); }
[556]97
98    void erase(const Node& i) const { graph->erase(i); }
99    void erase(const Edge& i) const { graph->erase(i); }
100 
101    void clear() const { graph->clear(); }
102   
[736]103    bool forward(const Edge& e) const { return graph->forward(e); }
104    bool backward(const Edge& e) const { return graph->backward(e); }
[739]105
106    int id(const Node& v) const { return graph->id(v); }
107    int id(const Edge& e) const { return graph->id(e); }
[650]108   
[738]109    Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
[650]110
[970]111    template <typename _Value>
112    class NodeMap : public _Graph::template NodeMap<_Value> {
113    public:
114      typedef typename _Graph::template NodeMap<_Value> Parent;
[1401]115      NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
116      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
[970]117      : Parent(*gw.graph, value) { }
118    };
[556]119
[970]120    template <typename _Value>
121    class EdgeMap : public _Graph::template EdgeMap<_Value> {
122    public:
123      typedef typename _Graph::template EdgeMap<_Value> Parent;
[1401]124      EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
125      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
[970]126      : Parent(*gw.graph, value) { }
127    };
[877]128
[556]129  };
130
[970]131  template <typename _Graph>
[1401]132  class GraphAdaptor :
133    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
[970]134  public:
135    typedef _Graph Graph;
[1401]136    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
[970]137  protected:
[1401]138    GraphAdaptor() : Parent() { }
[569]139
[970]140  public:
[1401]141    GraphAdaptor(Graph& _graph) { setGraph(_graph); }
[970]142  };
[569]143
[997]144  template <typename _Graph>
[1401]145  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[997]146  public:
147    typedef _Graph Graph;
[1401]148    typedef GraphAdaptorBase<_Graph> Parent;
[997]149  protected:
[1401]150    RevGraphAdaptorBase() : Parent() { }
[997]151  public:
152    typedef typename Parent::Node Node;
153    typedef typename Parent::Edge Edge;
154
[1383]155    //    using Parent::first;
[997]156    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
157    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
158
[1383]159    //    using Parent::next;
[997]160    void nextIn(Edge& i) const { Parent::nextOut(i); }
161    void nextOut(Edge& i) const { Parent::nextIn(i); }
162
163    Node source(const Edge& e) const { return Parent::target(e); }
164    Node target(const Edge& e) const { return Parent::source(e); }
165  };
166   
167
[1401]168  /// A graph adaptor which reverses the orientation of the edges.
[556]169
[1401]170  ///\warning Graph adaptors are in even more experimental state than the other
[879]171  ///parts of the lib. Use them at you own risk.
172  ///
[923]173  /// Let \f$G=(V, A)\f$ be a directed graph and
174  /// suppose that a graph instange \c g of type
175  /// \c ListGraph implements \f$G\f$.
176  /// \code
177  /// ListGraph g;
178  /// \endcode
179  /// For each directed edge
180  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
181  /// reversing its orientation.
[1401]182  /// Then RevGraphAdaptor implements the graph structure with node-set
[923]183  /// \f$V\f$ and edge-set
184  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
185  /// reversing the orientation of its edges. The following code shows how
186  /// such an instance can be constructed.
187  /// \code
[1401]188  /// RevGraphAdaptor<ListGraph> gw(g);
[923]189  /// \endcode
[556]190  ///\author Marton Makai
[997]191  template<typename _Graph>
[1401]192  class RevGraphAdaptor :
193    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
[650]194  public:
[997]195    typedef _Graph Graph;
196    typedef IterableGraphExtender<
[1401]197      RevGraphAdaptorBase<_Graph> > Parent;
[556]198  protected:
[1401]199    RevGraphAdaptor() { }
[556]200  public:
[1401]201    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
[997]202  };
[556]203
[992]204 
205  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
[1401]206  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[992]207  public:
208    typedef _Graph Graph;
[1401]209    typedef GraphAdaptorBase<_Graph> Parent;
[992]210  protected:
211    NodeFilterMap* node_filter_map;
212    EdgeFilterMap* edge_filter_map;
[1401]213    SubGraphAdaptorBase() : Parent(),
[992]214                            node_filter_map(0), edge_filter_map(0) { }
[775]215
[992]216    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
217      node_filter_map=&_node_filter_map;
218    }
219    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
220      edge_filter_map=&_edge_filter_map;
221    }
222
223  public:
[1401]224//     SubGraphAdaptorBase(Graph& _graph,
[992]225//                      NodeFilterMap& _node_filter_map,
226//                      EdgeFilterMap& _edge_filter_map) :
227//       Parent(&_graph),
228//       node_filter_map(&node_filter_map),
229//       edge_filter_map(&edge_filter_map) { }
230
231    typedef typename Parent::Node Node;
232    typedef typename Parent::Edge Edge;
233
234    void first(Node& i) const {
235      Parent::first(i);
236      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
237    }
238    void first(Edge& i) const {
239      Parent::first(i);
240      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
241    }
242    void firstIn(Edge& i, const Node& n) const {
243      Parent::firstIn(i, n);
244      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
245    }
246    void firstOut(Edge& i, const Node& n) const {
247      Parent::firstOut(i, n);
248      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
249    }
250
251    void next(Node& i) const {
252      Parent::next(i);
253      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
254    }
255    void next(Edge& i) const {
256      Parent::next(i);
257      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
258    }
259    void nextIn(Edge& i) const {
260      Parent::nextIn(i);
261      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
262    }
263    void nextOut(Edge& i) const {
264      Parent::nextOut(i);
265      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
266    }
267
268    /// This function hides \c n in the graph, i.e. the iteration
269    /// jumps over it. This is done by simply setting the value of \c n 
270    /// to be false in the corresponding node-map.
271    void hide(const Node& n) const { node_filter_map->set(n, false); }
272
273    /// This function hides \c e in the graph, i.e. the iteration
274    /// jumps over it. This is done by simply setting the value of \c e 
275    /// to be false in the corresponding edge-map.
276    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
277
278    /// The value of \c n is set to be true in the node-map which stores
279    /// hide information. If \c n was hidden previuosly, then it is shown
280    /// again
281     void unHide(const Node& n) const { node_filter_map->set(n, true); }
282
283    /// The value of \c e is set to be true in the edge-map which stores
284    /// hide information. If \c e was hidden previuosly, then it is shown
285    /// again
286    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
287
288    /// Returns true if \c n is hidden.
289    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
290
291    /// Returns true if \c n is hidden.
292    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
293
294    /// \warning This is a linear time operation and works only if s
295    /// \c Graph::NodeIt is defined.
296    /// \todo assign tags.
297    int nodeNum() const {
298      int i=0;
299      Node n;
300      for (first(n); n!=INVALID; next(n)) ++i;
301      return i;
302    }
303
304    /// \warning This is a linear time operation and works only if
305    /// \c Graph::EdgeIt is defined.
306    /// \todo assign tags.
307    int edgeNum() const {
308      int i=0;
309      Edge e;
310      for (first(e); e!=INVALID; next(e)) ++i;
311      return i;
312    }
313
314
315  };
[775]316
[1401]317  /*! \brief A graph adaptor for hiding nodes and edges from a graph.
[1242]318   
[1401]319  \warning Graph adaptors are in even more experimental state than the other
[930]320  parts of the lib. Use them at you own risk.
321 
[1401]322  SubGraphAdaptor shows the graph with filtered node-set and
[930]323  edge-set.
[1242]324  Let \f$G=(V, A)\f$ be a directed graph
325  and suppose that the graph instance \c g of type ListGraph implements
326  \f$G\f$.
327  Let moreover \f$b_V\f$ and
328  \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
[1401]329  SubGraphAdaptor<...>::NodeIt iterates
[1242]330  on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
[1401]331  SubGraphAdaptor<...>::EdgeIt iterates
[1242]332  on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
[1401]333  SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
[1242]334  only on edges leaving and entering a specific node which have true value.
335
336  We have to note that this does not mean that an
[930]337  induced subgraph is obtained, the node-iterator cares only the filter
338  on the node-set, and the edge-iterators care only the filter on the
[1242]339  edge-set.
[930]340  \code
[1242]341  typedef ListGraph Graph;
[930]342  Graph g;
343  typedef Graph::Node Node;
344  typedef Graph::Edge Edge;
345  Node u=g.addNode(); //node of id 0
346  Node v=g.addNode(); //node of id 1
347  Node e=g.addEdge(u, v); //edge of id 0
348  Node f=g.addEdge(v, u); //edge of id 1
349  Graph::NodeMap<bool> nm(g, true);
350  nm.set(u, false);
351  Graph::EdgeMap<bool> em(g, true);
352  em.set(e, false);
[1401]353  typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
[930]354  SubGW gw(g, nm, em);
355  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
356  std::cout << ":-)" << std::endl;
357  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
358  \endcode
359  The output of the above code is the following.
360  \code
361  1
362  :-)
363  1
364  \endcode
365  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
366  \c Graph::Node that is why \c g.id(n) can be applied.
367
[1401]368  For other examples see also the documentation of NodeSubGraphAdaptor and
369  EdgeSubGraphAdaptor.
[930]370
371  \author Marton Makai
372  */
[992]373  template<typename _Graph, typename NodeFilterMap,
[556]374           typename EdgeFilterMap>
[1401]375  class SubGraphAdaptor :
[992]376    public IterableGraphExtender<
[1401]377    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
[650]378  public:
[992]379    typedef _Graph Graph;
380    typedef IterableGraphExtender<
[1401]381      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
[556]382  protected:
[1401]383    SubGraphAdaptor() { }
[992]384  public:
[1401]385    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
[992]386                    EdgeFilterMap& _edge_filter_map) {
387      setGraph(_graph);
388      setNodeFilterMap(_node_filter_map);
389      setEdgeFilterMap(_edge_filter_map);
390    }
391  };
[556]392
393
[569]394
[1401]395  /*! \brief An adaptor for hiding nodes from a graph.
[933]396
[1401]397  \warning Graph adaptors are in even more experimental state than the other
[933]398  parts of the lib. Use them at you own risk.
399 
[1401]400  An adaptor for hiding nodes from a graph.
401  This adaptor specializes SubGraphAdaptor in the way that only the node-set
[933]402  can be filtered. Note that this does not mean of considering induced
403  subgraph, the edge-iterators consider the original edge-set.
404  \author Marton Makai
405  */
406  template<typename Graph, typename NodeFilterMap>
[1401]407  class NodeSubGraphAdaptor :
408    public SubGraphAdaptor<Graph, NodeFilterMap,
[933]409                           ConstMap<typename Graph::Edge,bool> > {
410  public:
[1401]411    typedef SubGraphAdaptor<Graph, NodeFilterMap,
[933]412                            ConstMap<typename Graph::Edge,bool> > Parent;
413  protected:
414    ConstMap<typename Graph::Edge, bool> const_true_map;
415  public:
[1401]416    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
[933]417      Parent(), const_true_map(true) {
418      Parent::setGraph(_graph);
419      Parent::setNodeFilterMap(_node_filter_map);
420      Parent::setEdgeFilterMap(const_true_map);
421    }
422  };
423
424
[1401]425  /*! \brief An adaptor for hiding edges from a graph.
[932]426
[1401]427  \warning Graph adaptors are in even more experimental state than the other
[932]428  parts of the lib. Use them at you own risk.
429 
[1401]430  An adaptor for hiding edges from a graph.
431  This adaptor specializes SubGraphAdaptor in the way that only the edge-set
432  can be filtered. The usefulness of this adaptor is demonstrated in the
[933]433  problem of searching a maximum number of edge-disjoint shortest paths
434  between
435  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
436  non-negative edge-lengths. Note that
437  the comprehension of the presented solution
[1252]438  need's some elementary knowledge from combinatorial optimization.
[933]439
440  If a single shortest path is to be
[1252]441  searched between \c s and \c t, then this can be done easily by
442  applying the Dijkstra algorithm. What happens, if a maximum number of
[933]443  edge-disjoint shortest paths is to be computed. It can be proved that an
444  edge can be in a shortest path if and only if it is tight with respect to
445  the potential function computed by Dijkstra. Moreover, any path containing
446  only such edges is a shortest one. Thus we have to compute a maximum number
447  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
448  all the tight edges. The computation will be demonstrated on the following
449  graph, which is read from a dimacs file.
450 
451  \dot
452  digraph lemon_dot_example {
453  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
454  n0 [ label="0 (s)" ];
455  n1 [ label="1" ];
456  n2 [ label="2" ];
457  n3 [ label="3" ];
458  n4 [ label="4" ];
459  n5 [ label="5" ];
460  n6 [ label="6 (t)" ];
461  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
462  n5 ->  n6 [ label="9, length:4" ];
463  n4 ->  n6 [ label="8, length:2" ];
464  n3 ->  n5 [ label="7, length:1" ];
465  n2 ->  n5 [ label="6, length:3" ];
466  n2 ->  n6 [ label="5, length:5" ];
467  n2 ->  n4 [ label="4, length:2" ];
468  n1 ->  n4 [ label="3, length:3" ];
469  n0 ->  n3 [ label="2, length:1" ];
470  n0 ->  n2 [ label="1, length:2" ];
471  n0 ->  n1 [ label="0, length:3" ];
472  }
473  \enddot
474
475  \code
476  Graph g;
477  Node s, t;
478  LengthMap length(g);
479
480  readDimacs(std::cin, g, length, s, t);
481
[986]482  cout << "edges with lengths (of form id, source--length->target): " << endl;
[933]483  for(EdgeIt e(g); e!=INVALID; ++e)
[986]484    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
485         << length[e] << "->" << g.id(g.target(e)) << endl;
[933]486
487  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
488  \endcode
489  Next, the potential function is computed with Dijkstra.
490  \code
491  typedef Dijkstra<Graph, LengthMap> Dijkstra;
492  Dijkstra dijkstra(g, length);
493  dijkstra.run(s);
494  \endcode
495  Next, we consrtruct a map which filters the edge-set to the tight edges.
496  \code
497  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
498    TightEdgeFilter;
499  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
500 
[1401]501  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
[933]502  SubGW gw(g, tight_edge_filter);
503  \endcode
504  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
505  with a max flow algorithm Preflow.
506  \code
507  ConstMap<Edge, int> const_1_map(1);
508  Graph::EdgeMap<int> flow(g, 0);
509
510  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
511    preflow(gw, s, t, const_1_map, flow);
512  preflow.run();
513  \endcode
514  Last, the output is:
515  \code 
516  cout << "maximum number of edge-disjoint shortest path: "
517       << preflow.flowValue() << endl;
518  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
519       << endl;
520  for(EdgeIt e(g); e!=INVALID; ++e)
521    if (flow[e])
[986]522      cout << " " << g.id(g.source(e)) << "--"
523           << length[e] << "->" << g.id(g.target(e)) << endl;
[933]524  \endcode
525  The program has the following (expected :-)) output:
526  \code
[986]527  edges with lengths (of form id, source--length->target):
[933]528   9, 5--4->6
529   8, 4--2->6
530   7, 3--1->5
531   6, 2--3->5
532   5, 2--5->6
533   4, 2--2->4
534   3, 1--3->4
535   2, 0--1->3
536   1, 0--2->2
537   0, 0--3->1
538  s: 0 t: 6
539  maximum number of edge-disjoint shortest path: 2
540  edges of the maximum number of edge-disjoint shortest s-t paths:
541   9, 5--4->6
542   8, 4--2->6
543   7, 3--1->5
544   4, 2--2->4
545   2, 0--1->3
546   1, 0--2->2
547  \endcode
548
[932]549  \author Marton Makai
550  */
551  template<typename Graph, typename EdgeFilterMap>
[1401]552  class EdgeSubGraphAdaptor :
553    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[932]554                           EdgeFilterMap> {
555  public:
[1401]556    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[932]557                            EdgeFilterMap> Parent;
558  protected:
559    ConstMap<typename Graph::Node, bool> const_true_map;
560  public:
[1401]561    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
[932]562      Parent(), const_true_map(true) {
563      Parent::setGraph(_graph);
564      Parent::setNodeFilterMap(const_true_map);
565      Parent::setEdgeFilterMap(_edge_filter_map);
566    }
567  };
568
[1383]569  template <typename _Graph>
[1401]570  class UndirGraphAdaptorBase :
571    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
[1383]572  public:
573    typedef _Graph Graph;
[1401]574    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
[1383]575  protected:
[1401]576    UndirGraphAdaptorBase() : Parent() { }
[1383]577  public:
578    typedef typename Parent::UndirEdge UndirEdge;
579    typedef typename Parent::Edge Edge;
580   
581    /// \bug Why cant an edge say that it is forward or not???
582    /// By this, a pointer to the graph have to be stored
583    /// The implementation
584    template <typename T>
585    class EdgeMap {
586    protected:
[1401]587      const UndirGraphAdaptorBase<_Graph>* g;
[1383]588      template <typename TT> friend class EdgeMap;
589      typename _Graph::template EdgeMap<T> forward_map, backward_map;
590    public:
591      typedef T Value;
592      typedef Edge Key;
593     
[1401]594      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
[1383]595        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
[569]596
[1401]597      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
[1383]598        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
599     
600      void set(Edge e, T a) {
601        if (g->forward(e))
602          forward_map.set(e, a);
603        else
604          backward_map.set(e, a);
605      }
[556]606
[1383]607      T operator[](Edge e) const {
608        if (g->forward(e))
609          return forward_map[e];
610        else
611          return backward_map[e];
[556]612      }
613    };
[1383]614       
615    template <typename T>
616    class UndirEdgeMap {
617      template <typename TT> friend class UndirEdgeMap;
618      typename _Graph::template EdgeMap<T> map;
619    public:
620      typedef T Value;
621      typedef UndirEdge Key;
622     
[1401]623      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
[1383]624        map(*(g.graph)) { }
[556]625
[1401]626      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
[1383]627        map(*(g.graph), a) { }
628     
629      void set(UndirEdge e, T a) {
630        map.set(e, a);
631      }
[556]632
[1383]633      T operator[](UndirEdge e) const {
634        return map[e];
635      }
636    };
637     
638  };
639
[1401]640  /// \brief An undirected graph is made from a directed graph by an adaptor
[1383]641  ///
642  /// Undocumented, untested!!!
643  /// If somebody knows nice demo application, let's polulate it.
644  ///
645  /// \author Marton Makai
646  template<typename _Graph>
[1401]647  class UndirGraphAdaptor :
[1383]648    public IterableUndirGraphExtender<
[1401]649    UndirGraphAdaptorBase<_Graph> > {
[1383]650  public:
651    typedef _Graph Graph;
652    typedef IterableUndirGraphExtender<
[1401]653      UndirGraphAdaptorBase<_Graph> > Parent;
[1383]654  protected:
[1401]655    UndirGraphAdaptor() { }
[1383]656  public:
[1401]657    UndirGraphAdaptor(_Graph& _graph) {
[1383]658      setGraph(_graph);
[556]659    }
660  };
661
[992]662 
663  template <typename _Graph,
664            typename ForwardFilterMap, typename BackwardFilterMap>
[1401]665  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[992]666  public:
667    typedef _Graph Graph;
[1401]668    typedef GraphAdaptorBase<_Graph> Parent;
[992]669  protected:
670    ForwardFilterMap* forward_filter;
671    BackwardFilterMap* backward_filter;
[1401]672    SubBidirGraphAdaptorBase() : Parent(),
[992]673                                 forward_filter(0), backward_filter(0) { }
674
675    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
676      forward_filter=&_forward_filter;
677    }
678    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
679      backward_filter=&_backward_filter;
680    }
681
682  public:
[1401]683//     SubGraphAdaptorBase(Graph& _graph,
[992]684//                      NodeFilterMap& _node_filter_map,
685//                      EdgeFilterMap& _edge_filter_map) :
686//       Parent(&_graph),
687//       node_filter_map(&node_filter_map),
688//       edge_filter_map(&edge_filter_map) { }
689
690    typedef typename Parent::Node Node;
691    typedef typename _Graph::Edge GraphEdge;
692    template <typename T> class EdgeMap;
[1401]693    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
[992]694    /// _Graph::Edge. It contains an extra bool flag which is true
695    /// if and only if the
696    /// edge is the backward version of the original edge.
697    class Edge : public _Graph::Edge {
[1401]698      friend class SubBidirGraphAdaptorBase<
[992]699        Graph, ForwardFilterMap, BackwardFilterMap>;
700      template<typename T> friend class EdgeMap;
701    protected:
702      bool backward; //true, iff backward
703    public:
704      Edge() { }
705      /// \todo =false is needed, or causes problems?
706      /// If \c _backward is false, then we get an edge corresponding to the
707      /// original one, otherwise its oppositely directed pair is obtained.
708      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
709        _Graph::Edge(e), backward(_backward) { }
710      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
711      bool operator==(const Edge& v) const {
712        return (this->backward==v.backward &&
713                static_cast<typename _Graph::Edge>(*this)==
714                static_cast<typename _Graph::Edge>(v));
715      }
716      bool operator!=(const Edge& v) const {
717        return (this->backward!=v.backward ||
718                static_cast<typename _Graph::Edge>(*this)!=
719                static_cast<typename _Graph::Edge>(v));
720      }
721    };
722
723    void first(Node& i) const {
724      Parent::first(i);
725    }
726
727    void first(Edge& i) const {
728      Parent::first(i);
729      i.backward=false;
730      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
731             !(*forward_filter)[i]) Parent::next(i);
732      if (*static_cast<GraphEdge*>(&i)==INVALID) {
733        Parent::first(i);
734        i.backward=true;
735        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
736               !(*backward_filter)[i]) Parent::next(i);
737      }
738    }
739
740    void firstIn(Edge& i, const Node& n) const {
741      Parent::firstIn(i, n);
742      i.backward=false;
743      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
[1269]744             !(*forward_filter)[i]) Parent::nextIn(i);
[992]745      if (*static_cast<GraphEdge*>(&i)==INVALID) {
746        Parent::firstOut(i, n);
747        i.backward=true;
748        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
749               !(*backward_filter)[i]) Parent::nextOut(i);
750      }
751    }
752
753    void firstOut(Edge& i, const Node& n) const {
754      Parent::firstOut(i, n);
755      i.backward=false;
756      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
757             !(*forward_filter)[i]) Parent::nextOut(i);
758      if (*static_cast<GraphEdge*>(&i)==INVALID) {
759        Parent::firstIn(i, n);
760        i.backward=true;
761        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
762               !(*backward_filter)[i]) Parent::nextIn(i);
763      }
764    }
765
766    void next(Node& i) const {
767      Parent::next(i);
768    }
769
770    void next(Edge& i) const {
771      if (!(i.backward)) {
772        Parent::next(i);
773        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
774               !(*forward_filter)[i]) Parent::next(i);
775        if (*static_cast<GraphEdge*>(&i)==INVALID) {
776          Parent::first(i);
777          i.backward=true;
778          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
779                 !(*backward_filter)[i]) Parent::next(i);
780        }
781      } else {
782        Parent::next(i);
783        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
784               !(*backward_filter)[i]) Parent::next(i);
785      }
786    }
787
788    void nextIn(Edge& i) const {
789      if (!(i.backward)) {
790        Node n=Parent::target(i);
791        Parent::nextIn(i);
792        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
793               !(*forward_filter)[i]) Parent::nextIn(i);
794        if (*static_cast<GraphEdge*>(&i)==INVALID) {
795          Parent::firstOut(i, n);
796          i.backward=true;
797          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
798                 !(*backward_filter)[i]) Parent::nextOut(i);
799        }
800      } else {
801        Parent::nextOut(i);
802        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
803               !(*backward_filter)[i]) Parent::nextOut(i);
804      }
805    }
806
807    void nextOut(Edge& i) const {
808      if (!(i.backward)) {
809        Node n=Parent::source(i);
810        Parent::nextOut(i);
811        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
812               !(*forward_filter)[i]) Parent::nextOut(i);
813        if (*static_cast<GraphEdge*>(&i)==INVALID) {
814          Parent::firstIn(i, n);
815          i.backward=true;
816          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
817                 !(*backward_filter)[i]) Parent::nextIn(i);
818        }
819      } else {
820        Parent::nextIn(i);
821        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
822               !(*backward_filter)[i]) Parent::nextIn(i);
823      }
824    }
825
826    Node source(Edge e) const {
827      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
828    Node target(Edge e) const {
829      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
830
831    /// Gives back the opposite edge.
832    Edge opposite(const Edge& e) const {
833      Edge f=e;
834      f.backward=!f.backward;
835      return f;
836    }
837
838    /// \warning This is a linear time operation and works only if
839    /// \c Graph::EdgeIt is defined.
840    /// \todo hmm
841    int edgeNum() const {
842      int i=0;
843      Edge e;
844      for (first(e); e!=INVALID; next(e)) ++i;
845      return i;
846    }
847
848    bool forward(const Edge& e) const { return !e.backward; }
849    bool backward(const Edge& e) const { return e.backward; }
850
851    template <typename T>
[1401]852    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
[992]853    /// _Graph::EdgeMap one for the forward edges and
854    /// one for the backward edges.
855    class EdgeMap {
856      template <typename TT> friend class EdgeMap;
857      typename _Graph::template EdgeMap<T> forward_map, backward_map;
858    public:
859      typedef T Value;
860      typedef Edge Key;
861
[1401]862      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
[992]863              ForwardFilterMap, BackwardFilterMap>& g) :
864        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
865
[1401]866      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
[992]867              ForwardFilterMap, BackwardFilterMap>& g, T a) :
868        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
869     
870      void set(Edge e, T a) {
871        if (!e.backward)
872          forward_map.set(e, a);
873        else
874          backward_map.set(e, a);
875      }
876
877//       typename _Graph::template EdgeMap<T>::ConstReference
878//       operator[](Edge e) const {
879//      if (!e.backward)
880//        return forward_map[e];
881//      else
882//        return backward_map[e];
883//       }
884
885//      typename _Graph::template EdgeMap<T>::Reference
[1016]886      T operator[](Edge e) const {
[992]887        if (!e.backward)
888          return forward_map[e];
889        else
890          return backward_map[e];
891      }
892
893      void update() {
894        forward_map.update();
895        backward_map.update();
896      }
897    };
898
899  };
[569]900
[650]901
[1401]902  ///\brief An adaptor for composing a subgraph of a
[792]903  /// bidirected graph made from a directed one.
[612]904  ///
[1401]905  /// An adaptor for composing a subgraph of a
[911]906  /// bidirected graph made from a directed one.
907  ///
[1401]908  ///\warning Graph adaptors are in even more experimental state than the other
[879]909  ///parts of the lib. Use them at you own risk.
910  ///
[923]911  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
912  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
913  /// reversing its orientation. We are given moreover two bool valued
914  /// maps on the edge-set,
915  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
[1401]916  /// SubBidirGraphAdaptor implements the graph structure with node-set
[923]917  /// \f$V\f$ and edge-set
918  /// \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]919  /// The purpose of writing + instead of union is because parallel
[923]920  /// edges can arise. (Similarly, antiparallel edges also can arise).
[792]921  /// In other words, a subgraph of the bidirected graph obtained, which
922  /// is given by orienting the edges of the original graph in both directions.
[923]923  /// As the oppositely directed edges are logically different,
924  /// the maps are able to attach different values for them.
925  ///
[1401]926  /// An example for such a construction is \c RevGraphAdaptor where the
[792]927  /// forward_filter is everywhere false and the backward_filter is
928  /// everywhere true. We note that for sake of efficiency,
[1401]929  /// \c RevGraphAdaptor is implemented in a different way.
930  /// But BidirGraphAdaptor is obtained from
931  /// SubBidirGraphAdaptor by considering everywhere true
[910]932  /// valued maps both for forward_filter and backward_filter.
[1252]933  ///
[1401]934  /// The most important application of SubBidirGraphAdaptor
935  /// is ResGraphAdaptor, which stands for the residual graph in directed
[792]936  /// flow and circulation problems.
[1401]937  /// As adaptors usually, the SubBidirGraphAdaptor implements the
[792]938  /// above mentioned graph structure without its physical storage,
[923]939  /// that is the whole stuff is stored in constant memory.
[992]940  template<typename _Graph,
[650]941           typename ForwardFilterMap, typename BackwardFilterMap>
[1401]942  class SubBidirGraphAdaptor :
[992]943    public IterableGraphExtender<
[1401]944    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
[650]945  public:
[992]946    typedef _Graph Graph;
947    typedef IterableGraphExtender<
[1401]948      SubBidirGraphAdaptorBase<
[992]949      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
[569]950  protected:
[1401]951    SubBidirGraphAdaptor() { }
[992]952  public:
[1401]953    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
[992]954                         BackwardFilterMap& _backward_filter) {
955      setGraph(_graph);
956      setForwardFilterMap(_forward_filter);
957      setBackwardFilterMap(_backward_filter);
958    }
959  };
[650]960
[569]961
[650]962
[1401]963  ///\brief An adaptor for composing bidirected graph from a directed one.
[650]964  ///
[1401]965  ///\warning Graph adaptors are in even more experimental state than the other
[879]966  ///parts of the lib. Use them at you own risk.
967  ///
[1401]968  /// An adaptor for composing bidirected graph from a directed one.
[650]969  /// A bidirected graph is composed over the directed one without physical
970  /// storage. As the oppositely directed edges are logically different ones
971  /// the maps are able to attach different values for them.
972  template<typename Graph>
[1401]973  class BidirGraphAdaptor :
974    public SubBidirGraphAdaptor<
[650]975    Graph,
976    ConstMap<typename Graph::Edge, bool>,
977    ConstMap<typename Graph::Edge, bool> > {
978  public:
[1401]979    typedef  SubBidirGraphAdaptor<
[650]980      Graph,
981      ConstMap<typename Graph::Edge, bool>,
982      ConstMap<typename Graph::Edge, bool> > Parent;
983  protected:
984    ConstMap<typename Graph::Edge, bool> cm;
985
[1401]986    BidirGraphAdaptor() : Parent(), cm(true) {
[655]987      Parent::setForwardFilterMap(cm);
988      Parent::setBackwardFilterMap(cm);
989    }
[650]990  public:
[1401]991    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
[650]992      Parent::setGraph(_graph);
993      Parent::setForwardFilterMap(cm);
994      Parent::setBackwardFilterMap(cm);
995    }
[738]996
997    int edgeNum() const {
998      return 2*this->graph->edgeNum();
999    }
[1401]1000    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
[650]1001  };
1002
1003
1004  template<typename Graph, typename Number,
1005           typename CapacityMap, typename FlowMap>
[658]1006  class ResForwardFilter {
1007    //    const Graph* graph;
[650]1008    const CapacityMap* capacity;
1009    const FlowMap* flow;
1010  public:
[658]1011    ResForwardFilter(/*const Graph& _graph, */
1012                     const CapacityMap& _capacity, const FlowMap& _flow) :
1013      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1014    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
[656]1015    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1016    void setFlow(const FlowMap& _flow) { flow=&_flow; }
[650]1017    bool operator[](const typename Graph::Edge& e) const {
[738]1018      return (Number((*flow)[e]) < Number((*capacity)[e]));
[650]1019    }
1020  };
1021
1022  template<typename Graph, typename Number,
1023           typename CapacityMap, typename FlowMap>
[658]1024  class ResBackwardFilter {
[650]1025    const CapacityMap* capacity;
1026    const FlowMap* flow;
1027  public:
[658]1028    ResBackwardFilter(/*const Graph& _graph,*/
1029                      const CapacityMap& _capacity, const FlowMap& _flow) :
1030      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1031    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
[656]1032    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1033    void setFlow(const FlowMap& _flow) { flow=&_flow; }
[650]1034    bool operator[](const typename Graph::Edge& e) const {
[738]1035      return (Number(0) < Number((*flow)[e]));
[650]1036    }
1037  };
1038
[653]1039 
[1401]1040  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
[650]1041
[1401]1042  An adaptor for composing the residual graph for directed flow and circulation problems.
[1242]1043  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1044  number type. Let moreover
1045  \f$f,c:A\to F\f$, be functions on the edge-set.
[1401]1046  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
[1242]1047  and \f$c\f$ for a capacity function.   
1048  Suppose that a graph instange \c g of type
1049  \c ListGraph implements \f$G\f$.
1050  \code
1051  ListGraph g;
1052  \endcode
[1401]1053  Then RevGraphAdaptor implements the graph structure with node-set
[1242]1054  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1055  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1056  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1057  i.e. the so called residual graph.
1058  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1059  multilicities are counted, i.e. if an edge is in both
[1401]1060  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
[1242]1061  appears twice.
1062  The following code shows how
1063  such an instance can be constructed.
1064  \code
1065  typedef ListGraph Graph;
1066  Graph::EdgeMap<int> f(g);
1067  Graph::EdgeMap<int> c(g);
[1401]1068  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
[1242]1069  \endcode
1070  \author Marton Makai
1071  */
[650]1072  template<typename Graph, typename Number,
1073           typename CapacityMap, typename FlowMap>
[1401]1074  class ResGraphAdaptor :
1075    public SubBidirGraphAdaptor<
[650]1076    Graph,
[658]1077    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1078    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
[650]1079  public:
[1401]1080    typedef SubBidirGraphAdaptor<
[650]1081      Graph,
[658]1082      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1083      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
[650]1084  protected:
1085    const CapacityMap* capacity;
1086    FlowMap* flow;
[658]1087    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1088    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
[1401]1089    ResGraphAdaptor() : Parent(),
[658]1090                        capacity(0), flow(0) { }
1091    void setCapacityMap(const CapacityMap& _capacity) {
1092      capacity=&_capacity;
1093      forward_filter.setCapacity(_capacity);
1094      backward_filter.setCapacity(_capacity);
1095    }
1096    void setFlowMap(FlowMap& _flow) {
1097      flow=&_flow;
1098      forward_filter.setFlow(_flow);
1099      backward_filter.setFlow(_flow);
1100    }
[650]1101  public:
[1401]1102    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
[650]1103                       FlowMap& _flow) :
1104      Parent(), capacity(&_capacity), flow(&_flow),
[658]1105      forward_filter(/*_graph,*/ _capacity, _flow),
1106      backward_filter(/*_graph,*/ _capacity, _flow) {
[650]1107      Parent::setGraph(_graph);
1108      Parent::setForwardFilterMap(forward_filter);
1109      Parent::setBackwardFilterMap(backward_filter);
1110    }
1111
[660]1112    typedef typename Parent::Edge Edge;
1113
1114    void augment(const Edge& e, Number a) const {
[650]1115      if (Parent::forward(e)) 
1116        flow->set(e, (*flow)[e]+a);
1117      else 
1118        flow->set(e, (*flow)[e]-a);
1119    }
1120
[660]1121    /// \brief Residual capacity map.
1122    ///
[910]1123    /// In generic residual graphs the residual capacity can be obtained
1124    /// as a map.
[660]1125    class ResCap {
1126    protected:
[1401]1127      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
[660]1128    public:
[987]1129      typedef Number Value;
1130      typedef Edge Key;
[1401]1131      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
[888]1132             _res_graph) : res_graph(&_res_graph) { }
[660]1133      Number operator[](const Edge& e) const {
1134        if (res_graph->forward(e))
1135          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1136        else
1137          return (*(res_graph->flow))[e];
1138      }
1139    };
1140
[1401]1141    //    KEEP_MAPS(Parent, ResGraphAdaptor);
[650]1142  };
1143
1144
[998]1145
1146  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1147  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[998]1148  public:
1149    typedef _Graph Graph;
[1401]1150    typedef GraphAdaptorBase<_Graph> Parent;
[998]1151  protected:
1152    FirstOutEdgesMap* first_out_edges;
[1401]1153    ErasingFirstGraphAdaptorBase() : Parent(),
[998]1154                                     first_out_edges(0) { }
1155
1156    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1157      first_out_edges=&_first_out_edges;
1158    }
1159
1160  public:
1161
1162    typedef typename Parent::Node Node;
1163    typedef typename Parent::Edge Edge;
1164
1165    void firstOut(Edge& i, const Node& n) const {
1166      i=(*first_out_edges)[n];
1167    }
1168
1169    void erase(const Edge& e) const {
1170      Node n=source(e);
1171      Edge f=e;
1172      Parent::nextOut(f);
1173      first_out_edges->set(n, f);
1174    }   
1175  };
1176
1177
[612]1178  /// For blocking flows.
[556]1179
[1401]1180  ///\warning Graph adaptors are in even more experimental state than the other
[879]1181  ///parts of the lib. Use them at you own risk.
1182  ///
[1401]1183  /// This graph adaptor is used for on-the-fly
[792]1184  /// Dinits blocking flow computations.
[612]1185  /// For each node, an out-edge is stored which is used when the
1186  /// \code
1187  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1188  /// \endcode
1189  /// is called.
[556]1190  ///
[792]1191  /// \author Marton Makai
[998]1192  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1193  class ErasingFirstGraphAdaptor :
[998]1194    public IterableGraphExtender<
[1401]1195    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
[650]1196  public:
[998]1197    typedef _Graph Graph;
1198    typedef IterableGraphExtender<
[1401]1199      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1200    ErasingFirstGraphAdaptor(Graph& _graph,
[998]1201                             FirstOutEdgesMap& _first_out_edges) {
1202      setGraph(_graph);
1203      setFirstOutEdgesMap(_first_out_edges);
1204    }
[1019]1205
[998]1206  };
[556]1207
1208  ///@}
1209
[921]1210} //namespace lemon
[556]1211
[1401]1212#endif //LEMON_GRAPH_ADAPTOR_H
[556]1213
Note: See TracBrowser for help on using the repository browser.