COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 52.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_GRAPH_UTILS_H
20#define LEMON_GRAPH_UTILS_H
21
22#include <iterator>
23#include <vector>
24#include <map>
25#include <cmath>
26
27#include <lemon/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  template <typename Graph>
377  inline typename Graph::Edge findEdge(const Graph &g,
378                                       typename Graph::Node u,
379                                       typename Graph::Node v,
380                                       typename Graph::Edge prev = INVALID) {
381    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
382  }
383
384  /// \brief Iterator for iterating on edges connected the same nodes.
385  ///
386  /// Iterator for iterating on edges connected the same nodes. It is
387  /// higher level interface for the findEdge() function. You can
388  /// use it the following way:
389  ///\code
390  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
391  ///   ...
392  /// }
393  ///\endcode
394  ///
395  /// \author Balazs Dezso
396  template <typename _Graph>
397  class ConEdgeIt : public _Graph::Edge {
398  public:
399
400    typedef _Graph Graph;
401    typedef typename Graph::Edge Parent;
402
403    typedef typename Graph::Edge Edge;
404    typedef typename Graph::Node Node;
405
406    /// \brief Constructor.
407    ///
408    /// Construct a new ConEdgeIt iterating on the edges which
409    /// connects the \c u and \c v node.
410    ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
411      Parent::operator=(findEdge(graph, u, v));
412    }
413
414    /// \brief Constructor.
415    ///
416    /// Construct a new ConEdgeIt which continues the iterating from
417    /// the \c e edge.
418    ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
419   
420    /// \brief Increment operator.
421    ///
422    /// It increments the iterator and gives back the next edge.
423    ConEdgeIt& operator++() {
424      Parent::operator=(findEdge(graph, graph.source(*this),
425                                 graph.target(*this), *this));
426      return *this;
427    }
428  private:
429    const Graph& graph;
430  };
431
432  namespace _graph_utils_bits {
433   
434    template <typename Graph, typename Enable = void>
435    struct FindUEdgeSelector {
436      typedef typename Graph::Node Node;
437      typedef typename Graph::UEdge UEdge;
438      static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
439        bool b;
440        if (u != v) {
441          if (e == INVALID) {
442            g.firstInc(e, b, u);
443          } else {
444            b = g.source(e) == u;
445            g.nextInc(e, b);
446          }
447          while (e != INVALID && g.target(e) != v) {
448            g.nextInc(e, b);
449          }
450        } else {
451          if (e == INVALID) {
452            g.firstInc(e, b, u);
453          } else {
454            b = true;
455            g.nextInc(e, b);
456          }
457          while (e != INVALID && (!b || g.target(e) != v)) {
458            g.nextInc(e, b);
459          }
460        }
461        return e;
462      }
463    };
464
465    template <typename Graph>
466    struct FindUEdgeSelector<
467      Graph,
468      typename enable_if<typename Graph::FindEdgeTag, void>::type>
469    {
470      typedef typename Graph::Node Node;
471      typedef typename Graph::UEdge UEdge;
472      static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
473        return g.findUEdge(u, v, prev);
474      }
475    };   
476  }
477
478  /// \brief Finds an uedge between two nodes of a graph.
479  ///
480  /// Finds an uedge from node \c u to node \c v in graph \c g.
481  /// If the node \c u and node \c v is equal then each loop edge
482  /// will be enumerated.
483  ///
484  /// If \c prev is \ref INVALID (this is the default value), then
485  /// it finds the first edge from \c u to \c v. Otherwise it looks for
486  /// the next edge from \c u to \c v after \c prev.
487  /// \return The found edge or \ref INVALID if there is no such an edge.
488  ///
489  /// Thus you can iterate through each edge from \c u to \c v as it follows.
490  ///\code
491  /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
492  ///     e = findUEdge(g,u,v,e)) {
493  ///   ...
494  /// }
495  ///\endcode
496  template <typename Graph>
497  inline typename Graph::UEdge findUEdge(const Graph &g,
498                                         typename Graph::Node u,
499                                         typename Graph::Node v,
500                                         typename Graph::UEdge p = INVALID) {
501    return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
502  }
503
504  /// \brief Iterator for iterating on uedges connected the same nodes.
505  ///
506  /// Iterator for iterating on uedges connected the same nodes. It is
507  /// higher level interface for the findUEdge() function. You can
508  /// use it the following way:
509  ///\code
510  /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
511  ///   ...
512  /// }
513  ///\endcode
514  ///
515  /// \author Balazs Dezso
516  template <typename _Graph>
517  class ConUEdgeIt : public _Graph::UEdge {
518  public:
519
520    typedef _Graph Graph;
521    typedef typename Graph::UEdge Parent;
522
523    typedef typename Graph::UEdge UEdge;
524    typedef typename Graph::Node Node;
525
526    /// \brief Constructor.
527    ///
528    /// Construct a new ConUEdgeIt iterating on the edges which
529    /// connects the \c u and \c v node.
530    ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
531      Parent::operator=(findUEdge(graph, u, v));
532    }
533
534    /// \brief Constructor.
535    ///
536    /// Construct a new ConUEdgeIt which continues the iterating from
537    /// the \c e edge.
538    ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
539   
540    /// \brief Increment operator.
541    ///
542    /// It increments the iterator and gives back the next edge.
543    ConUEdgeIt& operator++() {
544      Parent::operator=(findUEdge(graph, graph.source(*this),
545                                      graph.target(*this), *this));
546      return *this;
547    }
548  private:
549    const Graph& graph;
550  };
551
552  /// \brief Copy a map.
553  ///
554  /// This function copies the \c source map to the \c target map. It uses the
555  /// given iterator to iterate on the data structure and it uses the \c ref
556  /// mapping to convert the source's keys to the target's keys.
557  template <typename Target, typename Source,
558            typename ItemIt, typename Ref>         
559  void copyMap(Target& target, const Source& source,
560               ItemIt it, const Ref& ref) {
561    for (; it != INVALID; ++it) {
562      target[ref[it]] = source[it];
563    }
564  }
565
566  /// \brief Copy the source map to the target map.
567  ///
568  /// Copy the \c source map to the \c target map. It uses the given iterator
569  /// to iterate on the data structure.
570  template <typename Target, typename Source, typename ItemIt>     
571  void copyMap(Target& target, const Source& source, ItemIt it) {
572    for (; it != INVALID; ++it) {
573      target[it] = source[it];
574    }
575  }
576
577  /// \brief Class to copy a graph.
578  ///
579  /// Class to copy a graph to another graph (duplicate a graph). The
580  /// simplest way of using it is through the \c copyGraph() function.
581  template <typename Target, typename Source>
582  class GraphCopy {
583  public:
584    typedef typename Source::Node Node;
585    typedef typename Source::NodeIt NodeIt;
586    typedef typename Source::Edge Edge;
587    typedef typename Source::EdgeIt EdgeIt;
588
589    typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
590    typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
591
592    /// \brief Constructor for the GraphCopy.
593    ///
594    /// It copies the content of the \c _source graph into the
595    /// \c _target graph. It creates also two references, one beetween
596    /// the two nodeset and one beetween the two edgesets.
597    GraphCopy(Target& _target, const Source& _source)
598      : source(_source), target(_target),
599        nodeRefMap(_source), edgeRefMap(_source) {
600      for (NodeIt it(source); it != INVALID; ++it) {
601        nodeRefMap[it] = target.addNode();
602      }
603      for (EdgeIt it(source); it != INVALID; ++it) {
604        edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
605                                        nodeRefMap[source.target(it)]);
606      }
607    }
608
609    /// \brief Copies the node references into the given map.
610    ///
611    /// Copies the node references into the given map.
612    template <typename NodeRef>
613    const GraphCopy& nodeRef(NodeRef& map) const {
614      for (NodeIt it(source); it != INVALID; ++it) {
615        map.set(it, nodeRefMap[it]);
616      }
617      return *this;
618    }
619
620    /// \brief Reverse and copies the node references into the given map.
621    ///
622    /// Reverse and copies the node references into the given map.
623    template <typename NodeRef>
624    const GraphCopy& nodeCrossRef(NodeRef& map) const {
625      for (NodeIt it(source); it != INVALID; ++it) {
626        map.set(nodeRefMap[it], it);
627      }
628      return *this;
629    }
630
631    /// \brief Copies the edge references into the given map.
632    ///
633    /// Copies the edge references into the given map.
634    template <typename EdgeRef>
635    const GraphCopy& edgeRef(EdgeRef& map) const {
636      for (EdgeIt it(source); it != INVALID; ++it) {
637        map.set(it, edgeRefMap[it]);
638      }
639      return *this;
640    }
641
642    /// \brief Reverse and copies the edge references into the given map.
643    ///
644    /// Reverse and copies the edge references into the given map.
645    template <typename EdgeRef>
646    const GraphCopy& edgeCrossRef(EdgeRef& map) const {
647      for (EdgeIt it(source); it != INVALID; ++it) {
648        map.set(edgeRefMap[it], it);
649      }
650      return *this;
651    }
652
653    /// \brief Make copy of the given map.
654    ///
655    /// Makes copy of the given map for the newly created graph.
656    /// The new map's key type is the target graph's node type,
657    /// and the copied map's key type is the source graph's node
658    /// type. 
659    template <typename TargetMap, typename SourceMap>
660    const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
661      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
662      return *this;
663    }
664
665    /// \brief Make copy of the given map.
666    ///
667    /// Makes copy of the given map for the newly created graph.
668    /// The new map's key type is the target graph's edge type,
669    /// and the copied map's key type is the source graph's edge
670    /// type. 
671    template <typename TargetMap, typename SourceMap>
672    const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
673      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
674      return *this;
675    }
676
677    /// \brief Gives back the stored node references.
678    ///
679    /// Gives back the stored node references.
680    const NodeRefMap& nodeRef() const {
681      return nodeRefMap;
682    }
683
684    /// \brief Gives back the stored edge references.
685    ///
686    /// Gives back the stored edge references.
687    const EdgeRefMap& edgeRef() const {
688      return edgeRefMap;
689    }
690
691    void run() const {}
692
693  private:
694   
695    const Source& source;
696    Target& target;
697
698    NodeRefMap nodeRefMap;
699    EdgeRefMap edgeRefMap;
700  };
701
702  /// \brief Copy a graph to another graph.
703  ///
704  /// Copy a graph to another graph.
705  /// The usage of the function:
706  ///
707  ///\code
708  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
709  ///\endcode
710  ///
711  /// After the copy the \c nr map will contain the mapping from the
712  /// source graph's nodes to the target graph's nodes and the \c ecr will
713  /// contain the mapping from the target graph's edges to the source's
714  /// edges.
715  template <typename Target, typename Source>
716  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
717    return GraphCopy<Target, Source>(target, source);
718  }
719
720  /// \brief Class to copy an undirected graph.
721  ///
722  /// Class to copy an undirected graph to another graph (duplicate a graph).
723  /// The simplest way of using it is through the \c copyUGraph() function.
724  template <typename Target, typename Source>
725  class UGraphCopy {
726  public:
727    typedef typename Source::Node Node;
728    typedef typename Source::NodeIt NodeIt;
729    typedef typename Source::Edge Edge;
730    typedef typename Source::EdgeIt EdgeIt;
731    typedef typename Source::UEdge UEdge;
732    typedef typename Source::UEdgeIt UEdgeIt;
733
734    typedef typename Source::
735    template NodeMap<typename Target::Node> NodeRefMap;
736   
737    typedef typename Source::
738    template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
739
740  private:
741
742    struct EdgeRefMap {
743      EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
744      typedef typename Source::Edge Key;
745      typedef typename Target::Edge Value;
746
747      Value operator[](const Key& key) {
748        return gc.target.direct(gc.uEdgeRef[key],
749                                gc.target.direction(key));
750      }
751     
752      UGraphCopy& gc;
753    };
754   
755  public:
756
757    /// \brief Constructor for the UGraphCopy.
758    ///
759    /// It copies the content of the \c _source graph into the
760    /// \c _target graph. It creates also two references, one beetween
761    /// the two nodeset and one beetween the two edgesets.
762    UGraphCopy(Target& _target, const Source& _source)
763      : source(_source), target(_target),
764        nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
765      for (NodeIt it(source); it != INVALID; ++it) {
766        nodeRefMap[it] = target.addNode();
767      }
768      for (UEdgeIt it(source); it != INVALID; ++it) {
769        uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
770                                        nodeRefMap[source.target(it)]);
771      }
772    }
773
774    /// \brief Copies the node references into the given map.
775    ///
776    /// Copies the node references into the given map.
777    template <typename NodeRef>
778    const UGraphCopy& nodeRef(NodeRef& map) const {
779      for (NodeIt it(source); it != INVALID; ++it) {
780        map.set(it, nodeRefMap[it]);
781      }
782      return *this;
783    }
784
785    /// \brief Reverse and copies the node references into the given map.
786    ///
787    /// Reverse and copies the node references into the given map.
788    template <typename NodeRef>
789    const UGraphCopy& nodeCrossRef(NodeRef& map) const {
790      for (NodeIt it(source); it != INVALID; ++it) {
791        map.set(nodeRefMap[it], it);
792      }
793      return *this;
794    }
795
796    /// \brief Copies the edge references into the given map.
797    ///
798    /// Copies the edge references into the given map.
799    template <typename EdgeRef>
800    const UGraphCopy& edgeRef(EdgeRef& map) const {
801      for (EdgeIt it(source); it != INVALID; ++it) {
802        map.set(edgeRefMap[it], it);
803      }
804      return *this;
805    }
806
807    /// \brief Reverse and copies the undirected edge references into the
808    /// given map.
809    ///
810    /// Reverse and copies the undirected edge references into the given map.
811    template <typename EdgeRef>
812    const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
813      for (EdgeIt it(source); it != INVALID; ++it) {
814        map.set(it, edgeRefMap[it]);
815      }
816      return *this;
817    }
818
819    /// \brief Copies the undirected edge references into the given map.
820    ///
821    /// Copies the undirected edge references into the given map.
822    template <typename EdgeRef>
823    const UGraphCopy& uEdgeRef(EdgeRef& map) const {
824      for (UEdgeIt it(source); it != INVALID; ++it) {
825        map.set(it, uEdgeRefMap[it]);
826      }
827      return *this;
828    }
829
830    /// \brief Reverse and copies the undirected edge references into the
831    /// given map.
832    ///
833    /// Reverse and copies the undirected edge references into the given map.
834    template <typename EdgeRef>
835    const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
836      for (UEdgeIt it(source); it != INVALID; ++it) {
837        map.set(uEdgeRefMap[it], it);
838      }
839      return *this;
840    }
841
842    /// \brief Make copy of the given map.
843    ///
844    /// Makes copy of the given map for the newly created graph.
845    /// The new map's key type is the target graph's node type,
846    /// and the copied map's key type is the source graph's node
847    /// type. 
848    template <typename TargetMap, typename SourceMap>
849    const UGraphCopy& nodeMap(TargetMap& tMap,
850                                  const SourceMap& sMap) const {
851      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
852      return *this;
853    }
854
855    /// \brief Make copy of the given map.
856    ///
857    /// Makes copy of the given map for the newly created graph.
858    /// The new map's key type is the target graph's edge type,
859    /// and the copied map's key type is the source graph's edge
860    /// type. 
861    template <typename TargetMap, typename SourceMap>
862    const UGraphCopy& edgeMap(TargetMap& tMap,
863                                  const SourceMap& sMap) const {
864      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
865      return *this;
866    }
867
868    /// \brief Make copy of the given map.
869    ///
870    /// Makes copy of the given map for the newly created graph.
871    /// The new map's key type is the target graph's edge type,
872    /// and the copied map's key type is the source graph's edge
873    /// type. 
874    template <typename TargetMap, typename SourceMap>
875    const UGraphCopy& uEdgeMap(TargetMap& tMap,
876                                  const SourceMap& sMap) const {
877      copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
878      return *this;
879    }
880
881    /// \brief Gives back the stored node references.
882    ///
883    /// Gives back the stored node references.
884    const NodeRefMap& nodeRef() const {
885      return nodeRefMap;
886    }
887
888    /// \brief Gives back the stored edge references.
889    ///
890    /// Gives back the stored edge references.
891    const EdgeRefMap& edgeRef() const {
892      return edgeRefMap;
893    }
894
895    /// \brief Gives back the stored uedge references.
896    ///
897    /// Gives back the stored uedge references.
898    const UEdgeRefMap& uEdgeRef() const {
899      return uEdgeRefMap;
900    }
901
902    void run() const {}
903
904  private:
905   
906    const Source& source;
907    Target& target;
908
909    NodeRefMap nodeRefMap;
910    EdgeRefMap edgeRefMap;
911    UEdgeRefMap uEdgeRefMap;
912  };
913
914  /// \brief Copy a graph to another graph.
915  ///
916  /// Copy a graph to another graph.
917  /// The usage of the function:
918  ///
919  ///\code
920  /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
921  ///\endcode
922  ///
923  /// After the copy the \c nr map will contain the mapping from the
924  /// source graph's nodes to the target graph's nodes and the \c ecr will
925  /// contain the mapping from the target graph's edges to the source's
926  /// edges.
927  template <typename Target, typename Source>
928  UGraphCopy<Target, Source>
929  copyUGraph(Target& target, const Source& source) {
930    return UGraphCopy<Target, Source>(target, source);
931  }
932
933
934  /// @}
935
936  /// \addtogroup graph_maps
937  /// @{
938
939  /// Provides an immutable and unique id for each item in the graph.
940
941  /// The IdMap class provides a unique and immutable id for each item of the
942  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
943  /// different items (nodes) get different ids <li>\b immutable: the id of an
944  /// item (node) does not change (even if you delete other nodes).  </ul>
945  /// Through this map you get access (i.e. can read) the inner id values of
946  /// the items stored in the graph. This map can be inverted with its member
947  /// class \c InverseMap.
948  ///
949  template <typename _Graph, typename _Item>
950  class IdMap {
951  public:
952    typedef _Graph Graph;
953    typedef int Value;
954    typedef _Item Item;
955    typedef _Item Key;
956
957    /// \brief Constructor.
958    ///
959    /// Constructor for creating id map.
960    IdMap(const Graph& _graph) : graph(&_graph) {}
961
962    /// \brief Gives back the \e id of the item.
963    ///
964    /// Gives back the immutable and unique \e id of the map.
965    int operator[](const Item& item) const { return graph->id(item);}
966
967
968  private:
969    const Graph* graph;
970
971  public:
972
973    /// \brief The class represents the inverse of its owner (IdMap).
974    ///
975    /// The class represents the inverse of its owner (IdMap).
976    /// \see inverse()
977    class InverseMap {
978    public:
979
980      /// \brief Constructor.
981      ///
982      /// Constructor for creating an id-to-item map.
983      InverseMap(const Graph& _graph) : graph(&_graph) {}
984
985      /// \brief Constructor.
986      ///
987      /// Constructor for creating an id-to-item map.
988      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
989
990      /// \brief Gives back the given item from its id.
991      ///
992      /// Gives back the given item from its id.
993      ///
994      Item operator[](int id) const { return graph->fromId(id, Item());}
995    private:
996      const Graph* graph;
997    };
998
999    /// \brief Gives back the inverse of the map.
1000    ///
1001    /// Gives back the inverse of the IdMap.
1002    InverseMap inverse() const { return InverseMap(*graph);}
1003
1004  };
1005
1006 
1007  /// \brief General invertable graph-map type.
1008
1009  /// This type provides simple invertable graph-maps.
1010  /// The InvertableMap wraps an arbitrary ReadWriteMap
1011  /// and if a key is set to a new value then store it
1012  /// in the inverse map.
1013  ///
1014  /// The values of the map can be accessed
1015  /// with stl compatible forward iterator.
1016  ///
1017  /// \param _Graph The graph type.
1018  /// \param _Item The item type of the graph.
1019  /// \param _Value The value type of the map.
1020  ///
1021  /// \see IterableValueMap
1022#ifndef DOXYGEN
1023  /// \param _Map A ReadWriteMap mapping from the item type to integer.
1024  template <
1025    typename _Graph, typename _Item, typename _Value,
1026    typename _Map = DefaultMap<_Graph, _Item, _Value>
1027  >
1028#else
1029  template <typename _Graph, typename _Item, typename _Value>
1030#endif
1031  class InvertableMap : protected _Map {
1032  public:
1033
1034    /// The key type of InvertableMap (Node, Edge, UEdge).
1035    typedef typename _Map::Key Key;
1036    /// The value type of the InvertableMap.
1037    typedef typename _Map::Value Value;
1038
1039  private:
1040   
1041    typedef _Map Map;
1042    typedef _Graph Graph;
1043
1044    typedef std::map<Value, Key> Container;
1045    Container invMap;   
1046
1047  public:
1048 
1049
1050
1051    /// \brief Constructor.
1052    ///
1053    /// Construct a new InvertableMap for the graph.
1054    ///
1055    InvertableMap(const Graph& graph) : Map(graph) {}
1056
1057    /// \brief Forward iterator for values.
1058    ///
1059    /// This iterator is an stl compatible forward
1060    /// iterator on the values of the map. The values can
1061    /// be accessed in the [beginValue, endValue) range.
1062    ///
1063    class ValueIterator
1064      : public std::iterator<std::forward_iterator_tag, Value> {
1065      friend class InvertableMap;
1066    private:
1067      ValueIterator(typename Container::const_iterator _it)
1068        : it(_it) {}
1069    public:
1070     
1071      ValueIterator() {}
1072
1073      ValueIterator& operator++() { ++it; return *this; }
1074      ValueIterator operator++(int) {
1075        ValueIterator tmp(*this);
1076        operator++();
1077        return tmp;
1078      }
1079
1080      const Value& operator*() const { return it->first; }
1081      const Value* operator->() const { return &(it->first); }
1082
1083      bool operator==(ValueIterator jt) const { return it == jt.it; }
1084      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1085     
1086    private:
1087      typename Container::const_iterator it;
1088    };
1089
1090    /// \brief Returns an iterator to the first value.
1091    ///
1092    /// Returns an stl compatible iterator to the
1093    /// first value of the map. The values of the
1094    /// map can be accessed in the [beginValue, endValue)
1095    /// range.
1096    ValueIterator beginValue() const {
1097      return ValueIterator(invMap.begin());
1098    }
1099
1100    /// \brief Returns an iterator after the last value.
1101    ///
1102    /// Returns an stl compatible iterator after the
1103    /// last value of the map. The values of the
1104    /// map can be accessed in the [beginValue, endValue)
1105    /// range.
1106    ValueIterator endValue() const {
1107      return ValueIterator(invMap.end());
1108    }
1109   
1110    /// \brief The setter function of the map.
1111    ///
1112    /// Sets the mapped value.
1113    void set(const Key& key, const Value& val) {
1114      Value oldval = Map::operator[](key);
1115      typename Container::iterator it = invMap.find(oldval);
1116      if (it != invMap.end() && it->second == key) {
1117        invMap.erase(it);
1118      }     
1119      invMap.insert(make_pair(val, key));
1120      Map::set(key, val);
1121    }
1122
1123    /// \brief The getter function of the map.
1124    ///
1125    /// It gives back the value associated with the key.
1126    typename MapTraits<Map>::ConstReturnValue
1127    operator[](const Key& key) const {
1128      return Map::operator[](key);
1129    }
1130
1131  protected:
1132
1133    /// \brief Erase the key from the map.
1134    ///
1135    /// Erase the key to the map. It is called by the
1136    /// \c AlterationNotifier.
1137    virtual void erase(const Key& key) {
1138      Value val = Map::operator[](key);
1139      typename Container::iterator it = invMap.find(val);
1140      if (it != invMap.end() && it->second == key) {
1141        invMap.erase(it);
1142      }
1143      Map::erase(key);
1144    }
1145
1146    /// \brief Erase more keys from the map.
1147    ///
1148    /// Erase more keys from the map. It is called by the
1149    /// \c AlterationNotifier.
1150    virtual void erase(const std::vector<Key>& keys) {
1151      for (int i = 0; i < (int)keys.size(); ++i) {
1152        Value val = Map::operator[](keys[i]);
1153        typename Container::iterator it = invMap.find(val);
1154        if (it != invMap.end() && it->second == keys[i]) {
1155          invMap.erase(it);
1156        }
1157      }
1158      Map::erase(keys);
1159    }
1160
1161    /// \brief Clear the keys from the map and inverse map.
1162    ///
1163    /// Clear the keys from the map and inverse map. It is called by the
1164    /// \c AlterationNotifier.
1165    virtual void clear() {
1166      invMap.clear();
1167      Map::clear();
1168    }
1169
1170  public:
1171
1172    /// \brief The inverse map type.
1173    ///
1174    /// The inverse of this map. The subscript operator of the map
1175    /// gives back always the item what was last assigned to the value.
1176    class InverseMap {
1177    public:
1178      /// \brief Constructor of the InverseMap.
1179      ///
1180      /// Constructor of the InverseMap.
1181      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
1182
1183      /// The value type of the InverseMap.
1184      typedef typename InvertableMap::Key Value;
1185      /// The key type of the InverseMap.
1186      typedef typename InvertableMap::Value Key;
1187
1188      /// \brief Subscript operator.
1189      ///
1190      /// Subscript operator. It gives back always the item
1191      /// what was last assigned to the value.
1192      Value operator[](const Key& key) const {
1193        typename Container::const_iterator it = inverted.invMap.find(key);
1194        return it->second;
1195      }
1196     
1197    private:
1198      const InvertableMap& inverted;
1199    };
1200
1201    /// \brief It gives back the just readeable inverse map.
1202    ///
1203    /// It gives back the just readeable inverse map.
1204    InverseMap inverse() const {
1205      return InverseMap(*this);
1206    }
1207
1208
1209   
1210  };
1211
1212  /// \brief Provides a mutable, continuous and unique descriptor for each
1213  /// item in the graph.
1214  ///
1215  /// The DescriptorMap class provides a unique and continuous (but mutable)
1216  /// descriptor (id) for each item of the same type (e.g. node) in the
1217  /// graph. This id is <ul><li>\b unique: different items (nodes) get
1218  /// different ids <li>\b continuous: the range of the ids is the set of
1219  /// integers between 0 and \c n-1, where \c n is the number of the items of
1220  /// this type (e.g. nodes) (so the id of a node can change if you delete an
1221  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
1222  /// with its member class \c InverseMap.
1223  ///
1224  /// \param _Graph The graph class the \c DescriptorMap belongs to.
1225  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1226  /// UEdge.
1227#ifndef DOXYGEN
1228  /// \param _Map A ReadWriteMap mapping from the item type to integer.
1229  template <
1230    typename _Graph, typename _Item,
1231    typename _Map = DefaultMap<_Graph, _Item, int>
1232  >
1233#else
1234  template <typename _Graph, typename _Item>
1235#endif
1236  class DescriptorMap : protected _Map {
1237
1238    typedef _Item Item;
1239    typedef _Map Map;
1240
1241  public:
1242    /// The graph class of DescriptorMap.
1243    typedef _Graph Graph;
1244
1245    /// The key type of DescriptorMap (Node, Edge, UEdge).
1246    typedef typename _Map::Key Key;
1247    /// The value type of DescriptorMap.
1248    typedef typename _Map::Value Value;
1249
1250    /// \brief Constructor.
1251    ///
1252    /// Constructor for descriptor map.
1253    DescriptorMap(const Graph& _graph) : Map(_graph) {
1254      build();
1255    }
1256
1257  protected:
1258
1259    /// \brief Add a new key to the map.
1260    ///
1261    /// Add a new key to the map. It is called by the
1262    /// \c AlterationNotifier.
1263    virtual void add(const Item& item) {
1264      Map::add(item);
1265      Map::set(item, invMap.size());
1266      invMap.push_back(item);
1267    }
1268
1269    /// \brief Add more new keys to the map.
1270    ///
1271    /// Add more new keys to the map. It is called by the
1272    /// \c AlterationNotifier.
1273    virtual void add(const std::vector<Item>& items) {
1274      Map::add(items);
1275      for (int i = 0; i < (int)items.size(); ++i) {
1276        Map::set(items[i], invMap.size());
1277        invMap.push_back(items[i]);
1278      }
1279    }
1280
1281    /// \brief Erase the key from the map.
1282    ///
1283    /// Erase the key from the map. It is called by the
1284    /// \c AlterationNotifier.
1285    virtual void erase(const Item& item) {
1286      Map::set(invMap.back(), Map::operator[](item));
1287      invMap[Map::operator[](item)] = invMap.back();
1288      invMap.pop_back();
1289      Map::erase(item);
1290    }
1291
1292    /// \brief Erase more keys from the map.
1293    ///
1294    /// Erase more keys from the map. It is called by the
1295    /// \c AlterationNotifier.
1296    virtual void erase(const std::vector<Item>& items) {
1297      for (int i = 0; i < (int)items.size(); ++i) {
1298        Map::set(invMap.back(), Map::operator[](items[i]));
1299        invMap[Map::operator[](items[i])] = invMap.back();
1300        invMap.pop_back();
1301      }
1302      Map::erase(items);
1303    }
1304
1305    /// \brief Build the unique map.
1306    ///
1307    /// Build the unique map. It is called by the
1308    /// \c AlterationNotifier.
1309    virtual void build() {
1310      Map::build();
1311      Item it;
1312      const typename Map::Notifier* notifier = Map::getNotifier();
1313      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1314        Map::set(it, invMap.size());
1315        invMap.push_back(it);   
1316      }     
1317    }
1318   
1319    /// \brief Clear the keys from the map.
1320    ///
1321    /// Clear the keys from the map. It is called by the
1322    /// \c AlterationNotifier.
1323    virtual void clear() {
1324      invMap.clear();
1325      Map::clear();
1326    }
1327
1328  public:
1329
1330    /// \brief Returns the maximal value plus one.
1331    ///
1332    /// Returns the maximal value plus one in the map.
1333    unsigned int size() const {
1334      return invMap.size();
1335    }
1336
1337    /// \brief Swaps the position of the two items in the map.
1338    ///
1339    /// Swaps the position of the two items in the map.
1340    void swap(const Item& p, const Item& q) {
1341      int pi = Map::operator[](p);
1342      int qi = Map::operator[](q);
1343      Map::set(p, qi);
1344      invMap[qi] = p;
1345      Map::set(q, pi);
1346      invMap[pi] = q;
1347    }
1348
1349    /// \brief Gives back the \e descriptor of the item.
1350    ///
1351    /// Gives back the mutable and unique \e descriptor of the map.
1352    int operator[](const Item& item) const {
1353      return Map::operator[](item);
1354    }
1355   
1356  private:
1357
1358    typedef std::vector<Item> Container;
1359    Container invMap;
1360
1361  public:
1362    /// \brief The inverse map type of DescriptorMap.
1363    ///
1364    /// The inverse map type of DescriptorMap.
1365    class InverseMap {
1366    public:
1367      /// \brief Constructor of the InverseMap.
1368      ///
1369      /// Constructor of the InverseMap.
1370      InverseMap(const DescriptorMap& _inverted)
1371        : inverted(_inverted) {}
1372
1373
1374      /// The value type of the InverseMap.
1375      typedef typename DescriptorMap::Key Value;
1376      /// The key type of the InverseMap.
1377      typedef typename DescriptorMap::Value Key;
1378
1379      /// \brief Subscript operator.
1380      ///
1381      /// Subscript operator. It gives back the item
1382      /// that the descriptor belongs to currently.
1383      Value operator[](const Key& key) const {
1384        return inverted.invMap[key];
1385      }
1386
1387      /// \brief Size of the map.
1388      ///
1389      /// Returns the size of the map.
1390      unsigned int size() const {
1391        return inverted.invMap.size();
1392      }
1393     
1394    private:
1395      const DescriptorMap& inverted;
1396    };
1397
1398    /// \brief Gives back the inverse of the map.
1399    ///
1400    /// Gives back the inverse of the map.
1401    const InverseMap inverse() const {
1402      return InverseMap(*this);
1403    }
1404  };
1405
1406  /// \brief Returns the source of the given edge.
1407  ///
1408  /// The SourceMap gives back the source Node of the given edge.
1409  /// \author Balazs Dezso
1410  template <typename Graph>
1411  class SourceMap {
1412  public:
1413
1414    typedef typename Graph::Node Value;
1415    typedef typename Graph::Edge Key;
1416
1417    /// \brief Constructor
1418    ///
1419    /// Constructor
1420    /// \param _graph The graph that the map belongs to.
1421    SourceMap(const Graph& _graph) : graph(_graph) {}
1422
1423    /// \brief The subscript operator.
1424    ///
1425    /// The subscript operator.
1426    /// \param edge The edge
1427    /// \return The source of the edge
1428    Value operator[](const Key& edge) const {
1429      return graph.source(edge);
1430    }
1431
1432  private:
1433    const Graph& graph;
1434  };
1435
1436  /// \brief Returns a \ref SourceMap class
1437  ///
1438  /// This function just returns an \ref SourceMap class.
1439  /// \relates SourceMap
1440  template <typename Graph>
1441  inline SourceMap<Graph> sourceMap(const Graph& graph) {
1442    return SourceMap<Graph>(graph);
1443  }
1444
1445  /// \brief Returns the target of the given edge.
1446  ///
1447  /// The TargetMap gives back the target Node of the given edge.
1448  /// \author Balazs Dezso
1449  template <typename Graph>
1450  class TargetMap {
1451  public:
1452
1453    typedef typename Graph::Node Value;
1454    typedef typename Graph::Edge Key;
1455
1456    /// \brief Constructor
1457    ///
1458    /// Constructor
1459    /// \param _graph The graph that the map belongs to.
1460    TargetMap(const Graph& _graph) : graph(_graph) {}
1461
1462    /// \brief The subscript operator.
1463    ///
1464    /// The subscript operator.
1465    /// \param e The edge
1466    /// \return The target of the edge
1467    Value operator[](const Key& e) const {
1468      return graph.target(e);
1469    }
1470
1471  private:
1472    const Graph& graph;
1473  };
1474
1475  /// \brief Returns a \ref TargetMap class
1476  ///
1477  /// This function just returns a \ref TargetMap class.
1478  /// \relates TargetMap
1479  template <typename Graph>
1480  inline TargetMap<Graph> targetMap(const Graph& graph) {
1481    return TargetMap<Graph>(graph);
1482  }
1483
1484  /// \brief Returns the "forward" directed edge view of an undirected edge.
1485  ///
1486  /// Returns the "forward" directed edge view of an undirected edge.
1487  /// \author Balazs Dezso
1488  template <typename Graph>
1489  class ForwardMap {
1490  public:
1491
1492    typedef typename Graph::Edge Value;
1493    typedef typename Graph::UEdge Key;
1494
1495    /// \brief Constructor
1496    ///
1497    /// Constructor
1498    /// \param _graph The graph that the map belongs to.
1499    ForwardMap(const Graph& _graph) : graph(_graph) {}
1500
1501    /// \brief The subscript operator.
1502    ///
1503    /// The subscript operator.
1504    /// \param key An undirected edge
1505    /// \return The "forward" directed edge view of undirected edge
1506    Value operator[](const Key& key) const {
1507      return graph.direct(key, true);
1508    }
1509
1510  private:
1511    const Graph& graph;
1512  };
1513
1514  /// \brief Returns a \ref ForwardMap class
1515  ///
1516  /// This function just returns an \ref ForwardMap class.
1517  /// \relates ForwardMap
1518  template <typename Graph>
1519  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1520    return ForwardMap<Graph>(graph);
1521  }
1522
1523  /// \brief Returns the "backward" directed edge view of an undirected edge.
1524  ///
1525  /// Returns the "backward" directed edge view of an undirected edge.
1526  /// \author Balazs Dezso
1527  template <typename Graph>
1528  class BackwardMap {
1529  public:
1530
1531    typedef typename Graph::Edge Value;
1532    typedef typename Graph::UEdge Key;
1533
1534    /// \brief Constructor
1535    ///
1536    /// Constructor
1537    /// \param _graph The graph that the map belongs to.
1538    BackwardMap(const Graph& _graph) : graph(_graph) {}
1539
1540    /// \brief The subscript operator.
1541    ///
1542    /// The subscript operator.
1543    /// \param key An undirected edge
1544    /// \return The "backward" directed edge view of undirected edge
1545    Value operator[](const Key& key) const {
1546      return graph.direct(key, false);
1547    }
1548
1549  private:
1550    const Graph& graph;
1551  };
1552
1553  /// \brief Returns a \ref BackwardMap class
1554
1555  /// This function just returns a \ref BackwardMap class.
1556  /// \relates BackwardMap
1557  template <typename Graph>
1558  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1559    return BackwardMap<Graph>(graph);
1560  }
1561
1562  /// \brief Potential difference map
1563  ///
1564  /// If there is an potential map on the nodes then we
1565  /// can get an edge map as we get the substraction of the
1566  /// values of the target and source.
1567  template <typename Graph, typename NodeMap>
1568  class PotentialDifferenceMap {
1569  public:
1570    typedef typename Graph::Edge Key;
1571    typedef typename NodeMap::Value Value;
1572
1573    /// \brief Constructor
1574    ///
1575    /// Contructor of the map
1576    PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1577      : graph(_graph), potential(_potential) {}
1578
1579    /// \brief Const subscription operator
1580    ///
1581    /// Const subscription operator
1582    Value operator[](const Key& edge) const {
1583      return potential[graph.target(edge)] - potential[graph.source(edge)];
1584    }
1585
1586  private:
1587    const Graph& graph;
1588    const NodeMap& potential;
1589  };
1590
1591  /// \brief Just returns a PotentialDifferenceMap
1592  ///
1593  /// Just returns a PotentialDifferenceMap
1594  /// \relates PotentialDifferenceMap
1595  template <typename Graph, typename NodeMap>
1596  PotentialDifferenceMap<Graph, NodeMap>
1597  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1598    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1599  }
1600
1601  /// \brief Map of the node in-degrees.
1602  ///
1603  /// This map returns the in-degree of a node. Once it is constructed,
1604  /// the degrees are stored in a standard NodeMap, so each query is done
1605  /// in constant time. On the other hand, the values are updated automatically
1606  /// whenever the graph changes.
1607  ///
1608  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1609  /// alternative ways to modify the graph. The correct behavior of InDegMap
1610  /// is not guarantied if these additional features are used. For example
1611  /// the functions \ref ListGraph::changeSource() "changeSource()",
1612  /// \ref ListGraph::changeTarget() "changeTarget()" and
1613  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1614  /// of \ref ListGraph will \e not update the degree values correctly.
1615  ///
1616  /// \sa OutDegMap
1617
1618  template <typename _Graph>
1619  class InDegMap 
1620    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1621      ::ItemNotifier::ObserverBase {
1622
1623  public:
1624   
1625    typedef _Graph Graph;
1626    typedef int Value;
1627    typedef typename Graph::Node Key;
1628
1629    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1630    ::ItemNotifier::ObserverBase Parent;
1631
1632  private:
1633
1634    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1635    public:
1636
1637      typedef DefaultMap<_Graph, Key, int> Parent;
1638      typedef typename Parent::Graph Graph;
1639
1640      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1641     
1642      virtual void add(const Key& key) {
1643        Parent::add(key);
1644        Parent::set(key, 0);
1645      }
1646
1647      virtual void add(const std::vector<Key>& keys) {
1648        Parent::add(keys);
1649        for (int i = 0; i < (int)keys.size(); ++i) {
1650          Parent::set(keys[i], 0);
1651        }
1652      }
1653    };
1654
1655  public:
1656
1657    /// \brief Constructor.
1658    ///
1659    /// Constructor for creating in-degree map.
1660    InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1661      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1662     
1663      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1664        deg[it] = countInEdges(graph, it);
1665      }
1666    }
1667   
1668    /// Gives back the in-degree of a Node.
1669    int operator[](const Key& key) const {
1670      return deg[key];
1671    }
1672
1673  protected:
1674   
1675    typedef typename Graph::Edge Edge;
1676
1677    virtual void add(const Edge& edge) {
1678      ++deg[graph.target(edge)];
1679    }
1680
1681    virtual void add(const std::vector<Edge>& edges) {
1682      for (int i = 0; i < (int)edges.size(); ++i) {
1683        ++deg[graph.target(edges[i])];
1684      }
1685    }
1686
1687    virtual void erase(const Edge& edge) {
1688      --deg[graph.target(edge)];
1689    }
1690
1691    virtual void erase(const std::vector<Edge>& edges) {
1692      for (int i = 0; i < (int)edges.size(); ++i) {
1693        --deg[graph.target(edges[i])];
1694      }
1695    }
1696
1697    virtual void build() {
1698      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1699        deg[it] = countInEdges(graph, it);
1700      }     
1701    }
1702
1703    virtual void clear() {
1704      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1705        deg[it] = 0;
1706      }
1707    }
1708  private:
1709   
1710    const _Graph& graph;
1711    AutoNodeMap deg;
1712  };
1713
1714  /// \brief Map of the node out-degrees.
1715  ///
1716  /// This map returns the out-degree of a node. Once it is constructed,
1717  /// the degrees are stored in a standard NodeMap, so each query is done
1718  /// in constant time. On the other hand, the values are updated automatically
1719  /// whenever the graph changes.
1720  ///
1721  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1722  /// alternative ways to modify the graph. The correct behavior of OutDegMap
1723  /// is not guarantied if these additional features are used. For example
1724  /// the functions \ref ListGraph::changeSource() "changeSource()",
1725  /// \ref ListGraph::changeTarget() "changeTarget()" and
1726  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1727  /// of \ref ListGraph will \e not update the degree values correctly.
1728  ///
1729  /// \sa InDegMap
1730
1731  template <typename _Graph>
1732  class OutDegMap 
1733    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1734      ::ItemNotifier::ObserverBase {
1735
1736  public:
1737
1738    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1739    ::ItemNotifier::ObserverBase Parent;
1740   
1741    typedef _Graph Graph;
1742    typedef int Value;
1743    typedef typename Graph::Node Key;
1744
1745  private:
1746
1747    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1748    public:
1749
1750      typedef DefaultMap<_Graph, Key, int> Parent;
1751      typedef typename Parent::Graph Graph;
1752
1753      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1754     
1755      virtual void add(const Key& key) {
1756        Parent::add(key);
1757        Parent::set(key, 0);
1758      }
1759      virtual void add(const std::vector<Key>& keys) {
1760        Parent::add(keys);
1761        for (int i = 0; i < (int)keys.size(); ++i) {
1762          Parent::set(keys[i], 0);
1763        }
1764      }
1765    };
1766
1767  public:
1768
1769    /// \brief Constructor.
1770    ///
1771    /// Constructor for creating out-degree map.
1772    OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1773      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1774     
1775      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1776        deg[it] = countOutEdges(graph, it);
1777      }
1778    }
1779
1780    /// Gives back the out-degree of a Node.
1781    int operator[](const Key& key) const {
1782      return deg[key];
1783    }
1784
1785  protected:
1786   
1787    typedef typename Graph::Edge Edge;
1788
1789    virtual void add(const Edge& edge) {
1790      ++deg[graph.source(edge)];
1791    }
1792
1793    virtual void add(const std::vector<Edge>& edges) {
1794      for (int i = 0; i < (int)edges.size(); ++i) {
1795        ++deg[graph.source(edges[i])];
1796      }
1797    }
1798
1799    virtual void erase(const Edge& edge) {
1800      --deg[graph.source(edge)];
1801    }
1802
1803    virtual void erase(const std::vector<Edge>& edges) {
1804      for (int i = 0; i < (int)edges.size(); ++i) {
1805        --deg[graph.source(edges[i])];
1806      }
1807    }
1808
1809    virtual void build() {
1810      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1811        deg[it] = countOutEdges(graph, it);
1812      }     
1813    }
1814
1815    virtual void clear() {
1816      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1817        deg[it] = 0;
1818      }
1819    }
1820  private:
1821   
1822    const _Graph& graph;
1823    AutoNodeMap deg;
1824  };
1825
1826
1827  /// @}
1828
1829} //END OF NAMESPACE LEMON
1830
1831#endif
Note: See TracBrowser for help on using the repository browser.