COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2079:7fe378247fea

Last change on this file since 2079:7fe378247fea was 2079:7fe378247fea, checked in by Balazs Dezso, 14 years ago

Remade SplitGraphAdaptor?

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