COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1931:6abf67b02ff5

Last change on this file since 1931:6abf67b02ff5 was 1931:6abf67b02ff5, checked in by Balazs Dezso, 14 years ago

New iterable map with comparable values

it uses linked lists and balanced binary tree

IterableBoolMap? has ItemIt? type as the other iterable maps

InvertableMap? got ValueIterator?

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