COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_adaptor.h @ 2042:bdc953f2a449

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

New Algorithm group for matchings

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

File size: 60.2 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]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
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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
[1401]19#ifndef LEMON_GRAPH_ADAPTOR_H
20#define LEMON_GRAPH_ADAPTOR_H
[556]21
[2037]22///\ingroup graph_adaptors
23///\file
24///\brief Several graph adaptors.
[556]25///
[2037]26///This file contains several useful graph adaptor functions.
[556]27///
[2037]28///\author Marton Makai and Balazs Dezso
[556]29
[1993]30#include <lemon/bits/invalid.h>
[921]31#include <lemon/maps.h>
[1979]32
[1999]33#include <lemon/bits/base_extender.h>
[1979]34#include <lemon/bits/graph_adaptor_extender.h>
[1791]35#include <lemon/bits/graph_extender.h>
[1979]36
[2034]37#include <lemon/tolerance.h>
38
[774]39#include <iostream>
[556]40
[921]41namespace lemon {
[556]42
[1951]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
[970]58  template<typename _Graph>
[1401]59  class GraphAdaptorBase {
[970]60  public:
61    typedef _Graph Graph;
[2031]62    typedef GraphAdaptorBase Adaptor;
[970]63    typedef Graph ParentGraph;
64
[556]65  protected:
66    Graph* graph;
[1401]67    GraphAdaptorBase() : graph(0) { }
[556]68    void setGraph(Graph& _graph) { graph=&_graph; }
69
70  public:
[1401]71    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
[2034]72
[774]73    typedef typename Graph::Node Node;
74    typedef typename Graph::Edge Edge;
[556]75   
[970]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); }
[556]80
[970]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
[986]86    Node source(const Edge& e) const { return graph->source(e); }
87    Node target(const Edge& e) const { return graph->target(e); }
[556]88
[1697]89    typedef NodeNumTagIndicator<Graph> NodeNumTag;
[556]90    int nodeNum() const { return graph->nodeNum(); }
[1697]91   
92    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
[556]93    int edgeNum() const { return graph->edgeNum(); }
[1697]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    }
[556]100 
[1697]101    Node addNode() const {
102      return Node(graph->addNode());
103    }
104
[986]105    Edge addEdge(const Node& source, const Node& target) const {
[1697]106      return Edge(graph->addEdge(source, target));
107    }
[556]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   
[739]114    int id(const Node& v) const { return graph->id(v); }
115    int id(const Edge& e) const { return graph->id(e); }
[1991]116
[2031]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
[1991]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    }
[650]144   
[970]145    template <typename _Value>
[2031]146    class NodeMap : public Graph::template NodeMap<_Value> {
[970]147    public:
[2031]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)
[1991]155        : Parent(*ga.graph, value) { }
[2031]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     
[970]167    };
[556]168
[970]169    template <typename _Value>
[2031]170    class EdgeMap : public Graph::template EdgeMap<_Value> {
[970]171    public:
[2031]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
[970]191    };
[877]192
[556]193  };
194
[970]195  template <typename _Graph>
[1401]196  class GraphAdaptor :
[1979]197    public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
[970]198  public:
199    typedef _Graph Graph;
[1979]200    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
[970]201  protected:
[1401]202    GraphAdaptor() : Parent() { }
[569]203
[970]204  public:
[1755]205    explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
[970]206  };
[569]207
[1991]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
[997]219  template <typename _Graph>
[1401]220  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[997]221  public:
222    typedef _Graph Graph;
[1401]223    typedef GraphAdaptorBase<_Graph> Parent;
[997]224  protected:
[1401]225    RevGraphAdaptorBase() : Parent() { }
[997]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); }
[1991]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
[997]245  };
246   
247
[1949]248  ///\brief A graph adaptor which reverses the orientation of the edges.
249  ///\ingroup graph_adaptors
250  ///
251  /// If \c g is defined as
[1946]252  ///\code
[923]253  /// ListGraph g;
[1946]254  ///\endcode
[1949]255  /// then
[1946]256  ///\code
[1991]257  /// RevGraphAdaptor<ListGraph> ga(g);
[1946]258  ///\endcode
[1949]259  ///implements the graph obtained from \c g by
260  /// reversing the orientation of its edges.
[1946]261
[997]262  template<typename _Graph>
[1401]263  class RevGraphAdaptor :
[1979]264    public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
[650]265  public:
[997]266    typedef _Graph Graph;
[1979]267    typedef GraphAdaptorExtender<
[1401]268      RevGraphAdaptorBase<_Graph> > Parent;
[556]269  protected:
[1401]270    RevGraphAdaptor() { }
[556]271  public:
[1755]272    explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
[997]273  };
[556]274
[1991]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
[1681]284  template <typename _Graph, typename NodeFilterMap,
285            typename EdgeFilterMap, bool checked = true>
[1401]286  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[992]287  public:
288    typedef _Graph Graph;
[2031]289    typedef SubGraphAdaptorBase Adaptor;
[1401]290    typedef GraphAdaptorBase<_Graph> Parent;
[992]291  protected:
292    NodeFilterMap* node_filter_map;
293    EdgeFilterMap* edge_filter_map;
[1401]294    SubGraphAdaptorBase() : Parent(),
[992]295                            node_filter_map(0), edge_filter_map(0) { }
[775]296
[992]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    }
[1681]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
[1951]357    ///\e
[1949]358
[1951]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.
[1681]362    void hide(const Node& n) const { node_filter_map->set(n, false); }
363
[1951]364    ///\e
[1949]365
[1951]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.
[1681]369    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
370
[1951]371    ///\e
[1949]372
[1951]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
[1681]376     void unHide(const Node& n) const { node_filter_map->set(n, true); }
377
[1951]378    ///\e
[1949]379
[1951]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
[1681]383    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
384
[1951]385    /// Returns true if \c n is hidden.
[1949]386   
[1951]387    ///\e
388    ///
[1681]389    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
390
[1951]391    /// Returns true if \c n is hidden.
[1949]392   
[1951]393    ///\e
394    ///
[1681]395    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
396
[1697]397    typedef False NodeNumTag;
398    typedef False EdgeNumTag;
[1991]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    }
[2031]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
[1681]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;
[2031]472    typedef SubGraphAdaptorBase Adaptor;
[1681]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
[992]497    void first(Edge& i) const {
498      Parent::first(i);
499      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
500    }
[1681]501
[992]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    }
[1681]506
[992]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    }
[1681]524
[992]525    void nextOut(Edge& i) const {
526      Parent::nextOut(i);
527      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
528    }
529
[1951]530    ///\e
[1949]531
[1951]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.
[992]535    void hide(const Node& n) const { node_filter_map->set(n, false); }
536
[1951]537    ///\e
[1949]538
[1951]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.
[992]542    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
543
[1951]544    ///\e
[1949]545
[1951]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
[992]549     void unHide(const Node& n) const { node_filter_map->set(n, true); }
550
[1951]551    ///\e
[1949]552
[1951]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
[992]556    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
557
[1951]558    /// Returns true if \c n is hidden.
[1949]559   
[1951]560    ///\e
561    ///
[992]562    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
563
[1951]564    /// Returns true if \c n is hidden.
[1949]565   
[1951]566    ///\e
567    ///
[992]568    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
569
[1697]570    typedef False NodeNumTag;
571    typedef False EdgeNumTag;
[1991]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    }
[2031]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
[992]638  };
[775]639
[1951]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.
[1952]646  /// Let \f$ G=(V, A) \f$ be a directed graph
[1951]647  /// and suppose that the graph instance \c g of type ListGraph
[1952]648  /// implements \f$ G \f$.
649  /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
[1951]650  /// on the node-set and edge-set.
651  /// SubGraphAdaptor<...>::NodeIt iterates
[1952]652  /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
[1951]653  /// SubGraphAdaptor<...>::EdgeIt iterates
[1952]654  /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
[1951]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.
[1957]665  ///\code
[1951]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);
[1991]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;
[1951]681  /// std::cout << ":-)" << std::endl;
[1991]682  /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
[1957]683  ///\endcode
[1951]684  /// The output of the above code is the following.
[1957]685  ///\code
[1951]686  /// 1
687  /// :-)
688  /// 1
[1957]689  ///\endcode
[1991]690  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
[1951]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
[1242]697
[992]698  template<typename _Graph, typename NodeFilterMap,
[1681]699           typename EdgeFilterMap, bool checked = true>
[1401]700  class SubGraphAdaptor :
[1979]701    public GraphAdaptorExtender<
[1681]702    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
[650]703  public:
[992]704    typedef _Graph Graph;
[2031]705    typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
706                                                      EdgeFilterMap, checked> >
707    Parent;
708
[556]709  protected:
[1401]710    SubGraphAdaptor() { }
[992]711  public:
[2031]712
[1401]713    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
[992]714                    EdgeFilterMap& _edge_filter_map) {
715      setGraph(_graph);
716      setNodeFilterMap(_node_filter_map);
717      setEdgeFilterMap(_edge_filter_map);
718    }
[2031]719
[992]720  };
[556]721
[1991]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
[556]757
[569]758
[1951]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
[1681]769  template<typename Graph, typename NodeFilterMap, bool checked = true>
[1401]770  class NodeSubGraphAdaptor :
771    public SubGraphAdaptor<Graph, NodeFilterMap,
[1681]772                           ConstMap<typename Graph::Edge,bool>, checked> {
[933]773  public:
[2031]774
[1401]775    typedef SubGraphAdaptor<Graph, NodeFilterMap,
[2031]776                            ConstMap<typename Graph::Edge,bool>, checked >
777    Parent;
778
[933]779  protected:
780    ConstMap<typename Graph::Edge, bool> const_true_map;
[1991]781
782    NodeSubGraphAdaptor() : const_true_map(true) {
783      Parent::setEdgeFilterMap(const_true_map);
784    }
785
[933]786  public:
[2031]787
[1401]788    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
[933]789      Parent(), const_true_map(true) {
790      Parent::setGraph(_graph);
791      Parent::setNodeFilterMap(_node_filter_map);
792      Parent::setEdgeFilterMap(const_true_map);
793    }
[2031]794
[933]795  };
796
797
[1991]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
[1951]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  ///
[1991]897  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
898  ///SubGA ga(g, tight_edge_filter);
[1951]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  ///
[1991]906  ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
907  ///  preflow(ga, s, t, const_1_map, flow);
[1951]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
[932]946  template<typename Graph, typename EdgeFilterMap>
[1401]947  class EdgeSubGraphAdaptor :
948    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[1681]949                           EdgeFilterMap, false> {
[932]950  public:
[1401]951    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
[1685]952                            EdgeFilterMap, false> Parent;
[932]953  protected:
954    ConstMap<typename Graph::Node, bool> const_true_map;
[1991]955
956    EdgeSubGraphAdaptor() : const_true_map(true) {
957      Parent::setNodeFilterMap(const_true_map);
958    }
959
[932]960  public:
[2031]961
[1401]962    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
[932]963      Parent(), const_true_map(true) {
964      Parent::setGraph(_graph);
965      Parent::setNodeFilterMap(const_true_map);
966      Parent::setEdgeFilterMap(_edge_filter_map);
967    }
[2031]968
[932]969  };
970
[1991]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>
[1980]987  class UndirGraphAdaptorBase :
[1979]988    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
[1383]989  public:
990    typedef _Graph Graph;
[2031]991    typedef UndirGraphAdaptorBase Adaptor;
[1979]992    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
[1991]993
[1383]994  protected:
[1991]995
996    UndirGraphAdaptorBase() : Parent() {}
997
[1383]998  public:
[1991]999
[1909]1000    typedef typename Parent::UEdge UEdge;
[1383]1001    typedef typename Parent::Edge Edge;
[1991]1002
[2031]1003  private:
[1383]1004   
[1991]1005    template <typename _Value>
[2031]1006    class EdgeMapBase {
[1991]1007    private:
1008     
1009      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1010     
[1383]1011    public:
[1991]1012
1013      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1014
1015      typedef _Value Value;
[1383]1016      typedef Edge Key;
1017     
[2031]1018      EdgeMapBase(const Adaptor& adaptor) :
1019        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
[569]1020
[2031]1021      EdgeMapBase(const Adaptor& adaptor, const Value& v)
1022        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
[1383]1023     
[1991]1024      void set(const Edge& e, const Value& a) {
1025        if (Parent::direction(e)) {
[1383]1026          forward_map.set(e, a);
[1991]1027        } else {
1028          backward_map.set(e, a);
1029        }
[1383]1030      }
[556]1031
[1991]1032      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1033        if (Parent::direction(e)) {
[1383]1034          return forward_map[e];
[1991]1035        } else {
[1383]1036          return backward_map[e];
[1991]1037        }
[556]1038      }
[1991]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
[556]1052    };
[2031]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    };
[1383]1079       
[1991]1080    template <typename _Value>
[2031]1081    class UEdgeMap : public Graph::template EdgeMap<_Value> {
[1383]1082    public:
[2031]1083     
1084      typedef typename Graph::template EdgeMap<_Value> Parent;
1085     
1086      explicit UEdgeMap(const Adaptor& ga)
1087        : Parent(*ga.graph) {}
[1991]1088
[2031]1089      UEdgeMap(const Adaptor& ga, const _Value& value)
1090        : Parent(*ga.graph, value) {}
[1991]1091
[2031]1092      UEdgeMap& operator=(const UEdgeMap& cmap) {
1093        return operator=<UEdgeMap>(cmap);
1094      }
[1991]1095
[2031]1096      template <typename CMap>
1097      UEdgeMap& operator=(const CMap& cmap) {
1098        Parent::operator=(cmap);
1099        return *this;
1100      }
1101
[1991]1102    };
1103     
1104  };
[556]1105
[1991]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;
[2031]1114    typedef UndirGraphAdaptorBase Adaptor;
[1991]1115    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
1116
1117  protected:
1118
1119    UndirGraphAdaptorBase()
[1999]1120      : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
[1991]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() {
[1999]1130      edge_notifier.clear();
1131    }
1132
1133    int maxId(typename Parent::Edge) const {
1134      return Parent::maxEdgeId();
[1991]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
[1999]1145    typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
[1991]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;
[1383]1155     
[1991]1156      NotifierProxy(EdgeNotifier& _edge_notifier)
1157        : Parent(), edge_notifier(_edge_notifier) {
[1383]1158      }
[556]1159
[1991]1160      virtual ~NotifierProxy() {
1161        if (Parent::attached()) {
1162          Parent::detach();
1163        }
[1383]1164      }
[1991]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
[2031]1215  private:
[1991]1216   
1217    template <typename _Value>
[2031]1218    class EdgeMapBase {
[1991]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     
[2031]1230      EdgeMapBase(const Adaptor& adaptor) :
1231        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
[1991]1232
[2031]1233      EdgeMapBase(const Adaptor& adaptor, const Value& v)
1234        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
[1991]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
[2031]1244      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
[1991]1245        if (Parent::direction(e)) {
1246          return forward_map[e];
1247        } else {
1248          return backward_map[e];
1249        }
1250      }
1251
[2031]1252      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
[1991]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    };
[2031]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    };
[1991]1291       
1292    template <typename _Value>
[2031]1293    class UEdgeMap : public Graph::template EdgeMap<_Value> {
[1991]1294    public:
[2031]1295     
1296      typedef typename Graph::template EdgeMap<_Value> Parent;
1297     
1298      explicit UEdgeMap(const Adaptor& ga)
1299        : Parent(*ga.graph) {}
[1991]1300
[2031]1301      UEdgeMap(const Adaptor& ga, const _Value& value)
1302        : Parent(*ga.graph, value) {}
[1991]1303
[2031]1304      UEdgeMap& operator=(const UEdgeMap& cmap) {
1305        return operator=<UEdgeMap>(cmap);
1306      }
[1991]1307
[2031]1308      template <typename CMap>
1309      UEdgeMap& operator=(const CMap& cmap) {
1310        Parent::operator=(cmap);
1311        return *this;
1312      }
1313
[1383]1314    };
1315     
1316  };
1317
[1951]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
[1383]1325  template<typename _Graph>
[1980]1326  class UndirGraphAdaptor :
[1979]1327    public UGraphAdaptorExtender<
[1980]1328    UndirGraphAdaptorBase<_Graph> > {
[1383]1329  public:
1330    typedef _Graph Graph;
[1979]1331    typedef UGraphAdaptorExtender<
[1980]1332      UndirGraphAdaptorBase<_Graph> > Parent;
[1383]1333  protected:
[1980]1334    UndirGraphAdaptor() { }
[1383]1335  public:
[1980]1336    UndirGraphAdaptor(_Graph& _graph) {
[1383]1337      setGraph(_graph);
[556]1338    }
1339
[1991]1340    template <typename _ForwardMap, typename _BackwardMap>
1341    class CombinedEdgeMap {
1342    public:
1343     
1344      typedef _ForwardMap ForwardMap;
1345      typedef _BackwardMap BackwardMap;
[992]1346
[1991]1347      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
[992]1348
[1991]1349      typedef typename ForwardMap::Value Value;
1350      typedef typename Parent::Edge Key;
1351     
1352      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
[992]1353
[1991]1354      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
1355        : forward_map(&_forward_map), backward_map(&_backward_map) {}
[992]1356     
[1991]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        }
[992]1363      }
1364
[1991]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        }
[992]1372      }
1373
[1991]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        }
[992]1381      }
[1991]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
[992]1396    };
1397
1398  };
[569]1399
[1991]1400  /// \brief Just gives back an undir graph adaptor
[1951]1401  ///
[1991]1402  /// Just gives back an undir graph adaptor
[650]1403  template<typename Graph>
[1991]1404  UndirGraphAdaptor<const Graph>
1405  undirGraphAdaptor(const Graph& graph) {
1406    return UndirGraphAdaptor<const Graph>(graph);
1407  }
[650]1408
[2034]1409  template<typename Graph, typename Number, 
1410           typename CapacityMap, typename FlowMap,
1411           typename Tolerance = Tolerance<Number> >
[658]1412  class ResForwardFilter {
[650]1413    const CapacityMap* capacity;
1414    const FlowMap* flow;
[2034]1415    Tolerance tolerance;
[650]1416  public:
[1991]1417    typedef typename Graph::Edge Key;
1418    typedef bool Value;
1419
[2034]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
[1991]1427    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1428    void setFlow(const FlowMap& _flow) { flow = &_flow; }
[2034]1429
[650]1430    bool operator[](const typename Graph::Edge& e) const {
[2034]1431      return tolerance.less((*flow)[e], (*capacity)[e]);
[650]1432    }
1433  };
1434
1435  template<typename Graph, typename Number,
[2034]1436           typename CapacityMap, typename FlowMap,
1437           typename Tolerance = Tolerance<Number> >
[658]1438  class ResBackwardFilter {
[650]1439    const CapacityMap* capacity;
1440    const FlowMap* flow;
[2034]1441    Tolerance tolerance;
[650]1442  public:
[1991]1443    typedef typename Graph::Edge Key;
1444    typedef bool Value;
1445
[2034]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) { }
[1991]1451    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1452    void setFlow(const FlowMap& _flow) { flow = &_flow; }
[650]1453    bool operator[](const typename Graph::Edge& e) const {
[2034]1454      return tolerance.less(0, Number((*flow)[e]));
[650]1455    }
1456  };
1457
[653]1458 
[1951]1459  ///\brief An adaptor for composing the residual
1460  ///graph for directed flow and circulation problems.
[2037]1461  ///
[1951]1462  ///\ingroup graph_adaptors
1463  ///
[2042]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  ///
[650]1495  template<typename Graph, typename Number,
[2034]1496           typename CapacityMap, typename FlowMap,
1497           typename Tolerance = Tolerance<Number> >
[1401]1498  class ResGraphAdaptor :
[1991]1499    public EdgeSubGraphAdaptor<
[2034]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> > > {
[650]1504  public:
[1991]1505
[2034]1506    typedef UndirGraphAdaptor<const Graph> UGraph;
[1991]1507
[2034]1508    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
[1991]1509    ForwardFilter;
1510
[2034]1511    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
[1991]1512    BackwardFilter;
1513
1514    typedef typename UGraph::
1515    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
1516    EdgeFilter;
1517
1518    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
1519
[650]1520  protected:
[1991]1521
[650]1522    const CapacityMap* capacity;
1523    FlowMap* flow;
[1991]1524
1525    UGraph ugraph;
1526    ForwardFilter forward_filter;
1527    BackwardFilter backward_filter;
1528    EdgeFilter edge_filter;
1529
[658]1530    void setCapacityMap(const CapacityMap& _capacity) {
1531      capacity=&_capacity;
1532      forward_filter.setCapacity(_capacity);
1533      backward_filter.setCapacity(_capacity);
1534    }
[1991]1535
[658]1536    void setFlowMap(FlowMap& _flow) {
1537      flow=&_flow;
1538      forward_filter.setFlow(_flow);
1539      backward_filter.setFlow(_flow);
1540    }
[1991]1541
[650]1542  public:
[1991]1543
[2034]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    {
[1991]1555      Parent::setGraph(ugraph);
1556      Parent::setEdgeFilterMap(edge_filter);
[650]1557    }
1558
[660]1559    typedef typename Parent::Edge Edge;
1560
[2034]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.
[660]1577    void augment(const Edge& e, Number a) const {
[1991]1578      if (UGraph::direction(e)) {
[2034]1579        flow->set(e, (*flow)[e] + a);
[1991]1580      } else { 
[2034]1581        flow->set(e, (*flow)[e] - a);
[1991]1582      }
[650]1583    }
1584
[2034]1585    /// \brief Returns the direction of the edge.
1586    ///
1587    /// Returns true when the edge is same oriented as the original edge.
[1991]1588    static bool forward(const Edge& e) {
1589      return UGraph::direction(e);
1590    }
1591
[2034]1592    /// \brief Returns the direction of the edge.
1593    ///
1594    /// Returns true when the edge is opposite oriented as the original edge.
[1991]1595    static bool backward(const Edge& e) {
1596      return !UGraph::direction(e);
1597    }
1598
[2034]1599    /// \brief Gives back the forward oriented residual edge.
1600    ///
1601    /// Gives back the forward oriented residual edge.
[1991]1602    static Edge forward(const typename Graph::Edge& e) {
1603      return UGraph::direct(e, true);
1604    }
1605
[2034]1606    /// \brief Gives back the backward oriented residual edge.
1607    ///
1608    /// Gives back the backward oriented residual edge.
[1991]1609    static Edge backward(const typename Graph::Edge& e) {
1610      return UGraph::direct(e, false);
1611    }
1612
[1951]1613    /// \brief Residual capacity map.
1614    ///
1615    /// In generic residual graphs the residual capacity can be obtained
1616    /// as a map.
[660]1617    class ResCap {
1618    protected:
[1991]1619      const ResGraphAdaptor* res_graph;
[660]1620    public:
[987]1621      typedef Number Value;
1622      typedef Edge Key;
[1991]1623      ResCap(const ResGraphAdaptor& _res_graph)
1624        : res_graph(&_res_graph) {}
1625     
[2034]1626      Number operator[](const Edge& e) const {
1627        return res_graph->rescap(e);
[660]1628      }
[1991]1629     
[660]1630    };
1631
[650]1632  };
1633
1634
[998]1635
1636  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1637  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
[998]1638  public:
1639    typedef _Graph Graph;
[1401]1640    typedef GraphAdaptorBase<_Graph> Parent;
[998]1641  protected:
1642    FirstOutEdgesMap* first_out_edges;
[1401]1643    ErasingFirstGraphAdaptorBase() : Parent(),
[998]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
[1951]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  ///
[998]1681  template <typename _Graph, typename FirstOutEdgesMap>
[1401]1682  class ErasingFirstGraphAdaptor :
[1979]1683    public GraphAdaptorExtender<
[1401]1684    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
[650]1685  public:
[998]1686    typedef _Graph Graph;
[1979]1687    typedef GraphAdaptorExtender<
[1401]1688      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1689    ErasingFirstGraphAdaptor(Graph& _graph,
[998]1690                             FirstOutEdgesMap& _first_out_edges) {
1691      setGraph(_graph);
1692      setFirstOutEdgesMap(_first_out_edges);
1693    }
[1019]1694
[998]1695  };
[556]1696
[1989]1697//   template <typename _Graph>
1698//   class SplitGraphAdaptorBase
1699//     : public GraphAdaptorBase<_Graph> {
1700//   public:
1701//     typedef GraphAdaptorBase<_Graph> Parent;
[1697]1702
[1989]1703//     class Node;
1704//     class Edge;
1705//     template <typename T> class NodeMap;
1706//     template <typename T> class EdgeMap;
[1697]1707   
1708
[1989]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:
[1697]1714
[1989]1715//       bool entry;
1716//       Node(typename Parent::Node _node, bool _entry)
1717//      : Parent::Node(_node), entry(_entry) {}
[1697]1718     
[1989]1719//     public:
1720//       Node() {}
1721//       Node(Invalid) : NodeParent(INVALID), entry(true) {}
[1697]1722
[1989]1723//       bool operator==(const Node& node) const {
1724//      return NodeParent::operator==(node) && entry == node.entry;
1725//       }
[1697]1726     
[1989]1727//       bool operator!=(const Node& node) const {
1728//      return !(*this == node);
1729//       }
[1697]1730     
[1989]1731//       bool operator<(const Node& node) const {
1732//      return NodeParent::operator<(node) ||
1733//        (NodeParent::operator==(node) && entry < node.entry);
1734//       }
1735//     };
[1697]1736
[1989]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;
[1697]1745
[1989]1746//       Edge(const EdgeParent& edge, const NodeParent& node)
1747//      : EdgeParent(edge), bind(node) {}
1748//     public:
1749//       Edge() {}
1750//       Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
[1697]1751
[1989]1752//       bool operator==(const Edge& edge) const {
1753//      return EdgeParent::operator==(edge) && bind == edge.bind;
1754//       }
[1697]1755     
[1989]1756//       bool operator!=(const Edge& edge) const {
1757//      return !(*this == edge);
1758//       }
[1697]1759     
[1989]1760//       bool operator<(const Edge& edge) const {
1761//      return EdgeParent::operator<(edge) ||
1762//        (EdgeParent::operator==(edge) && bind < edge.bind);
1763//       }
1764//     };
[1697]1765
[1989]1766//     void first(Node& node) const {
1767//       Parent::first(node);
1768//       node.entry = true;
1769//     }
[1697]1770
[1989]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//     }
[1697]1779
[1989]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//     }
[1697]1788
[1989]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//     }
[1697]1799
[1989]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//     }
[1697]1809
[1989]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//     }
[1697]1817
[1989]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//     }
[1697]1827
[1989]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//     }
[1697]1835
[1989]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//     }
[1697]1843
[1989]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//     }
[1697]1851
[1989]1852//     static bool entryNode(const Node& node) {
1853//       return node.entry;
1854//     }
[1697]1855
[1989]1856//     static bool exitNode(const Node& node) {
1857//       return !node.entry;
1858//     }
[1697]1859
[1989]1860//     static Node getEntry(const typename Parent::Node& node) {
1861//       return Node(node, true);
1862//     }
[1697]1863
[1989]1864//     static Node getExit(const typename Parent::Node& node) {
1865//       return Node(node, false);
1866//     }
[1697]1867
[1989]1868//     static bool originalEdge(const Edge& edge) {
1869//       return (typename Parent::Edge&)edge != INVALID;
1870//     }
[1697]1871
[1989]1872//     static bool bindingEdge(const Edge& edge) {
1873//       return edge.bind != INVALID;
1874//     }
[1697]1875
[1989]1876//     static Node getBindedNode(const Edge& edge) {
1877//       return edge.bind;
1878//     }
[1697]1879
[1989]1880//     int nodeNum() const {
1881//       return Parent::nodeNum() * 2;
1882//     }
[1697]1883
[1989]1884//     typedef True EdgeNumTag;
[1697]1885   
[1989]1886//     int edgeNum() const {
1887//       return countEdges() + Parent::nodeNum();
1888//     }
[1697]1889
[1989]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//     }
[1697]1903   
[1989]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) {}
[1697]1912     
[1989]1913//       void set(const Node& key, const T& val) {
1914//      if (key.entry) { entry.set(key, val); }
1915//      else {exit.set(key, val); }
1916//       }
[1697]1917     
[1989]1918//       typename MapTraits<NodeImpl>::ReturnValue
1919//       operator[](const Node& key) {
1920//      if (key.entry) { return entry[key]; }
1921//      else { return exit[key]; }
1922//       }
[1697]1923
[1989]1924//       typename MapTraits<NodeImpl>::ConstReturnValue
1925//       operator[](const Node& key) const {
1926//      if (key.entry) { return entry[key]; }
1927//      else { return exit[key]; }
1928//       }
[1697]1929
[1989]1930//     private:
1931//       NodeImpl entry, exit;
1932//     };
[1697]1933
[1989]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) {}
[1697]1943     
[1989]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//       }
[1697]1948     
[1989]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//       }
[1697]1954
[1989]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//       }
[1697]1960
[1989]1961//     private:
1962//       typename Parent::template NodeMap<T> bind;
1963//       typename Parent::template EdgeMap<T> orig;
1964//     };
[1697]1965
[1989]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;
[1697]1970
[1989]1971//       typedef typename Parent::Key Key;
1972//       typedef typename Parent::Value Value;
[1697]1973
[1989]1974//       CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
1975//      : entryMap(_entryMap), exitMap(_exitMap) {}
[1697]1976
[1989]1977//       Value& operator[](const Key& key) {
1978//      if (key.entry) {
1979//        return entryMap[key];
1980//      } else {
1981//        return exitMap[key];
1982//      }
1983//       }
[1697]1984
[1989]1985//       Value operator[](const Key& key) const {
1986//      if (key.entry) {
1987//        return entryMap[key];
1988//      } else {
1989//        return exitMap[key];
1990//      }
1991//       }
[1697]1992
[1989]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//       }
[1697]2000     
[1989]2001//     private:
[1697]2002     
[1989]2003//       EntryMap& entryMap;
2004//       ExitMap& exitMap;
[1697]2005     
[1989]2006//     };
[1697]2007
[1989]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;
[1697]2012
[1989]2013//       typedef typename Parent::Key Key;
2014//       typedef typename Parent::Value Value;
[1697]2015
[1989]2016//       CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
2017//      : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
[1697]2018
[1989]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//       }
[1697]2026
[1989]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//       }     
[1697]2034
[1989]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//       }     
[1697]2042     
[1989]2043//     private:
2044//       EdgeMap& edgeMap;
2045//       NodeMap& nodeMap;
2046//     };
[1697]2047
[1989]2048//   };
[1697]2049
[1989]2050//   template <typename _Graph>
2051//   class SplitGraphAdaptor
2052//     : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
2053//   public:
2054//     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
[1697]2055
[1989]2056//     SplitGraphAdaptor(_Graph& graph) {
2057//       Parent::setGraph(graph);
2058//     }
[1697]2059
2060
[1989]2061//   };
[1697]2062
[921]2063} //namespace lemon
[556]2064
[1401]2065#endif //LEMON_GRAPH_ADAPTOR_H
[556]2066
Note: See TracBrowser for help on using the repository browser.