COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2034:b71f8ff62046

Last change on this file since 2034:b71f8ff62046 was 2034:b71f8ff62046, checked in by Balazs Dezso, 14 years ago

Edmonds-Karp MaxFlow?
ResGraphAdaptor? with Tolerance

File size: 61.1 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 <iostream>
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  ///\warning Graph adaptors are in even
49  ///more experimental state than the other
50  ///parts of the lib. Use them at you own risk.
51  ///
52  ///This is the base type for most of LEMON graph adaptors.
53  ///This class implements a trivial graph adaptor i.e. it only wraps the
54  ///functions and types of the graph. The purpose of this class is to
55  ///make easier implementing graph adaptors. E.g. if an adaptor is
56  ///considered which differs from the wrapped graph only in some of its
57  ///functions or types, then it can be derived from GraphAdaptor,
58  ///and only the
59  ///differences should be implemented.
60  ///
61  ///author Marton Makai
62  template<typename _Graph>
63  class GraphAdaptorBase {
64  public:
65    typedef _Graph Graph;
66    typedef GraphAdaptorBase Adaptor;
67    typedef Graph ParentGraph;
68
69  protected:
70    Graph* graph;
71    GraphAdaptorBase() : graph(0) { }
72    void setGraph(Graph& _graph) { graph=&_graph; }
73
74  public:
75    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
76
77    Graph& getGraph() { return *graph; }
78    const Graph& getGraph() const { return *graph; }
79 
80    typedef typename Graph::Node Node;
81    typedef typename Graph::Edge Edge;
82   
83    void first(Node& i) const { graph->first(i); }
84    void first(Edge& i) const { graph->first(i); }
85    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
86    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
87
88    void next(Node& i) const { graph->next(i); }
89    void next(Edge& i) const { graph->next(i); }
90    void nextIn(Edge& i) const { graph->nextIn(i); }
91    void nextOut(Edge& i) const { graph->nextOut(i); }
92
93    Node source(const Edge& e) const { return graph->source(e); }
94    Node target(const Edge& e) const { return graph->target(e); }
95
96    typedef NodeNumTagIndicator<Graph> NodeNumTag;
97    int nodeNum() const { return graph->nodeNum(); }
98   
99    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
100    int edgeNum() const { return graph->edgeNum(); }
101
102    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
103    Edge findEdge(const Node& source, const Node& target,
104                  const Edge& prev = INVALID) {
105      return graph->findEdge(source, target, prev);
106    }
107 
108    Node addNode() const {
109      return Node(graph->addNode());
110    }
111
112    Edge addEdge(const Node& source, const Node& target) const {
113      return Edge(graph->addEdge(source, target));
114    }
115
116    void erase(const Node& i) const { graph->erase(i); }
117    void erase(const Edge& i) const { graph->erase(i); }
118 
119    void clear() const { graph->clear(); }
120   
121    int id(const Node& v) const { return graph->id(v); }
122    int id(const Edge& e) const { return graph->id(e); }
123
124    Node fromNodeId(int id) const {
125      return graph->fromNodeId(id);
126    }
127
128    Edge fromEdgeId(int id) const {
129      return graph->fromEdgeId(id);
130    }
131
132    int maxNodeId() const {
133      return graph->maxNodeId();
134    }
135
136    int maxEdgeId() const {
137      return graph->maxEdgeId();
138    }
139
140    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
141
142    NodeNotifier& getNotifier(Node) const {
143      return graph->getNotifier(Node());
144    }
145
146    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
147
148    EdgeNotifier& getNotifier(Edge) const {
149      return graph->getNotifier(Edge());
150    }
151   
152    template <typename _Value>
153    class NodeMap : public Graph::template NodeMap<_Value> {
154    public:
155
156      typedef typename Graph::template NodeMap<_Value> Parent;
157
158      explicit NodeMap(const Adaptor& ga)
159        : Parent(*ga.graph) {}
160
161      NodeMap(const Adaptor& ga, const _Value& value)
162        : Parent(*ga.graph, value) { }
163
164      NodeMap& operator=(const NodeMap& cmap) {
165        return operator=<NodeMap>(cmap);
166      }
167
168      template <typename CMap>
169      NodeMap& operator=(const CMap& cmap) {
170        Parent::operator=(cmap);
171        return *this;
172      }
173     
174    };
175
176    template <typename _Value>
177    class EdgeMap : public Graph::template EdgeMap<_Value> {
178    public:
179     
180      typedef typename Graph::template EdgeMap<_Value> Parent;
181     
182      explicit EdgeMap(const Adaptor& ga)
183        : Parent(*ga.graph) {}
184
185      EdgeMap(const Adaptor& ga, const _Value& value)
186        : Parent(*ga.graph, value) {}
187
188      EdgeMap& operator=(const EdgeMap& cmap) {
189        return operator=<EdgeMap>(cmap);
190      }
191
192      template <typename CMap>
193      EdgeMap& operator=(const CMap& cmap) {
194        Parent::operator=(cmap);
195        return *this;
196      }
197
198    };
199
200  };
201
202  template <typename _Graph>
203  class GraphAdaptor :
204    public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
205  public:
206    typedef _Graph Graph;
207    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
208  protected:
209    GraphAdaptor() : Parent() { }
210
211  public:
212    explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
213  };
214
215  /// \brief Just gives back a graph adaptor
216  ///
217  /// Just gives back a graph adaptor which
218  /// should be provide original graph
219  template<typename Graph>
220  GraphAdaptor<const Graph>
221  graphAdaptor(const Graph& graph) {
222    return GraphAdaptor<const Graph>(graph);
223  }
224
225
226  template <typename _Graph>
227  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
228  public:
229    typedef _Graph Graph;
230    typedef GraphAdaptorBase<_Graph> Parent;
231  protected:
232    RevGraphAdaptorBase() : Parent() { }
233  public:
234    typedef typename Parent::Node Node;
235    typedef typename Parent::Edge Edge;
236
237    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
238    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
239
240    void nextIn(Edge& i) const { Parent::nextOut(i); }
241    void nextOut(Edge& i) const { Parent::nextIn(i); }
242
243    Node source(const Edge& e) const { return Parent::target(e); }
244    Node target(const Edge& e) const { return Parent::source(e); }
245
246    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
247    Edge findEdge(const Node& source, const Node& target,
248                  const Edge& prev = INVALID) {
249      return Parent::findEdge(target, source, prev);
250    }
251
252  };
253   
254
255  ///\brief A graph adaptor which reverses the orientation of the edges.
256  ///\ingroup graph_adaptors
257  ///
258  ///\warning Graph adaptors are in even more experimental
259  ///state than the other
260  ///parts of the lib. Use them at you own risk.
261  ///
262  /// If \c g is defined as
263  ///\code
264  /// ListGraph g;
265  ///\endcode
266  /// then
267  ///\code
268  /// RevGraphAdaptor<ListGraph> ga(g);
269  ///\endcode
270  ///implements the graph obtained from \c g by
271  /// reversing the orientation of its edges.
272
273  template<typename _Graph>
274  class RevGraphAdaptor :
275    public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
276  public:
277    typedef _Graph Graph;
278    typedef GraphAdaptorExtender<
279      RevGraphAdaptorBase<_Graph> > Parent;
280  protected:
281    RevGraphAdaptor() { }
282  public:
283    explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
284  };
285
286  /// \brief Just gives back a reverse graph adaptor
287  ///
288  /// Just gives back a reverse graph adaptor
289  template<typename Graph>
290  RevGraphAdaptor<const Graph>
291  revGraphAdaptor(const Graph& graph) {
292    return RevGraphAdaptor<const Graph>(graph);
293  }
294
295  template <typename _Graph, typename NodeFilterMap,
296            typename EdgeFilterMap, bool checked = true>
297  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
298  public:
299    typedef _Graph Graph;
300    typedef SubGraphAdaptorBase Adaptor;
301    typedef GraphAdaptorBase<_Graph> Parent;
302  protected:
303    NodeFilterMap* node_filter_map;
304    EdgeFilterMap* edge_filter_map;
305    SubGraphAdaptorBase() : Parent(),
306                            node_filter_map(0), edge_filter_map(0) { }
307
308    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
309      node_filter_map=&_node_filter_map;
310    }
311    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
312      edge_filter_map=&_edge_filter_map;
313    }
314
315  public:
316
317    typedef typename Parent::Node Node;
318    typedef typename Parent::Edge Edge;
319
320    void first(Node& i) const {
321      Parent::first(i);
322      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
323    }
324
325    void first(Edge& i) const {
326      Parent::first(i);
327      while (i!=INVALID && (!(*edge_filter_map)[i]
328             || !(*node_filter_map)[Parent::source(i)]
329             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
330    }
331
332    void firstIn(Edge& i, const Node& n) const {
333      Parent::firstIn(i, n);
334      while (i!=INVALID && (!(*edge_filter_map)[i]
335             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
336    }
337
338    void firstOut(Edge& i, const Node& n) const {
339      Parent::firstOut(i, n);
340      while (i!=INVALID && (!(*edge_filter_map)[i]
341             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
342    }
343
344    void next(Node& i) const {
345      Parent::next(i);
346      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
347    }
348
349    void next(Edge& i) const {
350      Parent::next(i);
351      while (i!=INVALID && (!(*edge_filter_map)[i]
352             || !(*node_filter_map)[Parent::source(i)]
353             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
354    }
355
356    void nextIn(Edge& i) const {
357      Parent::nextIn(i);
358      while (i!=INVALID && (!(*edge_filter_map)[i]
359             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
360    }
361
362    void nextOut(Edge& i) const {
363      Parent::nextOut(i);
364      while (i!=INVALID && (!(*edge_filter_map)[i]
365             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
366    }
367
368    ///\e
369
370    /// This function hides \c n in the graph, i.e. the iteration
371    /// jumps over it. This is done by simply setting the value of \c n 
372    /// to be false in the corresponding node-map.
373    void hide(const Node& n) const { node_filter_map->set(n, false); }
374
375    ///\e
376
377    /// This function hides \c e in the graph, i.e. the iteration
378    /// jumps over it. This is done by simply setting the value of \c e 
379    /// to be false in the corresponding edge-map.
380    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
381
382    ///\e
383
384    /// The value of \c n is set to be true in the node-map which stores
385    /// hide information. If \c n was hidden previuosly, then it is shown
386    /// again
387     void unHide(const Node& n) const { node_filter_map->set(n, true); }
388
389    ///\e
390
391    /// The value of \c e is set to be true in the edge-map which stores
392    /// hide information. If \c e was hidden previuosly, then it is shown
393    /// again
394    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
395
396    /// Returns true if \c n is hidden.
397   
398    ///\e
399    ///
400    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
401
402    /// Returns true if \c n is hidden.
403   
404    ///\e
405    ///
406    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
407
408    typedef False NodeNumTag;
409    typedef False EdgeNumTag;
410
411    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
412    Edge findEdge(const Node& source, const Node& target,
413                  const Edge& prev = INVALID) {
414      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
415        return INVALID;
416      }
417      Edge edge = Parent::findEdge(source, target, prev);
418      while (edge != INVALID && !(*edge_filter_map)[edge]) {
419        edge = Parent::findEdge(source, target, edge);
420      }
421      return edge;
422    }
423
424    template <typename _Value>
425    class NodeMap
426      : public SubMapExtender<Adaptor,
427                              typename Parent::template NodeMap<_Value> >
428    {
429    public:
430      typedef Adaptor Graph;
431      typedef SubMapExtender<Adaptor, typename Parent::
432                             template NodeMap<_Value> > Parent;
433   
434      NodeMap(const Graph& graph)
435        : Parent(graph) {}
436      NodeMap(const Graph& graph, const _Value& value)
437        : Parent(graph, value) {}
438   
439      NodeMap& operator=(const NodeMap& cmap) {
440        return operator=<NodeMap>(cmap);
441      }
442   
443      template <typename CMap>
444      NodeMap& operator=(const CMap& cmap) {
445        Parent::operator=(cmap);
446        return *this;
447      }
448    };
449
450    template <typename _Value>
451    class EdgeMap
452      : public SubMapExtender<Adaptor,
453                              typename Parent::template EdgeMap<_Value> >
454    {
455    public:
456      typedef Adaptor Graph;
457      typedef SubMapExtender<Adaptor, typename Parent::
458                             template EdgeMap<_Value> > Parent;
459   
460      EdgeMap(const Graph& graph)
461        : Parent(graph) {}
462      EdgeMap(const Graph& graph, const _Value& value)
463        : Parent(graph, value) {}
464   
465      EdgeMap& operator=(const EdgeMap& cmap) {
466        return operator=<EdgeMap>(cmap);
467      }
468   
469      template <typename CMap>
470      EdgeMap& operator=(const CMap& cmap) {
471        Parent::operator=(cmap);
472        return *this;
473      }
474    };
475
476  };
477
478  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
479  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
480    : public GraphAdaptorBase<_Graph> {
481  public:
482    typedef _Graph Graph;
483    typedef SubGraphAdaptorBase Adaptor;
484    typedef GraphAdaptorBase<_Graph> Parent;
485  protected:
486    NodeFilterMap* node_filter_map;
487    EdgeFilterMap* edge_filter_map;
488    SubGraphAdaptorBase() : Parent(),
489                            node_filter_map(0), edge_filter_map(0) { }
490
491    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
492      node_filter_map=&_node_filter_map;
493    }
494    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
495      edge_filter_map=&_edge_filter_map;
496    }
497
498  public:
499
500    typedef typename Parent::Node Node;
501    typedef typename Parent::Edge Edge;
502
503    void first(Node& i) const {
504      Parent::first(i);
505      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
506    }
507
508    void first(Edge& i) const {
509      Parent::first(i);
510      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
511    }
512
513    void firstIn(Edge& i, const Node& n) const {
514      Parent::firstIn(i, n);
515      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
516    }
517
518    void firstOut(Edge& i, const Node& n) const {
519      Parent::firstOut(i, n);
520      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
521    }
522
523    void next(Node& i) const {
524      Parent::next(i);
525      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
526    }
527    void next(Edge& i) const {
528      Parent::next(i);
529      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
530    }
531    void nextIn(Edge& i) const {
532      Parent::nextIn(i);
533      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
534    }
535
536    void nextOut(Edge& i) const {
537      Parent::nextOut(i);
538      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
539    }
540
541    ///\e
542
543    /// This function hides \c n in the graph, i.e. the iteration
544    /// jumps over it. This is done by simply setting the value of \c n 
545    /// to be false in the corresponding node-map.
546    void hide(const Node& n) const { node_filter_map->set(n, false); }
547
548    ///\e
549
550    /// This function hides \c e in the graph, i.e. the iteration
551    /// jumps over it. This is done by simply setting the value of \c e 
552    /// to be false in the corresponding edge-map.
553    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
554
555    ///\e
556
557    /// The value of \c n is set to be true in the node-map which stores
558    /// hide information. If \c n was hidden previuosly, then it is shown
559    /// again
560     void unHide(const Node& n) const { node_filter_map->set(n, true); }
561
562    ///\e
563
564    /// The value of \c e is set to be true in the edge-map which stores
565    /// hide information. If \c e was hidden previuosly, then it is shown
566    /// again
567    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
568
569    /// Returns true if \c n is hidden.
570   
571    ///\e
572    ///
573    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
574
575    /// Returns true if \c n is hidden.
576   
577    ///\e
578    ///
579    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
580
581    typedef False NodeNumTag;
582    typedef False EdgeNumTag;
583
584    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
585    Edge findEdge(const Node& source, const Node& target,
586                  const Edge& prev = INVALID) {
587      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
588        return INVALID;
589      }
590      Edge edge = Parent::findEdge(source, target, prev);
591      while (edge != INVALID && !(*edge_filter_map)[edge]) {
592        edge = Parent::findEdge(source, target, edge);
593      }
594      return edge;
595    }
596
597    template <typename _Value>
598    class NodeMap
599      : public SubMapExtender<Adaptor,
600                              typename Parent::template NodeMap<_Value> >
601    {
602    public:
603      typedef Adaptor Graph;
604      typedef SubMapExtender<Adaptor, typename Parent::
605                             template NodeMap<_Value> > Parent;
606   
607      NodeMap(const Graph& graph)
608        : Parent(graph) {}
609      NodeMap(const Graph& graph, const _Value& value)
610        : Parent(graph, value) {}
611   
612      NodeMap& operator=(const NodeMap& cmap) {
613        return operator=<NodeMap>(cmap);
614      }
615   
616      template <typename CMap>
617      NodeMap& operator=(const CMap& cmap) {
618        Parent::operator=(cmap);
619        return *this;
620      }
621    };
622
623    template <typename _Value>
624    class EdgeMap
625      : public SubMapExtender<Adaptor,
626                              typename Parent::template EdgeMap<_Value> >
627    {
628    public:
629      typedef Adaptor Graph;
630      typedef SubMapExtender<Adaptor, typename Parent::
631                             template EdgeMap<_Value> > Parent;
632   
633      EdgeMap(const Graph& graph)
634        : Parent(graph) {}
635      EdgeMap(const Graph& graph, const _Value& value)
636        : Parent(graph, value) {}
637   
638      EdgeMap& operator=(const EdgeMap& cmap) {
639        return operator=<EdgeMap>(cmap);
640      }
641   
642      template <typename CMap>
643      EdgeMap& operator=(const CMap& cmap) {
644        Parent::operator=(cmap);
645        return *this;
646      }
647    };
648
649  };
650
651  /// \brief A graph adaptor for hiding nodes and edges from a graph.
652  /// \ingroup graph_adaptors
653  ///
654  /// \warning Graph adaptors are in even more experimental state than the
655  /// other parts of the lib. Use them at you own risk.
656  ///
657  /// SubGraphAdaptor shows the graph with filtered node-set and
658  /// edge-set. If the \c checked parameter is true then it filters the edgeset
659  /// to do not get invalid edges without source or target.
660  /// Let \f$ G=(V, A) \f$ be a directed graph
661  /// and suppose that the graph instance \c g of type ListGraph
662  /// implements \f$ G \f$.
663  /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
664  /// on the node-set and edge-set.
665  /// SubGraphAdaptor<...>::NodeIt iterates
666  /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
667  /// SubGraphAdaptor<...>::EdgeIt iterates
668  /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
669  /// SubGraphAdaptor<...>::OutEdgeIt and
670  /// SubGraphAdaptor<...>::InEdgeIt iterates
671  /// only on edges leaving and entering a specific node which have true value.
672  ///
673  /// If the \c checked template parameter is false then we have to note that
674  /// the node-iterator cares only the filter on the node-set, and the
675  /// edge-iterator cares only the filter on the edge-set.
676  /// This way the edge-map
677  /// should filter all edges which's source or target is filtered by the
678  /// node-filter.
679  ///\code
680  /// typedef ListGraph Graph;
681  /// Graph g;
682  /// typedef Graph::Node Node;
683  /// typedef Graph::Edge Edge;
684  /// Node u=g.addNode(); //node of id 0
685  /// Node v=g.addNode(); //node of id 1
686  /// Node e=g.addEdge(u, v); //edge of id 0
687  /// Node f=g.addEdge(v, u); //edge of id 1
688  /// Graph::NodeMap<bool> nm(g, true);
689  /// nm.set(u, false);
690  /// Graph::EdgeMap<bool> em(g, true);
691  /// em.set(e, false);
692  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
693  /// SubGA ga(g, nm, em);
694  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
695  /// std::cout << ":-)" << std::endl;
696  /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
697  ///\endcode
698  /// The output of the above code is the following.
699  ///\code
700  /// 1
701  /// :-)
702  /// 1
703  ///\endcode
704  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
705  /// \c Graph::Node that is why \c g.id(n) can be applied.
706  ///
707  /// For other examples see also the documentation of NodeSubGraphAdaptor and
708  /// EdgeSubGraphAdaptor.
709  ///
710  /// \author Marton Makai
711
712  template<typename _Graph, typename NodeFilterMap,
713           typename EdgeFilterMap, bool checked = true>
714  class SubGraphAdaptor :
715    public GraphAdaptorExtender<
716    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
717  public:
718    typedef _Graph Graph;
719    typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
720                                                      EdgeFilterMap, checked> >
721    Parent;
722
723  protected:
724    SubGraphAdaptor() { }
725  public:
726
727    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
728                    EdgeFilterMap& _edge_filter_map) {
729      setGraph(_graph);
730      setNodeFilterMap(_node_filter_map);
731      setEdgeFilterMap(_edge_filter_map);
732    }
733
734  };
735
736  /// \brief Just gives back a sub graph adaptor
737  ///
738  /// Just gives back a sub graph adaptor
739  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
740  SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
741  subGraphAdaptor(const Graph& graph,
742                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
743    return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
744      (graph, nfm, efm);
745  }
746
747  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
748  SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
749  subGraphAdaptor(const Graph& graph,
750                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
751    return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
752      (graph, nfm, efm);
753  }
754
755  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
756  SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
757  subGraphAdaptor(const Graph& graph,
758                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
759    return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
760      (graph, nfm, efm);
761  }
762
763  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
764  SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
765  subGraphAdaptor(const Graph& graph,
766                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
767    return SubGraphAdaptor<const Graph, const NodeFilterMap,
768      const EdgeFilterMap>(graph, nfm, efm);
769  }
770
771
772
773  ///\brief An adaptor for hiding nodes from a graph.
774  ///\ingroup graph_adaptors
775  ///
776  ///\warning Graph adaptors are in even more experimental state
777  ///than the other
778  ///parts of the lib. Use them at you own risk.
779  ///
780  ///An adaptor for hiding nodes from a graph.
781  ///This adaptor specializes SubGraphAdaptor in the way that only
782  ///the node-set
783  ///can be filtered. In usual case the checked parameter is true, we get the
784  ///induced subgraph. But if the checked parameter is false then we can only
785  ///filter only isolated nodes.
786  ///\author Marton Makai
787  template<typename Graph, typename NodeFilterMap, bool checked = true>
788  class NodeSubGraphAdaptor :
789    public SubGraphAdaptor<Graph, NodeFilterMap,
790                           ConstMap<typename Graph::Edge,bool>, checked> {
791  public:
792
793    typedef SubGraphAdaptor<Graph, NodeFilterMap,
794                            ConstMap<typename Graph::Edge,bool>, checked >
795    Parent;
796
797  protected:
798    ConstMap<typename Graph::Edge, bool> const_true_map;
799
800    NodeSubGraphAdaptor() : const_true_map(true) {
801      Parent::setEdgeFilterMap(const_true_map);
802    }
803
804  public:
805
806    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
807      Parent(), const_true_map(true) {
808      Parent::setGraph(_graph);
809      Parent::setNodeFilterMap(_node_filter_map);
810      Parent::setEdgeFilterMap(const_true_map);
811    }
812
813  };
814
815
816  /// \brief Just gives back a node sub graph adaptor
817  ///
818  /// Just gives back a node sub graph adaptor
819  template<typename Graph, typename NodeFilterMap>
820  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
821  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
822    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
823  }
824
825  template<typename Graph, typename NodeFilterMap>
826  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
827  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
828    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
829  }
830
831  ///\brief An adaptor for hiding edges from a graph.
832  ///
833  ///\warning Graph adaptors are in even more experimental state
834  ///than the other parts of the lib. Use them at you own risk.
835  ///
836  ///An adaptor for hiding edges from a graph.
837  ///This adaptor specializes SubGraphAdaptor in the way that
838  ///only the edge-set
839  ///can be filtered. The usefulness of this adaptor is demonstrated in the
840  ///problem of searching a maximum number of edge-disjoint shortest paths
841  ///between
842  ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
843  ///non-negative edge-lengths. Note that
844  ///the comprehension of the presented solution
845  ///need's some elementary knowledge from combinatorial optimization.
846  ///
847  ///If a single shortest path is to be
848  ///searched between \c s and \c t, then this can be done easily by
849  ///applying the Dijkstra algorithm. What happens, if a maximum number of
850  ///edge-disjoint shortest paths is to be computed. It can be proved that an
851  ///edge can be in a shortest path if and only
852  ///if it is tight with respect to
853  ///the potential function computed by Dijkstra.
854  ///Moreover, any path containing
855  ///only such edges is a shortest one.
856  ///Thus we have to compute a maximum number
857  ///of edge-disjoint paths between \c s and \c t in
858  ///the graph which has edge-set
859  ///all the tight edges. The computation will be demonstrated
860  ///on the following
861  ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
862  ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
863  ///If you are interested in more demo programs, you can use
864  ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
865  ///The .dot file of the following figure was generated by 
866  ///the demo program \ref dim_to_dot.cc.
867  ///
868  ///\dot
869  ///digraph lemon_dot_example {
870  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
871  ///n0 [ label="0 (s)" ];
872  ///n1 [ label="1" ];
873  ///n2 [ label="2" ];
874  ///n3 [ label="3" ];
875  ///n4 [ label="4" ];
876  ///n5 [ label="5" ];
877  ///n6 [ label="6 (t)" ];
878  ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
879  ///n5 ->  n6 [ label="9, length:4" ];
880  ///n4 ->  n6 [ label="8, length:2" ];
881  ///n3 ->  n5 [ label="7, length:1" ];
882  ///n2 ->  n5 [ label="6, length:3" ];
883  ///n2 ->  n6 [ label="5, length:5" ];
884  ///n2 ->  n4 [ label="4, length:2" ];
885  ///n1 ->  n4 [ label="3, length:3" ];
886  ///n0 ->  n3 [ label="2, length:1" ];
887  ///n0 ->  n2 [ label="1, length:2" ];
888  ///n0 ->  n1 [ label="0, length:3" ];
889  ///}
890  ///\enddot
891  ///
892  ///\code
893  ///Graph g;
894  ///Node s, t;
895  ///LengthMap length(g);
896  ///
897  ///readDimacs(std::cin, g, length, s, t);
898  ///
899  ///cout << "edges with lengths (of form id, source--length->target): " << endl;
900  ///for(EdgeIt e(g); e!=INVALID; ++e)
901  ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
902  ///       << length[e] << "->" << g.id(g.target(e)) << endl;
903  ///
904  ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
905  ///\endcode
906  ///Next, the potential function is computed with Dijkstra.
907  ///\code
908  ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
909  ///Dijkstra dijkstra(g, length);
910  ///dijkstra.run(s);
911  ///\endcode
912  ///Next, we consrtruct a map which filters the edge-set to the tight edges.
913  ///\code
914  ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
915  ///  TightEdgeFilter;
916  ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
917  ///
918  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
919  ///SubGA ga(g, tight_edge_filter);
920  ///\endcode
921  ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
922  ///with a max flow algorithm Preflow.
923  ///\code
924  ///ConstMap<Edge, int> const_1_map(1);
925  ///Graph::EdgeMap<int> flow(g, 0);
926  ///
927  ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
928  ///  preflow(ga, s, t, const_1_map, flow);
929  ///preflow.run();
930  ///\endcode
931  ///Last, the output is:
932  ///\code 
933  ///cout << "maximum number of edge-disjoint shortest path: "
934  ///     << preflow.flowValue() << endl;
935  ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
936  ///     << endl;
937  ///for(EdgeIt e(g); e!=INVALID; ++e)
938  ///  if (flow[e])
939  ///    cout << " " << g.id(g.source(e)) << "--"
940  ///         << length[e] << "->" << g.id(g.target(e)) << endl;
941  ///\endcode
942  ///The program has the following (expected :-)) output:
943  ///\code
944  ///edges with lengths (of form id, source--length->target):
945  /// 9, 5--4->6
946  /// 8, 4--2->6
947  /// 7, 3--1->5
948  /// 6, 2--3->5
949  /// 5, 2--5->6
950  /// 4, 2--2->4
951  /// 3, 1--3->4
952  /// 2, 0--1->3
953  /// 1, 0--2->2
954  /// 0, 0--3->1
955  ///s: 0 t: 6
956  ///maximum number of edge-disjoint shortest path: 2
957  ///edges of the maximum number of edge-disjoint shortest s-t paths:
958  /// 9, 5--4->6
959  /// 8, 4--2->6
960  /// 7, 3--1->5
961  /// 4, 2--2->4
962  /// 2, 0--1->3
963  /// 1, 0--2->2
964  ///\endcode
965  ///
966  ///\author Marton Makai
967  template<typename Graph, typename EdgeFilterMap>
968  class EdgeSubGraphAdaptor :
969    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
970                           EdgeFilterMap, false> {
971  public:
972    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
973                            EdgeFilterMap, false> Parent;
974  protected:
975    ConstMap<typename Graph::Node, bool> const_true_map;
976
977    EdgeSubGraphAdaptor() : const_true_map(true) {
978      Parent::setNodeFilterMap(const_true_map);
979    }
980
981  public:
982
983    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
984      Parent(), const_true_map(true) {
985      Parent::setGraph(_graph);
986      Parent::setNodeFilterMap(const_true_map);
987      Parent::setEdgeFilterMap(_edge_filter_map);
988    }
989
990  };
991
992  /// \brief Just gives back an edge sub graph adaptor
993  ///
994  /// Just gives back an edge sub graph adaptor
995  template<typename Graph, typename EdgeFilterMap>
996  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
997  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
998    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
999  }
1000
1001  template<typename Graph, typename EdgeFilterMap>
1002  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
1003  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
1004    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
1005  }
1006
1007  template <typename _Graph, typename Enable = void>
1008  class UndirGraphAdaptorBase :
1009    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
1010  public:
1011    typedef _Graph Graph;
1012    typedef UndirGraphAdaptorBase Adaptor;
1013    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
1014
1015  protected:
1016
1017    UndirGraphAdaptorBase() : Parent() {}
1018
1019  public:
1020
1021    typedef typename Parent::UEdge UEdge;
1022    typedef typename Parent::Edge Edge;
1023
1024  private:
1025   
1026    template <typename _Value>
1027    class EdgeMapBase {
1028    private:
1029     
1030      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1031     
1032    public:
1033
1034      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1035
1036      typedef _Value Value;
1037      typedef Edge Key;
1038     
1039      EdgeMapBase(const Adaptor& adaptor) :
1040        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1041
1042      EdgeMapBase(const Adaptor& adaptor, const Value& v)
1043        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1044     
1045      void set(const Edge& e, const Value& a) {
1046        if (Parent::direction(e)) {
1047          forward_map.set(e, a);
1048        } else {
1049          backward_map.set(e, a);
1050        }
1051      }
1052
1053      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1054        if (Parent::direction(e)) {
1055          return forward_map[e];
1056        } else {
1057          return backward_map[e];
1058        }
1059      }
1060
1061      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1062        if (Parent::direction(e)) {
1063          return forward_map[e];
1064        } else {
1065          return backward_map[e];
1066        }
1067      }
1068
1069    protected:
1070
1071      MapImpl forward_map, backward_map;
1072
1073    };
1074
1075  public:
1076
1077    template <typename _Value>
1078    class EdgeMap
1079      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1080    {
1081    public:
1082      typedef Adaptor Graph;
1083      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1084   
1085      EdgeMap(const Graph& graph)
1086        : Parent(graph) {}
1087      EdgeMap(const Graph& graph, const _Value& value)
1088        : Parent(graph, value) {}
1089   
1090      EdgeMap& operator=(const EdgeMap& cmap) {
1091        return operator=<EdgeMap>(cmap);
1092      }
1093   
1094      template <typename CMap>
1095      EdgeMap& operator=(const CMap& cmap) {
1096        Parent::operator=(cmap);
1097        return *this;
1098      }
1099    };
1100       
1101    template <typename _Value>
1102    class UEdgeMap : public Graph::template EdgeMap<_Value> {
1103    public:
1104     
1105      typedef typename Graph::template EdgeMap<_Value> Parent;
1106     
1107      explicit UEdgeMap(const Adaptor& ga)
1108        : Parent(*ga.graph) {}
1109
1110      UEdgeMap(const Adaptor& ga, const _Value& value)
1111        : Parent(*ga.graph, value) {}
1112
1113      UEdgeMap& operator=(const UEdgeMap& cmap) {
1114        return operator=<UEdgeMap>(cmap);
1115      }
1116
1117      template <typename CMap>
1118      UEdgeMap& operator=(const CMap& cmap) {
1119        Parent::operator=(cmap);
1120        return *this;
1121      }
1122
1123    };
1124     
1125  };
1126
1127  template <typename _Graph>
1128  class UndirGraphAdaptorBase<
1129    _Graph, typename enable_if<
1130    typename _Graph::EdgeNotifier::Notifier>::type >
1131      : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
1132  public:
1133
1134    typedef _Graph Graph;
1135    typedef UndirGraphAdaptorBase Adaptor;
1136    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
1137
1138  protected:
1139
1140    UndirGraphAdaptorBase()
1141      : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
1142
1143    void setGraph(_Graph& graph) {
1144      Parent::setGraph(graph);
1145      edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
1146    }
1147
1148  public:
1149
1150    ~UndirGraphAdaptorBase() {
1151      edge_notifier.clear();
1152    }
1153
1154    int maxId(typename Parent::Edge) const {
1155      return Parent::maxEdgeId();
1156    }
1157
1158
1159    typedef typename Parent::UEdge UEdge;
1160    typedef typename Parent::Edge Edge;
1161
1162    typedef typename Parent::EdgeNotifier UEdgeNotifier;
1163
1164    using Parent::getNotifier;
1165
1166    typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
1167    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1168
1169  protected:
1170
1171    class NotifierProxy : public UEdgeNotifier::ObserverBase {
1172    public:
1173
1174      typedef typename UEdgeNotifier::ObserverBase Parent;
1175      typedef UndirGraphAdaptorBase AdaptorBase;
1176     
1177      NotifierProxy(EdgeNotifier& _edge_notifier)
1178        : Parent(), edge_notifier(_edge_notifier) {
1179      }
1180
1181      virtual ~NotifierProxy() {
1182        if (Parent::attached()) {
1183          Parent::detach();
1184        }
1185      }
1186
1187      void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
1188        Parent::attach(_uedge_notifier);
1189      }
1190
1191     
1192    protected:
1193
1194      virtual void add(const UEdge& uedge) {
1195        std::vector<Edge> edges;
1196        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
1197        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
1198        edge_notifier.add(edges);
1199      }
1200      virtual void add(const std::vector<UEdge>& uedges) {
1201        std::vector<Edge> edges;
1202        for (int i = 0; i < (int)uedges.size(); ++i) {
1203          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
1204          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
1205        }
1206        edge_notifier.add(edges);
1207      }
1208      virtual void erase(const UEdge& uedge) {
1209        std::vector<Edge> edges;
1210        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
1211        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
1212        edge_notifier.erase(edges);
1213      }
1214      virtual void erase(const std::vector<UEdge>& uedges) {
1215        std::vector<Edge> edges;
1216        for (int i = 0; i < (int)uedges.size(); ++i) {
1217          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
1218          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
1219        }
1220        edge_notifier.erase(edges);
1221      }
1222      virtual void build() {
1223        edge_notifier.build();
1224      }
1225      virtual void clear() {
1226        edge_notifier.clear();
1227      }
1228
1229      EdgeNotifier& edge_notifier;
1230    };
1231
1232
1233    mutable EdgeNotifier edge_notifier;
1234    NotifierProxy edge_notifier_proxy;
1235
1236  private:
1237   
1238    template <typename _Value>
1239    class EdgeMapBase {
1240    private:
1241     
1242      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1243     
1244    public:
1245
1246      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1247
1248      typedef _Value Value;
1249      typedef Edge Key;
1250     
1251      EdgeMapBase(const Adaptor& adaptor) :
1252        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1253
1254      EdgeMapBase(const Adaptor& adaptor, const Value& v)
1255        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1256     
1257      void set(const Edge& e, const Value& a) {
1258        if (Parent::direction(e)) {
1259          forward_map.set(e, a);
1260        } else {
1261          backward_map.set(e, a);
1262        }
1263      }
1264
1265      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1266        if (Parent::direction(e)) {
1267          return forward_map[e];
1268        } else {
1269          return backward_map[e];
1270        }
1271      }
1272
1273      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1274        if (Parent::direction(e)) {
1275          return forward_map[e];
1276        } else {
1277          return backward_map[e];
1278        }
1279      }
1280
1281    protected:
1282
1283      MapImpl forward_map, backward_map;
1284
1285    };
1286
1287  public:
1288
1289    template <typename _Value>
1290    class EdgeMap
1291      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1292    {
1293    public:
1294      typedef Adaptor Graph;
1295      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1296   
1297      EdgeMap(const Graph& graph)
1298        : Parent(graph) {}
1299      EdgeMap(const Graph& graph, const _Value& value)
1300        : Parent(graph, value) {}
1301   
1302      EdgeMap& operator=(const EdgeMap& cmap) {
1303        return operator=<EdgeMap>(cmap);
1304      }
1305   
1306      template <typename CMap>
1307      EdgeMap& operator=(const CMap& cmap) {
1308        Parent::operator=(cmap);
1309        return *this;
1310      }
1311    };
1312       
1313    template <typename _Value>
1314    class UEdgeMap : public Graph::template EdgeMap<_Value> {
1315    public:
1316     
1317      typedef typename Graph::template EdgeMap<_Value> Parent;
1318     
1319      explicit UEdgeMap(const Adaptor& ga)
1320        : Parent(*ga.graph) {}
1321
1322      UEdgeMap(const Adaptor& ga, const _Value& value)
1323        : Parent(*ga.graph, value) {}
1324
1325      UEdgeMap& operator=(const UEdgeMap& cmap) {
1326        return operator=<UEdgeMap>(cmap);
1327      }
1328
1329      template <typename CMap>
1330      UEdgeMap& operator=(const CMap& cmap) {
1331        Parent::operator=(cmap);
1332        return *this;
1333      }
1334
1335    };
1336     
1337  };
1338
1339  ///\brief An undirected graph is made from a directed graph by an adaptor
1340  ///\ingroup graph_adaptors
1341  ///
1342  /// Undocumented, untested!!!
1343  /// If somebody knows nice demo application, let's polulate it.
1344  ///
1345  /// \author Marton Makai
1346  template<typename _Graph>
1347  class UndirGraphAdaptor :
1348    public UGraphAdaptorExtender<
1349    UndirGraphAdaptorBase<_Graph> > {
1350  public:
1351    typedef _Graph Graph;
1352    typedef UGraphAdaptorExtender<
1353      UndirGraphAdaptorBase<_Graph> > Parent;
1354  protected:
1355    UndirGraphAdaptor() { }
1356  public:
1357    UndirGraphAdaptor(_Graph& _graph) {
1358      setGraph(_graph);
1359    }
1360
1361    template <typename _ForwardMap, typename _BackwardMap>
1362    class CombinedEdgeMap {
1363    public:
1364     
1365      typedef _ForwardMap ForwardMap;
1366      typedef _BackwardMap BackwardMap;
1367
1368      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1369
1370      typedef typename ForwardMap::Value Value;
1371      typedef typename Parent::Edge Key;
1372     
1373      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
1374
1375      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1376        : forward_map(&_forward_map), backward_map(&_backward_map) {}
1377     
1378      void set(const Key& e, const Value& a) {
1379        if (Parent::direction(e)) {
1380          forward_map->set(e, a);
1381        } else {
1382          backward_map->set(e, a);
1383        }
1384      }
1385
1386      typename MapTraits<ForwardMap>::ConstReturnValue
1387      operator[](const Key& e) const {
1388        if (Parent::direction(e)) {
1389          return (*forward_map)[e];
1390        } else {
1391          return (*backward_map)[e];
1392        }
1393      }
1394
1395      typename MapTraits<ForwardMap>::ReturnValue
1396      operator[](const Key& e) {
1397        if (Parent::direction(e)) {
1398          return (*forward_map)[e];
1399        } else {
1400          return (*backward_map)[e];
1401        }
1402      }
1403
1404      void setForwardMap(ForwardMap& _forward_map) {
1405        forward_map = &_forward_map;
1406      }
1407
1408      void setBackwardMap(BackwardMap& _backward_map) {
1409        backward_map = &_backward_map;
1410      }
1411
1412    protected:
1413
1414      ForwardMap* forward_map;
1415      BackwardMap* backward_map;
1416
1417    };
1418
1419  };
1420
1421  /// \brief Just gives back an undir graph adaptor
1422  ///
1423  /// Just gives back an undir graph adaptor
1424  template<typename Graph>
1425  UndirGraphAdaptor<const Graph>
1426  undirGraphAdaptor(const Graph& graph) {
1427    return UndirGraphAdaptor<const Graph>(graph);
1428  }
1429
1430  template<typename Graph, typename Number, 
1431           typename CapacityMap, typename FlowMap,
1432           typename Tolerance = Tolerance<Number> >
1433  class ResForwardFilter {
1434    const CapacityMap* capacity;
1435    const FlowMap* flow;
1436    Tolerance tolerance;
1437  public:
1438    typedef typename Graph::Edge Key;
1439    typedef bool Value;
1440
1441    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1442                     const Tolerance& _tolerance = Tolerance())
1443      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1444
1445    ResForwardFilter(const Tolerance& _tolerance)
1446      : capacity(0), flow(0), tolerance(_tolerance)  { }
1447
1448    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1449    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1450
1451    bool operator[](const typename Graph::Edge& e) const {
1452      return tolerance.less((*flow)[e], (*capacity)[e]);
1453    }
1454  };
1455
1456  template<typename Graph, typename Number,
1457           typename CapacityMap, typename FlowMap,
1458           typename Tolerance = Tolerance<Number> >
1459  class ResBackwardFilter {
1460    const CapacityMap* capacity;
1461    const FlowMap* flow;
1462    Tolerance tolerance;
1463  public:
1464    typedef typename Graph::Edge Key;
1465    typedef bool Value;
1466
1467    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
1468                      const Tolerance& _tolerance = Tolerance())
1469      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
1470    ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
1471      : capacity(0), flow(0), tolerance(_tolerance) { }
1472    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1473    void setFlow(const FlowMap& _flow) { flow = &_flow; }
1474    bool operator[](const typename Graph::Edge& e) const {
1475      return tolerance.less(0, Number((*flow)[e]));
1476    }
1477  };
1478
1479 
1480  ///\brief An adaptor for composing the residual
1481  ///graph for directed flow and circulation problems.
1482  ///\ingroup graph_adaptors
1483  ///
1484  ///An adaptor for composing the residual graph for
1485  ///directed flow and circulation problems.
1486  ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a
1487  ///number type. Let moreover
1488  ///\f$ f,c:A\to F \f$, be functions on the edge-set.
1489  ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a flow
1490  ///and \f$ c \f$ for a capacity function.   
1491  ///Suppose that a graph instange \c g of type
1492  ///\c ListGraph implements \f$ G \f$.
1493  ///\code
1494  ///  ListGraph g;
1495  ///\endcode
1496  ///Then RevGraphAdaptor implements the graph structure with node-set
1497  ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where
1498  ///\f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1499  ///\f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$,
1500  ///i.e. the so called residual graph.
1501  ///When we take the union \f$ A_{forward}\cup A_{backward} \f$,
1502  ///multilicities are counted, i.e. if an edge is in both
1503  ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it
1504  ///appears twice.
1505  ///The following code shows how
1506  ///such an instance can be constructed.
1507  ///\code
1508  ///typedef ListGraph Graph;
1509  ///Graph::EdgeMap<int> f(g);
1510  ///Graph::EdgeMap<int> c(g);
1511  ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
1512  ///\endcode
1513  ///\author Marton Makai
1514  ///
1515  template<typename Graph, typename Number,
1516           typename CapacityMap, typename FlowMap,
1517           typename Tolerance = Tolerance<Number> >
1518  class ResGraphAdaptor :
1519    public EdgeSubGraphAdaptor<
1520    UndirGraphAdaptor<const Graph>,
1521    typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
1522    ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>, 
1523    ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
1524  public:
1525
1526    typedef UndirGraphAdaptor<const Graph> UGraph;
1527
1528    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
1529    ForwardFilter;
1530
1531    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
1532    BackwardFilter;
1533
1534    typedef typename UGraph::
1535    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1536    EdgeFilter;
1537
1538    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1539
1540  protected:
1541
1542    const CapacityMap* capacity;
1543    FlowMap* flow;
1544
1545    UGraph ugraph;
1546    ForwardFilter forward_filter;
1547    BackwardFilter backward_filter;
1548    EdgeFilter edge_filter;
1549
1550    void setCapacityMap(const CapacityMap& _capacity) {
1551      capacity=&_capacity;
1552      forward_filter.setCapacity(_capacity);
1553      backward_filter.setCapacity(_capacity);
1554    }
1555
1556    void setFlowMap(FlowMap& _flow) {
1557      flow=&_flow;
1558      forward_filter.setFlow(_flow);
1559      backward_filter.setFlow(_flow);
1560    }
1561
1562  public:
1563
1564    const Graph& getGraph() const { return ugraph.getGraph(); }
1565
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,
1571                    FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
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    {
1577      Parent::setGraph(ugraph);
1578      Parent::setEdgeFilterMap(edge_filter);
1579    }
1580
1581    typedef typename Parent::Edge Edge;
1582
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.
1599    void augment(const Edge& e, Number a) const {
1600      if (UGraph::direction(e)) {
1601        flow->set(e, (*flow)[e] + a);
1602      } else { 
1603        flow->set(e, (*flow)[e] - a);
1604      }
1605    }
1606
1607    /// \brief Returns the direction of the edge.
1608    ///
1609    /// Returns true when the edge is same oriented as the original edge.
1610    static bool forward(const Edge& e) {
1611      return UGraph::direction(e);
1612    }
1613
1614    /// \brief Returns the direction of the edge.
1615    ///
1616    /// Returns true when the edge is opposite oriented as the original edge.
1617    static bool backward(const Edge& e) {
1618      return !UGraph::direction(e);
1619    }
1620
1621    /// \brief Gives back the forward oriented residual edge.
1622    ///
1623    /// Gives back the forward oriented residual edge.
1624    static Edge forward(const typename Graph::Edge& e) {
1625      return UGraph::direct(e, true);
1626    }
1627
1628    /// \brief Gives back the backward oriented residual edge.
1629    ///
1630    /// Gives back the backward oriented residual edge.
1631    static Edge backward(const typename Graph::Edge& e) {
1632      return UGraph::direct(e, false);
1633    }
1634
1635    /// \brief Residual capacity map.
1636    ///
1637    /// In generic residual graphs the residual capacity can be obtained
1638    /// as a map.
1639    class ResCap {
1640    protected:
1641      const ResGraphAdaptor* res_graph;
1642    public:
1643      typedef Number Value;
1644      typedef Edge Key;
1645      ResCap(const ResGraphAdaptor& _res_graph)
1646        : res_graph(&_res_graph) {}
1647     
1648      Number operator[](const Edge& e) const {
1649        return res_graph->rescap(e);
1650      }
1651     
1652    };
1653
1654  };
1655
1656
1657
1658  template <typename _Graph, typename FirstOutEdgesMap>
1659  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1660  public:
1661    typedef _Graph Graph;
1662    typedef GraphAdaptorBase<_Graph> Parent;
1663  protected:
1664    FirstOutEdgesMap* first_out_edges;
1665    ErasingFirstGraphAdaptorBase() : Parent(),
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
1690  ///\brief For blocking flows.
1691  ///\ingroup graph_adaptors
1692  ///
1693  ///\warning Graph adaptors are in even more
1694  ///experimental state than the other
1695  ///parts of the lib. Use them at you own risk.
1696  ///
1697  ///This graph adaptor is used for on-the-fly
1698  ///Dinits blocking flow computations.
1699  ///For each node, an out-edge is stored which is used when the
1700  ///\code
1701  ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1702  ///\endcode
1703  ///is called.
1704  ///
1705  ///\author Marton Makai
1706  ///
1707  template <typename _Graph, typename FirstOutEdgesMap>
1708  class ErasingFirstGraphAdaptor :
1709    public GraphAdaptorExtender<
1710    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1711  public:
1712    typedef _Graph Graph;
1713    typedef GraphAdaptorExtender<
1714      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1715    ErasingFirstGraphAdaptor(Graph& _graph,
1716                             FirstOutEdgesMap& _first_out_edges) {
1717      setGraph(_graph);
1718      setFirstOutEdgesMap(_first_out_edges);
1719    }
1720
1721  };
1722
1723//   template <typename _Graph>
1724//   class SplitGraphAdaptorBase
1725//     : public GraphAdaptorBase<_Graph> {
1726//   public:
1727//     typedef GraphAdaptorBase<_Graph> Parent;
1728
1729//     class Node;
1730//     class Edge;
1731//     template <typename T> class NodeMap;
1732//     template <typename T> class EdgeMap;
1733   
1734
1735//     class Node : public Parent::Node {
1736//       friend class SplitGraphAdaptorBase;
1737//       template <typename T> friend class NodeMap;
1738//       typedef typename Parent::Node NodeParent;
1739//     private:
1740
1741//       bool entry;
1742//       Node(typename Parent::Node _node, bool _entry)
1743//      : Parent::Node(_node), entry(_entry) {}
1744     
1745//     public:
1746//       Node() {}
1747//       Node(Invalid) : NodeParent(INVALID), entry(true) {}
1748
1749//       bool operator==(const Node& node) const {
1750//      return NodeParent::operator==(node) && entry == node.entry;
1751//       }
1752     
1753//       bool operator!=(const Node& node) const {
1754//      return !(*this == node);
1755//       }
1756     
1757//       bool operator<(const Node& node) const {
1758//      return NodeParent::operator<(node) ||
1759//        (NodeParent::operator==(node) && entry < node.entry);
1760//       }
1761//     };
1762
1763//     /// \todo May we want VARIANT/union type
1764//     class Edge : public Parent::Edge {
1765//       friend class SplitGraphAdaptorBase;
1766//       template <typename T> friend class EdgeMap;
1767//     private:
1768//       typedef typename Parent::Edge EdgeParent;
1769//       typedef typename Parent::Node NodeParent;
1770//       NodeParent bind;
1771
1772//       Edge(const EdgeParent& edge, const NodeParent& node)
1773//      : EdgeParent(edge), bind(node) {}
1774//     public:
1775//       Edge() {}
1776//       Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
1777
1778//       bool operator==(const Edge& edge) const {
1779//      return EdgeParent::operator==(edge) && bind == edge.bind;
1780//       }
1781     
1782//       bool operator!=(const Edge& edge) const {
1783//      return !(*this == edge);
1784//       }
1785     
1786//       bool operator<(const Edge& edge) const {
1787//      return EdgeParent::operator<(edge) ||
1788//        (EdgeParent::operator==(edge) && bind < edge.bind);
1789//       }
1790//     };
1791
1792//     void first(Node& node) const {
1793//       Parent::first(node);
1794//       node.entry = true;
1795//     }
1796
1797//     void next(Node& node) const {
1798//       if (node.entry) {
1799//      node.entry = false;
1800//       } else {
1801//      node.entry = true;
1802//      Parent::next(node);
1803//       }
1804//     }
1805
1806//     void first(Edge& edge) const {
1807//       Parent::first(edge);
1808//       if ((typename Parent::Edge&)edge == INVALID) {
1809//      Parent::first(edge.bind);
1810//       } else {
1811//      edge.bind = INVALID;
1812//       }
1813//     }
1814
1815//     void next(Edge& edge) const {
1816//       if ((typename Parent::Edge&)edge != INVALID) {
1817//      Parent::next(edge);
1818//      if ((typename Parent::Edge&)edge == INVALID) {
1819//        Parent::first(edge.bind);
1820//      }
1821//       } else {
1822//      Parent::next(edge.bind);
1823//       }     
1824//     }
1825
1826//     void firstIn(Edge& edge, const Node& node) const {
1827//       if (node.entry) {
1828//      Parent::firstIn(edge, node);
1829//      edge.bind = INVALID;
1830//       } else {
1831//      (typename Parent::Edge&)edge = INVALID;
1832//      edge.bind = node;
1833//       }
1834//     }
1835
1836//     void nextIn(Edge& edge) const {
1837//       if ((typename Parent::Edge&)edge != INVALID) {
1838//      Parent::nextIn(edge);
1839//       } else {
1840//      edge.bind = INVALID;
1841//       }     
1842//     }
1843
1844//     void firstOut(Edge& edge, const Node& node) const {
1845//       if (!node.entry) {
1846//      Parent::firstOut(edge, node);
1847//      edge.bind = INVALID;
1848//       } else {
1849//      (typename Parent::Edge&)edge = INVALID;
1850//      edge.bind = node;
1851//       }
1852//     }
1853
1854//     void nextOut(Edge& edge) const {
1855//       if ((typename Parent::Edge&)edge != INVALID) {
1856//      Parent::nextOut(edge);
1857//       } else {
1858//      edge.bind = INVALID;
1859//       }
1860//     }
1861
1862//     Node source(const Edge& edge) const {
1863//       if ((typename Parent::Edge&)edge != INVALID) {
1864//      return Node(Parent::source(edge), false);
1865//       } else {
1866//      return Node(edge.bind, true);
1867//       }
1868//     }
1869
1870//     Node target(const Edge& edge) const {
1871//       if ((typename Parent::Edge&)edge != INVALID) {
1872//      return Node(Parent::target(edge), true);
1873//       } else {
1874//      return Node(edge.bind, false);
1875//       }
1876//     }
1877
1878//     static bool entryNode(const Node& node) {
1879//       return node.entry;
1880//     }
1881
1882//     static bool exitNode(const Node& node) {
1883//       return !node.entry;
1884//     }
1885
1886//     static Node getEntry(const typename Parent::Node& node) {
1887//       return Node(node, true);
1888//     }
1889
1890//     static Node getExit(const typename Parent::Node& node) {
1891//       return Node(node, false);
1892//     }
1893
1894//     static bool originalEdge(const Edge& edge) {
1895//       return (typename Parent::Edge&)edge != INVALID;
1896//     }
1897
1898//     static bool bindingEdge(const Edge& edge) {
1899//       return edge.bind != INVALID;
1900//     }
1901
1902//     static Node getBindedNode(const Edge& edge) {
1903//       return edge.bind;
1904//     }
1905
1906//     int nodeNum() const {
1907//       return Parent::nodeNum() * 2;
1908//     }
1909
1910//     typedef True EdgeNumTag;
1911   
1912//     int edgeNum() const {
1913//       return countEdges() + Parent::nodeNum();
1914//     }
1915
1916//     Edge findEdge(const Node& source, const Node& target,
1917//                const Edge& prev = INVALID) const {
1918//       if (exitNode(source) && entryNode(target)) {
1919//      return Parent::findEdge(source, target, prev);
1920//       } else {
1921//      if (prev == INVALID && entryNode(source) && exitNode(target) &&
1922//          (typename Parent::Node&)source == (typename Parent::Node&)target) {
1923//        return Edge(INVALID, source);
1924//      } else {
1925//        return INVALID;
1926//      }
1927//       }
1928//     }
1929   
1930//     template <typename T>
1931//     class NodeMap : public MapBase<Node, T> {
1932//       typedef typename Parent::template NodeMap<T> NodeImpl;
1933//     public:
1934//       NodeMap(const SplitGraphAdaptorBase& _graph)
1935//      : entry(_graph), exit(_graph) {}
1936//       NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1937//      : entry(_graph, t), exit(_graph, t) {}
1938     
1939//       void set(const Node& key, const T& val) {
1940//      if (key.entry) { entry.set(key, val); }
1941//      else {exit.set(key, val); }
1942//       }
1943     
1944//       typename MapTraits<NodeImpl>::ReturnValue
1945//       operator[](const Node& key) {
1946//      if (key.entry) { return entry[key]; }
1947//      else { return exit[key]; }
1948//       }
1949
1950//       typename MapTraits<NodeImpl>::ConstReturnValue
1951//       operator[](const Node& key) const {
1952//      if (key.entry) { return entry[key]; }
1953//      else { return exit[key]; }
1954//       }
1955
1956//     private:
1957//       NodeImpl entry, exit;
1958//     };
1959
1960//     template <typename T>
1961//     class EdgeMap : public MapBase<Edge, T> {
1962//       typedef typename Parent::template NodeMap<T> NodeImpl;
1963//       typedef typename Parent::template EdgeMap<T> EdgeImpl;
1964//     public:
1965//       EdgeMap(const SplitGraphAdaptorBase& _graph)
1966//      : bind(_graph), orig(_graph) {}
1967//       EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1968//      : bind(_graph, t), orig(_graph, t) {}
1969     
1970//       void set(const Edge& key, const T& val) {
1971//      if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
1972//      else {bind.set(key.bind, val); }
1973//       }
1974     
1975//       typename MapTraits<EdgeImpl>::ReturnValue
1976//       operator[](const Edge& key) {
1977//      if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1978//      else {return bind[key.bind]; }
1979//       }
1980
1981//       typename MapTraits<EdgeImpl>::ConstReturnValue
1982//       operator[](const Edge& key) const {
1983//      if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1984//      else {return bind[key.bind]; }
1985//       }
1986
1987//     private:
1988//       typename Parent::template NodeMap<T> bind;
1989//       typename Parent::template EdgeMap<T> orig;
1990//     };
1991
1992//     template <typename EntryMap, typename ExitMap>
1993//     class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
1994//     public:
1995//       typedef MapBase<Node, typename EntryMap::Value> Parent;
1996
1997//       typedef typename Parent::Key Key;
1998//       typedef typename Parent::Value Value;
1999
2000//       CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
2001//      : entryMap(_entryMap), exitMap(_exitMap) {}
2002
2003//       Value& operator[](const Key& key) {
2004//      if (key.entry) {
2005//        return entryMap[key];
2006//      } else {
2007//        return exitMap[key];
2008//      }
2009//       }
2010
2011//       Value operator[](const Key& key) const {
2012//      if (key.entry) {
2013//        return entryMap[key];
2014//      } else {
2015//        return exitMap[key];
2016//      }
2017//       }
2018
2019//       void set(const Key& key, const Value& value) {
2020//      if (key.entry) {
2021//        entryMap.set(key, value);
2022//      } else {
2023//        exitMap.set(key, value);
2024//      }
2025//       }
2026     
2027//     private:
2028     
2029//       EntryMap& entryMap;
2030//       ExitMap& exitMap;
2031     
2032//     };
2033
2034//     template <typename EdgeMap, typename NodeMap>
2035//     class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
2036//     public:
2037//       typedef MapBase<Edge, typename EdgeMap::Value> Parent;
2038
2039//       typedef typename Parent::Key Key;
2040//       typedef typename Parent::Value Value;
2041
2042//       CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
2043//      : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
2044
2045//       void set(const Edge& edge, const Value& val) {
2046//      if (SplitGraphAdaptorBase::originalEdge(edge)) {
2047//        edgeMap.set(edge, val);
2048//      } else {
2049//        nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
2050//      }
2051//       }
2052
2053//       Value operator[](const Key& edge) const {
2054//      if (SplitGraphAdaptorBase::originalEdge(edge)) {
2055//        return edgeMap[edge];
2056//      } else {
2057//        return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
2058//      }
2059//       }     
2060
2061//       Value& operator[](const Key& edge) {
2062//      if (SplitGraphAdaptorBase::originalEdge(edge)) {
2063//        return edgeMap[edge];
2064//      } else {
2065//        return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
2066//      }
2067//       }     
2068     
2069//     private:
2070//       EdgeMap& edgeMap;
2071//       NodeMap& nodeMap;
2072//     };
2073
2074//   };
2075
2076//   template <typename _Graph>
2077//   class SplitGraphAdaptor
2078//     : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2079//   public:
2080//     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
2081
2082//     SplitGraphAdaptor(_Graph& graph) {
2083//       Parent::setGraph(graph);
2084//     }
2085
2086
2087//   };
2088
2089} //namespace lemon
2090
2091#endif //LEMON_GRAPH_ADAPTOR_H
2092
Note: See TracBrowser for help on using the repository browser.