COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

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