COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2022:0f3367da6104

Last change on this file since 2022:0f3367da6104 was 2022:0f3367da6104, checked in by Alpar Juttner, 18 years ago

docfix

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