COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1712:4fb435ad31cf

Last change on this file since 1712:4fb435ad31cf was 1712:4fb435ad31cf, checked in by Balazs Dezso, 18 years ago

Little modifications

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