COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1469:104aab6e5d86

Last change on this file since 1469:104aab6e5d86 was 1467:638124c0ef08, checked in by Akos Ladanyi, 19 years ago

gcc 3.4 compatibility fixes

File size: 26.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 structure 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 structure 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 edges in the graph.
125  ///
126  /// This function counts the 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  ///\e
178
179  ///\todo Please document.
180  ///
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  ///\e
187
188  ///\todo Please document.
189  ///
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 an 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 inversable graph-map type.
433
434  /// This type provides simple inversable map functions.
435  /// The InversableMap wraps an arbitrary ReadWriteMap
436  /// and if a key is setted 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 inversable 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    /// \brief Add a new key to the map.
486    ///
487    /// Add a new key to the map. It is called by the
488    /// \c AlterationNotifier.
489    virtual void add(const Key& key) {
490      Map::add(key);
491    }
492
493    /// \brief Erase the key from the map.
494    ///
495    /// Erase the key to the map. It is called by the
496    /// \c AlterationNotifier.
497    virtual void erase(const Key& key) {
498      Value val = Map::operator[](key);
499      typename Container::iterator it = invMap.find(val);
500      if (it != invMap.end() && it->second == key) {
501        invMap.erase(it);
502      }
503      Map::erase(key);
504    }
505
506    /// \brief Clear the keys from the map and inverse map.
507    ///
508    /// Clear the keys from the map and inverse map. It is called by the
509    /// \c AlterationNotifier.
510    virtual void clear() {
511      invMap.clear();
512      Map::clear();
513    }
514
515  private:
516   
517    typedef std::map<Value, Key> Container;
518    Container invMap;   
519
520  public:
521
522    /// \brief The inverse map type.
523    ///
524    /// The inverse of this map. The subscript operator of the map
525    /// gives back always the item what was last assigned to the value.
526    class InverseMap {
527    public:
528      /// \brief Constructor of the InverseMap.
529      ///
530      /// Constructor of the InverseMap.
531      InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
532
533      /// The value type of the InverseMap.
534      typedef typename InvertableMap::Key Value;
535      /// The key type of the InverseMap.
536      typedef typename InvertableMap::Value Key;
537
538      /// \brief Subscript operator.
539      ///
540      /// Subscript operator. It gives back always the item
541      /// what was last assigned to the value.
542      Value operator[](const Key& key) const {
543        typename Container::const_iterator it = inverted.invMap.find(key);
544        return it->second;
545      }
546     
547    private:
548      const InvertableMap& inverted;
549    };
550
551    /// \brief It gives back the just readeable inverse map.
552    ///
553    /// It gives back the just readeable inverse map.
554    InverseMap inverse() const {
555      return InverseMap(*this);
556    }
557
558
559   
560  };
561
562  /// \brief Provides a mutable, continuous and unique descriptor for each
563  /// item in the graph.
564  ///
565  /// The DescriptorMap class provides a mutable, continuous and immutable
566  /// mapping for each item in the graph. The value for an item may mutated
567  /// on each operation when the an item erased or added to graph.
568  ///
569  /// \param _Graph The graph class the \c DescriptorMap belongs to.
570  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
571  /// UndirEdge.
572  /// \param _Map A ReadWriteMap mapping from the item type to integer.
573  template <
574    typename _Graph,   
575    typename _Item,
576    typename _Map
577    = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
578  >
579  class DescriptorMap : protected _Map {
580
581    typedef _Item Item;
582    typedef _Map Map;
583
584  public:
585    /// The graph class of DescriptorMap.
586    typedef _Graph Graph;
587
588    /// The key type of DescriptorMap (Node, Edge, UndirEdge).
589    typedef typename _Map::Key Key;
590    /// The value type of DescriptorMap.
591    typedef typename _Map::Value Value;
592
593    /// \brief Constructor.
594    ///
595    /// Constructor for descriptor map.
596    DescriptorMap(const Graph& _graph) : Map(_graph) {
597      build();
598    }
599
600    /// \brief Add a new key to the map.
601    ///
602    /// Add a new key to the map. It is called by the
603    /// \c AlterationNotifier.
604    virtual void add(const Item& item) {
605      Map::add(item);
606      Map::set(item, invMap.size());
607      invMap.push_back(item);
608    }
609
610    /// \brief Erase the key from the map.
611    ///
612    /// Erase the key to the map. It is called by the
613    /// \c AlterationNotifier.
614    virtual void erase(const Item& item) {
615      Map::set(invMap.back(), Map::operator[](item));
616      invMap[Map::operator[](item)] = invMap.back();
617      invMap.pop_back();
618      Map::erase(item);
619    }
620
621    /// \brief Build the unique map.
622    ///
623    /// Build the unique map. It is called by the
624    /// \c AlterationNotifier.
625    virtual void build() {
626      Map::build();
627      Item it;
628      const typename Map::Graph* graph = Map::getGraph();
629      for (graph->first(it); it != INVALID; graph->next(it)) {
630        Map::set(it, invMap.size());
631        invMap.push_back(it);   
632      }     
633    }
634   
635    /// \brief Clear the keys from the map.
636    ///
637    /// Clear the keys from the map. It is called by the
638    /// \c AlterationNotifier.
639    virtual void clear() {
640      invMap.clear();
641      Map::clear();
642    }
643
644    /// \brief Gives back the \e descriptor of the item.
645    ///
646    /// Gives back the mutable and unique \e descriptor of the map.
647    int operator[](const Item& item) const {
648      return Map::operator[](item);
649    }
650   
651  private:
652
653    typedef std::vector<Item> Container;
654    Container invMap;
655
656  public:
657    /// \brief The inverse map type.
658    ///
659    /// The inverse map type.
660    class InverseMap {
661    public:
662      /// \brief Constructor of the InverseMap.
663      ///
664      /// Constructor of the InverseMap.
665      InverseMap(const DescriptorMap& _inverted)
666        : inverted(_inverted) {}
667
668
669      /// The value type of the InverseMap.
670      typedef typename DescriptorMap::Key Value;
671      /// The key type of the InverseMap.
672      typedef typename DescriptorMap::Value Key;
673
674      /// \brief Subscript operator.
675      ///
676      /// Subscript operator. It gives back the item
677      /// that the descriptor belongs to currently.
678      Value operator[](const Key& key) const {
679        return inverted.invMap[key];
680      }
681     
682    private:
683      const DescriptorMap& inverted;
684    };
685
686    /// \brief Gives back the inverse of the map.
687    ///
688    /// Gives back the inverse of the map.
689    const InverseMap inverse() const {
690      return InverseMap(*this);
691    }
692  };
693
694  /// \brief Returns the source of the given edge.
695  ///
696  /// The SourceMap gives back the source Node of the given edge.
697  /// \author Balazs Dezso
698  template <typename Graph>
699  class SourceMap {
700  public:
701
702    typedef True NeedCopy;
703
704    typedef typename Graph::Node Value;
705    typedef typename Graph::Edge Key;
706
707    /// \brief Constructor
708    ///
709    /// Constructor
710    /// \param _graph The graph that the map belongs to.
711    SourceMap(const Graph& _graph) : graph(_graph) {}
712
713    /// \brief The subscript operator.
714    ///
715    /// The subscript operator.
716    /// \param edge The edge
717    /// \return The source of the edge
718    Value operator[](const Key& edge) {
719      return graph.source(edge);
720    }
721
722  private:
723    const Graph& graph;
724  };
725
726  /// \brief Returns a \ref SourceMap class
727  ///
728  /// This function just returns an \ref SourceMap class.
729  /// \relates SourceMap
730  template <typename Graph>
731  inline SourceMap<Graph> sourceMap(const Graph& graph) {
732    return SourceMap<Graph>(graph);
733  }
734
735  /// \brief Returns the target of the given edge.
736  ///
737  /// The TargetMap gives back the target Node of the given edge.
738  /// \author Balazs Dezso
739  template <typename Graph>
740  class TargetMap {
741  public:
742
743    typedef True NeedCopy;
744
745    typedef typename Graph::Node Value;
746    typedef typename Graph::Edge Key;
747
748    /// \brief Constructor
749    ///
750    /// Constructor
751    /// \param _graph The graph that the map belongs to.
752    TargetMap(const Graph& _graph) : graph(_graph) {}
753
754    /// \brief The subscript operator.
755    ///
756    /// The subscript operator.
757    /// \param edge The edge
758    /// \return The target of the edge
759    Value operator[](const Key& key) {
760      return graph.target(key);
761    }
762
763  private:
764    const Graph& graph;
765  };
766
767  /// \brief Returns a \ref TargetMap class
768
769  /// This function just returns an \ref TargetMap class.
770  /// \relates TargetMap
771  template <typename Graph>
772  inline TargetMap<Graph> targetMap(const Graph& graph) {
773    return TargetMap<Graph>(graph);
774  }
775
776  /// \brief Returns the "forward" directed edge view of undirected edge.
777  ///
778  /// Returns the "forward" directed edge view of undirected edge.
779  /// \author Balazs Dezso
780  template <typename Graph>
781  class ForwardMap {
782  public:
783
784    typedef True NeedCopy;
785
786    typedef typename Graph::Edge Value;
787    typedef typename Graph::UndirEdge Key;
788
789    /// \brief Constructor
790    ///
791    /// Constructor
792    /// \param _graph The graph that the map belongs to.
793    ForwardMap(const Graph& _graph) : graph(_graph) {}
794
795    /// \brief The subscript operator.
796    ///
797    /// The subscript operator.
798    /// \param key An undirected edge
799    /// \return The "forward" directed edge view of undirected edge
800    Value operator[](const Key& key) const {
801      return graph.edgeWithSource(key, graph.source(key));
802    }
803
804  private:
805    const Graph& graph;
806  };
807
808  /// \brief Returns a \ref ForwardMap class
809
810  /// This function just returns an \ref ForwardMap class.
811  /// \relates ForwardMap
812  template <typename Graph>
813  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
814    return ForwardMap<Graph>(graph);
815  }
816
817  /// \brief Returns the "backward" directed edge view of undirected edge.
818  ///
819  /// Returns the "backward" directed edge view of undirected edge.
820  /// \author Balazs Dezso
821  template <typename Graph>
822  class BackwardMap {
823  public:
824    typedef True NeedCopy;
825
826    typedef typename Graph::Edge Value;
827    typedef typename Graph::UndirEdge Key;
828
829    /// \brief Constructor
830    ///
831    /// Constructor
832    /// \param _graph The graph that the map belongs to.
833    BackwardMap(const Graph& _graph) : graph(_graph) {}
834
835    /// \brief The subscript operator.
836    ///
837    /// The subscript operator.
838    /// \param key An undirected edge
839    /// \return The "backward" directed edge view of undirected edge
840    Value operator[](const Key& key) const {
841      return graph.edgeWithSource(key, graph.target(key));
842    }
843
844  private:
845    const Graph& graph;
846  };
847
848  /// \brief Returns a \ref BackwardMap class
849
850  /// This function just returns an \ref BackwardMap class.
851  /// \relates BackwardMap
852  template <typename Graph>
853  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
854    return BackwardMap<Graph>(graph);
855  }
856
857
858
859  /// Map of the node in-degrees.
860
861  ///This map returns the in-degree of a node. Ones it is constructed,
862  ///the degrees are stored in a standard NodeMap, so each query is done
863  ///in constant time. On the other hand, the values updates automatically
864  ///whenever the graph changes.
865  ///
866  ///\sa OutDegMap
867  template <typename _Graph>
868  class InDegMap  :
869    protected _Graph::template NodeMap<int>,
870    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
871  {
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) :
881      _Graph::template NodeMap<int>(_graph,0),
882      graph(_graph)
883    {
884      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          _Graph::template NodeMap<int>::operator[](graph.target(e))++;
890    }
891
892    virtual ~InDegMap()
893    {
894      AlterationNotifier<typename _Graph::Edge>::
895        ObserverBase::detach();
896    }
897   
898    /// Gives back the in-degree of a Node.
899    int operator[](const Key& k) const {
900      return _Graph::template NodeMap<int>::operator[](k);
901    }
902
903  protected:
904    virtual void add(const typename _Graph::Node& n) {
905      _Graph::template NodeMap<int>::add(n);
906       _Graph::template NodeMap<int>::operator[](n)=0;
907    }
908    virtual void erase(const typename _Graph::Node&n)
909    {
910      _Graph::template NodeMap<int>::erase(n);
911    }
912    virtual void add(const typename _Graph::Edge& e) {
913      _Graph::template NodeMap<int>::operator[](graph.target(e))++;
914    }
915    virtual void erase(const typename _Graph::Edge& e) {
916      _Graph::template NodeMap<int>::operator[](graph.target(e))--;
917    }
918
919    virtual void build() {}
920    virtual void clear() {}
921
922  };
923
924
925  /// Map of the node out-degrees.
926
927  ///This map returns the out-degree of a node. One it is constructed,
928  ///the degrees are stored in a standard NodeMap, so each query is done
929  ///in constant time. On the other hand, the values updates automatically
930  ///whenever the graph changes.
931  ///
932  ///\sa OutDegMap
933  template <typename _Graph>
934  class OutDegMap  :
935    protected _Graph::template NodeMap<int>,
936    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
937  {
938    const _Graph& graph;
939  public:
940    typedef int Value;
941    typedef typename _Graph::Node Key;
942
943    /// \brief Constructor.
944    ///
945    /// Constructor for creating out-degree map.
946    OutDegMap(const _Graph& _graph) :
947      _Graph::template NodeMap<int>(_graph,0),
948      graph(_graph)
949    {
950      AlterationNotifier<typename _Graph::Edge>
951        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
952
953      for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
954        for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
955          _Graph::template NodeMap<int>::operator[](graph.source(e))++;
956    }
957
958    ~OutDegMap()
959    {
960      AlterationNotifier<typename _Graph::Edge>::
961        ObserverBase::detach();
962    }
963   
964    /// Gives back the in-degree of a Node.
965    int operator[](const Key& k) const {
966      return _Graph::template NodeMap<int>::operator[](k);
967    }
968
969  protected:
970    virtual void add(const typename _Graph::Node& n) {
971      _Graph::template NodeMap<int>::add(n);
972       _Graph::template NodeMap<int>::operator[](n)=0;
973    }
974    virtual void erase(const typename _Graph::Node&n)
975    {
976      _Graph::template NodeMap<int>::erase(n);
977    }
978    virtual void add(const typename _Graph::Edge& e) {
979      _Graph::template NodeMap<int>::operator[](graph.source(e))++;
980    }
981    virtual void erase(const typename _Graph::Edge& e) {
982      _Graph::template NodeMap<int>::operator[](graph.source(e))--;
983    }
984
985    virtual void build() {}
986    virtual void clear() {}
987
988  };
989
990
991
992
993  /// @}
994
995} //END OF NAMESPACE LEMON
996
997#endif
Note: See TracBrowser for help on using the repository browser.