COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2037:32e4bebee616

Last change on this file since 2037:32e4bebee616 was 2037:32e4bebee616, checked in by Balazs Dezso, 13 years ago

Doxygen log corrections

doc of ResGraphAdaptor? has a bug in graph_adaptor.h

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