COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1981:81c8efe92706

Last change on this file since 1981:81c8efe92706 was 1981:81c8efe92706, checked in by Balazs Dezso, 14 years ago

Little bugfixes, spellchecks and improvements

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