COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2163:bef3457be038

Last change on this file since 2163:bef3457be038 was 2155:c712e66532d8, checked in by Alpar Juttner, 18 years ago

Minor doc changes.

File size: 52.7 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.nodeNum();
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.nodeNum();
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      build();
1264    }
1265
1266  protected:
1267
1268    /// \brief Add a new key to the map.
1269    ///
1270    /// Add a new key to the map. It is called by the
1271    /// \c AlterationNotifier.
1272    virtual void add(const Item& item) {
1273      Map::add(item);
1274      Map::set(item, invMap.size());
1275      invMap.push_back(item);
1276    }
1277
1278    /// \brief Add more new keys to the map.
1279    ///
1280    /// Add more new keys to the map. It is called by the
1281    /// \c AlterationNotifier.
1282    virtual void add(const std::vector<Item>& items) {
1283      Map::add(items);
1284      for (int i = 0; i < (int)items.size(); ++i) {
1285        Map::set(items[i], invMap.size());
1286        invMap.push_back(items[i]);
1287      }
1288    }
1289
1290    /// \brief Erase the key from the map.
1291    ///
1292    /// Erase the key from the map. It is called by the
1293    /// \c AlterationNotifier.
1294    virtual void erase(const Item& item) {
1295      Map::set(invMap.back(), Map::operator[](item));
1296      invMap[Map::operator[](item)] = invMap.back();
1297      invMap.pop_back();
1298      Map::erase(item);
1299    }
1300
1301    /// \brief Erase more keys from the map.
1302    ///
1303    /// Erase more keys from the map. It is called by the
1304    /// \c AlterationNotifier.
1305    virtual void erase(const std::vector<Item>& items) {
1306      for (int i = 0; i < (int)items.size(); ++i) {
1307        Map::set(invMap.back(), Map::operator[](items[i]));
1308        invMap[Map::operator[](items[i])] = invMap.back();
1309        invMap.pop_back();
1310      }
1311      Map::erase(items);
1312    }
1313
1314    /// \brief Build the unique map.
1315    ///
1316    /// Build the unique map. It is called by the
1317    /// \c AlterationNotifier.
1318    virtual void build() {
1319      Map::build();
1320      Item it;
1321      const typename Map::Notifier* notifier = Map::getNotifier();
1322      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1323        Map::set(it, invMap.size());
1324        invMap.push_back(it);   
1325      }     
1326    }
1327   
1328    /// \brief Clear the keys from the map.
1329    ///
1330    /// Clear the keys from the map. It is called by the
1331    /// \c AlterationNotifier.
1332    virtual void clear() {
1333      invMap.clear();
1334      Map::clear();
1335    }
1336
1337  public:
1338
1339    /// \brief Returns the maximal value plus one.
1340    ///
1341    /// Returns the maximal value plus one in the map.
1342    unsigned int size() const {
1343      return invMap.size();
1344    }
1345
1346    /// \brief Swaps the position of the two items in the map.
1347    ///
1348    /// Swaps the position of the two items in the map.
1349    void swap(const Item& p, const Item& q) {
1350      int pi = Map::operator[](p);
1351      int qi = Map::operator[](q);
1352      Map::set(p, qi);
1353      invMap[qi] = p;
1354      Map::set(q, pi);
1355      invMap[pi] = q;
1356    }
1357
1358    /// \brief Gives back the \e descriptor of the item.
1359    ///
1360    /// Gives back the mutable and unique \e descriptor of the map.
1361    int operator[](const Item& item) const {
1362      return Map::operator[](item);
1363    }
1364   
1365  private:
1366
1367    typedef std::vector<Item> Container;
1368    Container invMap;
1369
1370  public:
1371    /// \brief The inverse map type of DescriptorMap.
1372    ///
1373    /// The inverse map type of DescriptorMap.
1374    class InverseMap {
1375    public:
1376      /// \brief Constructor of the InverseMap.
1377      ///
1378      /// Constructor of the InverseMap.
1379      InverseMap(const DescriptorMap& _inverted)
1380        : inverted(_inverted) {}
1381
1382
1383      /// The value type of the InverseMap.
1384      typedef typename DescriptorMap::Key Value;
1385      /// The key type of the InverseMap.
1386      typedef typename DescriptorMap::Value Key;
1387
1388      /// \brief Subscript operator.
1389      ///
1390      /// Subscript operator. It gives back the item
1391      /// that the descriptor belongs to currently.
1392      Value operator[](const Key& key) const {
1393        return inverted.invMap[key];
1394      }
1395
1396      /// \brief Size of the map.
1397      ///
1398      /// Returns the size of the map.
1399      unsigned int size() const {
1400        return inverted.invMap.size();
1401      }
1402     
1403    private:
1404      const DescriptorMap& inverted;
1405    };
1406
1407    /// \brief Gives back the inverse of the map.
1408    ///
1409    /// Gives back the inverse of the map.
1410    const InverseMap inverse() const {
1411      return InverseMap(*this);
1412    }
1413  };
1414
1415  /// \brief Returns the source of the given edge.
1416  ///
1417  /// The SourceMap gives back the source Node of the given edge.
1418  /// \author Balazs Dezso
1419  template <typename Graph>
1420  class SourceMap {
1421  public:
1422
1423    typedef typename Graph::Node Value;
1424    typedef typename Graph::Edge Key;
1425
1426    /// \brief Constructor
1427    ///
1428    /// Constructor
1429    /// \param _graph The graph that the map belongs to.
1430    SourceMap(const Graph& _graph) : graph(_graph) {}
1431
1432    /// \brief The subscript operator.
1433    ///
1434    /// The subscript operator.
1435    /// \param edge The edge
1436    /// \return The source of the edge
1437    Value operator[](const Key& edge) const {
1438      return graph.source(edge);
1439    }
1440
1441  private:
1442    const Graph& graph;
1443  };
1444
1445  /// \brief Returns a \ref SourceMap class
1446  ///
1447  /// This function just returns an \ref SourceMap class.
1448  /// \relates SourceMap
1449  template <typename Graph>
1450  inline SourceMap<Graph> sourceMap(const Graph& graph) {
1451    return SourceMap<Graph>(graph);
1452  }
1453
1454  /// \brief Returns the target of the given edge.
1455  ///
1456  /// The TargetMap gives back the target Node of the given edge.
1457  /// \author Balazs Dezso
1458  template <typename Graph>
1459  class TargetMap {
1460  public:
1461
1462    typedef typename Graph::Node Value;
1463    typedef typename Graph::Edge Key;
1464
1465    /// \brief Constructor
1466    ///
1467    /// Constructor
1468    /// \param _graph The graph that the map belongs to.
1469    TargetMap(const Graph& _graph) : graph(_graph) {}
1470
1471    /// \brief The subscript operator.
1472    ///
1473    /// The subscript operator.
1474    /// \param e The edge
1475    /// \return The target of the edge
1476    Value operator[](const Key& e) const {
1477      return graph.target(e);
1478    }
1479
1480  private:
1481    const Graph& graph;
1482  };
1483
1484  /// \brief Returns a \ref TargetMap class
1485  ///
1486  /// This function just returns a \ref TargetMap class.
1487  /// \relates TargetMap
1488  template <typename Graph>
1489  inline TargetMap<Graph> targetMap(const Graph& graph) {
1490    return TargetMap<Graph>(graph);
1491  }
1492
1493  /// \brief Returns the "forward" directed edge view of an undirected edge.
1494  ///
1495  /// Returns the "forward" directed edge view of an undirected edge.
1496  /// \author Balazs Dezso
1497  template <typename Graph>
1498  class ForwardMap {
1499  public:
1500
1501    typedef typename Graph::Edge Value;
1502    typedef typename Graph::UEdge Key;
1503
1504    /// \brief Constructor
1505    ///
1506    /// Constructor
1507    /// \param _graph The graph that the map belongs to.
1508    ForwardMap(const Graph& _graph) : graph(_graph) {}
1509
1510    /// \brief The subscript operator.
1511    ///
1512    /// The subscript operator.
1513    /// \param key An undirected edge
1514    /// \return The "forward" directed edge view of undirected edge
1515    Value operator[](const Key& key) const {
1516      return graph.direct(key, true);
1517    }
1518
1519  private:
1520    const Graph& graph;
1521  };
1522
1523  /// \brief Returns a \ref ForwardMap class
1524  ///
1525  /// This function just returns an \ref ForwardMap class.
1526  /// \relates ForwardMap
1527  template <typename Graph>
1528  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1529    return ForwardMap<Graph>(graph);
1530  }
1531
1532  /// \brief Returns the "backward" directed edge view of an undirected edge.
1533  ///
1534  /// Returns the "backward" directed edge view of an undirected edge.
1535  /// \author Balazs Dezso
1536  template <typename Graph>
1537  class BackwardMap {
1538  public:
1539
1540    typedef typename Graph::Edge Value;
1541    typedef typename Graph::UEdge Key;
1542
1543    /// \brief Constructor
1544    ///
1545    /// Constructor
1546    /// \param _graph The graph that the map belongs to.
1547    BackwardMap(const Graph& _graph) : graph(_graph) {}
1548
1549    /// \brief The subscript operator.
1550    ///
1551    /// The subscript operator.
1552    /// \param key An undirected edge
1553    /// \return The "backward" directed edge view of undirected edge
1554    Value operator[](const Key& key) const {
1555      return graph.direct(key, false);
1556    }
1557
1558  private:
1559    const Graph& graph;
1560  };
1561
1562  /// \brief Returns a \ref BackwardMap class
1563
1564  /// This function just returns a \ref BackwardMap class.
1565  /// \relates BackwardMap
1566  template <typename Graph>
1567  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1568    return BackwardMap<Graph>(graph);
1569  }
1570
1571  /// \brief Potential difference map
1572  ///
1573  /// If there is an potential map on the nodes then we
1574  /// can get an edge map as we get the substraction of the
1575  /// values of the target and source.
1576  template <typename Graph, typename NodeMap>
1577  class PotentialDifferenceMap {
1578  public:
1579    typedef typename Graph::Edge Key;
1580    typedef typename NodeMap::Value Value;
1581
1582    /// \brief Constructor
1583    ///
1584    /// Contructor of the map
1585    PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1586      : graph(_graph), potential(_potential) {}
1587
1588    /// \brief Const subscription operator
1589    ///
1590    /// Const subscription operator
1591    Value operator[](const Key& edge) const {
1592      return potential[graph.target(edge)] - potential[graph.source(edge)];
1593    }
1594
1595  private:
1596    const Graph& graph;
1597    const NodeMap& potential;
1598  };
1599
1600  /// \brief Just returns a PotentialDifferenceMap
1601  ///
1602  /// Just returns a PotentialDifferenceMap
1603  /// \relates PotentialDifferenceMap
1604  template <typename Graph, typename NodeMap>
1605  PotentialDifferenceMap<Graph, NodeMap>
1606  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1607    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1608  }
1609
1610  /// \brief Map of the node in-degrees.
1611  ///
1612  /// This map returns the in-degree of a node. Once it is constructed,
1613  /// the degrees are stored in a standard NodeMap, so each query is done
1614  /// in constant time. On the other hand, the values are updated automatically
1615  /// whenever the graph changes.
1616  ///
1617  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1618  /// alternative ways to modify the graph. The correct behavior of InDegMap
1619  /// is not guarantied if these additional features are used. For example
1620  /// the functions \ref ListGraph::changeSource() "changeSource()",
1621  /// \ref ListGraph::changeTarget() "changeTarget()" and
1622  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1623  /// of \ref ListGraph will \e not update the degree values correctly.
1624  ///
1625  /// \sa OutDegMap
1626
1627  template <typename _Graph>
1628  class InDegMap 
1629    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1630      ::ItemNotifier::ObserverBase {
1631
1632  public:
1633   
1634    typedef _Graph Graph;
1635    typedef int Value;
1636    typedef typename Graph::Node Key;
1637
1638    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1639    ::ItemNotifier::ObserverBase Parent;
1640
1641  private:
1642
1643    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1644    public:
1645
1646      typedef DefaultMap<_Graph, Key, int> Parent;
1647      typedef typename Parent::Graph Graph;
1648
1649      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1650     
1651      virtual void add(const Key& key) {
1652        Parent::add(key);
1653        Parent::set(key, 0);
1654      }
1655
1656      virtual void add(const std::vector<Key>& keys) {
1657        Parent::add(keys);
1658        for (int i = 0; i < (int)keys.size(); ++i) {
1659          Parent::set(keys[i], 0);
1660        }
1661      }
1662    };
1663
1664  public:
1665
1666    /// \brief Constructor.
1667    ///
1668    /// Constructor for creating in-degree map.
1669    InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1670      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1671     
1672      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1673        deg[it] = countInEdges(graph, it);
1674      }
1675    }
1676   
1677    /// Gives back the in-degree of a Node.
1678    int operator[](const Key& key) const {
1679      return deg[key];
1680    }
1681
1682  protected:
1683   
1684    typedef typename Graph::Edge Edge;
1685
1686    virtual void add(const Edge& edge) {
1687      ++deg[graph.target(edge)];
1688    }
1689
1690    virtual void add(const std::vector<Edge>& edges) {
1691      for (int i = 0; i < (int)edges.size(); ++i) {
1692        ++deg[graph.target(edges[i])];
1693      }
1694    }
1695
1696    virtual void erase(const Edge& edge) {
1697      --deg[graph.target(edge)];
1698    }
1699
1700    virtual void erase(const std::vector<Edge>& edges) {
1701      for (int i = 0; i < (int)edges.size(); ++i) {
1702        --deg[graph.target(edges[i])];
1703      }
1704    }
1705
1706    virtual void build() {
1707      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1708        deg[it] = countInEdges(graph, it);
1709      }     
1710    }
1711
1712    virtual void clear() {
1713      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1714        deg[it] = 0;
1715      }
1716    }
1717  private:
1718   
1719    const _Graph& graph;
1720    AutoNodeMap deg;
1721  };
1722
1723  /// \brief Map of the node out-degrees.
1724  ///
1725  /// This map returns the out-degree of a node. Once it is constructed,
1726  /// the degrees are stored in a standard NodeMap, so each query is done
1727  /// in constant time. On the other hand, the values are updated automatically
1728  /// whenever the graph changes.
1729  ///
1730  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1731  /// alternative ways to modify the graph. The correct behavior of OutDegMap
1732  /// is not guarantied if these additional features are used. For example
1733  /// the functions \ref ListGraph::changeSource() "changeSource()",
1734  /// \ref ListGraph::changeTarget() "changeTarget()" and
1735  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1736  /// of \ref ListGraph will \e not update the degree values correctly.
1737  ///
1738  /// \sa InDegMap
1739
1740  template <typename _Graph>
1741  class OutDegMap 
1742    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1743      ::ItemNotifier::ObserverBase {
1744
1745  public:
1746
1747    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1748    ::ItemNotifier::ObserverBase Parent;
1749   
1750    typedef _Graph Graph;
1751    typedef int Value;
1752    typedef typename Graph::Node Key;
1753
1754  private:
1755
1756    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1757    public:
1758
1759      typedef DefaultMap<_Graph, Key, int> Parent;
1760      typedef typename Parent::Graph Graph;
1761
1762      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1763     
1764      virtual void add(const Key& key) {
1765        Parent::add(key);
1766        Parent::set(key, 0);
1767      }
1768      virtual void add(const std::vector<Key>& keys) {
1769        Parent::add(keys);
1770        for (int i = 0; i < (int)keys.size(); ++i) {
1771          Parent::set(keys[i], 0);
1772        }
1773      }
1774    };
1775
1776  public:
1777
1778    /// \brief Constructor.
1779    ///
1780    /// Constructor for creating out-degree map.
1781    OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1782      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1783     
1784      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1785        deg[it] = countOutEdges(graph, it);
1786      }
1787    }
1788
1789    /// Gives back the out-degree of a Node.
1790    int operator[](const Key& key) const {
1791      return deg[key];
1792    }
1793
1794  protected:
1795   
1796    typedef typename Graph::Edge Edge;
1797
1798    virtual void add(const Edge& edge) {
1799      ++deg[graph.source(edge)];
1800    }
1801
1802    virtual void add(const std::vector<Edge>& edges) {
1803      for (int i = 0; i < (int)edges.size(); ++i) {
1804        ++deg[graph.source(edges[i])];
1805      }
1806    }
1807
1808    virtual void erase(const Edge& edge) {
1809      --deg[graph.source(edge)];
1810    }
1811
1812    virtual void erase(const std::vector<Edge>& edges) {
1813      for (int i = 0; i < (int)edges.size(); ++i) {
1814        --deg[graph.source(edges[i])];
1815      }
1816    }
1817
1818    virtual void build() {
1819      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1820        deg[it] = countOutEdges(graph, it);
1821      }     
1822    }
1823
1824    virtual void clear() {
1825      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1826        deg[it] = 0;
1827      }
1828    }
1829  private:
1830   
1831    const _Graph& graph;
1832    AutoNodeMap deg;
1833  };
1834
1835
1836  /// @}
1837
1838} //END OF NAMESPACE LEMON
1839
1840#endif
Note: See TracBrowser for help on using the repository browser.