COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1990:15fb7a4ea6be

Last change on this file since 1990:15fb7a4ea6be was 1990:15fb7a4ea6be, checked in by Balazs Dezso, 14 years ago

Some classes assumed that the GraphMaps? should be inherited
from an ObserverBase?. These classes parents replaced with
DefaultMap? which cause that the graph maps should not be
inherited from the ObserverBase?.

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