COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2094:3ae02034be53

Last change on this file since 2094:3ae02034be53 was 2094:3ae02034be53, checked in by Alpar Juttner, 14 years ago

Spellcheck

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 && (b ? g.target(e) : g.source(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 readable inverse map.
1202    ///
1203    /// It gives back the just readable 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.