COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1747:bccf2379b5dd

Last change on this file since 1747:bccf2379b5dd was 1730:fffa6456548a, checked in by Balazs Dezso, 18 years ago

Minor changes and bugfixes

File size: 43.9 KB
Line 
1/* -*- C++ -*-
2 * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_GRAPH_UTILS_H
18#define LEMON_GRAPH_UTILS_H
19
20#include <iterator>
21#include <vector>
22#include <map>
23#include <cmath>
24
25#include <lemon/invalid.h>
26#include <lemon/utility.h>
27#include <lemon/maps.h>
28#include <lemon/traits.h>
29#include <lemon/bits/alteration_notifier.h>
30
31///\ingroup gutils
32///\file
33///\brief Graph utilities.
34///
35///
36
37
38namespace lemon {
39
40  /// \addtogroup gutils
41  /// @{
42
43  /// \brief Function to count the items in the graph.
44  ///
45  /// This function counts the items (nodes, edges etc) in the graph.
46  /// The complexity of the function is O(n) because
47  /// it iterates on all of the items.
48
49  template <typename Graph, typename ItemIt>
50  inline int countItems(const Graph& g) {
51    int num = 0;
52    for (ItemIt it(g); it != INVALID; ++it) {
53      ++num;
54    }
55    return num;
56  }
57
58  // Node counting:
59
60  template <typename Graph>
61  inline
62  typename enable_if<typename Graph::NodeNumTag, int>::type
63  _countNodes(const Graph &g) {
64    return g.nodeNum();
65  }
66
67  template <typename Graph>
68  inline int _countNodes(Wrap<Graph> w) {
69    return countItems<Graph, typename Graph::NodeIt>(w.value);
70  }
71
72  /// \brief Function to count the nodes in the graph.
73  ///
74  /// This function counts the nodes in the graph.
75  /// The complexity of the function is O(n) but for some
76  /// graph structures it is specialized to run in O(1).
77  ///
78  /// \todo refer how to specialize it
79
80  template <typename Graph>
81  inline int countNodes(const Graph& g) {
82    return _countNodes<Graph>(g);
83  }
84
85  // Edge counting:
86
87  template <typename Graph>
88  inline
89  typename enable_if<typename Graph::EdgeNumTag, int>::type
90  _countEdges(const Graph &g) {
91    return g.edgeNum();
92  }
93
94  template <typename Graph>
95  inline int _countEdges(Wrap<Graph> w) {
96    return countItems<Graph, typename Graph::EdgeIt>(w.value);
97  }
98
99  /// \brief Function to count the edges in the graph.
100  ///
101  /// This function counts the edges in the graph.
102  /// The complexity of the function is O(e) but for some
103  /// graph structures it is specialized to run in O(1).
104
105  template <typename Graph>
106  inline int countEdges(const Graph& g) {
107    return _countEdges<Graph>(g);
108  }
109
110  // Undirected edge counting:
111
112  template <typename Graph>
113  inline
114  typename enable_if<typename Graph::EdgeNumTag, int>::type
115  _countUndirEdges(const Graph &g) {
116    return g.undirEdgeNum();
117  }
118
119  template <typename Graph>
120  inline int _countUndirEdges(Wrap<Graph> w) {
121    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
122  }
123
124  /// \brief Function to count the undirected edges in the graph.
125  ///
126  /// This function counts the undirected edges in the graph.
127  /// The complexity of the function is O(e) but for some
128  /// graph structures it is specialized to run in O(1).
129
130  template <typename Graph>
131  inline int countUndirEdges(const Graph& g) {
132    return _countUndirEdges<Graph>(g);
133  }
134
135
136
137  template <typename Graph, typename DegIt>
138  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
139    int num = 0;
140    for (DegIt it(_g, _n); it != INVALID; ++it) {
141      ++num;
142    }
143    return num;
144  }
145
146  /// \brief Function to count the number of the out-edges from node \c n.
147  ///
148  /// This function counts the number of the out-edges from node \c n
149  /// in the graph. 
150  template <typename Graph>
151  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
152    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
153  }
154
155  /// \brief Function to count the number of the in-edges to node \c n.
156  ///
157  /// This function counts the number of the in-edges to node \c n
158  /// in the graph. 
159  template <typename Graph>
160  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
161    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
162  }
163
164  /// \brief Function to count the number of the inc-edges to node \c n.
165  ///
166  /// This function counts the number of the inc-edges to node \c n
167  /// in the graph. 
168  template <typename Graph>
169  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
170    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
171  }
172
173
174  template <typename Graph>
175  inline
176  typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
177  _findEdge(const Graph &g,
178            typename Graph::Node u, typename Graph::Node v,
179            typename Graph::Edge prev = INVALID) {
180    return g.findEdge(u, v, prev);
181  }
182
183  template <typename Graph>
184  inline typename Graph::Edge
185  _findEdge(Wrap<Graph> w,
186            typename Graph::Node u,
187            typename Graph::Node v,
188            typename Graph::Edge prev = INVALID) {
189    const Graph& g = w.value;
190    if (prev == INVALID) {
191      typename Graph::OutEdgeIt e(g, u);
192      while (e != INVALID && g.target(e) != v) ++e;
193      return e;
194    } else {
195      typename Graph::OutEdgeIt e(g, prev); ++e;
196      while (e != INVALID && g.target(e) != v) ++e;
197      return e;
198    }
199  }
200
201  /// \brief Finds an edge between two nodes of a graph.
202  ///
203  /// Finds an edge from node \c u to node \c v in graph \c g.
204  ///
205  /// If \c prev is \ref INVALID (this is the default value), then
206  /// it finds the first edge from \c u to \c v. Otherwise it looks for
207  /// the next edge from \c u to \c v after \c prev.
208  /// \return The found edge or \ref INVALID if there is no such an edge.
209  ///
210  /// Thus you can iterate through each edge from \c u to \c v as it follows.
211  /// \code
212  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
213  ///   ...
214  /// }
215  /// \endcode
216  // /// \todo We may want to use the "GraphBase"
217  // /// interface here...
218  template <typename Graph>
219  inline typename Graph::Edge findEdge(const Graph &g,
220                                       typename Graph::Node u,
221                                       typename Graph::Node v,
222                                       typename Graph::Edge prev = INVALID) {
223    return _findEdge<Graph>(g, u, v, prev);
224  }
225
226  /// \brief Iterator for iterating on edges connected the same nodes.
227  ///
228  /// Iterator for iterating on edges connected the same nodes. It is
229  /// higher level interface for the findEdge() function. You can
230  /// use it the following way:
231  /// \code
232  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
233  ///   ...
234  /// }
235  /// \endcode
236  ///
237  /// \author Balazs Dezso
238  template <typename _Graph>
239  class ConEdgeIt : public _Graph::Edge {
240  public:
241
242    typedef _Graph Graph;
243    typedef typename Graph::Edge Parent;
244
245    typedef typename Graph::Edge Edge;
246    typedef typename Graph::Node Node;
247
248    /// \brief Constructor.
249    ///
250    /// Construct a new ConEdgeIt iterating on the edges which
251    /// connects the \c u and \c v node.
252    ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
253      Parent::operator=(findEdge(graph, u, v));
254    }
255
256    /// \brief Constructor.
257    ///
258    /// Construct a new ConEdgeIt which continues the iterating from
259    /// the \c e edge.
260    ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
261   
262    /// \brief Increment operator.
263    ///
264    /// It increments the iterator and gives back the next edge.
265    ConEdgeIt& operator++() {
266      Parent::operator=(findEdge(graph, graph.source(*this),
267                                 graph.target(*this), *this));
268      return *this;
269    }
270  private:
271    const Graph& graph;
272  };
273
274  template <typename Graph>
275  inline
276  typename enable_if<
277    typename Graph::FindEdgeTag,
278    typename Graph::UndirEdge>::type
279  _findUndirEdge(const Graph &g,
280            typename Graph::Node u, typename Graph::Node v,
281            typename Graph::UndirEdge prev = INVALID) {
282    return g.findUndirEdge(u, v, prev);
283  }
284
285  template <typename Graph>
286  inline typename Graph::UndirEdge
287  _findUndirEdge(Wrap<Graph> w,
288            typename Graph::Node u,
289            typename Graph::Node v,
290            typename Graph::UndirEdge prev = INVALID) {
291    const Graph& g = w.value;
292    if (prev == INVALID) {
293      typename Graph::OutEdgeIt e(g, u);
294      while (e != INVALID && g.target(e) != v) ++e;
295      return e;
296    } else {
297      typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
298      while (e != INVALID && g.target(e) != v) ++e;
299      return e;
300    }
301  }
302
303  /// \brief Finds an undir edge between two nodes of a graph.
304  ///
305  /// Finds an undir edge from node \c u to node \c v in graph \c g.
306  ///
307  /// If \c prev is \ref INVALID (this is the default value), then
308  /// it finds the first edge from \c u to \c v. Otherwise it looks for
309  /// the next edge from \c u to \c v after \c prev.
310  /// \return The found edge or \ref INVALID if there is no such an edge.
311  ///
312  /// Thus you can iterate through each edge from \c u to \c v as it follows.
313  /// \code
314  /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
315  ///     e = findUndirEdge(g,u,v,e)) {
316  ///   ...
317  /// }
318  /// \endcode
319  // /// \todo We may want to use the "GraphBase"
320  // /// interface here...
321  template <typename Graph>
322  inline typename Graph::UndirEdge
323  findUndirEdge(const Graph &g,
324                typename Graph::Node u,
325                typename Graph::Node v,
326                typename Graph::UndirEdge prev = INVALID) {
327    return _findUndirEdge<Graph>(g, u, v, prev);
328  }
329
330  /// \brief Iterator for iterating on undir edges connected the same nodes.
331  ///
332  /// Iterator for iterating on undir edges connected the same nodes. It is
333  /// higher level interface for the findUndirEdge() function. You can
334  /// use it the following way:
335  /// \code
336  /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
337  ///   ...
338  /// }
339  /// \endcode
340  ///
341  /// \author Balazs Dezso
342  template <typename _Graph>
343  class ConUndirEdgeIt : public _Graph::UndirEdge {
344  public:
345
346    typedef _Graph Graph;
347    typedef typename Graph::UndirEdge Parent;
348
349    typedef typename Graph::UndirEdge UndirEdge;
350    typedef typename Graph::Node Node;
351
352    /// \brief Constructor.
353    ///
354    /// Construct a new ConUndirEdgeIt iterating on the edges which
355    /// connects the \c u and \c v node.
356    ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
357      Parent::operator=(findUndirEdge(graph, u, v));
358    }
359
360    /// \brief Constructor.
361    ///
362    /// Construct a new ConUndirEdgeIt which continues the iterating from
363    /// the \c e edge.
364    ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
365   
366    /// \brief Increment operator.
367    ///
368    /// It increments the iterator and gives back the next edge.
369    ConUndirEdgeIt& operator++() {
370      Parent::operator=(findUndirEdge(graph, graph.source(*this),
371                                 graph.target(*this), *this));
372      return *this;
373    }
374  private:
375    const Graph& graph;
376  };
377
378  /// \brief Copy a map.
379  ///
380  /// This function copies the \c source map to the \c target map. It uses the
381  /// given iterator to iterate on the data structure and it uses the \c ref
382  /// mapping to convert the source's keys to the target's keys.
383  template <typename Target, typename Source,
384            typename ItemIt, typename Ref>         
385  void copyMap(Target& target, const Source& source,
386               ItemIt it, const Ref& ref) {
387    for (; it != INVALID; ++it) {
388      target[ref[it]] = source[it];
389    }
390  }
391
392  /// \brief Copy the source map to the target map.
393  ///
394  /// Copy the \c source map to the \c target map. It uses the given iterator
395  /// to iterate on the data structure.
396  template <typename Target, typename Source,
397            typename ItemIt>       
398  void copyMap(Target& target, const Source& source, ItemIt it) {
399    for (; it != INVALID; ++it) {
400      target[it] = source[it];
401    }
402  }
403
404  /// \brief Class to copy a graph.
405  ///
406  /// Class to copy a graph to an other graph (duplicate a graph). The
407  /// simplest way of using it is through the \c copyGraph() function.
408  template <typename Target, typename Source>
409  class GraphCopy {
410  public:
411    typedef typename Source::Node Node;
412    typedef typename Source::NodeIt NodeIt;
413    typedef typename Source::Edge Edge;
414    typedef typename Source::EdgeIt EdgeIt;
415
416    typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
417    typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
418
419    /// \brief Constructor for the GraphCopy.
420    ///
421    /// It copies the content of the \c _source graph into the
422    /// \c _target graph. It creates also two references, one beetween
423    /// the two nodeset and one beetween the two edgesets.
424    GraphCopy(Target& _target, const Source& _source)
425      : source(_source), target(_target),
426        nodeRefMap(_source), edgeRefMap(_source) {
427      for (NodeIt it(source); it != INVALID; ++it) {
428        nodeRefMap[it] = target.addNode();
429      }
430      for (EdgeIt it(source); it != INVALID; ++it) {
431        edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
432                                        nodeRefMap[source.target(it)]);
433      }
434    }
435
436    /// \brief Copies the node references into the given map.
437    ///
438    /// Copies the node references into the given map.
439    template <typename NodeRef>
440    const GraphCopy& nodeRef(NodeRef& map) const {
441      for (NodeIt it(source); it != INVALID; ++it) {
442        map.set(it, nodeRefMap[it]);
443      }
444      return *this;
445    }
446
447    /// \brief Reverse and copies the node references into the given map.
448    ///
449    /// Reverse and copies the node references into the given map.
450    template <typename NodeRef>
451    const GraphCopy& nodeCrossRef(NodeRef& map) const {
452      for (NodeIt it(source); it != INVALID; ++it) {
453        map.set(nodeRefMap[it], it);
454      }
455      return *this;
456    }
457
458    /// \brief Copies the edge references into the given map.
459    ///
460    /// Copies the edge references into the given map.
461    template <typename EdgeRef>
462    const GraphCopy& edgeRef(EdgeRef& map) const {
463      for (EdgeIt it(source); it != INVALID; ++it) {
464        map.set(it, edgeRefMap[it]);
465      }
466      return *this;
467    }
468
469    /// \brief Reverse and copies the edge references into the given map.
470    ///
471    /// Reverse and copies the edge references into the given map.
472    template <typename EdgeRef>
473    const GraphCopy& edgeCrossRef(EdgeRef& map) const {
474      for (EdgeIt it(source); it != INVALID; ++it) {
475        map.set(edgeRefMap[it], it);
476      }
477      return *this;
478    }
479
480    /// \brief Make copy of the given map.
481    ///
482    /// Makes copy of the given map for the newly created graph.
483    /// The new map's key type is the target graph's node type,
484    /// and the copied map's key type is the source graph's node
485    /// type. 
486    template <typename TargetMap, typename SourceMap>
487    const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
488      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
489      return *this;
490    }
491
492    /// \brief Make copy of the given map.
493    ///
494    /// Makes copy of the given map for the newly created graph.
495    /// The new map's key type is the target graph's edge type,
496    /// and the copied map's key type is the source graph's edge
497    /// type. 
498    template <typename TargetMap, typename SourceMap>
499    const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
500      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
501      return *this;
502    }
503
504    /// \brief Gives back the stored node references.
505    ///
506    /// Gives back the stored node references.
507    const NodeRefMap& nodeRef() const {
508      return nodeRefMap;
509    }
510
511    /// \brief Gives back the stored edge references.
512    ///
513    /// Gives back the stored edge references.
514    const EdgeRefMap& edgeRef() const {
515      return edgeRefMap;
516    }
517
518    void run() {}
519
520  private:
521   
522    const Source& source;
523    Target& target;
524
525    NodeRefMap nodeRefMap;
526    EdgeRefMap edgeRefMap;
527  };
528
529  /// \brief Copy a graph to an other graph.
530  ///
531  /// Copy a graph to an other graph.
532  /// The usage of the function:
533  ///
534  /// \code
535  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
536  /// \endcode
537  ///
538  /// After the copy the \c nr map will contain the mapping from the
539  /// source graph's nodes to the target graph's nodes and the \c ecr will
540  /// contain the mapping from the target graph's edges to the source's
541  /// edges.
542  template <typename Target, typename Source>
543  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
544    return GraphCopy<Target, Source>(target, source);
545  }
546
547  /// \brief Class to copy an undirected graph.
548  ///
549  /// Class to copy an undirected graph to an other graph (duplicate a graph).
550  /// The simplest way of using it is through the \c copyUndirGraph() function.
551  template <typename Target, typename Source>
552  class UndirGraphCopy {
553  public:
554    typedef typename Source::Node Node;
555    typedef typename Source::NodeIt NodeIt;
556    typedef typename Source::Edge Edge;
557    typedef typename Source::EdgeIt EdgeIt;
558    typedef typename Source::UndirEdge UndirEdge;
559    typedef typename Source::UndirEdgeIt UndirEdgeIt;
560
561    typedef typename Source::
562    template NodeMap<typename Target::Node> NodeRefMap;
563   
564    typedef typename Source::
565    template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
566
567  private:
568
569    struct EdgeRefMap {
570      EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
571      typedef typename Source::Edge Key;
572      typedef typename Target::Edge Value;
573
574      Value operator[](const Key& key) {
575        return gc.target.direct(gc.undirEdgeRef[key],
576                                gc.target.direction(key));
577      }
578     
579      UndirGraphCopy& gc;
580    };
581   
582  public:
583
584    /// \brief Constructor for the UndirGraphCopy.
585    ///
586    /// It copies the content of the \c _source graph into the
587    /// \c _target graph. It creates also two references, one beetween
588    /// the two nodeset and one beetween the two edgesets.
589    UndirGraphCopy(Target& _target, const Source& _source)
590      : source(_source), target(_target),
591        nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
592      for (NodeIt it(source); it != INVALID; ++it) {
593        nodeRefMap[it] = target.addNode();
594      }
595      for (UndirEdgeIt it(source); it != INVALID; ++it) {
596        undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
597                                        nodeRefMap[source.target(it)]);
598      }
599    }
600
601    /// \brief Copies the node references into the given map.
602    ///
603    /// Copies the node references into the given map.
604    template <typename NodeRef>
605    const UndirGraphCopy& nodeRef(NodeRef& map) const {
606      for (NodeIt it(source); it != INVALID; ++it) {
607        map.set(it, nodeRefMap[it]);
608      }
609      return *this;
610    }
611
612    /// \brief Reverse and copies the node references into the given map.
613    ///
614    /// Reverse and copies the node references into the given map.
615    template <typename NodeRef>
616    const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
617      for (NodeIt it(source); it != INVALID; ++it) {
618        map.set(nodeRefMap[it], it);
619      }
620      return *this;
621    }
622
623    /// \brief Copies the edge references into the given map.
624    ///
625    /// Copies the edge references into the given map.
626    template <typename EdgeRef>
627    const UndirGraphCopy& edgeRef(EdgeRef& map) const {
628      for (EdgeIt it(source); it != INVALID; ++it) {
629        map.set(edgeRefMap[it], it);
630      }
631      return *this;
632    }
633
634    /// \brief Reverse and copies the undirected edge references into the
635    /// given map.
636    ///
637    /// Reverse and copies the undirected edge references into the given map.
638    template <typename EdgeRef>
639    const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
640      for (EdgeIt it(source); it != INVALID; ++it) {
641        map.set(it, edgeRefMap[it]);
642      }
643      return *this;
644    }
645
646    /// \brief Copies the undirected edge references into the given map.
647    ///
648    /// Copies the undirected edge references into the given map.
649    template <typename EdgeRef>
650    const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
651      for (UndirEdgeIt it(source); it != INVALID; ++it) {
652        map.set(it, undirEdgeRefMap[it]);
653      }
654      return *this;
655    }
656
657    /// \brief Reverse and copies the undirected edge references into the
658    /// given map.
659    ///
660    /// Reverse and copies the undirected edge references into the given map.
661    template <typename EdgeRef>
662    const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
663      for (UndirEdgeIt it(source); it != INVALID; ++it) {
664        map.set(undirEdgeRefMap[it], it);
665      }
666      return *this;
667    }
668
669    /// \brief Make copy of the given map.
670    ///
671    /// Makes copy of the given map for the newly created graph.
672    /// The new map's key type is the target graph's node type,
673    /// and the copied map's key type is the source graph's node
674    /// type. 
675    template <typename TargetMap, typename SourceMap>
676    const UndirGraphCopy& nodeMap(TargetMap& tMap,
677                                  const SourceMap& sMap) const {
678      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
679      return *this;
680    }
681
682    /// \brief Make copy of the given map.
683    ///
684    /// Makes copy of the given map for the newly created graph.
685    /// The new map's key type is the target graph's edge type,
686    /// and the copied map's key type is the source graph's edge
687    /// type. 
688    template <typename TargetMap, typename SourceMap>
689    const UndirGraphCopy& edgeMap(TargetMap& tMap,
690                                  const SourceMap& sMap) const {
691      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
692      return *this;
693    }
694
695    /// \brief Make copy of the given map.
696    ///
697    /// Makes copy of the given map for the newly created graph.
698    /// The new map's key type is the target graph's edge type,
699    /// and the copied map's key type is the source graph's edge
700    /// type. 
701    template <typename TargetMap, typename SourceMap>
702    const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
703                                  const SourceMap& sMap) const {
704      copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
705      return *this;
706    }
707
708    /// \brief Gives back the stored node references.
709    ///
710    /// Gives back the stored node references.
711    const NodeRefMap& nodeRef() const {
712      return nodeRefMap;
713    }
714
715    /// \brief Gives back the stored edge references.
716    ///
717    /// Gives back the stored edge references.
718    const EdgeRefMap& edgeRef() const {
719      return edgeRefMap;
720    }
721
722    /// \brief Gives back the stored undir edge references.
723    ///
724    /// Gives back the stored undir edge references.
725    const UndirEdgeRefMap& undirEdgeRef() const {
726      return undirEdgeRefMap;
727    }
728
729    void run() {}
730
731  private:
732   
733    const Source& source;
734    Target& target;
735
736    NodeRefMap nodeRefMap;
737    EdgeRefMap edgeRefMap;
738    UndirEdgeRefMap undirEdgeRefMap;
739  };
740
741  /// \brief Copy a graph to an other graph.
742  ///
743  /// Copy a graph to an other graph.
744  /// The usage of the function:
745  ///
746  /// \code
747  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
748  /// \endcode
749  ///
750  /// After the copy the \c nr map will contain the mapping from the
751  /// source graph's nodes to the target graph's nodes and the \c ecr will
752  /// contain the mapping from the target graph's edges to the source's
753  /// edges.
754  template <typename Target, typename Source>
755  UndirGraphCopy<Target, Source>
756  copyUndirGraph(Target& target, const Source& source) {
757    return UndirGraphCopy<Target, Source>(target, source);
758  }
759
760
761  /// @}
762
763  /// \addtogroup graph_maps
764  /// @{
765
766  /// Provides an immutable and unique id for each item in the graph.
767
768  /// The IdMap class provides a unique and immutable id for each item of the
769  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
770  /// different items (nodes) get different ids <li>\b immutable: the id of an
771  /// item (node) does not change (even if you delete other nodes).  </ul>
772  /// Through this map you get access (i.e. can read) the inner id values of
773  /// the items stored in the graph. This map can be inverted with its member
774  /// class \c InverseMap.
775  ///
776  template <typename _Graph, typename _Item>
777  class IdMap {
778  public:
779    typedef _Graph Graph;
780    typedef int Value;
781    typedef _Item Item;
782    typedef _Item Key;
783
784    /// \brief Constructor.
785    ///
786    /// Constructor for creating id map.
787    IdMap(const Graph& _graph) : graph(&_graph) {}
788
789    /// \brief Gives back the \e id of the item.
790    ///
791    /// Gives back the immutable and unique \e id of the map.
792    int operator[](const Item& item) const { return graph->id(item);}
793
794
795  private:
796    const Graph* graph;
797
798  public:
799
800    /// \brief The class represents the inverse of its owner (IdMap).
801    ///
802    /// The class represents the inverse of its owner (IdMap).
803    /// \see inverse()
804    class InverseMap {
805    public:
806
807      /// \brief Constructor.
808      ///
809      /// Constructor for creating an id-to-item map.
810      InverseMap(const Graph& _graph) : graph(&_graph) {}
811
812      /// \brief Constructor.
813      ///
814      /// Constructor for creating an id-to-item map.
815      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
816
817      /// \brief Gives back the given item from its id.
818      ///
819      /// Gives back the given item from its id.
820      ///
821      Item operator[](int id) const { return graph->fromId(id, Item());}
822    private:
823      const Graph* graph;
824    };
825
826    /// \brief Gives back the inverse of the map.
827    ///
828    /// Gives back the inverse of the IdMap.
829    InverseMap inverse() const { return InverseMap(*graph);}
830
831  };
832
833 
834  /// \brief General invertable graph-map type.
835
836  /// This type provides simple invertable graph-maps.
837  /// The InvertableMap wraps an arbitrary ReadWriteMap
838  /// and if a key is set to a new value then store it
839  /// in the inverse map.
840  /// \param _Graph The graph type.
841  /// \param _Map The map to extend with invertable functionality.
842  template <
843    typename _Graph,
844    typename _Item,
845    typename _Value,
846    typename _Map
847    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
848  >
849  class InvertableMap : protected _Map {
850
851  public:
852 
853    typedef _Map Map;
854    typedef _Graph Graph;
855
856    /// The key type of InvertableMap (Node, Edge, UndirEdge).
857    typedef typename _Map::Key Key;
858    /// The value type of the InvertableMap.
859    typedef typename _Map::Value Value;
860
861    /// \brief Constructor.
862    ///
863    /// Construct a new InvertableMap for the graph.
864    ///
865    InvertableMap(const Graph& graph) : Map(graph) {}
866   
867    /// \brief The setter function of the map.
868    ///
869    /// Sets the mapped value.
870    void set(const Key& key, const Value& val) {
871      Value oldval = Map::operator[](key);
872      typename Container::iterator it = invMap.find(oldval);
873      if (it != invMap.end() && it->second == key) {
874        invMap.erase(it);
875      }     
876      invMap.insert(make_pair(val, key));
877      Map::set(key, val);
878    }
879
880    /// \brief The getter function of the map.
881    ///
882    /// It gives back the value associated with the key.
883    Value operator[](const Key& key) const {
884      return Map::operator[](key);
885    }
886
887  protected:
888
889    /// \brief Add a new key to the map.
890    ///
891    /// Add a new key to the map. It is called by the
892    /// \c AlterationNotifier.
893    virtual void add(const Key& key) {
894      Map::add(key);
895    }
896
897    /// \brief Erase the key from the map.
898    ///
899    /// Erase the key to the map. It is called by the
900    /// \c AlterationNotifier.
901    virtual void erase(const Key& key) {
902      Value val = Map::operator[](key);
903      typename Container::iterator it = invMap.find(val);
904      if (it != invMap.end() && it->second == key) {
905        invMap.erase(it);
906      }
907      Map::erase(key);
908    }
909
910    /// \brief Clear the keys from the map and inverse map.
911    ///
912    /// Clear the keys from the map and inverse map. It is called by the
913    /// \c AlterationNotifier.
914    virtual void clear() {
915      invMap.clear();
916      Map::clear();
917    }
918
919  private:
920   
921    typedef std::map<Value, Key> Container;
922    Container invMap;   
923
924  public:
925
926    /// \brief The inverse map type.
927    ///
928    /// The inverse of this map. The subscript operator of the map
929    /// gives back always the item what was last assigned to the value.
930    class InverseMap {
931    public:
932      /// \brief Constructor of the InverseMap.
933      ///
934      /// Constructor of the InverseMap.
935      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
936
937      /// The value type of the InverseMap.
938      typedef typename InvertableMap::Key Value;
939      /// The key type of the InverseMap.
940      typedef typename InvertableMap::Value Key;
941
942      /// \brief Subscript operator.
943      ///
944      /// Subscript operator. It gives back always the item
945      /// what was last assigned to the value.
946      Value operator[](const Key& key) const {
947        typename Container::const_iterator it = inverted.invMap.find(key);
948        return it->second;
949      }
950     
951    private:
952      const InvertableMap& inverted;
953    };
954
955    /// \brief It gives back the just readeable inverse map.
956    ///
957    /// It gives back the just readeable inverse map.
958    InverseMap inverse() const {
959      return InverseMap(*this);
960    }
961
962
963   
964  };
965
966  /// \brief Provides a mutable, continuous and unique descriptor for each
967  /// item in the graph.
968  ///
969  /// The DescriptorMap class provides a unique and continuous (but mutable)
970  /// descriptor (id) for each item of the same type (e.g. node) in the
971  /// graph. This id is <ul><li>\b unique: different items (nodes) get
972  /// different ids <li>\b continuous: the range of the ids is the set of
973  /// integers between 0 and \c n-1, where \c n is the number of the items of
974  /// this type (e.g. nodes) (so the id of a node can change if you delete an
975  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
976  /// with its member class \c InverseMap.
977  ///
978  /// \param _Graph The graph class the \c DescriptorMap belongs to.
979  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
980  /// UndirEdge.
981  /// \param _Map A ReadWriteMap mapping from the item type to integer.
982  template <
983    typename _Graph,   
984    typename _Item,
985    typename _Map
986    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
987  >
988  class DescriptorMap : protected _Map {
989
990    typedef _Item Item;
991    typedef _Map Map;
992
993  public:
994    /// The graph class of DescriptorMap.
995    typedef _Graph Graph;
996
997    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
998    typedef typename _Map::Key Key;
999    /// The value type of DescriptorMap.
1000    typedef typename _Map::Value Value;
1001
1002    /// \brief Constructor.
1003    ///
1004    /// Constructor for descriptor map.
1005    DescriptorMap(const Graph& _graph) : Map(_graph) {
1006      build();
1007    }
1008
1009  protected:
1010
1011    /// \brief Add a new key to the map.
1012    ///
1013    /// Add a new key to the map. It is called by the
1014    /// \c AlterationNotifier.
1015    virtual void add(const Item& item) {
1016      Map::add(item);
1017      Map::set(item, invMap.size());
1018      invMap.push_back(item);
1019    }
1020
1021    /// \brief Erase the key from the map.
1022    ///
1023    /// Erase the key to the map. It is called by the
1024    /// \c AlterationNotifier.
1025    virtual void erase(const Item& item) {
1026      Map::set(invMap.back(), Map::operator[](item));
1027      invMap[Map::operator[](item)] = invMap.back();
1028      invMap.pop_back();
1029      Map::erase(item);
1030    }
1031
1032    /// \brief Build the unique map.
1033    ///
1034    /// Build the unique map. It is called by the
1035    /// \c AlterationNotifier.
1036    virtual void build() {
1037      Map::build();
1038      Item it;
1039      const typename Map::Graph* graph = Map::getGraph();
1040      for (graph->first(it); it != INVALID; graph->next(it)) {
1041        Map::set(it, invMap.size());
1042        invMap.push_back(it);   
1043      }     
1044    }
1045   
1046    /// \brief Clear the keys from the map.
1047    ///
1048    /// Clear the keys from the map. It is called by the
1049    /// \c AlterationNotifier.
1050    virtual void clear() {
1051      invMap.clear();
1052      Map::clear();
1053    }
1054
1055  public:
1056
1057    /// \brief Swaps the position of the two items in the map.
1058    ///
1059    /// Swaps the position of the two items in the map.
1060    void swap(const Item& p, const Item& q) {
1061      int pi = Map::operator[](p);
1062      int qi = Map::operator[](q);
1063      Map::set(p, qi);
1064      invMap[qi] = p;
1065      Map::set(q, pi);
1066      invMap[pi] = q;
1067    }
1068
1069    /// \brief Gives back the \e descriptor of the item.
1070    ///
1071    /// Gives back the mutable and unique \e descriptor of the map.
1072    int operator[](const Item& item) const {
1073      return Map::operator[](item);
1074    }
1075   
1076  private:
1077
1078    typedef std::vector<Item> Container;
1079    Container invMap;
1080
1081  public:
1082    /// \brief The inverse map type of DescriptorMap.
1083    ///
1084    /// The inverse map type of DescriptorMap.
1085    class InverseMap {
1086    public:
1087      /// \brief Constructor of the InverseMap.
1088      ///
1089      /// Constructor of the InverseMap.
1090      InverseMap(const DescriptorMap& _inverted)
1091        : inverted(_inverted) {}
1092
1093
1094      /// The value type of the InverseMap.
1095      typedef typename DescriptorMap::Key Value;
1096      /// The key type of the InverseMap.
1097      typedef typename DescriptorMap::Value Key;
1098
1099      /// \brief Subscript operator.
1100      ///
1101      /// Subscript operator. It gives back the item
1102      /// that the descriptor belongs to currently.
1103      Value operator[](const Key& key) const {
1104        return inverted.invMap[key];
1105      }
1106
1107      /// \brief Size of the map.
1108      ///
1109      /// Returns the size of the map.
1110      int size() const {
1111        return inverted.invMap.size();
1112      }
1113     
1114    private:
1115      const DescriptorMap& inverted;
1116    };
1117
1118    /// \brief Gives back the inverse of the map.
1119    ///
1120    /// Gives back the inverse of the map.
1121    const InverseMap inverse() const {
1122      return InverseMap(*this);
1123    }
1124  };
1125
1126  /// \brief Returns the source of the given edge.
1127  ///
1128  /// The SourceMap gives back the source Node of the given edge.
1129  /// \author Balazs Dezso
1130  template <typename Graph>
1131  class SourceMap {
1132  public:
1133
1134    typedef typename Graph::Node Value;
1135    typedef typename Graph::Edge Key;
1136
1137    /// \brief Constructor
1138    ///
1139    /// Constructor
1140    /// \param _graph The graph that the map belongs to.
1141    SourceMap(const Graph& _graph) : graph(_graph) {}
1142
1143    /// \brief The subscript operator.
1144    ///
1145    /// The subscript operator.
1146    /// \param edge The edge
1147    /// \return The source of the edge
1148    Value operator[](const Key& edge) const {
1149      return graph.source(edge);
1150    }
1151
1152  private:
1153    const Graph& graph;
1154  };
1155
1156  /// \brief Returns a \ref SourceMap class
1157  ///
1158  /// This function just returns an \ref SourceMap class.
1159  /// \relates SourceMap
1160  template <typename Graph>
1161  inline SourceMap<Graph> sourceMap(const Graph& graph) {
1162    return SourceMap<Graph>(graph);
1163  }
1164
1165  /// \brief Returns the target of the given edge.
1166  ///
1167  /// The TargetMap gives back the target Node of the given edge.
1168  /// \author Balazs Dezso
1169  template <typename Graph>
1170  class TargetMap {
1171  public:
1172
1173    typedef typename Graph::Node Value;
1174    typedef typename Graph::Edge Key;
1175
1176    /// \brief Constructor
1177    ///
1178    /// Constructor
1179    /// \param _graph The graph that the map belongs to.
1180    TargetMap(const Graph& _graph) : graph(_graph) {}
1181
1182    /// \brief The subscript operator.
1183    ///
1184    /// The subscript operator.
1185    /// \param e The edge
1186    /// \return The target of the edge
1187    Value operator[](const Key& e) const {
1188      return graph.target(e);
1189    }
1190
1191  private:
1192    const Graph& graph;
1193  };
1194
1195  /// \brief Returns a \ref TargetMap class
1196  ///
1197  /// This function just returns a \ref TargetMap class.
1198  /// \relates TargetMap
1199  template <typename Graph>
1200  inline TargetMap<Graph> targetMap(const Graph& graph) {
1201    return TargetMap<Graph>(graph);
1202  }
1203
1204  /// \brief Returns the "forward" directed edge view of an undirected edge.
1205  ///
1206  /// Returns the "forward" directed edge view of an undirected edge.
1207  /// \author Balazs Dezso
1208  template <typename Graph>
1209  class ForwardMap {
1210  public:
1211
1212    typedef typename Graph::Edge Value;
1213    typedef typename Graph::UndirEdge Key;
1214
1215    /// \brief Constructor
1216    ///
1217    /// Constructor
1218    /// \param _graph The graph that the map belongs to.
1219    ForwardMap(const Graph& _graph) : graph(_graph) {}
1220
1221    /// \brief The subscript operator.
1222    ///
1223    /// The subscript operator.
1224    /// \param key An undirected edge
1225    /// \return The "forward" directed edge view of undirected edge
1226    Value operator[](const Key& key) const {
1227      return graph.direct(key, true);
1228    }
1229
1230  private:
1231    const Graph& graph;
1232  };
1233
1234  /// \brief Returns a \ref ForwardMap class
1235  ///
1236  /// This function just returns an \ref ForwardMap class.
1237  /// \relates ForwardMap
1238  template <typename Graph>
1239  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1240    return ForwardMap<Graph>(graph);
1241  }
1242
1243  /// \brief Returns the "backward" directed edge view of an undirected edge.
1244  ///
1245  /// Returns the "backward" directed edge view of an undirected edge.
1246  /// \author Balazs Dezso
1247  template <typename Graph>
1248  class BackwardMap {
1249  public:
1250
1251    typedef typename Graph::Edge Value;
1252    typedef typename Graph::UndirEdge Key;
1253
1254    /// \brief Constructor
1255    ///
1256    /// Constructor
1257    /// \param _graph The graph that the map belongs to.
1258    BackwardMap(const Graph& _graph) : graph(_graph) {}
1259
1260    /// \brief The subscript operator.
1261    ///
1262    /// The subscript operator.
1263    /// \param key An undirected edge
1264    /// \return The "backward" directed edge view of undirected edge
1265    Value operator[](const Key& key) const {
1266      return graph.direct(key, false);
1267    }
1268
1269  private:
1270    const Graph& graph;
1271  };
1272
1273  /// \brief Returns a \ref BackwardMap class
1274
1275  /// This function just returns a \ref BackwardMap class.
1276  /// \relates BackwardMap
1277  template <typename Graph>
1278  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1279    return BackwardMap<Graph>(graph);
1280  }
1281
1282  /// \brief Potential difference map
1283  ///
1284  /// If there is an potential map on the nodes then we
1285  /// can get an edge map as we get the substraction of the
1286  /// values of the target and source.
1287  template <typename Graph, typename NodeMap>
1288  class PotentialDifferenceMap {
1289  public:
1290    typedef typename Graph::Edge Key;
1291    typedef typename NodeMap::Value Value;
1292
1293    /// \brief Constructor
1294    ///
1295    /// Contructor of the map
1296    PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1297      : graph(_graph), potential(_potential) {}
1298
1299    /// \brief Const subscription operator
1300    ///
1301    /// Const subscription operator
1302    Value operator[](const Key& edge) const {
1303      return potential[graph.target(edge)] - potential[graph.source(edge)];
1304    }
1305
1306  private:
1307    const Graph& graph;
1308    const NodeMap& potential;
1309  };
1310
1311  /// \brief Just returns a PotentialDifferenceMap
1312  ///
1313  /// Just returns a PotentialDifferenceMap
1314  /// \relates PotentialDifferenceMap
1315  template <typename Graph, typename NodeMap>
1316  PotentialDifferenceMap<Graph, NodeMap>
1317  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1318    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1319  }
1320
1321  /// \brief Map of the node in-degrees.
1322  ///
1323  /// This map returns the in-degree of a node. Once it is constructed,
1324  /// the degrees are stored in a standard NodeMap, so each query is done
1325  /// in constant time. On the other hand, the values are updated automatically
1326  /// whenever the graph changes.
1327  ///
1328  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1329  /// alternative ways to modify the graph. The correct behavior of InDegMap
1330  /// is not guarantied if these additional featureas are used. For example
1331  /// the funstions \ref ListGraph::changeSource() "changeSource()",
1332  /// \ref ListGraph::changeTarget() "changeTarget()" and
1333  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1334  /// of \ref ListGraph will \e not update the degree values correctly.
1335  ///
1336  /// \sa OutDegMap
1337
1338  template <typename _Graph>
1339  class InDegMap 
1340    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1341
1342  public:
1343   
1344    typedef _Graph Graph;
1345    typedef int Value;
1346    typedef typename Graph::Node Key;
1347
1348  private:
1349
1350    class AutoNodeMap : public Graph::template NodeMap<int> {
1351    public:
1352
1353      typedef typename Graph::template NodeMap<int> Parent;
1354
1355      typedef typename Parent::Key Key;
1356      typedef typename Parent::Value Value;
1357     
1358      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1359     
1360      void add(const Key& key) {
1361        Parent::add(key);
1362        Parent::set(key, 0);
1363      }
1364    };
1365
1366  public:
1367
1368    /// \brief Constructor.
1369    ///
1370    /// Constructor for creating in-degree map.
1371    InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1372      AlterationNotifier<typename _Graph::Edge>
1373        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1374     
1375      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1376        deg[it] = countInEdges(graph, it);
1377      }
1378    }
1379
1380    virtual ~InDegMap() {
1381      AlterationNotifier<typename _Graph::Edge>::
1382        ObserverBase::detach();
1383    }
1384   
1385    /// Gives back the in-degree of a Node.
1386    int operator[](const Key& key) const {
1387      return deg[key];
1388    }
1389
1390  protected:
1391   
1392    typedef typename Graph::Edge Edge;
1393
1394    virtual void add(const Edge& edge) {
1395      ++deg[graph.target(edge)];
1396    }
1397
1398    virtual void erase(const Edge& edge) {
1399      --deg[graph.target(edge)];
1400    }
1401
1402    virtual void signalChange(const Edge& edge) {
1403      erase(edge);
1404    }
1405
1406    virtual void commitChange(const Edge& edge) {
1407      add(edge);
1408    }
1409
1410    virtual void build() {
1411      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1412        deg[it] = countInEdges(graph, it);
1413      }     
1414    }
1415
1416    virtual void clear() {
1417      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1418        deg[it] = 0;
1419      }
1420    }
1421  private:
1422   
1423    const _Graph& graph;
1424    AutoNodeMap deg;
1425  };
1426
1427  /// \brief Map of the node out-degrees.
1428  ///
1429  /// This map returns the out-degree of a node. Once it is constructed,
1430  /// the degrees are stored in a standard NodeMap, so each query is done
1431  /// in constant time. On the other hand, the values are updated automatically
1432  /// whenever the graph changes.
1433  ///
1434  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1435  /// alternative ways to modify the graph. The correct behavior of OutDegMap
1436  /// is not guarantied if these additional featureas are used. For example
1437  /// the funstions \ref ListGraph::changeSource() "changeSource()",
1438  /// \ref ListGraph::changeTarget() "changeTarget()" and
1439  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1440  /// of \ref ListGraph will \e not update the degree values correctly.
1441  ///
1442  /// \sa InDegMap
1443
1444  template <typename _Graph>
1445  class OutDegMap 
1446    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1447
1448  public:
1449   
1450    typedef _Graph Graph;
1451    typedef int Value;
1452    typedef typename Graph::Node Key;
1453
1454  private:
1455
1456    class AutoNodeMap : public Graph::template NodeMap<int> {
1457    public:
1458
1459      typedef typename Graph::template NodeMap<int> Parent;
1460
1461      typedef typename Parent::Key Key;
1462      typedef typename Parent::Value Value;
1463     
1464      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1465     
1466      void add(const Key& key) {
1467        Parent::add(key);
1468        Parent::set(key, 0);
1469      }
1470    };
1471
1472  public:
1473
1474    /// \brief Constructor.
1475    ///
1476    /// Constructor for creating out-degree map.
1477    OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1478      AlterationNotifier<typename _Graph::Edge>
1479        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1480     
1481      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1482        deg[it] = countOutEdges(graph, it);
1483      }
1484    }
1485
1486    virtual ~OutDegMap() {
1487      AlterationNotifier<typename _Graph::Edge>::
1488        ObserverBase::detach();
1489    }
1490   
1491    /// Gives back the in-degree of a Node.
1492    int operator[](const Key& key) const {
1493      return deg[key];
1494    }
1495
1496  protected:
1497   
1498    typedef typename Graph::Edge Edge;
1499
1500    virtual void add(const Edge& edge) {
1501      ++deg[graph.source(edge)];
1502    }
1503
1504    virtual void erase(const Edge& edge) {
1505      --deg[graph.source(edge)];
1506    }
1507
1508    virtual void signalChange(const Edge& edge) {
1509      erase(edge);
1510    }
1511
1512    virtual void commitChange(const Edge& edge) {
1513      add(edge);
1514    }
1515
1516
1517    virtual void build() {
1518      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1519        deg[it] = countOutEdges(graph, it);
1520      }     
1521    }
1522
1523    virtual void clear() {
1524      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1525        deg[it] = 0;
1526      }
1527    }
1528  private:
1529   
1530    const _Graph& graph;
1531    AutoNodeMap deg;
1532  };
1533
1534
1535  /// @}
1536
1537} //END OF NAMESPACE LEMON
1538
1539#endif
Note: See TracBrowser for help on using the repository browser.