COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1526:8c14aa8f27a2

Last change on this file since 1526:8c14aa8f27a2 was 1526:8c14aa8f27a2, checked in by athos, 14 years ago

Mainly doc review.

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