COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_adaptor.h @ 1425:f3717c08e2be

Last change on this file since 1425:f3717c08e2be was 1425:f3717c08e2be, checked in by marci, 19 years ago

minor modifications

File size: 39.6 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
[1425]449  graph, which is read from the dimacs file \ref sub_graph_adaptor_demo.dim.
450  The full source code is available in \ref sub_graph_adaptor_demo.cc.
451  If you are interested in more demo programs, you can use
452  \ref dim_to_dot.cc to generate .dot files from dimacs files.
453  The .dot file of the following figure of was generated generated by 
454  the demo program \ref dim_to_dot.cc.
455
[933]456  \dot
457  digraph lemon_dot_example {
458  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
459  n0 [ label="0 (s)" ];
460  n1 [ label="1" ];
461  n2 [ label="2" ];
462  n3 [ label="3" ];
463  n4 [ label="4" ];
464  n5 [ label="5" ];
465  n6 [ label="6 (t)" ];
466  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
467  n5 ->  n6 [ label="9, length:4" ];
468  n4 ->  n6 [ label="8, length:2" ];
469  n3 ->  n5 [ label="7, length:1" ];
470  n2 ->  n5 [ label="6, length:3" ];
471  n2 ->  n6 [ label="5, length:5" ];
472  n2 ->  n4 [ label="4, length:2" ];
473  n1 ->  n4 [ label="3, length:3" ];
474  n0 ->  n3 [ label="2, length:1" ];
475  n0 ->  n2 [ label="1, length:2" ];
476  n0 ->  n1 [ label="0, length:3" ];
477  }
478  \enddot
479
480  \code
481  Graph g;
482  Node s, t;
483  LengthMap length(g);
484
485  readDimacs(std::cin, g, length, s, t);
486
[986]487  cout << "edges with lengths (of form id, source--length->target): " << endl;
[933]488  for(EdgeIt e(g); e!=INVALID; ++e)
[986]489    cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
490         << length[e] << "->" << g.id(g.target(e)) << endl;
[933]491
492  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
493  \endcode
494  Next, the potential function is computed with Dijkstra.
495  \code
496  typedef Dijkstra<Graph, LengthMap> Dijkstra;
497  Dijkstra dijkstra(g, length);
498  dijkstra.run(s);
499  \endcode
500  Next, we consrtruct a map which filters the edge-set to the tight edges.
501  \code
502  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
503    TightEdgeFilter;
504  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
505 
[1401]506  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
[933]507  SubGW gw(g, tight_edge_filter);
508  \endcode
509  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
510  with a max flow algorithm Preflow.
511  \code
512  ConstMap<Edge, int> const_1_map(1);
513  Graph::EdgeMap<int> flow(g, 0);
514
515  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
516    preflow(gw, s, t, const_1_map, flow);
517  preflow.run();
518  \endcode
519  Last, the output is:
520  \code 
521  cout << "maximum number of edge-disjoint shortest path: "
522       << preflow.flowValue() << endl;
523  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
524       << endl;
525  for(EdgeIt e(g); e!=INVALID; ++e)
526    if (flow[e])
[986]527      cout << " " << g.id(g.source(e)) << "--"
528           << length[e] << "->" << g.id(g.target(e)) << endl;
[933]529  \endcode
530  The program has the following (expected :-)) output:
531  \code
[986]532  edges with lengths (of form id, source--length->target):
[933]533   9, 5--4->6
534   8, 4--2->6
535   7, 3--1->5
536   6, 2--3->5
537   5, 2--5->6
538   4, 2--2->4
539   3, 1--3->4
540   2, 0--1->3
541   1, 0--2->2
542   0, 0--3->1
543  s: 0 t: 6
544  maximum number of edge-disjoint shortest path: 2
545  edges of the maximum number of edge-disjoint shortest s-t paths:
546   9, 5--4->6
547   8, 4--2->6
548   7, 3--1->5
549   4, 2--2->4
550   2, 0--1->3
551   1, 0--2->2
552  \endcode
553
[932]554  \author Marton Makai
555  */
556  template<typename Graph, typename EdgeFilterMap>
[1401]557  class EdgeSubGraphAdaptor :
558    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[932]559                           EdgeFilterMap> {
560  public:
[1401]561    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[932]562                            EdgeFilterMap> Parent;
563  protected:
564    ConstMap<typename Graph::Node, bool> const_true_map;
565  public:
[1401]566    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
[932]567      Parent(), const_true_map(true) {
568      Parent::setGraph(_graph);
569      Parent::setNodeFilterMap(const_true_map);
570      Parent::setEdgeFilterMap(_edge_filter_map);
571    }
572  };
573
[1383]574  template <typename _Graph>
[1401]575  class UndirGraphAdaptorBase :
576    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
[1383]577  public:
578    typedef _Graph Graph;
[1401]579    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
[1383]580  protected:
[1401]581    UndirGraphAdaptorBase() : Parent() { }
[1383]582  public:
583    typedef typename Parent::UndirEdge UndirEdge;
584    typedef typename Parent::Edge Edge;
585   
586    /// \bug Why cant an edge say that it is forward or not???
587    /// By this, a pointer to the graph have to be stored
588    /// The implementation
589    template <typename T>
590    class EdgeMap {
591    protected:
[1401]592      const UndirGraphAdaptorBase<_Graph>* g;
[1383]593      template <typename TT> friend class EdgeMap;
594      typename _Graph::template EdgeMap<T> forward_map, backward_map;
595    public:
596      typedef T Value;
597      typedef Edge Key;
598     
[1401]599      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
[1383]600        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
[569]601
[1401]602      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
[1383]603        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
604     
605      void set(Edge e, T a) {
606        if (g->forward(e))
607          forward_map.set(e, a);
608        else
609          backward_map.set(e, a);
610      }
[556]611
[1383]612      T operator[](Edge e) const {
613        if (g->forward(e))
614          return forward_map[e];
615        else
616          return backward_map[e];
[556]617      }
618    };
[1383]619       
620    template <typename T>
621    class UndirEdgeMap {
622      template <typename TT> friend class UndirEdgeMap;
623      typename _Graph::template EdgeMap<T> map;
624    public:
625      typedef T Value;
626      typedef UndirEdge Key;
627     
[1401]628      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
[1383]629        map(*(g.graph)) { }
[556]630
[1401]631      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
[1383]632        map(*(g.graph), a) { }
633     
634      void set(UndirEdge e, T a) {
635        map.set(e, a);
636      }
[556]637
[1383]638      T operator[](UndirEdge e) const {
639        return map[e];
640      }
641    };
642     
643  };
644
[1401]645  /// \brief An undirected graph is made from a directed graph by an adaptor
[1383]646  ///
647  /// Undocumented, untested!!!
648  /// If somebody knows nice demo application, let's polulate it.
649  ///
650  /// \author Marton Makai
651  template<typename _Graph>
[1401]652  class UndirGraphAdaptor :
[1383]653    public IterableUndirGraphExtender<
[1401]654    UndirGraphAdaptorBase<_Graph> > {
[1383]655  public:
656    typedef _Graph Graph;
657    typedef IterableUndirGraphExtender<
[1401]658      UndirGraphAdaptorBase<_Graph> > Parent;
[1383]659  protected:
[1401]660    UndirGraphAdaptor() { }
[1383]661  public:
[1401]662    UndirGraphAdaptor(_Graph& _graph) {
[1383]663      setGraph(_graph);
[556]664    }
665  };
666
[992]667 
668  template <typename _Graph,
669            typename ForwardFilterMap, typename BackwardFilterMap>
[1401]670  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[992]671  public:
672    typedef _Graph Graph;
[1401]673    typedef GraphAdaptorBase<_Graph> Parent;
[992]674  protected:
675    ForwardFilterMap* forward_filter;
676    BackwardFilterMap* backward_filter;
[1401]677    SubBidirGraphAdaptorBase() : Parent(),
[992]678                                 forward_filter(0), backward_filter(0) { }
679
680    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
681      forward_filter=&_forward_filter;
682    }
683    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
684      backward_filter=&_backward_filter;
685    }
686
687  public:
[1401]688//     SubGraphAdaptorBase(Graph& _graph,
[992]689//                      NodeFilterMap& _node_filter_map,
690//                      EdgeFilterMap& _edge_filter_map) :
691//       Parent(&_graph),
692//       node_filter_map(&node_filter_map),
693//       edge_filter_map(&edge_filter_map) { }
694
695    typedef typename Parent::Node Node;
696    typedef typename _Graph::Edge GraphEdge;
697    template <typename T> class EdgeMap;
[1401]698    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
[992]699    /// _Graph::Edge. It contains an extra bool flag which is true
700    /// if and only if the
701    /// edge is the backward version of the original edge.
702    class Edge : public _Graph::Edge {
[1401]703      friend class SubBidirGraphAdaptorBase<
[992]704        Graph, ForwardFilterMap, BackwardFilterMap>;
705      template<typename T> friend class EdgeMap;
706    protected:
707      bool backward; //true, iff backward
708    public:
709      Edge() { }
710      /// \todo =false is needed, or causes problems?
711      /// If \c _backward is false, then we get an edge corresponding to the
712      /// original one, otherwise its oppositely directed pair is obtained.
713      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
714        _Graph::Edge(e), backward(_backward) { }
715      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
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      bool operator!=(const Edge& v) const {
722        return (this->backward!=v.backward ||
723                static_cast<typename _Graph::Edge>(*this)!=
724                static_cast<typename _Graph::Edge>(v));
725      }
726    };
727
728    void first(Node& i) const {
729      Parent::first(i);
730    }
731
732    void first(Edge& i) const {
733      Parent::first(i);
734      i.backward=false;
735      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
736             !(*forward_filter)[i]) Parent::next(i);
737      if (*static_cast<GraphEdge*>(&i)==INVALID) {
738        Parent::first(i);
739        i.backward=true;
740        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
741               !(*backward_filter)[i]) Parent::next(i);
742      }
743    }
744
745    void firstIn(Edge& i, const Node& n) const {
746      Parent::firstIn(i, n);
747      i.backward=false;
748      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
[1269]749             !(*forward_filter)[i]) Parent::nextIn(i);
[992]750      if (*static_cast<GraphEdge*>(&i)==INVALID) {
751        Parent::firstOut(i, n);
752        i.backward=true;
753        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
754               !(*backward_filter)[i]) Parent::nextOut(i);
755      }
756    }
757
758    void firstOut(Edge& i, const Node& n) const {
759      Parent::firstOut(i, n);
760      i.backward=false;
761      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
762             !(*forward_filter)[i]) Parent::nextOut(i);
763      if (*static_cast<GraphEdge*>(&i)==INVALID) {
764        Parent::firstIn(i, n);
765        i.backward=true;
766        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
767               !(*backward_filter)[i]) Parent::nextIn(i);
768      }
769    }
770
771    void next(Node& i) const {
772      Parent::next(i);
773    }
774
775    void next(Edge& i) const {
776      if (!(i.backward)) {
777        Parent::next(i);
778        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
779               !(*forward_filter)[i]) Parent::next(i);
780        if (*static_cast<GraphEdge*>(&i)==INVALID) {
781          Parent::first(i);
782          i.backward=true;
783          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
784                 !(*backward_filter)[i]) Parent::next(i);
785        }
786      } else {
787        Parent::next(i);
788        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
789               !(*backward_filter)[i]) Parent::next(i);
790      }
791    }
792
793    void nextIn(Edge& i) const {
794      if (!(i.backward)) {
795        Node n=Parent::target(i);
796        Parent::nextIn(i);
797        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
798               !(*forward_filter)[i]) Parent::nextIn(i);
799        if (*static_cast<GraphEdge*>(&i)==INVALID) {
800          Parent::firstOut(i, n);
801          i.backward=true;
802          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
803                 !(*backward_filter)[i]) Parent::nextOut(i);
804        }
805      } else {
806        Parent::nextOut(i);
807        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
808               !(*backward_filter)[i]) Parent::nextOut(i);
809      }
810    }
811
812    void nextOut(Edge& i) const {
813      if (!(i.backward)) {
814        Node n=Parent::source(i);
815        Parent::nextOut(i);
816        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
817               !(*forward_filter)[i]) Parent::nextOut(i);
818        if (*static_cast<GraphEdge*>(&i)==INVALID) {
819          Parent::firstIn(i, n);
820          i.backward=true;
821          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
822                 !(*backward_filter)[i]) Parent::nextIn(i);
823        }
824      } else {
825        Parent::nextIn(i);
826        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
827               !(*backward_filter)[i]) Parent::nextIn(i);
828      }
829    }
830
831    Node source(Edge e) const {
832      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
833    Node target(Edge e) const {
834      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
835
836    /// Gives back the opposite edge.
837    Edge opposite(const Edge& e) const {
838      Edge f=e;
839      f.backward=!f.backward;
840      return f;
841    }
842
843    /// \warning This is a linear time operation and works only if
844    /// \c Graph::EdgeIt is defined.
845    /// \todo hmm
846    int edgeNum() const {
847      int i=0;
848      Edge e;
849      for (first(e); e!=INVALID; next(e)) ++i;
850      return i;
851    }
852
853    bool forward(const Edge& e) const { return !e.backward; }
854    bool backward(const Edge& e) const { return e.backward; }
855
856    template <typename T>
[1401]857    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
[992]858    /// _Graph::EdgeMap one for the forward edges and
859    /// one for the backward edges.
860    class EdgeMap {
861      template <typename TT> friend class EdgeMap;
862      typename _Graph::template EdgeMap<T> forward_map, backward_map;
863    public:
864      typedef T Value;
865      typedef Edge Key;
866
[1401]867      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
[992]868              ForwardFilterMap, BackwardFilterMap>& g) :
869        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
870
[1401]871      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
[992]872              ForwardFilterMap, BackwardFilterMap>& g, T a) :
873        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
874     
875      void set(Edge e, T a) {
876        if (!e.backward)
877          forward_map.set(e, a);
878        else
879          backward_map.set(e, a);
880      }
881
882//       typename _Graph::template EdgeMap<T>::ConstReference
883//       operator[](Edge e) const {
884//      if (!e.backward)
885//        return forward_map[e];
886//      else
887//        return backward_map[e];
888//       }
889
890//      typename _Graph::template EdgeMap<T>::Reference
[1016]891      T operator[](Edge e) const {
[992]892        if (!e.backward)
893          return forward_map[e];
894        else
895          return backward_map[e];
896      }
897
898      void update() {
899        forward_map.update();
900        backward_map.update();
901      }
902    };
903
904  };
[569]905
[650]906
[1401]907  ///\brief An adaptor for composing a subgraph of a
[792]908  /// bidirected graph made from a directed one.
[612]909  ///
[1401]910  /// An adaptor for composing a subgraph of a
[911]911  /// bidirected graph made from a directed one.
912  ///
[1401]913  ///\warning Graph adaptors are in even more experimental state than the other
[879]914  ///parts of the lib. Use them at you own risk.
915  ///
[923]916  /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
917  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
918  /// reversing its orientation. We are given moreover two bool valued
919  /// maps on the edge-set,
920  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
[1401]921  /// SubBidirGraphAdaptor implements the graph structure with node-set
[923]922  /// \f$V\f$ and edge-set
923  /// \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]924  /// The purpose of writing + instead of union is because parallel
[923]925  /// edges can arise. (Similarly, antiparallel edges also can arise).
[792]926  /// In other words, a subgraph of the bidirected graph obtained, which
927  /// is given by orienting the edges of the original graph in both directions.
[923]928  /// As the oppositely directed edges are logically different,
929  /// the maps are able to attach different values for them.
930  ///
[1401]931  /// An example for such a construction is \c RevGraphAdaptor where the
[792]932  /// forward_filter is everywhere false and the backward_filter is
933  /// everywhere true. We note that for sake of efficiency,
[1401]934  /// \c RevGraphAdaptor is implemented in a different way.
935  /// But BidirGraphAdaptor is obtained from
936  /// SubBidirGraphAdaptor by considering everywhere true
[910]937  /// valued maps both for forward_filter and backward_filter.
[1252]938  ///
[1401]939  /// The most important application of SubBidirGraphAdaptor
940  /// is ResGraphAdaptor, which stands for the residual graph in directed
[792]941  /// flow and circulation problems.
[1401]942  /// As adaptors usually, the SubBidirGraphAdaptor implements the
[792]943  /// above mentioned graph structure without its physical storage,
[923]944  /// that is the whole stuff is stored in constant memory.
[992]945  template<typename _Graph,
[650]946           typename ForwardFilterMap, typename BackwardFilterMap>
[1401]947  class SubBidirGraphAdaptor :
[992]948    public IterableGraphExtender<
[1401]949    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
[650]950  public:
[992]951    typedef _Graph Graph;
952    typedef IterableGraphExtender<
[1401]953      SubBidirGraphAdaptorBase<
[992]954      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
[569]955  protected:
[1401]956    SubBidirGraphAdaptor() { }
[992]957  public:
[1401]958    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
[992]959                         BackwardFilterMap& _backward_filter) {
960      setGraph(_graph);
961      setForwardFilterMap(_forward_filter);
962      setBackwardFilterMap(_backward_filter);
963    }
964  };
[650]965
[569]966
[650]967
[1401]968  ///\brief An adaptor for composing bidirected graph from a directed one.
[650]969  ///
[1401]970  ///\warning Graph adaptors are in even more experimental state than the other
[879]971  ///parts of the lib. Use them at you own risk.
972  ///
[1401]973  /// An adaptor for composing bidirected graph from a directed one.
[650]974  /// A bidirected graph is composed over the directed one without physical
975  /// storage. As the oppositely directed edges are logically different ones
976  /// the maps are able to attach different values for them.
977  template<typename Graph>
[1401]978  class BidirGraphAdaptor :
979    public SubBidirGraphAdaptor<
[650]980    Graph,
981    ConstMap<typename Graph::Edge, bool>,
982    ConstMap<typename Graph::Edge, bool> > {
983  public:
[1401]984    typedef  SubBidirGraphAdaptor<
[650]985      Graph,
986      ConstMap<typename Graph::Edge, bool>,
987      ConstMap<typename Graph::Edge, bool> > Parent;
988  protected:
989    ConstMap<typename Graph::Edge, bool> cm;
990
[1401]991    BidirGraphAdaptor() : Parent(), cm(true) {
[655]992      Parent::setForwardFilterMap(cm);
993      Parent::setBackwardFilterMap(cm);
994    }
[650]995  public:
[1401]996    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
[650]997      Parent::setGraph(_graph);
998      Parent::setForwardFilterMap(cm);
999      Parent::setBackwardFilterMap(cm);
1000    }
[738]1001
1002    int edgeNum() const {
1003      return 2*this->graph->edgeNum();
1004    }
[1401]1005    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
[650]1006  };
1007
1008
1009  template<typename Graph, typename Number,
1010           typename CapacityMap, typename FlowMap>
[658]1011  class ResForwardFilter {
1012    //    const Graph* graph;
[650]1013    const CapacityMap* capacity;
1014    const FlowMap* flow;
1015  public:
[658]1016    ResForwardFilter(/*const Graph& _graph, */
1017                     const CapacityMap& _capacity, const FlowMap& _flow) :
1018      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1019    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
[656]1020    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1021    void setFlow(const FlowMap& _flow) { flow=&_flow; }
[650]1022    bool operator[](const typename Graph::Edge& e) const {
[738]1023      return (Number((*flow)[e]) < Number((*capacity)[e]));
[650]1024    }
1025  };
1026
1027  template<typename Graph, typename Number,
1028           typename CapacityMap, typename FlowMap>
[658]1029  class ResBackwardFilter {
[650]1030    const CapacityMap* capacity;
1031    const FlowMap* flow;
1032  public:
[658]1033    ResBackwardFilter(/*const Graph& _graph,*/
1034                      const CapacityMap& _capacity, const FlowMap& _flow) :
1035      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1036    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
[656]1037    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1038    void setFlow(const FlowMap& _flow) { flow=&_flow; }
[650]1039    bool operator[](const typename Graph::Edge& e) const {
[738]1040      return (Number(0) < Number((*flow)[e]));
[650]1041    }
1042  };
1043
[653]1044 
[1401]1045  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
[650]1046
[1401]1047  An adaptor for composing the residual graph for directed flow and circulation problems.
[1242]1048  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1049  number type. Let moreover
1050  \f$f,c:A\to F\f$, be functions on the edge-set.
[1401]1051  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
[1242]1052  and \f$c\f$ for a capacity function.   
1053  Suppose that a graph instange \c g of type
1054  \c ListGraph implements \f$G\f$.
1055  \code
1056  ListGraph g;
1057  \endcode
[1401]1058  Then RevGraphAdaptor implements the graph structure with node-set
[1242]1059  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1060  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1061  \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1062  i.e. the so called residual graph.
1063  When we take the union \f$A_{forward}\cup A_{backward}\f$,
1064  multilicities are counted, i.e. if an edge is in both
[1401]1065  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
[1242]1066  appears twice.
1067  The following code shows how
1068  such an instance can be constructed.
1069  \code
1070  typedef ListGraph Graph;
1071  Graph::EdgeMap<int> f(g);
1072  Graph::EdgeMap<int> c(g);
[1401]1073  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
[1242]1074  \endcode
1075  \author Marton Makai
1076  */
[650]1077  template<typename Graph, typename Number,
1078           typename CapacityMap, typename FlowMap>
[1401]1079  class ResGraphAdaptor :
1080    public SubBidirGraphAdaptor<
[650]1081    Graph,
[658]1082    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1083    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
[650]1084  public:
[1401]1085    typedef SubBidirGraphAdaptor<
[650]1086      Graph,
[658]1087      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
1088      ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
[650]1089  protected:
1090    const CapacityMap* capacity;
1091    FlowMap* flow;
[658]1092    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1093    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
[1401]1094    ResGraphAdaptor() : Parent(),
[658]1095                        capacity(0), flow(0) { }
1096    void setCapacityMap(const CapacityMap& _capacity) {
1097      capacity=&_capacity;
1098      forward_filter.setCapacity(_capacity);
1099      backward_filter.setCapacity(_capacity);
1100    }
1101    void setFlowMap(FlowMap& _flow) {
1102      flow=&_flow;
1103      forward_filter.setFlow(_flow);
1104      backward_filter.setFlow(_flow);
1105    }
[650]1106  public:
[1401]1107    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
[650]1108                       FlowMap& _flow) :
1109      Parent(), capacity(&_capacity), flow(&_flow),
[658]1110      forward_filter(/*_graph,*/ _capacity, _flow),
1111      backward_filter(/*_graph,*/ _capacity, _flow) {
[650]1112      Parent::setGraph(_graph);
1113      Parent::setForwardFilterMap(forward_filter);
1114      Parent::setBackwardFilterMap(backward_filter);
1115    }
1116
[660]1117    typedef typename Parent::Edge Edge;
1118
1119    void augment(const Edge& e, Number a) const {
[650]1120      if (Parent::forward(e)) 
1121        flow->set(e, (*flow)[e]+a);
1122      else 
1123        flow->set(e, (*flow)[e]-a);
1124    }
1125
[660]1126    /// \brief Residual capacity map.
1127    ///
[910]1128    /// In generic residual graphs the residual capacity can be obtained
1129    /// as a map.
[660]1130    class ResCap {
1131    protected:
[1401]1132      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
[660]1133    public:
[987]1134      typedef Number Value;
1135      typedef Edge Key;
[1401]1136      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
[888]1137             _res_graph) : res_graph(&_res_graph) { }
[660]1138      Number operator[](const Edge& e) const {
1139        if (res_graph->forward(e))
1140          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1141        else
1142          return (*(res_graph->flow))[e];
1143      }
1144    };
1145
[1401]1146    //    KEEP_MAPS(Parent, ResGraphAdaptor);
[650]1147  };
1148
1149
[998]1150
1151  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1152  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[998]1153  public:
1154    typedef _Graph Graph;
[1401]1155    typedef GraphAdaptorBase<_Graph> Parent;
[998]1156  protected:
1157    FirstOutEdgesMap* first_out_edges;
[1401]1158    ErasingFirstGraphAdaptorBase() : Parent(),
[998]1159                                     first_out_edges(0) { }
1160
1161    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1162      first_out_edges=&_first_out_edges;
1163    }
1164
1165  public:
1166
1167    typedef typename Parent::Node Node;
1168    typedef typename Parent::Edge Edge;
1169
1170    void firstOut(Edge& i, const Node& n) const {
1171      i=(*first_out_edges)[n];
1172    }
1173
1174    void erase(const Edge& e) const {
1175      Node n=source(e);
1176      Edge f=e;
1177      Parent::nextOut(f);
1178      first_out_edges->set(n, f);
1179    }   
1180  };
1181
1182
[612]1183  /// For blocking flows.
[556]1184
[1401]1185  ///\warning Graph adaptors are in even more experimental state than the other
[879]1186  ///parts of the lib. Use them at you own risk.
1187  ///
[1401]1188  /// This graph adaptor is used for on-the-fly
[792]1189  /// Dinits blocking flow computations.
[612]1190  /// For each node, an out-edge is stored which is used when the
1191  /// \code
1192  /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1193  /// \endcode
1194  /// is called.
[556]1195  ///
[792]1196  /// \author Marton Makai
[998]1197  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1198  class ErasingFirstGraphAdaptor :
[998]1199    public IterableGraphExtender<
[1401]1200    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
[650]1201  public:
[998]1202    typedef _Graph Graph;
1203    typedef IterableGraphExtender<
[1401]1204      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1205    ErasingFirstGraphAdaptor(Graph& _graph,
[998]1206                             FirstOutEdgesMap& _first_out_edges) {
1207      setGraph(_graph);
1208      setFirstOutEdgesMap(_first_out_edges);
1209    }
[1019]1210
[998]1211  };
[556]1212
1213  ///@}
1214
[921]1215} //namespace lemon
[556]1216
[1401]1217#endif //LEMON_GRAPH_ADAPTOR_H
[556]1218
Note: See TracBrowser for help on using the repository browser.