COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 1946:17eb3eaad9f8

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