COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2340:03c71d754990

Last change on this file since 2340:03c71d754990 was 2340:03c71d754990, checked in by Balazs Dezso, 13 years ago

Make Hao-Orlin epsilon-safe

File size: 81.1 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
[1401]19#ifndef LEMON_GRAPH_ADAPTOR_H
20#define LEMON_GRAPH_ADAPTOR_H
[556]21
[2037]22///\ingroup graph_adaptors
23///\file
24///\brief Several graph adaptors.
[556]25///
[2037]26///This file contains several useful graph adaptor functions.
[556]27///
[2037]28///\author Marton Makai and Balazs Dezso
[556]29
[1993]30#include <lemon/bits/invalid.h>
[2177]31#include <lemon/bits/variant.h>
[921]32#include <lemon/maps.h>
[1979]33
[1999]34#include <lemon/bits/base_extender.h>
[1979]35#include <lemon/bits/graph_adaptor_extender.h>
[1791]36#include <lemon/bits/graph_extender.h>
[1979]37
[2034]38#include <lemon/tolerance.h>
39
[2079]40#include <algorithm>
[556]41
[921]42namespace lemon {
[556]43
[1951]44  ///\brief Base type for the Graph Adaptors
45  ///
46  ///Base type for the Graph Adaptors
47  ///
48  ///This is the base type for most of LEMON graph adaptors.
49  ///This class implements a trivial graph adaptor i.e. it only wraps the
50  ///functions and types of the graph. The purpose of this class is to
51  ///make easier implementing graph adaptors. E.g. if an adaptor is
52  ///considered which differs from the wrapped graph only in some of its
53  ///functions or types, then it can be derived from GraphAdaptor,
54  ///and only the
55  ///differences should be implemented.
56  ///
57  ///author Marton Makai
[970]58  template<typename _Graph>
[1401]59  class GraphAdaptorBase {
[970]60  public:
61    typedef _Graph Graph;
[2031]62    typedef GraphAdaptorBase Adaptor;
[970]63    typedef Graph ParentGraph;
64
[556]65  protected:
66    Graph* graph;
[1401]67    GraphAdaptorBase() : graph(0) { }
[556]68    void setGraph(Graph& _graph) { graph=&_graph; }
69
70  public:
[1401]71    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
[2034]72
[774]73    typedef typename Graph::Node Node;
74    typedef typename Graph::Edge Edge;
[556]75   
[970]76    void first(Node& i) const { graph->first(i); }
77    void first(Edge& i) const { graph->first(i); }
78    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
79    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
[556]80
[970]81    void next(Node& i) const { graph->next(i); }
82    void next(Edge& i) const { graph->next(i); }
83    void nextIn(Edge& i) const { graph->nextIn(i); }
84    void nextOut(Edge& i) const { graph->nextOut(i); }
85
[986]86    Node source(const Edge& e) const { return graph->source(e); }
87    Node target(const Edge& e) const { return graph->target(e); }
[556]88
[1697]89    typedef NodeNumTagIndicator<Graph> NodeNumTag;
[556]90    int nodeNum() const { return graph->nodeNum(); }
[1697]91   
92    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
[556]93    int edgeNum() const { return graph->edgeNum(); }
[1697]94
95    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
96    Edge findEdge(const Node& source, const Node& target,
97                  const Edge& prev = INVALID) {
98      return graph->findEdge(source, target, prev);
99    }
[556]100 
[1697]101    Node addNode() const {
102      return Node(graph->addNode());
103    }
104
[986]105    Edge addEdge(const Node& source, const Node& target) const {
[1697]106      return Edge(graph->addEdge(source, target));
107    }
[556]108
109    void erase(const Node& i) const { graph->erase(i); }
110    void erase(const Edge& i) const { graph->erase(i); }
111 
112    void clear() const { graph->clear(); }
113   
[739]114    int id(const Node& v) const { return graph->id(v); }
115    int id(const Edge& e) const { return graph->id(e); }
[1991]116
[2031]117    Node fromNodeId(int id) const {
118      return graph->fromNodeId(id);
119    }
120
121    Edge fromEdgeId(int id) const {
122      return graph->fromEdgeId(id);
123    }
124
[1991]125    int maxNodeId() const {
126      return graph->maxNodeId();
127    }
128
129    int maxEdgeId() const {
130      return graph->maxEdgeId();
131    }
132
133    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
134
135    NodeNotifier& getNotifier(Node) const {
136      return graph->getNotifier(Node());
137    }
138
139    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
140
141    EdgeNotifier& getNotifier(Edge) const {
142      return graph->getNotifier(Edge());
143    }
[650]144   
[970]145    template <typename _Value>
[2031]146    class NodeMap : public Graph::template NodeMap<_Value> {
[970]147    public:
[2031]148
149      typedef typename Graph::template NodeMap<_Value> Parent;
150
151      explicit NodeMap(const Adaptor& ga)
152        : Parent(*ga.graph) {}
153
154      NodeMap(const Adaptor& ga, const _Value& value)
[1991]155        : Parent(*ga.graph, value) { }
[2031]156
157      NodeMap& operator=(const NodeMap& cmap) {
158        return operator=<NodeMap>(cmap);
159      }
160
161      template <typename CMap>
162      NodeMap& operator=(const CMap& cmap) {
163        Parent::operator=(cmap);
164        return *this;
165      }
166     
[970]167    };
[556]168
[970]169    template <typename _Value>
[2031]170    class EdgeMap : public Graph::template EdgeMap<_Value> {
[970]171    public:
[2031]172     
173      typedef typename Graph::template EdgeMap<_Value> Parent;
174     
175      explicit EdgeMap(const Adaptor& ga)
176        : Parent(*ga.graph) {}
177
178      EdgeMap(const Adaptor& ga, const _Value& value)
179        : Parent(*ga.graph, value) {}
180
181      EdgeMap& operator=(const EdgeMap& cmap) {
182        return operator=<EdgeMap>(cmap);
183      }
184
185      template <typename CMap>
186      EdgeMap& operator=(const CMap& cmap) {
187        Parent::operator=(cmap);
188        return *this;
189      }
190
[970]191    };
[877]192
[556]193  };
194
[2081]195  ///\ingroup graph_adaptors
196  ///
197  ///\brief Trivial Graph Adaptor
198  ///
199  /// This class is an adaptor which does not change the adapted graph.
200  /// It can be used only to test the graph adaptors.
[970]201  template <typename _Graph>
[1401]202  class GraphAdaptor :
[1979]203    public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
[970]204  public:
205    typedef _Graph Graph;
[1979]206    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
[970]207  protected:
[1401]208    GraphAdaptor() : Parent() { }
[569]209
[970]210  public:
[1755]211    explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
[970]212  };
[569]213
[1991]214  /// \brief Just gives back a graph adaptor
215  ///
216  /// Just gives back a graph adaptor which
217  /// should be provide original graph
218  template<typename Graph>
219  GraphAdaptor<const Graph>
220  graphAdaptor(const Graph& graph) {
221    return GraphAdaptor<const Graph>(graph);
222  }
223
224
[997]225  template <typename _Graph>
[1401]226  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[997]227  public:
228    typedef _Graph Graph;
[1401]229    typedef GraphAdaptorBase<_Graph> Parent;
[997]230  protected:
[1401]231    RevGraphAdaptorBase() : Parent() { }
[997]232  public:
233    typedef typename Parent::Node Node;
234    typedef typename Parent::Edge Edge;
235
236    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
237    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
238
239    void nextIn(Edge& i) const { Parent::nextOut(i); }
240    void nextOut(Edge& i) const { Parent::nextIn(i); }
241
242    Node source(const Edge& e) const { return Parent::target(e); }
243    Node target(const Edge& e) const { return Parent::source(e); }
[1991]244
245    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
246    Edge findEdge(const Node& source, const Node& target,
247                  const Edge& prev = INVALID) {
248      return Parent::findEdge(target, source, prev);
249    }
250
[997]251  };
252   
253
[2081]254  ///\ingroup graph_adaptors
255  ///
[1949]256  ///\brief A graph adaptor which reverses the orientation of the edges.
257  ///
258  /// If \c g is defined as
[1946]259  ///\code
[923]260  /// ListGraph g;
[1946]261  ///\endcode
[1949]262  /// then
[1946]263  ///\code
[1991]264  /// RevGraphAdaptor<ListGraph> ga(g);
[1946]265  ///\endcode
[2079]266  /// implements the graph obtained from \c g by
[1949]267  /// reversing the orientation of its edges.
[2084]268  ///
269  /// A good example of using RevGraphAdaptor is to decide that the
270  /// directed graph is wheter strongly connected or not. If from one
271  /// node each node is reachable and from each node is reachable this
272  /// node then and just then the graph is strongly connected. Instead of
273  /// this condition we use a little bit different. From one node each node
274  /// ahould be reachable in the graph and in the reversed graph. Now this
275  /// condition can be checked with the Dfs algorithm class and the
276  /// RevGraphAdaptor algorithm class.
277  ///
278  /// And look at the code:
279  ///
280  ///\code
281  /// bool stronglyConnected(const Graph& graph) {
282  ///   if (NodeIt(graph) == INVALID) return true;
283  ///   Dfs<Graph> dfs(graph);
284  ///   dfs.run(NodeIt(graph));
285  ///   for (NodeIt it(graph); it != INVALID; ++it) {
286  ///     if (!dfs.reached(it)) {
287  ///       return false;
288  ///     }
289  ///   }
290  ///   typedef RevGraphAdaptor<const Graph> RGraph;
291  ///   RGraph rgraph(graph);
292  ///   DfsVisit<RGraph> rdfs(rgraph);
293  ///   rdfs.run(NodeIt(graph));
294  ///   for (NodeIt it(graph); it != INVALID; ++it) {
295  ///     if (!rdfs.reached(it)) {
296  ///       return false;
297  ///     }
298  ///   }
299  ///   return true;
300  /// }
301  ///\endcode
[997]302  template<typename _Graph>
[1401]303  class RevGraphAdaptor :
[1979]304    public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
[650]305  public:
[997]306    typedef _Graph Graph;
[1979]307    typedef GraphAdaptorExtender<
[1401]308      RevGraphAdaptorBase<_Graph> > Parent;
[556]309  protected:
[1401]310    RevGraphAdaptor() { }
[556]311  public:
[1755]312    explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
[997]313  };
[556]314
[1991]315  /// \brief Just gives back a reverse graph adaptor
316  ///
317  /// Just gives back a reverse graph adaptor
318  template<typename Graph>
319  RevGraphAdaptor<const Graph>
320  revGraphAdaptor(const Graph& graph) {
321    return RevGraphAdaptor<const Graph>(graph);
322  }
323
[1681]324  template <typename _Graph, typename NodeFilterMap,
325            typename EdgeFilterMap, bool checked = true>
[1401]326  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[992]327  public:
328    typedef _Graph Graph;
[2031]329    typedef SubGraphAdaptorBase Adaptor;
[1401]330    typedef GraphAdaptorBase<_Graph> Parent;
[992]331  protected:
332    NodeFilterMap* node_filter_map;
333    EdgeFilterMap* edge_filter_map;
[1401]334    SubGraphAdaptorBase() : Parent(),
[992]335                            node_filter_map(0), edge_filter_map(0) { }
[775]336
[992]337    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
338      node_filter_map=&_node_filter_map;
339    }
340    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
341      edge_filter_map=&_edge_filter_map;
342    }
343
344  public:
345
346    typedef typename Parent::Node Node;
347    typedef typename Parent::Edge Edge;
348
349    void first(Node& i) const {
350      Parent::first(i);
351      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
352    }
[1681]353
354    void first(Edge& i) const {
355      Parent::first(i);
356      while (i!=INVALID && (!(*edge_filter_map)[i]
357             || !(*node_filter_map)[Parent::source(i)]
358             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
359    }
360
361    void firstIn(Edge& i, const Node& n) const {
362      Parent::firstIn(i, n);
363      while (i!=INVALID && (!(*edge_filter_map)[i]
364             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
365    }
366
367    void firstOut(Edge& i, const Node& n) const {
368      Parent::firstOut(i, n);
369      while (i!=INVALID && (!(*edge_filter_map)[i]
370             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
371    }
372
373    void next(Node& i) const {
374      Parent::next(i);
375      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
376    }
377
378    void next(Edge& i) const {
379      Parent::next(i);
380      while (i!=INVALID && (!(*edge_filter_map)[i]
381             || !(*node_filter_map)[Parent::source(i)]
382             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
383    }
384
385    void nextIn(Edge& i) const {
386      Parent::nextIn(i);
387      while (i!=INVALID && (!(*edge_filter_map)[i]
388             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
389    }
390
391    void nextOut(Edge& i) const {
392      Parent::nextOut(i);
393      while (i!=INVALID && (!(*edge_filter_map)[i]
394             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
395    }
396
[1951]397    ///\e
[1949]398
[1951]399    /// This function hides \c n in the graph, i.e. the iteration
400    /// jumps over it. This is done by simply setting the value of \c n 
401    /// to be false in the corresponding node-map.
[1681]402    void hide(const Node& n) const { node_filter_map->set(n, false); }
403
[1951]404    ///\e
[1949]405
[1951]406    /// This function hides \c e in the graph, i.e. the iteration
407    /// jumps over it. This is done by simply setting the value of \c e 
408    /// to be false in the corresponding edge-map.
[1681]409    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
410
[1951]411    ///\e
[1949]412
[1951]413    /// The value of \c n is set to be true in the node-map which stores
414    /// hide information. If \c n was hidden previuosly, then it is shown
415    /// again
[1681]416     void unHide(const Node& n) const { node_filter_map->set(n, true); }
417
[1951]418    ///\e
[1949]419
[1951]420    /// The value of \c e is set to be true in the edge-map which stores
421    /// hide information. If \c e was hidden previuosly, then it is shown
422    /// again
[1681]423    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
424
[1951]425    /// Returns true if \c n is hidden.
[1949]426   
[1951]427    ///\e
428    ///
[1681]429    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
430
[1951]431    /// Returns true if \c n is hidden.
[1949]432   
[1951]433    ///\e
434    ///
[1681]435    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
436
[1697]437    typedef False NodeNumTag;
438    typedef False EdgeNumTag;
[1991]439
440    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
441    Edge findEdge(const Node& source, const Node& target,
442                  const Edge& prev = INVALID) {
443      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
444        return INVALID;
445      }
446      Edge edge = Parent::findEdge(source, target, prev);
447      while (edge != INVALID && !(*edge_filter_map)[edge]) {
448        edge = Parent::findEdge(source, target, edge);
449      }
450      return edge;
451    }
[2031]452
453    template <typename _Value>
454    class NodeMap
455      : public SubMapExtender<Adaptor,
456                              typename Parent::template NodeMap<_Value> >
457    {
458    public:
459      typedef Adaptor Graph;
460      typedef SubMapExtender<Adaptor, typename Parent::
461                             template NodeMap<_Value> > Parent;
462   
463      NodeMap(const Graph& graph)
464        : Parent(graph) {}
465      NodeMap(const Graph& graph, const _Value& value)
466        : Parent(graph, value) {}
467   
468      NodeMap& operator=(const NodeMap& cmap) {
469        return operator=<NodeMap>(cmap);
470      }
471   
472      template <typename CMap>
473      NodeMap& operator=(const CMap& cmap) {
474        Parent::operator=(cmap);
475        return *this;
476      }
477    };
478
479    template <typename _Value>
480    class EdgeMap
481      : public SubMapExtender<Adaptor,
482                              typename Parent::template EdgeMap<_Value> >
483    {
484    public:
485      typedef Adaptor Graph;
486      typedef SubMapExtender<Adaptor, typename Parent::
487                             template EdgeMap<_Value> > Parent;
488   
489      EdgeMap(const Graph& graph)
490        : Parent(graph) {}
491      EdgeMap(const Graph& graph, const _Value& value)
492        : Parent(graph, value) {}
493   
494      EdgeMap& operator=(const EdgeMap& cmap) {
495        return operator=<EdgeMap>(cmap);
496      }
497   
498      template <typename CMap>
499      EdgeMap& operator=(const CMap& cmap) {
500        Parent::operator=(cmap);
501        return *this;
502      }
503    };
504
[1681]505  };
506
507  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
508  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
509    : public GraphAdaptorBase<_Graph> {
510  public:
511    typedef _Graph Graph;
[2031]512    typedef SubGraphAdaptorBase Adaptor;
[1681]513    typedef GraphAdaptorBase<_Graph> Parent;
514  protected:
515    NodeFilterMap* node_filter_map;
516    EdgeFilterMap* edge_filter_map;
517    SubGraphAdaptorBase() : Parent(),
518                            node_filter_map(0), edge_filter_map(0) { }
519
520    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
521      node_filter_map=&_node_filter_map;
522    }
523    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
524      edge_filter_map=&_edge_filter_map;
525    }
526
527  public:
528
529    typedef typename Parent::Node Node;
530    typedef typename Parent::Edge Edge;
531
532    void first(Node& i) const {
533      Parent::first(i);
534      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
535    }
536
[992]537    void first(Edge& i) const {
538      Parent::first(i);
539      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
540    }
[1681]541
[992]542    void firstIn(Edge& i, const Node& n) const {
543      Parent::firstIn(i, n);
544      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
545    }
[1681]546
[992]547    void firstOut(Edge& i, const Node& n) const {
548      Parent::firstOut(i, n);
549      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
550    }
551
552    void next(Node& i) const {
553      Parent::next(i);
554      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
555    }
556    void next(Edge& i) const {
557      Parent::next(i);
558      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
559    }
560    void nextIn(Edge& i) const {
561      Parent::nextIn(i);
562      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
563    }
[1681]564
[992]565    void nextOut(Edge& i) const {
566      Parent::nextOut(i);
567      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
568    }
569
[1951]570    ///\e
[1949]571
[1951]572    /// This function hides \c n in the graph, i.e. the iteration
573    /// jumps over it. This is done by simply setting the value of \c n 
574    /// to be false in the corresponding node-map.
[992]575    void hide(const Node& n) const { node_filter_map->set(n, false); }
576
[1951]577    ///\e
[1949]578
[1951]579    /// This function hides \c e in the graph, i.e. the iteration
580    /// jumps over it. This is done by simply setting the value of \c e 
581    /// to be false in the corresponding edge-map.
[992]582    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
583
[1951]584    ///\e
[1949]585
[1951]586    /// The value of \c n is set to be true in the node-map which stores
587    /// hide information. If \c n was hidden previuosly, then it is shown
588    /// again
[992]589     void unHide(const Node& n) const { node_filter_map->set(n, true); }
590
[1951]591    ///\e
[1949]592
[1951]593    /// The value of \c e is set to be true in the edge-map which stores
594    /// hide information. If \c e was hidden previuosly, then it is shown
595    /// again
[992]596    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
597
[1951]598    /// Returns true if \c n is hidden.
[1949]599   
[1951]600    ///\e
601    ///
[992]602    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
603
[1951]604    /// Returns true if \c n is hidden.
[1949]605   
[1951]606    ///\e
607    ///
[992]608    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
609
[1697]610    typedef False NodeNumTag;
611    typedef False EdgeNumTag;
[1991]612
613    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
614    Edge findEdge(const Node& source, const Node& target,
615                  const Edge& prev = INVALID) {
616      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
617        return INVALID;
618      }
619      Edge edge = Parent::findEdge(source, target, prev);
620      while (edge != INVALID && !(*edge_filter_map)[edge]) {
621        edge = Parent::findEdge(source, target, edge);
622      }
623      return edge;
624    }
[2031]625
626    template <typename _Value>
627    class NodeMap
628      : public SubMapExtender<Adaptor,
629                              typename Parent::template NodeMap<_Value> >
630    {
631    public:
632      typedef Adaptor Graph;
633      typedef SubMapExtender<Adaptor, typename Parent::
634                             template NodeMap<_Value> > Parent;
635   
636      NodeMap(const Graph& graph)
637        : Parent(graph) {}
638      NodeMap(const Graph& graph, const _Value& value)
639        : Parent(graph, value) {}
640   
641      NodeMap& operator=(const NodeMap& cmap) {
642        return operator=<NodeMap>(cmap);
643      }
644   
645      template <typename CMap>
646      NodeMap& operator=(const CMap& cmap) {
647        Parent::operator=(cmap);
648        return *this;
649      }
650    };
651
652    template <typename _Value>
653    class EdgeMap
654      : public SubMapExtender<Adaptor,
655                              typename Parent::template EdgeMap<_Value> >
656    {
657    public:
658      typedef Adaptor Graph;
659      typedef SubMapExtender<Adaptor, typename Parent::
660                             template EdgeMap<_Value> > Parent;
661   
662      EdgeMap(const Graph& graph)
663        : Parent(graph) {}
664      EdgeMap(const Graph& graph, const _Value& value)
665        : Parent(graph, value) {}
666   
667      EdgeMap& operator=(const EdgeMap& cmap) {
668        return operator=<EdgeMap>(cmap);
669      }
670   
671      template <typename CMap>
672      EdgeMap& operator=(const CMap& cmap) {
673        Parent::operator=(cmap);
674        return *this;
675      }
676    };
677
[992]678  };
[775]679
[2081]680  /// \ingroup graph_adaptors
681  ///
[1951]682  /// \brief A graph adaptor for hiding nodes and edges from a graph.
683  ///
684  /// SubGraphAdaptor shows the graph with filtered node-set and
685  /// edge-set. If the \c checked parameter is true then it filters the edgeset
686  /// to do not get invalid edges without source or target.
[1952]687  /// Let \f$ G=(V, A) \f$ be a directed graph
[1951]688  /// and suppose that the graph instance \c g of type ListGraph
[1952]689  /// implements \f$ G \f$.
690  /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
[1951]691  /// on the node-set and edge-set.
692  /// SubGraphAdaptor<...>::NodeIt iterates
[1952]693  /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
[1951]694  /// SubGraphAdaptor<...>::EdgeIt iterates
[1952]695  /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
[1951]696  /// SubGraphAdaptor<...>::OutEdgeIt and
697  /// SubGraphAdaptor<...>::InEdgeIt iterates
698  /// only on edges leaving and entering a specific node which have true value.
699  ///
700  /// If the \c checked template parameter is false then we have to note that
701  /// the node-iterator cares only the filter on the node-set, and the
702  /// edge-iterator cares only the filter on the edge-set.
703  /// This way the edge-map
704  /// should filter all edges which's source or target is filtered by the
705  /// node-filter.
[1957]706  ///\code
[1951]707  /// typedef ListGraph Graph;
708  /// Graph g;
709  /// typedef Graph::Node Node;
710  /// typedef Graph::Edge Edge;
711  /// Node u=g.addNode(); //node of id 0
712  /// Node v=g.addNode(); //node of id 1
713  /// Node e=g.addEdge(u, v); //edge of id 0
714  /// Node f=g.addEdge(v, u); //edge of id 1
715  /// Graph::NodeMap<bool> nm(g, true);
716  /// nm.set(u, false);
717  /// Graph::EdgeMap<bool> em(g, true);
718  /// em.set(e, false);
[1991]719  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
720  /// SubGA ga(g, nm, em);
721  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
[1951]722  /// std::cout << ":-)" << std::endl;
[1991]723  /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
[1957]724  ///\endcode
[1951]725  /// The output of the above code is the following.
[1957]726  ///\code
[1951]727  /// 1
728  /// :-)
729  /// 1
[1957]730  ///\endcode
[1991]731  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
[1951]732  /// \c Graph::Node that is why \c g.id(n) can be applied.
733  ///
734  /// For other examples see also the documentation of NodeSubGraphAdaptor and
735  /// EdgeSubGraphAdaptor.
736  ///
737  /// \author Marton Makai
[1242]738
[992]739  template<typename _Graph, typename NodeFilterMap,
[1681]740           typename EdgeFilterMap, bool checked = true>
[1401]741  class SubGraphAdaptor :
[1979]742    public GraphAdaptorExtender<
[1681]743    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
[650]744  public:
[992]745    typedef _Graph Graph;
[2031]746    typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
747                                                      EdgeFilterMap, checked> >
748    Parent;
749
[556]750  protected:
[1401]751    SubGraphAdaptor() { }
[992]752  public:
[2031]753
[1401]754    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
[992]755                    EdgeFilterMap& _edge_filter_map) {
756      setGraph(_graph);
757      setNodeFilterMap(_node_filter_map);
758      setEdgeFilterMap(_edge_filter_map);
759    }
[2031]760
[992]761  };
[556]762
[1991]763  /// \brief Just gives back a sub graph adaptor
764  ///
765  /// Just gives back a sub graph adaptor
766  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
767  SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
768  subGraphAdaptor(const Graph& graph,
769                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
770    return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
771      (graph, nfm, efm);
772  }
773
774  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
775  SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
776  subGraphAdaptor(const Graph& graph,
777                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
778    return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
779      (graph, nfm, efm);
780  }
781
782  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
783  SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
784  subGraphAdaptor(const Graph& graph,
785                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
786    return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
787      (graph, nfm, efm);
788  }
789
790  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
791  SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
792  subGraphAdaptor(const Graph& graph,
793                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
794    return SubGraphAdaptor<const Graph, const NodeFilterMap,
795      const EdgeFilterMap>(graph, nfm, efm);
796  }
797
[556]798
[569]799
[2081]800  ///\ingroup graph_adaptors
801  ///
[1951]802  ///\brief An adaptor for hiding nodes from a graph.
803  ///
804  ///An adaptor for hiding nodes from a graph.
805  ///This adaptor specializes SubGraphAdaptor in the way that only
806  ///the node-set
807  ///can be filtered. In usual case the checked parameter is true, we get the
808  ///induced subgraph. But if the checked parameter is false then we can only
809  ///filter only isolated nodes.
810  ///\author Marton Makai
[1681]811  template<typename Graph, typename NodeFilterMap, bool checked = true>
[1401]812  class NodeSubGraphAdaptor :
813    public SubGraphAdaptor<Graph, NodeFilterMap,
[1681]814                           ConstMap<typename Graph::Edge,bool>, checked> {
[933]815  public:
[2031]816
[1401]817    typedef SubGraphAdaptor<Graph, NodeFilterMap,
[2031]818                            ConstMap<typename Graph::Edge,bool>, checked >
819    Parent;
820
[933]821  protected:
822    ConstMap<typename Graph::Edge, bool> const_true_map;
[1991]823
824    NodeSubGraphAdaptor() : const_true_map(true) {
825      Parent::setEdgeFilterMap(const_true_map);
826    }
827
[933]828  public:
[2031]829
[1401]830    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
[933]831      Parent(), const_true_map(true) {
832      Parent::setGraph(_graph);
833      Parent::setNodeFilterMap(_node_filter_map);
834      Parent::setEdgeFilterMap(const_true_map);
835    }
[2031]836
[933]837  };
838
839
[1991]840  /// \brief Just gives back a node sub graph adaptor
841  ///
842  /// Just gives back a node sub graph adaptor
843  template<typename Graph, typename NodeFilterMap>
844  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
845  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
846    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
847  }
848
849  template<typename Graph, typename NodeFilterMap>
850  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
851  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
852    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
853  }
854
[2081]855  ///\ingroup graph_adaptors
856  ///
[1951]857  ///\brief An adaptor for hiding edges from a graph.
858  ///
859  ///An adaptor for hiding edges from a graph.
860  ///This adaptor specializes SubGraphAdaptor in the way that
861  ///only the edge-set
862  ///can be filtered. The usefulness of this adaptor is demonstrated in the
863  ///problem of searching a maximum number of edge-disjoint shortest paths
864  ///between
865  ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
866  ///non-negative edge-lengths. Note that
867  ///the comprehension of the presented solution
868  ///need's some elementary knowledge from combinatorial optimization.
869  ///
870  ///If a single shortest path is to be
871  ///searched between \c s and \c t, then this can be done easily by
872  ///applying the Dijkstra algorithm. What happens, if a maximum number of
873  ///edge-disjoint shortest paths is to be computed. It can be proved that an
874  ///edge can be in a shortest path if and only
875  ///if it is tight with respect to
876  ///the potential function computed by Dijkstra.
877  ///Moreover, any path containing
878  ///only such edges is a shortest one.
879  ///Thus we have to compute a maximum number
880  ///of edge-disjoint paths between \c s and \c t in
881  ///the graph which has edge-set
882  ///all the tight edges. The computation will be demonstrated
883  ///on the following
884  ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
885  ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
886  ///If you are interested in more demo programs, you can use
887  ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
888  ///The .dot file of the following figure was generated by 
889  ///the demo program \ref dim_to_dot.cc.
890  ///
891  ///\dot
892  ///digraph lemon_dot_example {
893  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
894  ///n0 [ label="0 (s)" ];
895  ///n1 [ label="1" ];
896  ///n2 [ label="2" ];
897  ///n3 [ label="3" ];
898  ///n4 [ label="4" ];
899  ///n5 [ label="5" ];
900  ///n6 [ label="6 (t)" ];
901  ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
902  ///n5 ->  n6 [ label="9, length:4" ];
903  ///n4 ->  n6 [ label="8, length:2" ];
904  ///n3 ->  n5 [ label="7, length:1" ];
905  ///n2 ->  n5 [ label="6, length:3" ];
906  ///n2 ->  n6 [ label="5, length:5" ];
907  ///n2 ->  n4 [ label="4, length:2" ];
908  ///n1 ->  n4 [ label="3, length:3" ];
909  ///n0 ->  n3 [ label="2, length:1" ];
910  ///n0 ->  n2 [ label="1, length:2" ];
911  ///n0 ->  n1 [ label="0, length:3" ];
912  ///}
913  ///\enddot
914  ///
915  ///\code
916  ///Graph g;
917  ///Node s, t;
918  ///LengthMap length(g);
919  ///
920  ///readDimacs(std::cin, g, length, s, t);
921  ///
922  ///cout << "edges with lengths (of form id, source--length->target): " << endl;
923  ///for(EdgeIt e(g); e!=INVALID; ++e)
924  ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
925  ///       << length[e] << "->" << g.id(g.target(e)) << endl;
926  ///
927  ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
928  ///\endcode
929  ///Next, the potential function is computed with Dijkstra.
930  ///\code
931  ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
932  ///Dijkstra dijkstra(g, length);
933  ///dijkstra.run(s);
934  ///\endcode
935  ///Next, we consrtruct a map which filters the edge-set to the tight edges.
936  ///\code
937  ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
938  ///  TightEdgeFilter;
939  ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
940  ///
[1991]941  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
942  ///SubGA ga(g, tight_edge_filter);
[1951]943  ///\endcode
944  ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
945  ///with a max flow algorithm Preflow.
946  ///\code
947  ///ConstMap<Edge, int> const_1_map(1);
948  ///Graph::EdgeMap<int> flow(g, 0);
949  ///
[1991]950  ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
951  ///  preflow(ga, s, t, const_1_map, flow);
[1951]952  ///preflow.run();
953  ///\endcode
954  ///Last, the output is:
955  ///\code 
956  ///cout << "maximum number of edge-disjoint shortest path: "
957  ///     << preflow.flowValue() << endl;
958  ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
959  ///     << endl;
960  ///for(EdgeIt e(g); e!=INVALID; ++e)
961  ///  if (flow[e])
962  ///    cout << " " << g.id(g.source(e)) << "--"
963  ///         << length[e] << "->" << g.id(g.target(e)) << endl;
964  ///\endcode
965  ///The program has the following (expected :-)) output:
966  ///\code
967  ///edges with lengths (of form id, source--length->target):
968  /// 9, 5--4->6
969  /// 8, 4--2->6
970  /// 7, 3--1->5
971  /// 6, 2--3->5
972  /// 5, 2--5->6
973  /// 4, 2--2->4
974  /// 3, 1--3->4
975  /// 2, 0--1->3
976  /// 1, 0--2->2
977  /// 0, 0--3->1
978  ///s: 0 t: 6
979  ///maximum number of edge-disjoint shortest path: 2
980  ///edges of the maximum number of edge-disjoint shortest s-t paths:
981  /// 9, 5--4->6
982  /// 8, 4--2->6
983  /// 7, 3--1->5
984  /// 4, 2--2->4
985  /// 2, 0--1->3
986  /// 1, 0--2->2
987  ///\endcode
988  ///
989  ///\author Marton Makai
[932]990  template<typename Graph, typename EdgeFilterMap>
[1401]991  class EdgeSubGraphAdaptor :
992    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[1681]993                           EdgeFilterMap, false> {
[932]994  public:
[1401]995    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[1685]996                            EdgeFilterMap, false> Parent;
[932]997  protected:
998    ConstMap<typename Graph::Node, bool> const_true_map;
[1991]999
1000    EdgeSubGraphAdaptor() : const_true_map(true) {
1001      Parent::setNodeFilterMap(const_true_map);
1002    }
1003
[932]1004  public:
[2031]1005
[1401]1006    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
[932]1007      Parent(), const_true_map(true) {
1008      Parent::setGraph(_graph);
1009      Parent::setNodeFilterMap(const_true_map);
1010      Parent::setEdgeFilterMap(_edge_filter_map);
1011    }
[2031]1012
[932]1013  };
1014
[1991]1015  /// \brief Just gives back an edge sub graph adaptor
1016  ///
1017  /// Just gives back an edge sub graph adaptor
1018  template<typename Graph, typename EdgeFilterMap>
1019  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
1020  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
1021    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
1022  }
1023
1024  template<typename Graph, typename EdgeFilterMap>
1025  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
1026  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
1027    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
1028  }
1029
[2079]1030  template <typename _Graph>
[1980]1031  class UndirGraphAdaptorBase :
[2079]1032    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
[1383]1033  public:
1034    typedef _Graph Graph;
[2031]1035    typedef UndirGraphAdaptorBase Adaptor;
[2079]1036    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
[1991]1037
[1383]1038  protected:
[1991]1039
1040    UndirGraphAdaptorBase() : Parent() {}
1041
[1383]1042  public:
[1991]1043
[1909]1044    typedef typename Parent::UEdge UEdge;
[1383]1045    typedef typename Parent::Edge Edge;
[1991]1046
[2031]1047  private:
[1383]1048   
[1991]1049    template <typename _Value>
[2031]1050    class EdgeMapBase {
[1991]1051    private:
1052     
1053      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1054     
[1383]1055    public:
[1991]1056
1057      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1058
1059      typedef _Value Value;
[1383]1060      typedef Edge Key;
1061     
[2031]1062      EdgeMapBase(const Adaptor& adaptor) :
1063        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
[569]1064
[2031]1065      EdgeMapBase(const Adaptor& adaptor, const Value& v)
1066        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
[1383]1067     
[1991]1068      void set(const Edge& e, const Value& a) {
1069        if (Parent::direction(e)) {
[1383]1070          forward_map.set(e, a);
[1991]1071        } else {
1072          backward_map.set(e, a);
1073        }
[1383]1074      }
[556]1075
[1991]1076      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1077        if (Parent::direction(e)) {
[1383]1078          return forward_map[e];
[1991]1079        } else {
[1383]1080          return backward_map[e];
[1991]1081        }
[556]1082      }
[1991]1083
1084      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1085        if (Parent::direction(e)) {
1086          return forward_map[e];
1087        } else {
1088          return backward_map[e];
1089        }
1090      }
1091
1092    protected:
1093
1094      MapImpl forward_map, backward_map;
1095
[556]1096    };
[2031]1097
1098  public:
1099
1100    template <typename _Value>
1101    class EdgeMap
1102      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1103    {
1104    public:
1105      typedef Adaptor Graph;
1106      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1107   
1108      EdgeMap(const Graph& graph)
1109        : Parent(graph) {}
1110      EdgeMap(const Graph& graph, const _Value& value)
1111        : Parent(graph, value) {}
1112   
1113      EdgeMap& operator=(const EdgeMap& cmap) {
1114        return operator=<EdgeMap>(cmap);
1115      }
1116   
1117      template <typename CMap>
1118      EdgeMap& operator=(const CMap& cmap) {
1119        Parent::operator=(cmap);
1120        return *this;
1121      }
1122    };
[1383]1123       
[1991]1124    template <typename _Value>
[2031]1125    class UEdgeMap : public Graph::template EdgeMap<_Value> {
[1383]1126    public:
[2031]1127     
1128      typedef typename Graph::template EdgeMap<_Value> Parent;
1129     
1130      explicit UEdgeMap(const Adaptor& ga)
1131        : Parent(*ga.graph) {}
[1991]1132
[2031]1133      UEdgeMap(const Adaptor& ga, const _Value& value)
1134        : Parent(*ga.graph, value) {}
[1991]1135
[2031]1136      UEdgeMap& operator=(const UEdgeMap& cmap) {
1137        return operator=<UEdgeMap>(cmap);
1138      }
[1991]1139
[2031]1140      template <typename CMap>
1141      UEdgeMap& operator=(const CMap& cmap) {
1142        Parent::operator=(cmap);
1143        return *this;
1144      }
1145
[1991]1146    };
1147     
1148  };
[556]1149
[2079]1150  template <typename _Graph, typename Enable = void>
1151  class AlterableUndirGraphAdaptor
1152    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1153  public:
1154    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1155   
1156  protected:
1157
1158    AlterableUndirGraphAdaptor() : Parent() {}
1159
[1991]1160  public:
1161
[2079]1162    typedef typename Parent::EdgeNotifier UEdgeNotifier;
1163    typedef InvalidType EdgeNotifier;
1164
1165  };
1166
1167  template <typename _Graph>
1168  class AlterableUndirGraphAdaptor<
1169    _Graph,
1170    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
1171    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1172  public:
1173
1174    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
[1991]1175    typedef _Graph Graph;
[2079]1176    typedef typename _Graph::Edge GraphEdge;
1177   
[1991]1178  protected:
1179
[2079]1180    AlterableUndirGraphAdaptor()
1181      : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
[1991]1182
1183    void setGraph(_Graph& graph) {
1184      Parent::setGraph(graph);
[2079]1185      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
[1991]1186    }
1187
1188  public:
1189
[2079]1190    ~AlterableUndirGraphAdaptor() {
[1999]1191      edge_notifier.clear();
1192    }
1193
[1991]1194    typedef typename Parent::UEdge UEdge;
1195    typedef typename Parent::Edge Edge;
1196
1197    typedef typename Parent::EdgeNotifier UEdgeNotifier;
1198
1199    using Parent::getNotifier;
1200
[2079]1201    typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1202                               Edge> EdgeNotifier;
[1991]1203    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1204
1205  protected:
1206
[2079]1207    class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
[1991]1208    public:
1209
[2079]1210      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1211      typedef AlterableUndirGraphAdaptor AdaptorBase;
[1383]1212     
[2079]1213      NotifierProxy(const AdaptorBase& _adaptor)
1214        : Parent(), adaptor(&_adaptor) {
[1383]1215      }
[556]1216
[1991]1217      virtual ~NotifierProxy() {
1218        if (Parent::attached()) {
1219          Parent::detach();
1220        }
[1383]1221      }
[1991]1222
[2079]1223      void setNotifier(typename Graph::EdgeNotifier& notifier) {
1224        Parent::attach(notifier);
[1991]1225      }
1226
1227     
1228    protected:
1229
[2079]1230      virtual void add(const GraphEdge& ge) {
[1991]1231        std::vector<Edge> edges;
[2079]1232        edges.push_back(AdaptorBase::Parent::direct(ge, true));
1233        edges.push_back(AdaptorBase::Parent::direct(ge, false));
1234        adaptor->getNotifier(Edge()).add(edges);
[1991]1235      }
[2079]1236      virtual void add(const std::vector<GraphEdge>& ge) {
[1991]1237        std::vector<Edge> edges;
[2079]1238        for (int i = 0; i < (int)ge.size(); ++i) {
1239          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1240          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
[1991]1241        }
[2079]1242        adaptor->getNotifier(Edge()).add(edges);
[1991]1243      }
[2079]1244      virtual void erase(const GraphEdge& ge) {
[1991]1245        std::vector<Edge> edges;
[2079]1246        edges.push_back(AdaptorBase::Parent::direct(ge, true));
1247        edges.push_back(AdaptorBase::Parent::direct(ge, false));
1248        adaptor->getNotifier(Edge()).erase(edges);
[1991]1249      }
[2079]1250      virtual void erase(const std::vector<GraphEdge>& ge) {
[1991]1251        std::vector<Edge> edges;
[2079]1252        for (int i = 0; i < (int)ge.size(); ++i) {
1253          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1254          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
[1991]1255        }
[2079]1256        adaptor->getNotifier(Edge()).erase(edges);
[1991]1257      }
1258      virtual void build() {
[2079]1259        adaptor->getNotifier(Edge()).build();
[1991]1260      }
1261      virtual void clear() {
[2079]1262        adaptor->getNotifier(Edge()).clear();
[1991]1263      }
1264
[2079]1265      const AdaptorBase* adaptor;
[1991]1266    };
1267
1268
1269    mutable EdgeNotifier edge_notifier;
1270    NotifierProxy edge_notifier_proxy;
1271
[1383]1272  };
1273
[2079]1274
[2081]1275  ///\ingroup graph_adaptors
1276  ///
[2079]1277  /// \brief An undirected graph is made from a directed graph by an adaptor
[1951]1278  ///
[2251]1279  /// This adaptor makes an undirected graph from a directed
1280  /// graph. All edge of the underlying will be showed in the adaptor
1281  /// as an undirected edge. Let's see an informal example about using
1282  /// this adaptor:
1283  ///
1284  /// There is a network of the streets of a town. Of course there are
1285  /// some one-way street in the town hence the network is a directed
1286  /// one. There is a crazy driver who go oppositely in the one-way
1287  /// street without moral sense. Of course he can pass this streets
1288  /// slower than the regular way, in fact his speed is half of the
1289  /// normal speed. How long should he drive to get from a source
1290  /// point to the target? Let see the example code which calculate it:
1291  ///
1292  ///\code
1293  /// typedef UndirGraphAdaptor<Graph> UGraph;
1294  /// UGraph ugraph(graph);
1295  ///
1296  /// typedef SimpleMap<LengthMap> FLengthMap;
1297  /// FLengthMap flength(length);
1298  ///
1299  /// typedef ScaleMap<LengthMap> RLengthMap;
1300  /// RLengthMap rlength(length, 2.0);
1301  ///
1302  /// typedef UGraph::CombinedEdgeMap<FLengthMap, RLengthMap > ULengthMap;
1303  /// ULengthMap ulength(flength, rlength);
[1951]1304  ///
[2251]1305  /// Dijkstra<UGraph, ULengthMap> dijkstra(ugraph, ulength);
1306  /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
1307  ///\endcode
1308  ///
1309  /// The combined edge map makes the length map for the undirected
1310  /// graph. It is created from a forward and reverse map. The forward
1311  /// map is created from the original length map with a SimpleMap
1312  /// adaptor which just makes a read-write map from the reference map
1313  /// i.e. it forgets that it can be return reference to values. The
1314  /// reverse map is just the scaled original map with the ScaleMap
1315  /// adaptor. The combination solves that passing the reverse way
1316  /// takes double time than the original. To get the driving time we
1317  /// run the dijkstra algorithm on the undirected graph.
1318  ///
1319  /// \author Marton Makai and Balazs Dezso
[1383]1320  template<typename _Graph>
[2079]1321  class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
[1383]1322  public:
1323    typedef _Graph Graph;
[2079]1324    typedef AlterableUndirGraphAdaptor<_Graph> Parent;
[1383]1325  protected:
[1980]1326    UndirGraphAdaptor() { }
[1383]1327  public:
[2251]1328
1329    /// \brief Constructor
1330    ///
1331    /// Constructor
[1980]1332    UndirGraphAdaptor(_Graph& _graph) {
[1383]1333      setGraph(_graph);
[556]1334    }
1335
[2251]1336    /// \brief EdgeMap combined from two original EdgeMap
1337    ///
1338    /// This class adapts two original graph EdgeMap to
1339    /// get an edge map on the adaptor.
[1991]1340    template <typename _ForwardMap, typename _BackwardMap>
1341    class CombinedEdgeMap {
1342    public:
1343     
1344      typedef _ForwardMap ForwardMap;
1345      typedef _BackwardMap BackwardMap;
[992]1346
[1991]1347      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
[992]1348
[1991]1349      typedef typename ForwardMap::Value Value;
1350      typedef typename Parent::Edge Key;
[2251]1351
1352      /// \brief Constructor     
1353      ///
1354      /// Constructor     
[1991]1355      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
[992]1356
[2251]1357      /// \brief Constructor     
1358      ///
1359      /// Constructor     
[1991]1360      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1361        : forward_map(&_forward_map), backward_map(&_backward_map) {}
[992]1362     
[2251]1363
1364      /// \brief Sets the value associated with a key.
1365      ///
1366      /// Sets the value associated with a key.
[1991]1367      void set(const Key& e, const Value& a) {
1368        if (Parent::direction(e)) {
1369          forward_map->set(e, a);
1370        } else {
1371          backward_map->set(e, a);
1372        }
[992]1373      }
1374
[2251]1375      /// \brief Returns the value associated with a key.
1376      ///
1377      /// Returns the value associated with a key.
[1991]1378      typename MapTraits<ForwardMap>::ConstReturnValue
1379      operator[](const Key& e) const {
1380        if (Parent::direction(e)) {
1381          return (*forward_map)[e];
1382        } else {
1383          return (*backward_map)[e];
1384        }
[992]1385      }
1386
[2251]1387      /// \brief Returns the value associated with a key.
1388      ///
1389      /// Returns the value associated with a key.
[1991]1390      typename MapTraits<ForwardMap>::ReturnValue
1391      operator[](const Key& e) {
1392        if (Parent::direction(e)) {
1393          return (*forward_map)[e];
1394        } else {
1395          return (*backward_map)[e];
1396        }
[992]1397      }
[1991]1398
[2251]1399      /// \brief Sets the forward map
1400      ///
1401      /// Sets the forward map
[1991]1402      void setForwardMap(ForwardMap& _forward_map) {
1403        forward_map = &_forward_map;
1404      }
1405
[2251]1406      /// \brief Sets the backward map
1407      ///
1408      /// Sets the backward map
[1991]1409      void setBackwardMap(BackwardMap& _backward_map) {
1410        backward_map = &_backward_map;
1411      }
1412
1413    protected:
1414
1415      ForwardMap* forward_map;
1416      BackwardMap* backward_map;
1417
[992]1418    };
1419
1420  };
[569]1421
[1991]1422  /// \brief Just gives back an undir graph adaptor
[1951]1423  ///
[1991]1424  /// Just gives back an undir graph adaptor
[650]1425  template<typename Graph>
[1991]1426  UndirGraphAdaptor<const Graph>
1427  undirGraphAdaptor(const Graph& graph) {
1428    return UndirGraphAdaptor<const Graph>(graph);
1429  }
[650]1430
[2034]1431  template<typename Graph, typename Number, 
1432           typename CapacityMap, typename FlowMap,
[2277]1433           typename Tol = Tolerance<Number> >
[658]1434  class ResForwardFilter {
[650]1435    const CapacityMap* capacity;
1436    const FlowMap* flow;
[2277]1437    Tol tolerance;
[650]1438  public:
[1991]1439    typedef typename Graph::Edge Key;
1440    typedef bool Value;
1441
[2034]1442    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
[2277]1443                     const Tol& _tolerance = Tol())
[2034]1444      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1445
[2277]1446    ResForwardFilter(const Tol& _tolerance)
[2034]1447      : capacity(0), flow(0), tolerance(_tolerance)  { }
1448
[1991]1449    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1450    void setFlow(const FlowMap& _flow) { flow = &_flow; }
[2034]1451
[650]1452    bool operator[](const typename Graph::Edge& e) const {
[2340]1453      return tolerance.positive((*capacity)[e] - (*flow)[e]);
[650]1454    }
1455  };
1456
1457  template<typename Graph, typename Number,
[2034]1458           typename CapacityMap, typename FlowMap,
[2277]1459           typename Tol = Tolerance<Number> >
[658]1460  class ResBackwardFilter {
[650]1461    const CapacityMap* capacity;
1462    const FlowMap* flow;
[2277]1463    Tol tolerance;
[650]1464  public:
[1991]1465    typedef typename Graph::Edge Key;
1466    typedef bool Value;
1467
[2034]1468    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
[2277]1469                      const Tol& _tolerance = Tol())
[2034]1470      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
[2277]1471    ResBackwardFilter(const Tol& _tolerance = Tol())
[2034]1472      : capacity(0), flow(0), tolerance(_tolerance) { }
[1991]1473    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1474    void setFlow(const FlowMap& _flow) { flow = &_flow; }
[650]1475    bool operator[](const typename Graph::Edge& e) const {
[2340]1476      return tolerance.positive((*flow)[e]);
[650]1477    }
1478  };
1479
[653]1480 
[2081]1481  ///\ingroup graph_adaptors
1482  ///
[1951]1483  ///\brief An adaptor for composing the residual
1484  ///graph for directed flow and circulation problems.
[2037]1485  ///
[2042]1486  ///An adaptor for composing the residual graph for directed flow and
1487  ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
1488  ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1489  ///be functions on the edge-set.
1490  ///
1491  ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
1492  ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
1493  ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
1494  ///
1495  ///\code
1496  ///  ListGraph g;
1497  ///\endcode
1498  ///
1499  ///Then RevGraphAdaptor implements the graph structure with node-set
1500  /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
1501  ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1502  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
1503  ///residual graph.  When we take the union
1504  /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
1505  ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
1506  ///then in the adaptor it appears twice. The following code shows how
1507  ///such an instance can be constructed.
1508  ///
1509  ///\code
1510  ///  typedef ListGraph Graph;
1511  ///  Graph::EdgeMap<int> f(g);
1512  ///  Graph::EdgeMap<int> c(g);
1513  ///  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1514  ///\endcode
1515  ///\author Marton Makai
1516  ///
[650]1517  template<typename Graph, typename Number,
[2034]1518           typename CapacityMap, typename FlowMap,
[2277]1519           typename Tol = Tolerance<Number> >
[1401]1520  class ResGraphAdaptor :
[1991]1521    public EdgeSubGraphAdaptor<
[2034]1522    UndirGraphAdaptor<const Graph>,
1523    typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1524    ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>, 
1525    ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
[650]1526  public:
[1991]1527
[2034]1528    typedef UndirGraphAdaptor<const Graph> UGraph;
[1991]1529
[2034]1530    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
[1991]1531    ForwardFilter;
1532
[2034]1533    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
[1991]1534    BackwardFilter;
1535
1536    typedef typename UGraph::
1537    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1538    EdgeFilter;
1539
1540    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1541
[650]1542  protected:
[1991]1543
[650]1544    const CapacityMap* capacity;
1545    FlowMap* flow;
[1991]1546
1547    UGraph ugraph;
1548    ForwardFilter forward_filter;
1549    BackwardFilter backward_filter;
1550    EdgeFilter edge_filter;
1551
[658]1552    void setCapacityMap(const CapacityMap& _capacity) {
1553      capacity=&_capacity;
1554      forward_filter.setCapacity(_capacity);
1555      backward_filter.setCapacity(_capacity);
1556    }
[1991]1557
[658]1558    void setFlowMap(FlowMap& _flow) {
1559      flow=&_flow;
1560      forward_filter.setFlow(_flow);
1561      backward_filter.setFlow(_flow);
1562    }
[1991]1563
[650]1564  public:
[1991]1565
[2034]1566    /// \brief Constructor of the residual graph.
1567    ///
1568    /// Constructor of the residual graph. The parameters are the graph type,
1569    /// the flow map, the capacity map and a tolerance object.
1570    ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
[2277]1571                    FlowMap& _flow, const Tol& _tolerance = Tol())
[2034]1572      : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
1573        forward_filter(_capacity, _flow, _tolerance),
1574        backward_filter(_capacity, _flow, _tolerance),
1575        edge_filter(forward_filter, backward_filter)
1576    {
[1991]1577      Parent::setGraph(ugraph);
1578      Parent::setEdgeFilterMap(edge_filter);
[650]1579    }
1580
[660]1581    typedef typename Parent::Edge Edge;
1582
[2034]1583    /// \brief Gives back the residual capacity of the edge.
1584    ///
1585    /// Gives back the residual capacity of the edge.
1586    Number rescap(const Edge& edge) const {
1587      if (UGraph::direction(edge)) {
1588        return (*capacity)[edge]-(*flow)[edge];
1589      } else {
1590        return (*flow)[edge];
1591      }
1592    }
1593
1594    /// \brief Augment on the given edge in the residual graph.
1595    ///
1596    /// Augment on the given edge in the residual graph. It increase
1597    /// or decrease the flow on the original edge depend on the direction
1598    /// of the residual edge.
[660]1599    void augment(const Edge& e, Number a) const {
[1991]1600      if (UGraph::direction(e)) {
[2034]1601        flow->set(e, (*flow)[e] + a);
[1991]1602      } else { 
[2034]1603        flow->set(e, (*flow)[e] - a);
[1991]1604      }
[650]1605    }
1606
[2034]1607    /// \brief Returns the direction of the edge.
1608    ///
1609    /// Returns true when the edge is same oriented as the original edge.
[1991]1610    static bool forward(const Edge& e) {
1611      return UGraph::direction(e);
1612    }
1613
[2034]1614    /// \brief Returns the direction of the edge.
1615    ///
1616    /// Returns true when the edge is opposite oriented as the original edge.
[1991]1617    static bool backward(const Edge& e) {
1618      return !UGraph::direction(e);
1619    }
1620
[2034]1621    /// \brief Gives back the forward oriented residual edge.
1622    ///
1623    /// Gives back the forward oriented residual edge.
[1991]1624    static Edge forward(const typename Graph::Edge& e) {
1625      return UGraph::direct(e, true);
1626    }
1627
[2034]1628    /// \brief Gives back the backward oriented residual edge.
1629    ///
1630    /// Gives back the backward oriented residual edge.
[1991]1631    static Edge backward(const typename Graph::Edge& e) {
1632      return UGraph::direct(e, false);
1633    }
1634
[1951]1635    /// \brief Residual capacity map.
1636    ///
1637    /// In generic residual graphs the residual capacity can be obtained
1638    /// as a map.
[660]1639    class ResCap {
1640    protected:
[1991]1641      const ResGraphAdaptor* res_graph;
[660]1642    public:
[987]1643      typedef Number Value;
1644      typedef Edge Key;
[1991]1645      ResCap(const ResGraphAdaptor& _res_graph)
1646        : res_graph(&_res_graph) {}
1647     
[2034]1648      Number operator[](const Edge& e) const {
1649        return res_graph->rescap(e);
[660]1650      }
[1991]1651     
[660]1652    };
1653
[650]1654  };
1655
1656
[998]1657
1658  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1659  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[998]1660  public:
1661    typedef _Graph Graph;
[1401]1662    typedef GraphAdaptorBase<_Graph> Parent;
[998]1663  protected:
1664    FirstOutEdgesMap* first_out_edges;
[1401]1665    ErasingFirstGraphAdaptorBase() : Parent(),
[998]1666                                     first_out_edges(0) { }
1667
1668    void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1669      first_out_edges=&_first_out_edges;
1670    }
1671
1672  public:
1673
1674    typedef typename Parent::Node Node;
1675    typedef typename Parent::Edge Edge;
1676
1677    void firstOut(Edge& i, const Node& n) const {
1678      i=(*first_out_edges)[n];
1679    }
1680
1681    void erase(const Edge& e) const {
1682      Node n=source(e);
1683      Edge f=e;
1684      Parent::nextOut(f);
1685      first_out_edges->set(n, f);
1686    }   
1687  };
1688
1689
[2081]1690  ///\ingroup graph_adaptors
1691  ///
[1951]1692  ///\brief For blocking flows.
1693  ///
1694  ///This graph adaptor is used for on-the-fly
1695  ///Dinits blocking flow computations.
1696  ///For each node, an out-edge is stored which is used when the
1697  ///\code
1698  ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1699  ///\endcode
1700  ///is called.
1701  ///
1702  ///\author Marton Makai
1703  ///
[998]1704  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1705  class ErasingFirstGraphAdaptor :
[1979]1706    public GraphAdaptorExtender<
[1401]1707    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
[650]1708  public:
[998]1709    typedef _Graph Graph;
[1979]1710    typedef GraphAdaptorExtender<
[1401]1711      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1712    ErasingFirstGraphAdaptor(Graph& _graph,
[998]1713                             FirstOutEdgesMap& _first_out_edges) {
1714      setGraph(_graph);
1715      setFirstOutEdgesMap(_first_out_edges);
1716    }
[1019]1717
[998]1718  };
[556]1719
[2079]1720  /// \brief Base class for split graph adaptor
1721  ///
1722  /// Base class of split graph adaptor. In most case you do not need to
1723  /// use it directly but the documented member functions of this class can
1724  /// be used with the SplitGraphAdaptor class.
1725  /// \sa SplitGraphAdaptor
1726  template <typename _Graph>
1727  class SplitGraphAdaptorBase
1728    : public GraphAdaptorBase<const _Graph> {
1729  public:
[1697]1730
[2079]1731    typedef _Graph Graph;
1732
1733    typedef GraphAdaptorBase<const _Graph> Parent;
1734
1735    typedef typename Graph::Node GraphNode;
1736    typedef typename Graph::Edge GraphEdge;
1737
1738    class Node;
1739    class Edge;
1740
1741    template <typename T> class NodeMap;
1742    template <typename T> class EdgeMap;
[1697]1743   
1744
[2079]1745    class Node : public GraphNode {
1746      friend class SplitGraphAdaptorBase;
1747      template <typename T> friend class NodeMap;
1748    private:
[1697]1749
[2079]1750      bool in_node;
1751      Node(GraphNode _node, bool _in_node)
1752        : GraphNode(_node), in_node(_in_node) {}
[1697]1753     
[2079]1754    public:
[1697]1755
[2079]1756      Node() {}
1757      Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1758
1759      bool operator==(const Node& node) const {
1760        return GraphNode::operator==(node) && in_node == node.in_node;
1761      }
[1697]1762     
[2079]1763      bool operator!=(const Node& node) const {
1764        return !(*this == node);
1765      }
[1697]1766     
[2079]1767      bool operator<(const Node& node) const {
1768        return GraphNode::operator<(node) ||
1769          (GraphNode::operator==(node) && in_node < node.in_node);
1770      }
1771    };
[1697]1772
[2079]1773    class Edge {
1774      friend class SplitGraphAdaptorBase;
1775      template <typename T> friend class EdgeMap;
1776    private:
1777      typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
[1697]1778
[2079]1779      explicit Edge(const GraphEdge& edge) : item(edge) {}
1780      explicit Edge(const GraphNode& node) : item(node) {}
1781     
1782      EdgeImpl item;
[1697]1783
[2079]1784    public:
1785      Edge() {}
1786      Edge(Invalid) : item(GraphEdge(INVALID)) {}
1787
1788      bool operator==(const Edge& edge) const {
1789        if (item.firstState()) {
1790          if (edge.item.firstState()) {
1791            return item.first() == edge.item.first();
1792          }
1793        } else {
1794          if (edge.item.secondState()) {
1795            return item.second() == edge.item.second();
1796          }
1797        }
1798        return false;
1799      }
[1697]1800     
[2079]1801      bool operator!=(const Edge& edge) const {
1802        return !(*this == edge);
1803      }
[1697]1804     
[2079]1805      bool operator<(const Edge& edge) const {
1806        if (item.firstState()) {
1807          if (edge.item.firstState()) {
1808            return item.first() < edge.item.first();
1809          }
1810          return false;
1811        } else {
1812          if (edge.item.secondState()) {
1813            return item.second() < edge.item.second();
1814          }
1815          return true;
1816        }
1817      }
[1697]1818
[2079]1819      operator GraphEdge() const { return item.first(); }
1820      operator GraphNode() const { return item.second(); }
[1697]1821
[2079]1822    };
[1697]1823
[2079]1824    void first(Node& node) const {
1825      Parent::first(node);
1826      node.in_node = true;
1827    }
[1697]1828
[2079]1829    void next(Node& node) const {
1830      if (node.in_node) {
1831        node.in_node = false;
1832      } else {
1833        node.in_node = true;
1834        Parent::next(node);
1835      }
1836    }
[1697]1837
[2079]1838    void first(Edge& edge) const {
1839      edge.item.setSecond();
1840      Parent::first(edge.item.second());
1841      if (edge.item.second() == INVALID) {
1842        edge.item.setFirst();
1843        Parent::first(edge.item.first());
1844      }
1845    }
[1697]1846
[2079]1847    void next(Edge& edge) const {
1848      if (edge.item.secondState()) {
1849        Parent::next(edge.item.second());
1850        if (edge.item.second() == INVALID) {
1851          edge.item.setFirst();
1852          Parent::first(edge.item.first());
1853        }
1854      } else {
1855        Parent::next(edge.item.first());
1856      }     
1857    }
[1697]1858
[2079]1859    void firstOut(Edge& edge, const Node& node) const {
1860      if (node.in_node) {
1861        edge.item.setSecond(node);
1862      } else {
1863        edge.item.setFirst();
1864        Parent::firstOut(edge.item.first(), node);
1865      }
1866    }
[1697]1867
[2079]1868    void nextOut(Edge& edge) const {
1869      if (!edge.item.firstState()) {
1870        edge.item.setFirst(INVALID);
1871      } else {
1872        Parent::nextOut(edge.item.first());
1873      }     
1874    }
[1697]1875
[2079]1876    void firstIn(Edge& edge, const Node& node) const {
1877      if (!node.in_node) {
1878        edge.item.setSecond(node);       
1879      } else {
1880        edge.item.setFirst();
1881        Parent::firstIn(edge.item.first(), node);
1882      }
1883    }
[1697]1884
[2079]1885    void nextIn(Edge& edge) const {
1886      if (!edge.item.firstState()) {
1887        edge.item.setFirst(INVALID);
1888      } else {
1889        Parent::nextIn(edge.item.first());
1890      }
1891    }
[1697]1892
[2079]1893    Node source(const Edge& edge) const {
1894      if (edge.item.firstState()) {
1895        return Node(Parent::source(edge.item.first()), false);
1896      } else {
1897        return Node(edge.item.second(), true);
1898      }
1899    }
[1697]1900
[2079]1901    Node target(const Edge& edge) const {
1902      if (edge.item.firstState()) {
1903        return Node(Parent::target(edge.item.first()), true);
1904      } else {
1905        return Node(edge.item.second(), false);
1906      }
1907    }
[1697]1908
[2079]1909    int id(const Node& node) const {
1910      return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
1911    }
1912    Node nodeFromId(int id) const {
1913      return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
1914    }
1915    int maxNodeId() const {
1916      return 2 * Parent::maxNodeId() + 1;
1917    }
[1697]1918
[2079]1919    int id(const Edge& edge) const {
1920      if (edge.item.firstState()) {
1921        return Parent::id(edge.item.first()) << 1;
1922      } else {
1923        return (Parent::id(edge.item.second()) << 1) | 1;
1924      }
1925    }
1926    Edge edgeFromId(int id) const {
1927      if ((id & 1) == 0) {
1928        return Edge(Parent::edgeFromId(id >> 1));
1929      } else {
1930        return Edge(Parent::nodeFromId(id >> 1));
1931      }
1932    }
1933    int maxEdgeId() const {
1934      return std::max(Parent::maxNodeId() << 1,
1935                      (Parent::maxEdgeId() << 1) | 1);
1936    }
[1697]1937
[2079]1938    /// \brief Returns true when the node is in-node.
1939    ///
1940    /// Returns true when the node is in-node.
1941    static bool inNode(const Node& node) {
1942      return node.in_node;
1943    }
[1697]1944
[2079]1945    /// \brief Returns true when the node is out-node.
1946    ///
1947    /// Returns true when the node is out-node.
1948    static bool outNode(const Node& node) {
1949      return !node.in_node;
1950    }
[1697]1951
[2079]1952    /// \brief Returns true when the edge is edge in the original graph.
1953    ///
1954    /// Returns true when the edge is edge in the original graph.
1955    static bool origEdge(const Edge& edge) {
1956      return edge.item.firstState();
1957    }
[1697]1958
[2079]1959    /// \brief Returns true when the edge binds an in-node and an out-node.
1960    ///
1961    /// Returns true when the edge binds an in-node and an out-node.
1962    static bool bindEdge(const Edge& edge) {
1963      return edge.item.secondState();
1964    }
[1697]1965
[2079]1966    /// \brief Gives back the in-node created from the \c node.
1967    ///
1968    /// Gives back the in-node created from the \c node.
1969    static Node inNode(const GraphNode& node) {
1970      return Node(node, true);
1971    }
1972
1973    /// \brief Gives back the out-node created from the \c node.
1974    ///
1975    /// Gives back the out-node created from the \c node.
1976    static Node outNode(const GraphNode& node) {
1977      return Node(node, false);
1978    }
1979
1980    /// \brief Gives back the edge binds the two part of the node.
1981    ///
1982    /// Gives back the edge binds the two part of the node.
1983    static Edge edge(const GraphNode& node) {
1984      return Edge(node);
1985    }
1986
1987    /// \brief Gives back the edge of the original edge.
1988    ///
1989    /// Gives back the edge of the original edge.
1990    static Edge edge(const GraphEdge& edge) {
1991      return Edge(edge);
1992    }
1993
1994    typedef True NodeNumTag;
1995
1996    int nodeNum() const {
1997      return  2 * countNodes(*Parent::graph);
1998    }
1999
2000    typedef True EdgeNumTag;
[1697]2001   
[2079]2002    int edgeNum() const {
2003      return countEdges(*Parent::graph) + countNodes(*Parent::graph);
2004    }
[1697]2005
[2079]2006    typedef True FindEdgeTag;
2007
2008    Edge findEdge(const Node& source, const Node& target,
2009                  const Edge& prev = INVALID) const {
2010      if (inNode(source)) {
2011        if (outNode(target)) {
2012          if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
2013            return Edge(source);
2014          }
2015        }
2016      } else {
2017        if (inNode(target)) {
2018          return Edge(findEdge(*Parent::graph, source, target, prev));
2019        }
2020      }
2021      return INVALID;
2022    }
[1697]2023   
[2079]2024    template <typename T>
2025    class NodeMap : public MapBase<Node, T> {
2026      typedef typename Parent::template NodeMap<T> NodeImpl;
2027    public:
2028      NodeMap(const SplitGraphAdaptorBase& _graph)
2029        : inNodeMap(_graph), outNodeMap(_graph) {}
2030      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
2031        : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
[1697]2032     
[2079]2033      void set(const Node& key, const T& val) {
2034        if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
2035        else {outNodeMap.set(key, val); }
2036      }
[1697]2037     
[2079]2038      typename MapTraits<NodeImpl>::ReturnValue
2039      operator[](const Node& key) {
2040        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
2041        else { return outNodeMap[key]; }
2042      }
[1697]2043
[2079]2044      typename MapTraits<NodeImpl>::ConstReturnValue
2045      operator[](const Node& key) const {
2046        if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
2047        else { return outNodeMap[key]; }
2048      }
[1697]2049
[2079]2050    private:
2051      NodeImpl inNodeMap, outNodeMap;
2052    };
[1697]2053
[2079]2054    template <typename T>
2055    class EdgeMap : public MapBase<Edge, T> {
2056      typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
2057      typedef typename Parent::template NodeMap<T> NodeMapImpl;
2058    public:
2059
2060      EdgeMap(const SplitGraphAdaptorBase& _graph)
2061        : edge_map(_graph), node_map(_graph) {}
2062      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
2063        : edge_map(_graph, t), node_map(_graph, t) {}
[1697]2064     
[2079]2065      void set(const Edge& key, const T& val) {
2066        if (SplitGraphAdaptorBase::origEdge(key)) {
2067          edge_map.set(key.item.first(), val);
2068        } else {
2069          node_map.set(key.item.second(), val);
2070        }
2071      }
[1697]2072     
[2079]2073      typename MapTraits<EdgeMapImpl>::ReturnValue
2074      operator[](const Edge& key) {
2075        if (SplitGraphAdaptorBase::origEdge(key)) {
2076          return edge_map[key.item.first()];
2077        } else {
2078          return node_map[key.item.second()];
2079        }
2080      }
[1697]2081
[2079]2082      typename MapTraits<EdgeMapImpl>::ConstReturnValue
2083      operator[](const Edge& key) const {
2084        if (SplitGraphAdaptorBase::origEdge(key)) {
2085          return edge_map[key.item.first()];
2086        } else {
2087          return node_map[key.item.second()];
2088        }
2089      }
[1697]2090
[2079]2091    private:
2092      typename Parent::template EdgeMap<T> edge_map;
2093      typename Parent::template NodeMap<T> node_map;
2094    };
[1697]2095
2096
[2079]2097  };
[1697]2098
[2079]2099  template <typename _Graph, typename NodeEnable = void,
2100            typename EdgeEnable = void>
2101  class AlterableSplitGraphAdaptor
2102    : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2103  public:
[1697]2104
[2079]2105    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2106    typedef _Graph Graph;
[1697]2107
[2079]2108    typedef typename Graph::Node GraphNode;
2109    typedef typename Graph::Node GraphEdge;
[1697]2110
[2079]2111  protected:
2112
2113    AlterableSplitGraphAdaptor() : Parent() {}
2114
2115  public:
2116   
2117    typedef InvalidType NodeNotifier;
2118    typedef InvalidType EdgeNotifier;
2119
2120  };
2121
2122  template <typename _Graph, typename EdgeEnable>
2123  class AlterableSplitGraphAdaptor<
2124    _Graph,
2125    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2126    EdgeEnable>
2127      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2128  public:
2129
2130    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2131    typedef _Graph Graph;
2132
2133    typedef typename Graph::Node GraphNode;
2134    typedef typename Graph::Edge GraphEdge;
2135
2136    typedef typename Parent::Node Node;
2137    typedef typename Parent::Edge Edge;
2138 
2139  protected:
2140
2141    AlterableSplitGraphAdaptor()
2142      : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
2143
2144    void setGraph(_Graph& graph) {
2145      Parent::setGraph(graph);
2146      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2147    }
2148
2149  public:
2150
2151    ~AlterableSplitGraphAdaptor() {
2152      node_notifier.clear();
2153    }
2154
2155    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2156    typedef InvalidType EdgeNotifier;
2157
2158    NodeNotifier& getNotifier(Node) const { return node_notifier; }
2159
2160  protected:
2161
2162    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2163    public:
2164
2165      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2166      typedef AlterableSplitGraphAdaptor AdaptorBase;
[1697]2167     
[2079]2168      NodeNotifierProxy(const AdaptorBase& _adaptor)
2169        : Parent(), adaptor(&_adaptor) {
2170      }
2171
2172      virtual ~NodeNotifierProxy() {
2173        if (Parent::attached()) {
2174          Parent::detach();
2175        }
2176      }
2177
2178      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2179        Parent::attach(graph_notifier);
2180      }
2181
[1697]2182     
[2079]2183    protected:
2184
2185      virtual void add(const GraphNode& gn) {
2186        std::vector<Node> nodes;
2187        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2188        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2189        adaptor->getNotifier(Node()).add(nodes);
2190      }
2191
2192      virtual void add(const std::vector<GraphNode>& gn) {
2193        std::vector<Node> nodes;
2194        for (int i = 0; i < (int)gn.size(); ++i) {
2195          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2196          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2197        }
2198        adaptor->getNotifier(Node()).add(nodes);
2199      }
2200
2201      virtual void erase(const GraphNode& gn) {
2202        std::vector<Node> nodes;
2203        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2204        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2205        adaptor->getNotifier(Node()).erase(nodes);
2206      }
2207
2208      virtual void erase(const std::vector<GraphNode>& gn) {
2209        std::vector<Node> nodes;
2210        for (int i = 0; i < (int)gn.size(); ++i) {
2211          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2212          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2213        }
2214        adaptor->getNotifier(Node()).erase(nodes);
2215      }
2216      virtual void build() {
2217        adaptor->getNotifier(Node()).build();
2218      }
2219      virtual void clear() {
2220        adaptor->getNotifier(Node()).clear();
2221      }
2222
2223      const AdaptorBase* adaptor;
2224    };
2225
2226
2227    mutable NodeNotifier node_notifier;
2228
2229    NodeNotifierProxy node_notifier_proxy;
2230
2231  };
2232
2233  template <typename _Graph>
2234  class AlterableSplitGraphAdaptor<
2235    _Graph,
2236    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
2237    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
2238      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2239  public:
2240
2241    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2242    typedef _Graph Graph;
2243
2244    typedef typename Graph::Node GraphNode;
2245    typedef typename Graph::Edge GraphEdge;
2246
2247    typedef typename Parent::Node Node;
2248    typedef typename Parent::Edge Edge;
2249 
2250  protected:
2251   
2252    AlterableSplitGraphAdaptor()
2253      : Parent(), node_notifier(*this), edge_notifier(*this),
2254        node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
2255   
2256    void setGraph(_Graph& graph) {
2257      Parent::setGraph(graph);
2258      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
2259      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
2260    }
2261
2262  public:
2263
2264    ~AlterableSplitGraphAdaptor() {
2265      node_notifier.clear();
2266      edge_notifier.clear();
2267    }
2268
2269    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
2270    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
2271
2272    NodeNotifier& getNotifier(Node) const { return node_notifier; }
2273    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
2274
2275  protected:
2276
2277    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
2278    public:
[1697]2279     
[2079]2280      typedef typename Graph::NodeNotifier::ObserverBase Parent;
2281      typedef AlterableSplitGraphAdaptor AdaptorBase;
2282     
2283      NodeNotifierProxy(const AdaptorBase& _adaptor)
2284        : Parent(), adaptor(&_adaptor) {
2285      }
[1697]2286
[2079]2287      virtual ~NodeNotifierProxy() {
2288        if (Parent::attached()) {
2289          Parent::detach();
2290        }
2291      }
[1697]2292
[2079]2293      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
2294        Parent::attach(graph_notifier);
2295      }
[1697]2296
[2079]2297     
2298    protected:
[1697]2299
[2079]2300      virtual void add(const GraphNode& gn) {
2301        std::vector<Node> nodes;
2302        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2303        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2304        adaptor->getNotifier(Node()).add(nodes);
2305        adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
2306      }
2307      virtual void add(const std::vector<GraphNode>& gn) {
2308        std::vector<Node> nodes;
2309        std::vector<Edge> edges;
2310        for (int i = 0; i < (int)gn.size(); ++i) {
2311          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2312          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2313          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2314        }
2315        adaptor->getNotifier(Node()).add(nodes);
2316        adaptor->getNotifier(Edge()).add(edges);
2317      }
2318      virtual void erase(const GraphNode& gn) {
2319        adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
2320        std::vector<Node> nodes;
2321        nodes.push_back(AdaptorBase::Parent::inNode(gn));
2322        nodes.push_back(AdaptorBase::Parent::outNode(gn));
2323        adaptor->getNotifier(Node()).erase(nodes);
2324      }
2325      virtual void erase(const std::vector<GraphNode>& gn) {
2326        std::vector<Node> nodes;
2327        std::vector<Edge> edges;
2328        for (int i = 0; i < (int)gn.size(); ++i) {
2329          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
2330          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
2331          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
2332        }
2333        adaptor->getNotifier(Edge()).erase(edges);
2334        adaptor->getNotifier(Node()).erase(nodes);
2335      }
2336      virtual void build() {
2337        std::vector<Edge> edges;
2338        const typename Parent::Notifier* notifier = Parent::getNotifier();
2339        GraphNode it;
2340        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2341          edges.push_back(AdaptorBase::Parent::edge(it));
2342        }
2343        adaptor->getNotifier(Node()).build();
2344        adaptor->getNotifier(Edge()).add(edges);       
2345      }
2346      virtual void clear() {
2347        std::vector<Edge> edges;
2348        const typename Parent::Notifier* notifier = Parent::getNotifier();
2349        GraphNode it;
2350        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2351          edges.push_back(AdaptorBase::Parent::edge(it));
2352        }
2353        adaptor->getNotifier(Edge()).erase(edges);       
2354        adaptor->getNotifier(Node()).clear();
2355      }
[1697]2356
[2079]2357      const AdaptorBase* adaptor;
2358    };
[1697]2359
[2079]2360    class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
2361    public:
2362
2363      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
2364      typedef AlterableSplitGraphAdaptor AdaptorBase;
[1697]2365     
[2079]2366      EdgeNotifierProxy(const AdaptorBase& _adaptor)
2367        : Parent(), adaptor(&_adaptor) {
2368      }
[1697]2369
[2079]2370      virtual ~EdgeNotifierProxy() {
2371        if (Parent::attached()) {
2372          Parent::detach();
2373        }
2374      }
[1697]2375
[2079]2376      void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
2377        Parent::attach(graph_notifier);
2378      }
[1697]2379
[2079]2380     
2381    protected:
[1697]2382
[2079]2383      virtual void add(const GraphEdge& ge) {
2384        adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
2385      }
2386      virtual void add(const std::vector<GraphEdge>& ge) {
2387        std::vector<Edge> edges;
2388        for (int i = 0; i < (int)ge.size(); ++i) {
2389          edges.push_back(AdaptorBase::edge(ge[i]));
2390        }
2391        adaptor->getNotifier(Edge()).add(edges);
2392      }
2393      virtual void erase(const GraphEdge& ge) {
2394        adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
2395      }
2396      virtual void erase(const std::vector<GraphEdge>& ge) {
2397        std::vector<Edge> edges;
2398        for (int i = 0; i < (int)ge.size(); ++i) {
2399          edges.push_back(AdaptorBase::edge(ge[i]));
2400        }
2401        adaptor->getNotifier(Edge()).erase(edges);
2402      }
2403      virtual void build() {
2404        std::vector<Edge> edges;
2405        const typename Parent::Notifier* notifier = Parent::getNotifier();
2406        GraphEdge it;
2407        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2408          edges.push_back(AdaptorBase::Parent::edge(it));
2409        }
2410        adaptor->getNotifier(Edge()).add(edges);
2411      }
2412      virtual void clear() {
2413        std::vector<Edge> edges;
2414        const typename Parent::Notifier* notifier = Parent::getNotifier();
2415        GraphEdge it;
2416        for (notifier->first(it); it != INVALID; notifier->next(it)) {
2417          edges.push_back(AdaptorBase::Parent::edge(it));
2418        }
2419        adaptor->getNotifier(Edge()).erase(edges);
2420      }
[1697]2421
[2079]2422      const AdaptorBase* adaptor;
2423    };
2424
2425
2426    mutable NodeNotifier node_notifier;
2427    mutable EdgeNotifier edge_notifier;
2428
2429    NodeNotifierProxy node_notifier_proxy;
2430    EdgeNotifierProxy edge_notifier_proxy;
2431
2432  };
2433
2434  /// \ingroup graph_adaptors
2435  ///
[2081]2436  /// \brief Split graph adaptor class
[2079]2437  ///
2438  /// This is an graph adaptor which splits all node into an in-node
2439  /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
2440  /// node in the graph with two node, \f$ u_{in} \f$ node and
2441  /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
2442  /// original graph the new target of the edge will be \f$ u_{in} \f$ and
2443  /// similarly the source of the original \f$ (u, v) \f$ edge will be
2444  /// \f$ u_{out} \f$.  The adaptor will add for each node in the
2445  /// original graph an additional edge which will connect
2446  /// \f$ (u_{in}, u_{out}) \f$.
2447  ///
2448  /// The aim of this class is to run algorithm with node costs if the
2449  /// algorithm can use directly just edge costs. In this case we should use
2450  /// a \c SplitGraphAdaptor and set the node cost of the graph to the
2451  /// bind edge in the adapted graph.
2452  ///
2453  /// By example a maximum flow algoritm can compute how many edge
2454  /// disjoint paths are in the graph. But we would like to know how
2455  /// many node disjoint paths are in the graph. First we have to
2456  /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
2457  /// algorithm on the adapted graph. The bottleneck of the flow will
2458  /// be the bind edges which bounds the flow with the count of the
2459  /// node disjoint paths.
2460  ///
2461  ///\code
2462  ///
2463  /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
2464  ///
2465  /// SGraph sgraph(graph);
2466  ///
2467  /// typedef ConstMap<SGraph::Edge, int> SCapacity;
2468  /// SCapacity scapacity(1);
2469  ///
2470  /// SGraph::EdgeMap<int> sflow(sgraph);
2471  ///
2472  /// Preflow<SGraph, int, SCapacity>
2473  ///   spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target), 
2474  ///            scapacity, sflow);
2475  ///                                           
2476  /// spreflow.run();
2477  ///
2478  ///\endcode
2479  ///
2480  /// The result of the mamixum flow on the original graph
2481  /// shows the next figure:
2482  ///
2483  /// \image html edge_disjoint.png
2484  /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
2485  ///
2486  /// And the maximum flow on the adapted graph:
2487  ///
2488  /// \image html node_disjoint.png
2489  /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
2490  ///
2491  /// The second solution contains just 3 disjoint paths while the first 4.
[2084]2492  /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
[2079]2493  ///
2494  /// This graph adaptor is fully conform to the
[2260]2495  /// \ref concepts::Graph "Graph" concept and
[2079]2496  /// contains some additional member functions and types. The
2497  /// documentation of some member functions may be found just in the
2498  /// SplitGraphAdaptorBase class.
2499  ///
2500  /// \sa SplitGraphAdaptorBase
2501  template <typename _Graph>
2502  class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
2503  public:
2504    typedef AlterableSplitGraphAdaptor<_Graph> Parent;
2505
2506    typedef typename Parent::Node Node;
2507    typedef typename Parent::Edge Edge;
2508
2509    /// \brief Constructor of the adaptor.
2510    ///
2511    /// Constructor of the adaptor.
2512    SplitGraphAdaptor(_Graph& graph) {
2513      Parent::setGraph(graph);
2514    }
2515
2516    /// \brief NodeMap combined from two original NodeMap
2517    ///
2518    /// This class adapt two of the original graph NodeMap to
2519    /// get a node map on the adapted graph.
2520    template <typename InNodeMap, typename OutNodeMap>
2521    class CombinedNodeMap {
2522    public:
2523
2524      typedef Node Key;
2525      typedef typename InNodeMap::Value Value;
2526
2527      /// \brief Constructor
2528      ///
2529      /// Constructor.
2530      CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
2531        : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
2532
2533      /// \brief The subscript operator.
2534      ///
2535      /// The subscript operator.
2536      Value& operator[](const Key& key) {
2537        if (Parent::inNode(key)) {
2538          return inNodeMap[key];
2539        } else {
2540          return outNodeMap[key];
2541        }
2542      }
2543
2544      /// \brief The const subscript operator.
2545      ///
2546      /// The const subscript operator.
2547      Value operator[](const Key& key) const {
2548        if (Parent::inNode(key)) {
2549          return inNodeMap[key];
2550        } else {
2551          return outNodeMap[key];
2552        }
2553      }
2554
2555      /// \brief The setter function of the map.
2556      ///
2557      /// The setter function of the map.
2558      void set(const Key& key, const Value& value) {
2559        if (Parent::inNode(key)) {
2560          inNodeMap.set(key, value);
2561        } else {
2562          outNodeMap.set(key, value);
2563        }
2564      }
2565     
2566    private:
2567     
2568      InNodeMap& inNodeMap;
2569      OutNodeMap& outNodeMap;
2570     
2571    };
2572
2573
2574    /// \brief Just gives back a combined node map.
2575    ///
2576    /// Just gives back a combined node map.
2577    template <typename InNodeMap, typename OutNodeMap>
2578    static CombinedNodeMap<InNodeMap, OutNodeMap>
2579    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
2580      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
2581    }
2582
2583    template <typename InNodeMap, typename OutNodeMap>
2584    static CombinedNodeMap<const InNodeMap, OutNodeMap>
2585    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
2586      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
2587    }
2588
2589    template <typename InNodeMap, typename OutNodeMap>
2590    static CombinedNodeMap<InNodeMap, const OutNodeMap>
2591    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
2592      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
2593    }
2594
2595    template <typename InNodeMap, typename OutNodeMap>
2596    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
2597    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
2598      return CombinedNodeMap<const InNodeMap,
2599        const OutNodeMap>(in_map, out_map);
2600    }
2601
2602    /// \brief EdgeMap combined from an original EdgeMap and NodeMap
2603    ///
2604    /// This class adapt an original graph EdgeMap and NodeMap to
2605    /// get an edge map on the adapted graph.
2606    template <typename GraphEdgeMap, typename GraphNodeMap>
2607    class CombinedEdgeMap
2608      : public MapBase<Edge, typename GraphEdgeMap::Value> {
2609    public:
2610      typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
2611
2612      typedef typename Parent::Key Key;
2613      typedef typename Parent::Value Value;
2614
2615      /// \brief Constructor
2616      ///
2617      /// Constructor.
2618      CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
2619        : edge_map(_edge_map), node_map(_node_map) {}
2620
2621      /// \brief The subscript operator.
2622      ///
2623      /// The subscript operator.
2624      void set(const Edge& edge, const Value& val) {
2625        if (Parent::origEdge(edge)) {
2626          edge_map.set(edge, val);
2627        } else {
2628          node_map.set(edge, val);
2629        }
2630      }
2631
2632      /// \brief The const subscript operator.
2633      ///
2634      /// The const subscript operator.
2635      Value operator[](const Key& edge) const {
2636        if (Parent::origEdge(edge)) {
2637          return edge_map[edge];
2638        } else {
2639          return node_map[edge];
2640        }
2641      }     
2642
2643      /// \brief The const subscript operator.
2644      ///
2645      /// The const subscript operator.
2646      Value& operator[](const Key& edge) {
2647        if (Parent::origEdge(edge)) {
2648          return edge_map[edge];
2649        } else {
2650          return node_map[edge];
2651        }
2652      }     
2653     
2654    private:
2655      GraphEdgeMap& edge_map;
2656      GraphNodeMap& node_map;
2657    };
2658                   
2659    /// \brief Just gives back a combined edge map.
2660    ///
2661    /// Just gives back a combined edge map.
2662    template <typename GraphEdgeMap, typename GraphNodeMap>
2663    static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
2664    combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2665      return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
2666    }
2667
2668    template <typename GraphEdgeMap, typename GraphNodeMap>
2669    static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
2670    combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
2671      return CombinedEdgeMap<const GraphEdgeMap,
2672        GraphNodeMap>(edge_map, node_map);
2673    }
2674
2675    template <typename GraphEdgeMap, typename GraphNodeMap>
2676    static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
2677    combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
2678      return CombinedEdgeMap<GraphEdgeMap,
2679        const GraphNodeMap>(edge_map, node_map);
2680    }
2681
2682    template <typename GraphEdgeMap, typename GraphNodeMap>
2683    static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
2684    combinedEdgeMap(const GraphEdgeMap& edge_map,
2685                    const GraphNodeMap& node_map) {
2686      return CombinedEdgeMap<const GraphEdgeMap,
2687        const GraphNodeMap>(edge_map, node_map);
2688    }
2689
2690  };
2691
[2084]2692  /// \brief Just gives back a split graph adaptor
2693  ///
2694  /// Just gives back a split graph adaptor
2695  template<typename Graph>
2696  SplitGraphAdaptor<Graph>
2697  splitGraphAdaptor(const Graph& graph) {
2698    return SplitGraphAdaptor<Graph>(graph);
2699  }
2700
[1697]2701
[921]2702} //namespace lemon
[556]2703
[1401]2704#endif //LEMON_GRAPH_ADAPTOR_H
[556]2705
Note: See TracBrowser for help on using the repository browser.