COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1454:e0177bbe75a9

Last change on this file since 1454:e0177bbe75a9 was 1454:e0177bbe75a9, checked in by Mihaly Barasz, 15 years ago

Bugfixes to compile w. gcc 4.0.0

File size: 24.3 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
24#include <lemon/invalid.h>
25#include <lemon/utility.h>
26#include <lemon/maps.h>
27
28///\ingroup gutils
29///\file
30///\brief Graph utilities.
31///
32///\todo Please
33///revise the documentation.
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 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 structure 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 structure 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 edges in the graph.
124  ///
125  /// This function counts the edges in the graph.
126  /// The complexity of the function is O(e) but for some
127  /// graph structure 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  /// Finds an edge between two nodes of a graph.
146
147  /// Finds an edge from node \c u to node \c v in graph \c g.
148  ///
149  /// If \c prev is \ref INVALID (this is the default value), then
150  /// it finds the first edge from \c u to \c v. Otherwise it looks for
151  /// the next edge from \c u to \c v after \c prev.
152  /// \return The found edge or \ref INVALID if there is no such an edge.
153  ///
154  /// Thus you can iterate through each edge from \c u to \c v as it follows.
155  /// \code
156  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
157  ///   ...
158  /// }
159  /// \endcode
160  /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
161  /// interface here...
162  /// \bug Untested ...
163  template <typename Graph>
164  typename Graph::Edge findEdge(const Graph &g,
165                                typename Graph::Node u, typename Graph::Node v,
166                                typename Graph::Edge prev = INVALID)
167  {
168    typename Graph::OutEdgeIt e(g,prev);
169    //    if(prev==INVALID) g.first(e,u);
170    if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
171    else ++e;
172    while(e!=INVALID && g.target(e)!=v) ++e;
173    return e;
174  }
175 
176  ///\e
177
178  ///\todo Please document.
179  ///
180  template <typename Graph>
181  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
182    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
183  }
184
185  ///\e
186
187  ///\todo Please document.
188  ///
189  template <typename Graph>
190  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
191    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
192  }
193
194  // graph copy
195
196  template <
197    typename DestinationGraph,
198    typename SourceGraph,
199    typename NodeBijection>
200  void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
201                 NodeBijection& _nb) {   
202    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
203      _nb[it] = _d.addNode();
204    }
205  }
206
207  template <
208    typename DestinationGraph,
209    typename SourceGraph,
210    typename NodeBijection,
211    typename EdgeBijection>
212  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
213                 const NodeBijection& _nb, EdgeBijection& _eb) {   
214    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
215      _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
216    }
217  }
218
219  template <
220    typename DestinationGraph,
221    typename SourceGraph,
222    typename NodeBijection,
223    typename EdgeBijection>
224  void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
225                 NodeBijection& _nb, EdgeBijection& _eb) {
226    nodeCopy(_d, _s, _nb);
227    edgeCopy(_d, _s, _nb, _eb);
228  }
229 
230  template <
231    typename _DestinationGraph,
232    typename _SourceGraph,
233    typename _NodeBijection
234    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
235    typename _EdgeBijection
236    = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
237  >
238  class GraphCopy {
239  public:
240   
241    typedef _DestinationGraph DestinationGraph;
242    typedef _SourceGraph SourceGraph;
243
244    typedef _NodeBijection NodeBijection;
245    typedef _EdgeBijection EdgeBijection;
246   
247  protected:         
248   
249    NodeBijection node_bijection;
250    EdgeBijection edge_bijection;     
251
252  public:
253     
254    GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
255      copyGraph(_d, _s, node_bijection, edge_bijection);
256    }
257   
258    const NodeBijection& getNodeBijection() const {
259      return node_bijection;
260    }
261
262    const EdgeBijection& getEdgeBijection() const {
263      return edge_bijection;
264    }
265     
266  };
267
268
269  template <typename _Graph, typename _Item>
270  class ItemSetTraits {};
271 
272  template <typename _Graph>
273  class ItemSetTraits<_Graph, typename _Graph::Node> {
274  public:
275   
276    typedef _Graph Graph;
277
278    typedef typename Graph::Node Item;
279    typedef typename Graph::NodeIt ItemIt;
280
281    template <typename _Value>
282    class Map : public Graph::template NodeMap<_Value> {
283    public:
284      typedef typename Graph::template NodeMap<_Value> Parent;
285      typedef typename Parent::Value Value;
286
287      Map(const Graph& _graph) : Parent(_graph) {}
288      Map(const Graph& _graph, const Value& _value)
289        : Parent(_graph, _value) {}
290    };
291
292  };
293
294  template <typename _Graph>
295  class ItemSetTraits<_Graph, typename _Graph::Edge> {
296  public:
297   
298    typedef _Graph Graph;
299
300    typedef typename Graph::Edge Item;
301    typedef typename Graph::EdgeIt ItemIt;
302
303    template <typename _Value>
304    class Map : public Graph::template EdgeMap<_Value> {
305    public:
306      typedef typename Graph::template EdgeMap<_Value> Parent;
307      typedef typename Parent::Value Value;
308
309      Map(const Graph& _graph) : Parent(_graph) {}
310      Map(const Graph& _graph, const Value& _value)
311        : Parent(_graph, _value) {}
312    };
313
314  };
315
316  template <typename _Graph>
317  class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
318  public:
319   
320    typedef _Graph Graph;
321
322    typedef typename Graph::UndirEdge Item;
323    typedef typename Graph::UndirEdgeIt ItemIt;
324
325    template <typename _Value>
326    class Map : public Graph::template UndirEdgeMap<_Value> {
327    public:
328      typedef typename Graph::template UndirEdgeMap<_Value> Parent;
329      typedef typename Parent::Value Value;
330
331      Map(const Graph& _graph) : Parent(_graph) {}
332      Map(const Graph& _graph, const Value& _value)
333        : Parent(_graph, _value) {}
334    };
335
336  };
337
338  /// @}
339
340  /// \addtogroup graph_maps
341  /// @{
342
343  template <typename Map, typename Enable = void>
344  struct ReferenceMapTraits {
345    typedef typename Map::Value Value;
346    typedef typename Map::Value& Reference;
347    typedef const typename Map::Value& ConstReference;
348    typedef typename Map::Value* Pointer;
349    typedef const typename Map::Value* ConstPointer;
350  };
351
352  template <typename Map>
353  struct ReferenceMapTraits<
354    Map,
355    typename enable_if<typename Map::FullTypeTag, void>::type
356  > {
357    typedef typename Map::Value Value;
358    typedef typename Map::Reference Reference;
359    typedef typename Map::ConstReference ConstReference;
360    typedef typename Map::Pointer Pointer;
361    typedef typename Map::ConstPointer ConstPointer;
362  };
363
364  /// Provides an immutable and unique id for each item in the graph.
365
366  /// The IdMap class provides an unique and immutable mapping for each item
367  /// in the graph.
368  ///
369  template <typename _Graph, typename _Item>
370  class IdMap {
371  public:
372    typedef _Graph Graph;
373    typedef int Value;
374    typedef _Item Item;
375    typedef _Item Key;
376
377    typedef True NeedCopy;
378
379    /// \brief Constructor.
380    ///
381    /// Constructor for creating id map.
382    IdMap(const Graph& _graph) : graph(&_graph) {}
383
384    /// \brief Gives back the \e id of the item.
385    ///
386    /// Gives back the immutable and unique \e id of the map.
387    int operator[](const Item& item) const { return graph->id(item);}
388
389
390  private:
391    const Graph* graph;
392
393  public:
394
395    /// \brief The class represents the inverse of the map.
396    ///
397    /// The class represents the inverse of the map.
398    /// \see inverse()
399    class InverseMap {
400    public:
401
402      typedef True NeedCopy;
403
404      /// \brief Constructor.
405      ///
406      /// Constructor for creating an id-to-item map.
407      InverseMap(const Graph& _graph) : graph(&_graph) {}
408
409      /// \brief Constructor.
410      ///
411      /// Constructor for creating an id-to-item map.
412      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
413
414      /// \brief Gives back the given item from its id.
415      ///
416      /// Gives back the given item from its id.
417      ///
418      Item operator[](int id) const { return graph->fromId(id, Item());}
419    private:
420      const Graph* graph;
421    };
422
423    /// \brief Gives back the inverse of the map.
424    ///
425    /// Gives back the inverse of the map.
426    InverseMap inverse() const { return InverseMap(*graph);}
427
428  };
429
430 
431  /// \brief General inversable graph-map type.
432
433  /// This type provides simple inversable map functions.
434  /// The InversableMap wraps an arbitrary ReadWriteMap
435  /// and if a key is setted to a new value then store it
436  /// in the inverse map.
437  /// \param _Graph The graph type.
438  /// \param _Map The map to extend with inversable functionality.
439  template <
440    typename _Graph,
441    typename _Item,
442    typename _Value,
443    typename _Map
444    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
445  >
446  class InvertableMap : protected _Map {
447
448  public:
449 
450    typedef _Map Map;
451    typedef _Graph Graph;
452
453    /// The key type of InvertableMap (Node, Edge, UndirEdge).
454    typedef typename _Map::Key Key;
455    /// The value type of the InvertableMap.
456    typedef typename _Map::Value Value;
457
458    /// \brief Constructor.
459    ///
460    /// Construct a new InvertableMap for the graph.
461    ///
462    InvertableMap(const Graph& graph) : Map(graph) {}
463   
464    /// \brief The setter function of the map.
465    ///
466    /// Sets the mapped value.
467    void set(const Key& key, const Value& val) {
468      Value oldval = Map::operator[](key);
469      typename Container::iterator it = invMap.find(oldval);
470      if (it != invMap.end() && it->second == key) {
471        invMap.erase(it);
472      }     
473      invMap.insert(make_pair(val, key));
474      Map::set(key, val);
475    }
476
477    /// \brief The getter function of the map.
478    ///
479    /// It gives back the value associated with the key.
480    const Value operator[](const Key& key) const {
481      return Map::operator[](key);
482    }
483
484    /// \brief Add a new key to the map.
485    ///
486    /// Add a new key to the map. It is called by the
487    /// \c AlterationNotifier.
488    virtual void add(const Key& key) {
489      Map::add(key);
490    }
491
492    /// \brief Erase the key from the map.
493    ///
494    /// Erase the key to the map. It is called by the
495    /// \c AlterationNotifier.
496    virtual void erase(const Key& key) {
497      Value val = Map::operator[](key);
498      typename Container::iterator it = invMap.find(val);
499      if (it != invMap.end() && it->second == key) {
500        invMap.erase(it);
501      }
502      Map::erase(key);
503    }
504
505    /// \brief Clear the keys from the map and inverse map.
506    ///
507    /// Clear the keys from the map and inverse map. It is called by the
508    /// \c AlterationNotifier.
509    virtual void clear() {
510      invMap.clear();
511      Map::clear();
512    }
513
514  private:
515   
516    typedef std::map<Value, Key> Container;
517    Container invMap;   
518
519  public:
520
521    /// \brief The inverse map type.
522    ///
523    /// The inverse of this map. The subscript operator of the map
524    /// gives back always the item what was last assigned to the value.
525    class InverseMap {
526    public:
527      /// \brief Constructor of the InverseMap.
528      ///
529      /// Constructor of the InverseMap.
530      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
531
532      /// The value type of the InverseMap.
533      typedef typename InvertableMap::Key Value;
534      /// The key type of the InverseMap.
535      typedef typename InvertableMap::Value Key;
536
537      /// \brief Subscript operator.
538      ///
539      /// Subscript operator. It gives back always the item
540      /// what was last assigned to the value.
541      Value operator[](const Key& key) const {
542        typename Container::const_iterator it = inverted.invMap.find(key);
543        return it->second;
544      }
545     
546    private:
547      const InvertableMap& inverted;
548    };
549
550    /// \brief It gives back the just readeable inverse map.
551    ///
552    /// It gives back the just readeable inverse map.
553    InverseMap inverse() const {
554      return InverseMap(*this);
555    }
556
557
558   
559  };
560
561  /// \brief Provides a mutable, continuous and unique descriptor for each
562  /// item in the graph.
563  ///
564  /// The DescriptorMap class provides a mutable, continuous and immutable
565  /// mapping for each item in the graph. The value for an item may mutated
566  /// on each operation when the an item erased or added to graph.
567  ///
568  /// \param _Graph The graph class the \c DescriptorMap belongs to.
569  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
570  /// UndirEdge.
571  /// \param _Map A ReadWriteMap mapping from the item type to integer.
572  template <
573    typename _Graph,   
574    typename _Item,
575    typename _Map
576    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
577  >
578  class DescriptorMap : protected _Map {
579
580    typedef _Item Item;
581    typedef _Map Map;
582
583  public:
584    /// The graph class of DescriptorMap.
585    typedef _Graph Graph;
586
587    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
588    typedef typename _Map::Key Key;
589    /// The value type of DescriptorMap.
590    typedef typename _Map::Value Value;
591
592    /// \brief Constructor.
593    ///
594    /// Constructor for descriptor map.
595    DescriptorMap(const Graph& _graph) : Map(_graph) {
596      build();
597    }
598
599    /// \brief Add a new key to the map.
600    ///
601    /// Add a new key to the map. It is called by the
602    /// \c AlterationNotifier.
603    virtual void add(const Item& item) {
604      Map::add(item);
605      Map::set(item, invMap.size());
606      invMap.push_back(item);
607    }
608
609    /// \brief Erase the key from the map.
610    ///
611    /// Erase the key to the map. It is called by the
612    /// \c AlterationNotifier.
613    virtual void erase(const Item& item) {
614      Map::set(invMap.back(), Map::operator[](item));
615      invMap[Map::operator[](item)] = invMap.back();
616      invMap.pop_back();
617      Map::erase(item);
618    }
619
620    /// \brief Build the unique map.
621    ///
622    /// Build the unique map. It is called by the
623    /// \c AlterationNotifier.
624    virtual void build() {
625      Map::build();
626      Item it;
627      const typename Map::Graph* graph = Map::getGraph();
628      for (graph->first(it); it != INVALID; graph->next(it)) {
629        Map::set(it, invMap.size());
630        invMap.push_back(it);   
631      }     
632    }
633   
634    /// \brief Clear the keys from the map.
635    ///
636    /// Clear the keys from the map. It is called by the
637    /// \c AlterationNotifier.
638    virtual void clear() {
639      invMap.clear();
640      Map::clear();
641    }
642
643    /// \brief Gives back the \e descriptor of the item.
644    ///
645    /// Gives back the mutable and unique \e descriptor of the map.
646    int operator[](const Item& item) const {
647      return Map::operator[](item);
648    }
649   
650  private:
651
652    typedef std::vector<Item> Container;
653    Container invMap;
654
655  public:
656    /// \brief The inverse map type.
657    ///
658    /// The inverse map type.
659    class InverseMap {
660    public:
661      /// \brief Constructor of the InverseMap.
662      ///
663      /// Constructor of the InverseMap.
664      InverseMap(const DescriptorMap& _inverted)
665        : inverted(_inverted) {}
666
667
668      /// The value type of the InverseMap.
669      typedef typename DescriptorMap::Key Value;
670      /// The key type of the InverseMap.
671      typedef typename DescriptorMap::Value Key;
672
673      /// \brief Subscript operator.
674      ///
675      /// Subscript operator. It gives back the item
676      /// that the descriptor belongs to currently.
677      Value operator[](const Key& key) const {
678        return inverted.invMap[key];
679      }
680     
681    private:
682      const DescriptorMap& inverted;
683    };
684
685    /// \brief Gives back the inverse of the map.
686    ///
687    /// Gives back the inverse of the map.
688    const InverseMap inverse() const {
689      return InverseMap(*this);
690    }
691  };
692
693  /// \brief Returns the source of the given edge.
694  ///
695  /// The SourceMap gives back the source Node of the given edge.
696  /// \author Balazs Dezso
697  template <typename Graph>
698  class SourceMap {
699  public:
700
701    typedef True NeedCopy;
702
703    typedef typename Graph::Node Value;
704    typedef typename Graph::Edge Key;
705
706    /// \brief Constructor
707    ///
708    /// Constructor
709    /// \param _graph The graph that the map belongs to.
710    SourceMap(const Graph& _graph) : graph(_graph) {}
711
712    /// \brief The subscript operator.
713    ///
714    /// The subscript operator.
715    /// \param edge The edge
716    /// \return The source of the edge
717    Value operator[](const Key& edge) {
718      return graph.source(edge);
719    }
720
721  private:
722    const Graph& graph;
723  };
724
725  /// \brief Returns a \ref SourceMap class
726  ///
727  /// This function just returns an \ref SourceMap class.
728  /// \relates SourceMap
729  template <typename Graph>
730  inline SourceMap<Graph> sourceMap(const Graph& graph) {
731    return SourceMap<Graph>(graph);
732  }
733
734  /// \brief Returns the target of the given edge.
735  ///
736  /// The TargetMap gives back the target Node of the given edge.
737  /// \author Balazs Dezso
738  template <typename Graph>
739  class TargetMap {
740  public:
741
742    typedef True NeedCopy;
743
744    typedef typename Graph::Node Value;
745    typedef typename Graph::Edge Key;
746
747    /// \brief Constructor
748    ///
749    /// Constructor
750    /// \param _graph The graph that the map belongs to.
751    TargetMap(const Graph& _graph) : graph(_graph) {}
752
753    /// \brief The subscript operator.
754    ///
755    /// The subscript operator.
756    /// \param edge The edge
757    /// \return The target of the edge
758    Value operator[](const Key& key) {
759      return graph.target(key);
760    }
761
762  private:
763    const Graph& graph;
764  };
765
766  /// \brief Returns a \ref TargetMap class
767
768  /// This function just returns an \ref TargetMap class.
769  /// \relates TargetMap
770  template <typename Graph>
771  inline TargetMap<Graph> targetMap(const Graph& graph) {
772    return TargetMap<Graph>(graph);
773  }
774
775  /// \brief Returns the "forward" directed edge view of undirected edge.
776  ///
777  /// Returns the "forward" directed edge view of undirected edge.
778  /// \author Balazs Dezso
779  template <typename Graph>
780  class ForwardMap {
781  public:
782
783    typedef True NeedCopy;
784
785    typedef typename Graph::Edge Value;
786    typedef typename Graph::UndirEdge Key;
787
788    /// \brief Constructor
789    ///
790    /// Constructor
791    /// \param _graph The graph that the map belongs to.
792    ForwardMap(const Graph& _graph) : graph(_graph) {}
793
794    /// \brief The subscript operator.
795    ///
796    /// The subscript operator.
797    /// \param key An undirected edge
798    /// \return The "forward" directed edge view of undirected edge
799    Value operator[](const Key& key) const {
800      return graph.edgeWithSource(key, graph.source(key));
801    }
802
803  private:
804    const Graph& graph;
805  };
806
807  /// \brief Returns a \ref ForwardMap class
808
809  /// This function just returns an \ref ForwardMap class.
810  /// \relates ForwardMap
811  template <typename Graph>
812  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
813    return ForwardMap<Graph>(graph);
814  }
815
816  /// \brief Returns the "backward" directed edge view of undirected edge.
817  ///
818  /// Returns the "backward" directed edge view of undirected edge.
819  /// \author Balazs Dezso
820  template <typename Graph>
821  class BackwardMap {
822  public:
823    typedef True NeedCopy;
824
825    typedef typename Graph::Edge Value;
826    typedef typename Graph::UndirEdge Key;
827
828    /// \brief Constructor
829    ///
830    /// Constructor
831    /// \param _graph The graph that the map belongs to.
832    BackwardMap(const Graph& _graph) : graph(_graph) {}
833
834    /// \brief The subscript operator.
835    ///
836    /// The subscript operator.
837    /// \param key An undirected edge
838    /// \return The "backward" directed edge view of undirected edge
839    Value operator[](const Key& key) const {
840      return graph.edgeWithSource(key, graph.target(key));
841    }
842
843  private:
844    const Graph& graph;
845  };
846
847  /// \brief Returns a \ref BackwardMap class
848
849  /// This function just returns an \ref BackwardMap class.
850  /// \relates BackwardMap
851  template <typename Graph>
852  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
853    return BackwardMap<Graph>(graph);
854  }
855
856
857
858  /* ***************************************************************** */
859
860  /// Provides O(1) time node-degree queries.
861
862  ///\todo Undocumented
863  ///
864  template <typename _Graph>
865  class InDegMap  :
866    protected _Graph::template AlterationNotifier<typename _Graph::Node>::
867    ObserverBase,
868    protected _Graph::template AlterationNotifier<typename _Graph::Edge>::
869    ObserverBase
870  {
871    typename _Graph::template NodeMap<int> deg;
872    const _Graph* graph;
873  public:
874    typedef int Value;
875    typedef typename _Graph::Node Key;
876
877    /// \brief Constructor.
878    ///
879    /// Constructor for creating in-degree map.
880    InDegMap(const _Graph& _graph) : graph(_graph), deg(graph,0)
881    {
882      typename _Graph::template AlterationNotifier<typename _Graph::Node>
883        ::ObserverBase::attach(graph->getNotifier(typename _Graph::Node()));
884      typename _Graph::template AlterationNotifier<typename _Graph::Edge>
885        ::ObserverBase::attach(graph->getNotifier(typename _Graph::Edge()));
886
887      for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
888        for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
889          deg[e]++;
890    }
891
892    ~InDegMap()
893    {
894      typename _Graph::template AlterationNotifier<typename _Graph::Node>::
895        ObserverBase::detach();
896      typename _Graph::template AlterationNotifier<typename _Graph::Edge>::
897        ObserverBase::detach();
898    }
899   
900    /// Gives back the in degree of a Node.
901    int operator[](const Key& k) const { return deg[k];}
902
903  protected:
904    virtual void add(const typename _Graph::Node& n) {
905      ///\bug Which 'add' comes before to other?
906      deg[n]=0;
907    }
908    virtual void erase(const typename _Graph::Node&)
909    {
910    }
911    virtual void add(const typename _Graph::Edge& e) {
912      deg[graph.target(e)]++;
913    }
914    virtual void erase(const typename _Graph::Edge& e) {
915      deg[graph.target(e)]--;
916    }
917
918
919  };
920
921
922
923
924  /// @}
925
926} //END OF NAMESPACE LEMON
927
928#endif
Note: See TracBrowser for help on using the repository browser.