COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2267:3575f17a6e7f

Last change on this file since 2267:3575f17a6e7f was 2235:48801095a410, checked in by Alpar Juttner, 17 years ago

EdgeLookUp? and AllEdgeLookUp? added.

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