COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2204:5617107d27e9

Last change on this file since 2204:5617107d27e9 was 2201:597714206430, checked in by Balazs Dezso, 18 years ago

Bug fix in DescriptorMap?
Avoiding the possibility of the memory leak

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