COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 1506:e8f1ad6cc8dd

Last change on this file since 1506:e8f1ad6cc8dd was 1506:e8f1ad6cc8dd, checked in by Alpar Juttner, 14 years ago

Some callbacks are still unimplemented

File size: 26.7 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      /// \brief Size of the map.
683      ///
684      /// Returns the size of the map.
685      unsigned size() const {
686        return inverted.invMap.size();
687      }
688     
689    private:
690      const DescriptorMap& inverted;
691    };
692
693    /// \brief Gives back the inverse of the map.
694    ///
695    /// Gives back the inverse of the map.
696    const InverseMap inverse() const {
697      return InverseMap(*this);
698    }
699  };
700
701  /// \brief Returns the source of the given edge.
702  ///
703  /// The SourceMap gives back the source Node of the given edge.
704  /// \author Balazs Dezso
705  template <typename Graph>
706  class SourceMap {
707  public:
708
709    typedef True NeedCopy;
710
711    typedef typename Graph::Node Value;
712    typedef typename Graph::Edge Key;
713
714    /// \brief Constructor
715    ///
716    /// Constructor
717    /// \param _graph The graph that the map belongs to.
718    SourceMap(const Graph& _graph) : graph(_graph) {}
719
720    /// \brief The subscript operator.
721    ///
722    /// The subscript operator.
723    /// \param edge The edge
724    /// \return The source of the edge
725    Value operator[](const Key& edge) {
726      return graph.source(edge);
727    }
728
729  private:
730    const Graph& graph;
731  };
732
733  /// \brief Returns a \ref SourceMap class
734  ///
735  /// This function just returns an \ref SourceMap class.
736  /// \relates SourceMap
737  template <typename Graph>
738  inline SourceMap<Graph> sourceMap(const Graph& graph) {
739    return SourceMap<Graph>(graph);
740  }
741
742  /// \brief Returns the target of the given edge.
743  ///
744  /// The TargetMap gives back the target Node of the given edge.
745  /// \author Balazs Dezso
746  template <typename Graph>
747  class TargetMap {
748  public:
749
750    typedef True NeedCopy;
751
752    typedef typename Graph::Node Value;
753    typedef typename Graph::Edge Key;
754
755    /// \brief Constructor
756    ///
757    /// Constructor
758    /// \param _graph The graph that the map belongs to.
759    TargetMap(const Graph& _graph) : graph(_graph) {}
760
761    /// \brief The subscript operator.
762    ///
763    /// The subscript operator.
764    /// \param edge The edge
765    /// \return The target of the edge
766    Value operator[](const Key& key) {
767      return graph.target(key);
768    }
769
770  private:
771    const Graph& graph;
772  };
773
774  /// \brief Returns a \ref TargetMap class
775
776  /// This function just returns an \ref TargetMap class.
777  /// \relates TargetMap
778  template <typename Graph>
779  inline TargetMap<Graph> targetMap(const Graph& graph) {
780    return TargetMap<Graph>(graph);
781  }
782
783  /// \brief Returns the "forward" directed edge view of undirected edge.
784  ///
785  /// Returns the "forward" directed edge view of undirected edge.
786  /// \author Balazs Dezso
787  template <typename Graph>
788  class ForwardMap {
789  public:
790
791    typedef True NeedCopy;
792
793    typedef typename Graph::Edge Value;
794    typedef typename Graph::UndirEdge Key;
795
796    /// \brief Constructor
797    ///
798    /// Constructor
799    /// \param _graph The graph that the map belongs to.
800    ForwardMap(const Graph& _graph) : graph(_graph) {}
801
802    /// \brief The subscript operator.
803    ///
804    /// The subscript operator.
805    /// \param key An undirected edge
806    /// \return The "forward" directed edge view of undirected edge
807    Value operator[](const Key& key) const {
808      return graph.edgeWithSource(key, graph.source(key));
809    }
810
811  private:
812    const Graph& graph;
813  };
814
815  /// \brief Returns a \ref ForwardMap class
816
817  /// This function just returns an \ref ForwardMap class.
818  /// \relates ForwardMap
819  template <typename Graph>
820  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
821    return ForwardMap<Graph>(graph);
822  }
823
824  /// \brief Returns the "backward" directed edge view of undirected edge.
825  ///
826  /// Returns the "backward" directed edge view of undirected edge.
827  /// \author Balazs Dezso
828  template <typename Graph>
829  class BackwardMap {
830  public:
831    typedef True NeedCopy;
832
833    typedef typename Graph::Edge Value;
834    typedef typename Graph::UndirEdge Key;
835
836    /// \brief Constructor
837    ///
838    /// Constructor
839    /// \param _graph The graph that the map belongs to.
840    BackwardMap(const Graph& _graph) : graph(_graph) {}
841
842    /// \brief The subscript operator.
843    ///
844    /// The subscript operator.
845    /// \param key An undirected edge
846    /// \return The "backward" directed edge view of undirected edge
847    Value operator[](const Key& key) const {
848      return graph.edgeWithSource(key, graph.target(key));
849    }
850
851  private:
852    const Graph& graph;
853  };
854
855  /// \brief Returns a \ref BackwardMap class
856
857  /// This function just returns an \ref BackwardMap class.
858  /// \relates BackwardMap
859  template <typename Graph>
860  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
861    return BackwardMap<Graph>(graph);
862  }
863
864
865
866  /// Map of the node in-degrees.
867
868  ///This map returns the in-degree of a node. Ones it is constructed,
869  ///the degrees are stored in a standard NodeMap, so each query is done
870  ///in constant time. On the other hand, the values updates automatically
871  ///whenever the graph changes.
872  ///
873  ///\sa OutDegMap
874  template <typename _Graph>
875  class InDegMap  :
876    protected _Graph::template NodeMap<int>,
877    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
878  {
879    const _Graph& graph;
880  public:
881    typedef int Value;
882    typedef typename _Graph::Node Key;
883
884    /// \brief Constructor.
885    ///
886    /// Constructor for creating in-degree map.
887    InDegMap(const _Graph& _graph) :
888      _Graph::template NodeMap<int>(_graph,0),
889      graph(_graph)
890    {
891      AlterationNotifier<typename _Graph::Edge>
892        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
893
894      for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
895        for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
896          _Graph::template NodeMap<int>::operator[](graph.target(e))++;
897    }
898
899    virtual ~InDegMap()
900    {
901      AlterationNotifier<typename _Graph::Edge>::
902        ObserverBase::detach();
903    }
904   
905    /// Gives back the in-degree of a Node.
906    int operator[](const Key& k) const {
907      return _Graph::template NodeMap<int>::operator[](k);
908    }
909
910  protected:
911    virtual void add(const typename _Graph::Node& n) {
912      _Graph::template NodeMap<int>::add(n);
913       _Graph::template NodeMap<int>::operator[](n)=0;
914    }
915    virtual void erase(const typename _Graph::Node&n)
916    {
917      _Graph::template NodeMap<int>::erase(n);
918    }
919    virtual void add(const typename _Graph::Edge& e) {
920      _Graph::template NodeMap<int>::operator[](graph.target(e))++;
921    }
922    virtual void erase(const typename _Graph::Edge& e) {
923      _Graph::template NodeMap<int>::operator[](graph.target(e))--;
924    }
925
926    ///\e
927   
928    ///\bug Unimplemented
929    ///
930    virtual void build() {}
931    ///\e
932   
933    ///\bug Unimplemented
934    ///
935    virtual void clear() {}
936
937  };
938
939
940  /// Map of the node out-degrees.
941
942  ///This map returns the out-degree of a node. One it is constructed,
943  ///the degrees are stored in a standard NodeMap, so each query is done
944  ///in constant time. On the other hand, the values updates automatically
945  ///whenever the graph changes.
946  ///
947  ///\sa OutDegMap
948  template <typename _Graph>
949  class OutDegMap  :
950    protected _Graph::template NodeMap<int>,
951    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
952  {
953    const _Graph& graph;
954  public:
955    typedef int Value;
956    typedef typename _Graph::Node Key;
957
958    /// \brief Constructor.
959    ///
960    /// Constructor for creating out-degree map.
961    OutDegMap(const _Graph& _graph) :
962      _Graph::template NodeMap<int>(_graph,0),
963      graph(_graph)
964    {
965      AlterationNotifier<typename _Graph::Edge>
966        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
967
968      for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
969        for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
970          _Graph::template NodeMap<int>::operator[](graph.source(e))++;
971    }
972
973    ~OutDegMap()
974    {
975      AlterationNotifier<typename _Graph::Edge>::
976        ObserverBase::detach();
977    }
978   
979    /// Gives back the in-degree of a Node.
980    int operator[](const Key& k) const {
981      return _Graph::template NodeMap<int>::operator[](k);
982    }
983
984  protected:
985    virtual void add(const typename _Graph::Node& n) {
986      _Graph::template NodeMap<int>::add(n);
987       _Graph::template NodeMap<int>::operator[](n)=0;
988    }
989    virtual void erase(const typename _Graph::Node&n)
990    {
991      _Graph::template NodeMap<int>::erase(n);
992    }
993    virtual void add(const typename _Graph::Edge& e) {
994      _Graph::template NodeMap<int>::operator[](graph.source(e))++;
995    }
996    virtual void erase(const typename _Graph::Edge& e) {
997      _Graph::template NodeMap<int>::operator[](graph.source(e))--;
998    }
999
1000    ///\e
1001   
1002    ///\bug Unimplemented
1003    ///
1004    virtual void build() {}
1005    ///\e
1006   
1007    ///\bug Unimplemented
1008    ///
1009    virtual void clear() {}
1010
1011  };
1012
1013
1014
1015
1016  /// @}
1017
1018} //END OF NAMESPACE LEMON
1019
1020#endif
Note: See TracBrowser for help on using the repository browser.