COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2076:10681ee9d8ae

Last change on this file since 2076:10681ee9d8ae was 2042:bdc953f2a449, checked in by Balazs Dezso, 18 years ago

New Algorithm group for matchings

LaTeX formulas
Bug fix => /\f$ will cause parsing error in doxygen

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