COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1829:183b4cbf9733

Last change on this file since 1829:183b4cbf9733 was 1829:183b4cbf9733, checked in by Balazs Dezso, 14 years ago

Correcting alteration notifing

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