COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1538:777834118f73

Last change on this file since 1538:777834118f73 was 1538:777834118f73, checked in by Balazs Dezso, 14 years ago

NewUndirEdgeSetAdaptor? class
some doc
some bug fix

File size: 30.9 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#include <lemon/bits/alteration_notifier.h>
28
29///\ingroup gutils
30///\file
31///\brief Graph utilities.
32///
33///\todo Please
34///revise the documentation.
35///
36
37
38namespace lemon {
39
40  /// \addtogroup gutils
41  /// @{
42
43  /// \brief Function to count the items in the graph.
44  ///
45  /// This function counts the items in the graph.
46  /// The complexity of the function is O(n) because
47  /// it iterates on all of the items.
48
49  template <typename Graph, typename ItemIt>
50  inline int countItems(const Graph& g) {
51    int num = 0;
52    for (ItemIt it(g); it != INVALID; ++it) {
53      ++num;
54    }
55    return num;
56  }
57
58  // Node counting:
59
60  template <typename Graph>
61  inline
62  typename enable_if<typename Graph::NodeNumTag, int>::type
63  _countNodes(const Graph &g) {
64    return g.nodeNum();
65  }
66
67  template <typename Graph>
68  inline int _countNodes(Wrap<Graph> w) {
69    return countItems<Graph, typename Graph::NodeIt>(w.value);
70  }
71
72  /// \brief Function to count the nodes in the graph.
73  ///
74  /// This function counts the nodes in the graph.
75  /// The complexity of the function is O(n) but for some
76  /// graph structures it is specialized to run in O(1).
77  ///
78  /// \todo refer how to specialize it
79
80  template <typename Graph>
81  inline int countNodes(const Graph& g) {
82    return _countNodes<Graph>(g);
83  }
84
85  // Edge counting:
86
87  template <typename Graph>
88  inline
89  typename enable_if<typename Graph::EdgeNumTag, int>::type
90  _countEdges(const Graph &g) {
91    return g.edgeNum();
92  }
93
94  template <typename Graph>
95  inline int _countEdges(Wrap<Graph> w) {
96    return countItems<Graph, typename Graph::EdgeIt>(w.value);
97  }
98
99  /// \brief Function to count the edges in the graph.
100  ///
101  /// This function counts the edges in the graph.
102  /// The complexity of the function is O(e) but for some
103  /// graph structures it is specialized to run in O(1).
104
105  template <typename Graph>
106  inline int countEdges(const Graph& g) {
107    return _countEdges<Graph>(g);
108  }
109
110  // Undirected edge counting:
111
112  template <typename Graph>
113  inline
114  typename enable_if<typename Graph::EdgeNumTag, int>::type
115  _countUndirEdges(const Graph &g) {
116    return g.undirEdgeNum();
117  }
118
119  template <typename Graph>
120  inline int _countUndirEdges(Wrap<Graph> w) {
121    return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
122  }
123
124  /// \brief Function to count the undirected edges in the graph.
125  ///
126  /// This function counts the undirected edges in the graph.
127  /// The complexity of the function is O(e) but for some
128  /// graph structure it is specialized to run in O(1).
129
130  template <typename Graph>
131  inline int countUndirEdges(const Graph& g) {
132    return _countUndirEdges<Graph>(g);
133  }
134
135
136
137  template <typename Graph, typename DegIt>
138  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
139    int num = 0;
140    for (DegIt it(_g, _n); it != INVALID; ++it) {
141      ++num;
142    }
143    return num;
144  }
145
146  /// \brief Function to count the number of the out-edges from node \c n.
147  ///
148  /// This function counts the number of the out-edges from node \c n
149  /// in the graph. 
150  template <typename Graph>
151  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
152    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
153  }
154
155  /// \brief Function to count the number of the in-edges to node \c n.
156  ///
157  /// This function counts the number of the in-edges to node \c n
158  /// in the graph. 
159  template <typename Graph>
160  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
161    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
162  }
163
164
165  /// Finds an edge between two nodes of a graph.
166
167  /// Finds an edge from node \c u to node \c v in graph \c g.
168  ///
169  /// If \c prev is \ref INVALID (this is the default value), then
170  /// it finds the first edge from \c u to \c v. Otherwise it looks for
171  /// the next edge from \c u to \c v after \c prev.
172  /// \return The found edge or \ref INVALID if there is no such an edge.
173  ///
174  /// Thus you can iterate through each edge from \c u to \c v as it follows.
175  /// \code
176  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
177  ///   ...
178  /// }
179  /// \endcode
180  /// \todo We may want to use the "GraphBase"
181  /// interface here...
182  /// \bug Untested ...
183  template <typename Graph>
184  typename Graph::Edge findEdge(const Graph &g,
185                                typename Graph::Node u, typename Graph::Node v,
186                                typename Graph::Edge prev = INVALID)
187  {
188    typename Graph::OutEdgeIt e(g,prev);
189    //    if(prev==INVALID) g.first(e,u);
190    if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
191    else ++e;
192    while(e!=INVALID && g.target(e)!=v) ++e;
193    return e;
194  }
195
196  /// \brief Copy the source map to the target map.
197  ///
198  /// Copy the \c source map to the \c target map. It uses the given iterator
199  /// to iterate on the data structure and it use the \c ref mapping to
200  /// convert the source's keys to the target's keys.
201  template <typename Target, typename Source,
202            typename ItemIt, typename Ref>         
203  void copyMap(Target& target, const Source& source,
204               ItemIt it, const Ref& ref) {
205    for (; it != INVALID; ++it) {
206      target[ref[it]] = source[it];
207    }
208  }
209
210  /// \brief Copy the source map to the target map.
211  ///
212  /// Copy the \c source map to the \c target map. It uses the given iterator
213  /// to iterate on the data structure.
214  template <typename Target, typename Source,
215            typename ItemIt>       
216  void copyMap(Target& target, const Source& source, ItemIt it) {
217    for (; it != INVALID; ++it) {
218      target[it] = source[it];
219    }
220  }
221
222
223  /// \brief Class to copy a graph to an other graph.
224  ///
225  /// Class to copy a graph to an other graph. It can be used easier
226  /// with the \c copyGraph() function.
227  template <typename Target, typename Source>
228  class GraphCopy {
229  public:
230    typedef typename Source::Node Node;
231    typedef typename Source::NodeIt NodeIt;
232    typedef typename Source::Edge Edge;
233    typedef typename Source::EdgeIt EdgeIt;
234
235    typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
236    typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
237
238    /// \brief Constructor for the GraphCopy.
239    ///
240    /// It copies the content of the \c _source graph into the
241    /// \c _target graph. It creates also two references, one beetween
242    /// the two nodeset and one beetween the two edgesets.
243    GraphCopy(Target& _target, const Source& _source)
244      : source(_source), target(_target),
245        nodeRefMap(_source), edgeRefMap(_source) {
246      for (NodeIt it(source); it != INVALID; ++it) {
247        nodeRefMap[it] = target.addNode();
248      }
249      for (EdgeIt it(source); it != INVALID; ++it) {
250        edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
251                                        nodeRefMap[source.target(it)]);
252      }
253    }
254
255    /// \brief Copies the node references into the given map.
256    ///
257    /// Copies the node references into the given map.
258    template <typename NodeRef>
259    const GraphCopy& nodeRef(NodeRef& map) const {
260      for (NodeIt it(source); it != INVALID; ++it) {
261        map.set(it, nodeRefMap[it]);
262      }
263      return *this;
264    }
265
266    /// \brief Reverse and copies the node references into the given map.
267    ///
268    /// Reverse and copies the node references into the given map.
269    template <typename NodeRef>
270    const GraphCopy& nodeCrossRef(NodeRef& map) const {
271      for (NodeIt it(source); it != INVALID; ++it) {
272        map.set(nodeRefMap[it], it);
273      }
274      return *this;
275    }
276
277    /// \brief Copies the edge references into the given map.
278    ///
279    /// Copies the edge references into the given map.
280    template <typename EdgeRef>
281    const GraphCopy& edgeRef(EdgeRef& map) const {
282      for (EdgeIt it(source); it != INVALID; ++it) {
283        map.set(it, edgeRefMap[it]);
284      }
285      return *this;
286    }
287
288    /// \brief Reverse and copies the edge references into the given map.
289    ///
290    /// Reverse and copies the edge references into the given map.
291    template <typename EdgeRef>
292    const GraphCopy& edgeCrossRef(EdgeRef& map) const {
293      for (EdgeIt it(source); it != INVALID; ++it) {
294        map.set(edgeRefMap[it], it);
295      }
296      return *this;
297    }
298
299    /// \brief Make copy of the given map.
300    ///
301    /// Makes copy of the given map for the newly created graph.
302    /// The new map's key type is the target graph's node type,
303    /// and the copied map's key type is the source graph's node
304    /// type. 
305    template <typename TargetMap, typename SourceMap>
306    const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
307      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
308      return *this;
309    }
310
311    /// \brief Make copy of the given map.
312    ///
313    /// Makes copy of the given map for the newly created graph.
314    /// The new map's key type is the target graph's edge type,
315    /// and the copied map's key type is the source graph's edge
316    /// type. 
317    template <typename TargetMap, typename SourceMap>
318    const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
319      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
320      return *this;
321    }
322
323    /// \brief Gives back the stored node references.
324    ///
325    /// Gives back the stored node references.
326    const NodeRefMap& nodeRef() const {
327      return nodeRefMap;
328    }
329
330    /// \brief Gives back the stored edge references.
331    ///
332    /// Gives back the stored edge references.
333    const EdgeRefMap& edgeRef() const {
334      return edgeRefMap;
335    }
336
337  private:
338   
339    const Source& source;
340    Target& target;
341
342    NodeRefMap nodeRefMap;
343    EdgeRefMap edgeRefMap;
344  };
345
346  /// \brief Copy a graph to an other graph.
347  ///
348  /// Copy a graph to an other graph.
349  /// The usage of the function:
350  ///
351  /// \code
352  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
353  /// \endcode
354  ///
355  /// After the copy the \c nr map will contain the mapping from the
356  /// source graph's nodes to the target graph's nodes and the \c ecr will
357  /// contain the mapping from the target graph's edge to the source's
358  /// edges.
359  template <typename Target, typename Source>
360  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
361    return GraphCopy<Target, Source>(target, source);
362  }
363
364  template <typename _Graph, typename _Item>
365  class ItemSetTraits {};
366 
367  template <typename _Graph>
368  class ItemSetTraits<_Graph, typename _Graph::Node> {
369  public:
370   
371    typedef _Graph Graph;
372
373    typedef typename Graph::Node Item;
374    typedef typename Graph::NodeIt ItemIt;
375
376    template <typename _Value>
377    class Map : public Graph::template NodeMap<_Value> {
378    public:
379      typedef typename Graph::template NodeMap<_Value> Parent;
380      typedef typename Parent::Value Value;
381
382      Map(const Graph& _graph) : Parent(_graph) {}
383      Map(const Graph& _graph, const Value& _value)
384        : Parent(_graph, _value) {}
385    };
386
387  };
388
389  template <typename _Graph>
390  class ItemSetTraits<_Graph, typename _Graph::Edge> {
391  public:
392   
393    typedef _Graph Graph;
394
395    typedef typename Graph::Edge Item;
396    typedef typename Graph::EdgeIt ItemIt;
397
398    template <typename _Value>
399    class Map : public Graph::template EdgeMap<_Value> {
400    public:
401      typedef typename Graph::template EdgeMap<_Value> Parent;
402      typedef typename Parent::Value Value;
403
404      Map(const Graph& _graph) : Parent(_graph) {}
405      Map(const Graph& _graph, const Value& _value)
406        : Parent(_graph, _value) {}
407    };
408
409  };
410
411  template <typename _Graph>
412  class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
413  public:
414   
415    typedef _Graph Graph;
416
417    typedef typename Graph::UndirEdge Item;
418    typedef typename Graph::UndirEdgeIt ItemIt;
419
420    template <typename _Value>
421    class Map : public Graph::template UndirEdgeMap<_Value> {
422    public:
423      typedef typename Graph::template UndirEdgeMap<_Value> Parent;
424      typedef typename Parent::Value Value;
425
426      Map(const Graph& _graph) : Parent(_graph) {}
427      Map(const Graph& _graph, const Value& _value)
428        : Parent(_graph, _value) {}
429    };
430
431  };
432
433  /// @}
434
435  /// \addtogroup graph_maps
436  /// @{
437
438  template <typename Map, typename Enable = void>
439  struct ReferenceMapTraits {
440    typedef typename Map::Value Value;
441    typedef typename Map::Value& Reference;
442    typedef const typename Map::Value& ConstReference;
443    typedef typename Map::Value* Pointer;
444    typedef const typename Map::Value* ConstPointer;
445  };
446
447  template <typename Map>
448  struct ReferenceMapTraits<
449    Map,
450    typename enable_if<typename Map::FullTypeTag, void>::type
451  > {
452    typedef typename Map::Value Value;
453    typedef typename Map::Reference Reference;
454    typedef typename Map::ConstReference ConstReference;
455    typedef typename Map::Pointer Pointer;
456    typedef typename Map::ConstPointer ConstPointer;
457  };
458
459  /// Provides an immutable and unique id for each item in the graph.
460
461  /// The IdMap class provides a unique and immutable mapping for each item
462  /// in the graph.
463  ///
464  template <typename _Graph, typename _Item>
465  class IdMap {
466  public:
467    typedef _Graph Graph;
468    typedef int Value;
469    typedef _Item Item;
470    typedef _Item Key;
471
472    typedef True NeedCopy;
473
474    /// \brief Constructor.
475    ///
476    /// Constructor for creating id map.
477    IdMap(const Graph& _graph) : graph(&_graph) {}
478
479    /// \brief Gives back the \e id of the item.
480    ///
481    /// Gives back the immutable and unique \e id of the map.
482    int operator[](const Item& item) const { return graph->id(item);}
483
484
485  private:
486    const Graph* graph;
487
488  public:
489
490    /// \brief The class represents the inverse of the map.
491    ///
492    /// The class represents the inverse of the map.
493    /// \see inverse()
494    class InverseMap {
495    public:
496
497      typedef True NeedCopy;
498
499      /// \brief Constructor.
500      ///
501      /// Constructor for creating an id-to-item map.
502      InverseMap(const Graph& _graph) : graph(&_graph) {}
503
504      /// \brief Constructor.
505      ///
506      /// Constructor for creating an id-to-item map.
507      InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
508
509      /// \brief Gives back the given item from its id.
510      ///
511      /// Gives back the given item from its id.
512      ///
513      Item operator[](int id) const { return graph->fromId(id, Item());}
514    private:
515      const Graph* graph;
516    };
517
518    /// \brief Gives back the inverse of the map.
519    ///
520    /// Gives back the inverse of the map.
521    InverseMap inverse() const { return InverseMap(*graph);}
522
523  };
524
525 
526  /// \brief General invertable graph-map type.
527
528  /// This type provides simple invertable map functions.
529  /// The InvertableMap wraps an arbitrary ReadWriteMap
530  /// and if a key is set to a new value then store it
531  /// in the inverse map.
532  /// \param _Graph The graph type.
533  /// \param _Map The map to extend with invertable functionality.
534  template <
535    typename _Graph,
536    typename _Item,
537    typename _Value,
538    typename _Map
539    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
540  >
541  class InvertableMap : protected _Map {
542
543  public:
544 
545    typedef _Map Map;
546    typedef _Graph Graph;
547
548    /// The key type of InvertableMap (Node, Edge, UndirEdge).
549    typedef typename _Map::Key Key;
550    /// The value type of the InvertableMap.
551    typedef typename _Map::Value Value;
552
553    /// \brief Constructor.
554    ///
555    /// Construct a new InvertableMap for the graph.
556    ///
557    InvertableMap(const Graph& graph) : Map(graph) {}
558   
559    /// \brief The setter function of the map.
560    ///
561    /// Sets the mapped value.
562    void set(const Key& key, const Value& val) {
563      Value oldval = Map::operator[](key);
564      typename Container::iterator it = invMap.find(oldval);
565      if (it != invMap.end() && it->second == key) {
566        invMap.erase(it);
567      }     
568      invMap.insert(make_pair(val, key));
569      Map::set(key, val);
570    }
571
572    /// \brief The getter function of the map.
573    ///
574    /// It gives back the value associated with the key.
575    const Value operator[](const Key& key) const {
576      return Map::operator[](key);
577    }
578
579  protected:
580
581    /// \brief Add a new key to the map.
582    ///
583    /// Add a new key to the map. It is called by the
584    /// \c AlterationNotifier.
585    virtual void add(const Key& key) {
586      Map::add(key);
587    }
588
589    /// \brief Erase the key from the map.
590    ///
591    /// Erase the key to the map. It is called by the
592    /// \c AlterationNotifier.
593    virtual void erase(const Key& key) {
594      Value val = Map::operator[](key);
595      typename Container::iterator it = invMap.find(val);
596      if (it != invMap.end() && it->second == key) {
597        invMap.erase(it);
598      }
599      Map::erase(key);
600    }
601
602    /// \brief Clear the keys from the map and inverse map.
603    ///
604    /// Clear the keys from the map and inverse map. It is called by the
605    /// \c AlterationNotifier.
606    virtual void clear() {
607      invMap.clear();
608      Map::clear();
609    }
610
611  private:
612   
613    typedef std::map<Value, Key> Container;
614    Container invMap;   
615
616  public:
617
618    /// \brief The inverse map type.
619    ///
620    /// The inverse of this map. The subscript operator of the map
621    /// gives back always the item what was last assigned to the value.
622    class InverseMap {
623    public:
624      /// \brief Constructor of the InverseMap.
625      ///
626      /// Constructor of the InverseMap.
627      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
628
629      /// The value type of the InverseMap.
630      typedef typename InvertableMap::Key Value;
631      /// The key type of the InverseMap.
632      typedef typename InvertableMap::Value Key;
633
634      /// \brief Subscript operator.
635      ///
636      /// Subscript operator. It gives back always the item
637      /// what was last assigned to the value.
638      Value operator[](const Key& key) const {
639        typename Container::const_iterator it = inverted.invMap.find(key);
640        return it->second;
641      }
642     
643    private:
644      const InvertableMap& inverted;
645    };
646
647    /// \brief It gives back the just readeable inverse map.
648    ///
649    /// It gives back the just readeable inverse map.
650    InverseMap inverse() const {
651      return InverseMap(*this);
652    }
653
654
655   
656  };
657
658  /// \brief Provides a mutable, continuous and unique descriptor for each
659  /// item in the graph.
660  ///
661  /// The DescriptorMap class provides a mutable, continuous and immutable
662  /// mapping for each item in the graph. The value for an item may mutated
663  /// on each operation when the an item erased or added to graph.
664  ///
665  /// \param _Graph The graph class the \c DescriptorMap belongs to.
666  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
667  /// UndirEdge.
668  /// \param _Map A ReadWriteMap mapping from the item type to integer.
669  template <
670    typename _Graph,   
671    typename _Item,
672    typename _Map
673    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
674  >
675  class DescriptorMap : protected _Map {
676
677    typedef _Item Item;
678    typedef _Map Map;
679
680  public:
681    /// The graph class of DescriptorMap.
682    typedef _Graph Graph;
683
684    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
685    typedef typename _Map::Key Key;
686    /// The value type of DescriptorMap.
687    typedef typename _Map::Value Value;
688
689    /// \brief Constructor.
690    ///
691    /// Constructor for descriptor map.
692    DescriptorMap(const Graph& _graph) : Map(_graph) {
693      build();
694    }
695
696  protected:
697
698    /// \brief Add a new key to the map.
699    ///
700    /// Add a new key to the map. It is called by the
701    /// \c AlterationNotifier.
702    virtual void add(const Item& item) {
703      Map::add(item);
704      Map::set(item, invMap.size());
705      invMap.push_back(item);
706    }
707
708    /// \brief Erase the key from the map.
709    ///
710    /// Erase the key to the map. It is called by the
711    /// \c AlterationNotifier.
712    virtual void erase(const Item& item) {
713      Map::set(invMap.back(), Map::operator[](item));
714      invMap[Map::operator[](item)] = invMap.back();
715      invMap.pop_back();
716      Map::erase(item);
717    }
718
719    /// \brief Build the unique map.
720    ///
721    /// Build the unique map. It is called by the
722    /// \c AlterationNotifier.
723    virtual void build() {
724      Map::build();
725      Item it;
726      const typename Map::Graph* graph = Map::getGraph();
727      for (graph->first(it); it != INVALID; graph->next(it)) {
728        Map::set(it, invMap.size());
729        invMap.push_back(it);   
730      }     
731    }
732   
733    /// \brief Clear the keys from the map.
734    ///
735    /// Clear the keys from the map. It is called by the
736    /// \c AlterationNotifier.
737    virtual void clear() {
738      invMap.clear();
739      Map::clear();
740    }
741
742  public:
743
744    /// \brief Gives back the \e descriptor of the item.
745    ///
746    /// Gives back the mutable and unique \e descriptor of the map.
747    int operator[](const Item& item) const {
748      return Map::operator[](item);
749    }
750   
751  private:
752
753    typedef std::vector<Item> Container;
754    Container invMap;
755
756  public:
757    /// \brief The inverse map type.
758    ///
759    /// The inverse map type.
760    class InverseMap {
761    public:
762      /// \brief Constructor of the InverseMap.
763      ///
764      /// Constructor of the InverseMap.
765      InverseMap(const DescriptorMap& _inverted)
766        : inverted(_inverted) {}
767
768
769      /// The value type of the InverseMap.
770      typedef typename DescriptorMap::Key Value;
771      /// The key type of the InverseMap.
772      typedef typename DescriptorMap::Value Key;
773
774      /// \brief Subscript operator.
775      ///
776      /// Subscript operator. It gives back the item
777      /// that the descriptor belongs to currently.
778      Value operator[](const Key& key) const {
779        return inverted.invMap[key];
780      }
781
782      /// \brief Size of the map.
783      ///
784      /// Returns the size of the map.
785      unsigned size() const {
786        return inverted.invMap.size();
787      }
788     
789    private:
790      const DescriptorMap& inverted;
791    };
792
793    /// \brief Gives back the inverse of the map.
794    ///
795    /// Gives back the inverse of the map.
796    const InverseMap inverse() const {
797      return InverseMap(*this);
798    }
799  };
800
801  /// \brief Returns the source of the given edge.
802  ///
803  /// The SourceMap gives back the source Node of the given edge.
804  /// \author Balazs Dezso
805  template <typename Graph>
806  class SourceMap {
807  public:
808
809    typedef True NeedCopy;
810
811    typedef typename Graph::Node Value;
812    typedef typename Graph::Edge Key;
813
814    /// \brief Constructor
815    ///
816    /// Constructor
817    /// \param _graph The graph that the map belongs to.
818    SourceMap(const Graph& _graph) : graph(_graph) {}
819
820    /// \brief The subscript operator.
821    ///
822    /// The subscript operator.
823    /// \param edge The edge
824    /// \return The source of the edge
825    Value operator[](const Key& edge) {
826      return graph.source(edge);
827    }
828
829  private:
830    const Graph& graph;
831  };
832
833  /// \brief Returns a \ref SourceMap class
834  ///
835  /// This function just returns an \ref SourceMap class.
836  /// \relates SourceMap
837  template <typename Graph>
838  inline SourceMap<Graph> sourceMap(const Graph& graph) {
839    return SourceMap<Graph>(graph);
840  }
841
842  /// \brief Returns the target of the given edge.
843  ///
844  /// The TargetMap gives back the target Node of the given edge.
845  /// \author Balazs Dezso
846  template <typename Graph>
847  class TargetMap {
848  public:
849
850    typedef True NeedCopy;
851
852    typedef typename Graph::Node Value;
853    typedef typename Graph::Edge Key;
854
855    /// \brief Constructor
856    ///
857    /// Constructor
858    /// \param _graph The graph that the map belongs to.
859    TargetMap(const Graph& _graph) : graph(_graph) {}
860
861    /// \brief The subscript operator.
862    ///
863    /// The subscript operator.
864    /// \param e The edge
865    /// \return The target of the edge
866    Value operator[](const Key& e) {
867      return graph.target(e);
868    }
869
870  private:
871    const Graph& graph;
872  };
873
874  /// \brief Returns a \ref TargetMap class
875  ///
876  /// This function just returns an \ref TargetMap class.
877  /// \relates TargetMap
878  template <typename Graph>
879  inline TargetMap<Graph> targetMap(const Graph& graph) {
880    return TargetMap<Graph>(graph);
881  }
882
883  /// \brief Returns the "forward" directed edge view of undirected edge.
884  ///
885  /// Returns the "forward" directed edge view of undirected edge.
886  /// \author Balazs Dezso
887  template <typename Graph>
888  class ForwardMap {
889  public:
890
891    typedef True NeedCopy;
892
893    typedef typename Graph::Edge Value;
894    typedef typename Graph::UndirEdge Key;
895
896    /// \brief Constructor
897    ///
898    /// Constructor
899    /// \param _graph The graph that the map belongs to.
900    ForwardMap(const Graph& _graph) : graph(_graph) {}
901
902    /// \brief The subscript operator.
903    ///
904    /// The subscript operator.
905    /// \param key An undirected edge
906    /// \return The "forward" directed edge view of undirected edge
907    Value operator[](const Key& key) const {
908      return graph.edgeWithSource(key, graph.source(key));
909    }
910
911  private:
912    const Graph& graph;
913  };
914
915  /// \brief Returns a \ref ForwardMap class
916  ///
917  /// This function just returns an \ref ForwardMap class.
918  /// \relates ForwardMap
919  template <typename Graph>
920  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
921    return ForwardMap<Graph>(graph);
922  }
923
924  /// \brief Returns the "backward" directed edge view of undirected edge.
925  ///
926  /// Returns the "backward" directed edge view of undirected edge.
927  /// \author Balazs Dezso
928  template <typename Graph>
929  class BackwardMap {
930  public:
931    typedef True NeedCopy;
932
933    typedef typename Graph::Edge Value;
934    typedef typename Graph::UndirEdge Key;
935
936    /// \brief Constructor
937    ///
938    /// Constructor
939    /// \param _graph The graph that the map belongs to.
940    BackwardMap(const Graph& _graph) : graph(_graph) {}
941
942    /// \brief The subscript operator.
943    ///
944    /// The subscript operator.
945    /// \param key An undirected edge
946    /// \return The "backward" directed edge view of undirected edge
947    Value operator[](const Key& key) const {
948      return graph.edgeWithSource(key, graph.target(key));
949    }
950
951  private:
952    const Graph& graph;
953  };
954
955  /// \brief Returns a \ref BackwardMap class
956
957  /// This function just returns an \ref BackwardMap class.
958  /// \relates BackwardMap
959  template <typename Graph>
960  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
961    return BackwardMap<Graph>(graph);
962  }
963
964  template <typename _Graph>
965  class DegMapBase {
966  public:
967   
968    typedef _Graph Graph;
969
970  protected:
971
972    typedef typename Graph::template NodeMap<int> IntNodeMap;
973   
974  };
975
976  /// \brief Map of the node in-degrees.
977  ///
978  /// This map returns the in-degree of a node. Ones it is constructed,
979  /// the degrees are stored in a standard NodeMap, so each query is done
980  /// in constant time. On the other hand, the values updates automatically
981  /// whenever the graph changes.
982  ///
983  /// \sa OutDegMap
984
985  template <typename _Graph>
986  class InDegMap 
987    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
988
989  public:
990   
991    typedef _Graph Graph;
992    typedef int Value;
993    typedef typename Graph::Node Key;
994
995  private:
996
997    class AutoNodeMap : public Graph::template NodeMap<int> {
998    public:
999
1000      typedef typename Graph::template NodeMap<int> Parent;
1001
1002      typedef typename Parent::Key Key;
1003      typedef typename Parent::Value Value;
1004     
1005      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1006     
1007      void add(const Key& key) {
1008        Parent::add(key);
1009        Parent::set(key, 0);
1010      }
1011    };
1012
1013  public:
1014
1015    /// \brief Constructor.
1016    ///
1017    /// Constructor for creating in-degree map.
1018    InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1019      AlterationNotifier<typename _Graph::Edge>
1020        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1021     
1022      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1023        deg[it] = countInEdges(graph, it);
1024      }
1025    }
1026
1027    virtual ~InDegMap() {
1028      AlterationNotifier<typename _Graph::Edge>::
1029        ObserverBase::detach();
1030    }
1031   
1032    /// Gives back the in-degree of a Node.
1033    int operator[](const Key& key) const {
1034      return deg[key];
1035    }
1036
1037  protected:
1038   
1039    typedef typename Graph::Edge Edge;
1040
1041    virtual void add(const Edge& edge) {
1042      ++deg[graph.target(edge)];
1043    }
1044
1045    virtual void erase(const Edge& edge) {
1046      --deg[graph.target(edge)];
1047    }
1048
1049
1050    virtual void build() {
1051      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1052        deg[it] = countInEdges(graph, it);
1053      }     
1054    }
1055
1056    virtual void clear() {
1057      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1058        deg[it] = 0;
1059      }
1060    }
1061  private:
1062   
1063    const _Graph& graph;
1064    AutoNodeMap deg;
1065  };
1066
1067
1068  /// \brief Map of the node out-degrees.
1069  ///
1070  /// This map returns the out-degree of a node. One it is constructed,
1071  /// the degrees are stored in a standard NodeMap, so each query is done
1072  /// in constant time. On the other hand, the values updates automatically
1073  /// whenever the graph changes.
1074  ///
1075  /// \sa OutDegMap
1076
1077  template <typename _Graph>
1078  class OutDegMap 
1079    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1080
1081  public:
1082   
1083    typedef _Graph Graph;
1084    typedef int Value;
1085    typedef typename Graph::Node Key;
1086
1087  private:
1088
1089    class AutoNodeMap : public Graph::template NodeMap<int> {
1090    public:
1091
1092      typedef typename Graph::template NodeMap<int> Parent;
1093
1094      typedef typename Parent::Key Key;
1095      typedef typename Parent::Value Value;
1096     
1097      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1098     
1099      void add(const Key& key) {
1100        Parent::add(key);
1101        Parent::set(key, 0);
1102      }
1103    };
1104
1105  public:
1106
1107    /// \brief Constructor.
1108    ///
1109    /// Constructor for creating out-degree map.
1110    OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1111      AlterationNotifier<typename _Graph::Edge>
1112        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1113     
1114      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1115        deg[it] = countOutEdges(graph, it);
1116      }
1117    }
1118
1119    virtual ~OutDegMap() {
1120      AlterationNotifier<typename _Graph::Edge>::
1121        ObserverBase::detach();
1122    }
1123   
1124    /// Gives back the in-degree of a Node.
1125    int operator[](const Key& key) const {
1126      return deg[key];
1127    }
1128
1129  protected:
1130   
1131    typedef typename Graph::Edge Edge;
1132
1133    virtual void add(const Edge& edge) {
1134      ++deg[graph.source(edge)];
1135    }
1136
1137    virtual void erase(const Edge& edge) {
1138      --deg[graph.source(edge)];
1139    }
1140
1141
1142    virtual void build() {
1143      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1144        deg[it] = countOutEdges(graph, it);
1145      }     
1146    }
1147
1148    virtual void clear() {
1149      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1150        deg[it] = 0;
1151      }
1152    }
1153  private:
1154   
1155    const _Graph& graph;
1156    AutoNodeMap deg;
1157  };
1158
1159  /// @}
1160
1161} //END OF NAMESPACE LEMON
1162
1163#endif
Note: See TracBrowser for help on using the repository browser.