Some more doxygen command killed.
2 * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
17 #ifndef LEMON_GRAPH_UTILS_H
18 #define LEMON_GRAPH_UTILS_H
24 #include <lemon/invalid.h>
25 #include <lemon/utility.h>
26 #include <lemon/maps.h>
27 #include <lemon/bits/alteration_notifier.h>
31 ///\brief Graph utilities.
34 ///revise the documentation.
40 /// \addtogroup gutils
43 /// \brief Function to count the items in the graph.
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.
49 template <typename Graph, typename ItemIt>
50 inline int countItems(const Graph& g) {
52 for (ItemIt it(g); it != INVALID; ++it) {
60 template <typename Graph>
62 typename enable_if<typename Graph::NodeNumTag, int>::type
63 _countNodes(const Graph &g) {
67 template <typename Graph>
68 inline int _countNodes(Wrap<Graph> w) {
69 return countItems<Graph, typename Graph::NodeIt>(w.value);
72 /// \brief Function to count the nodes in the graph.
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).
78 /// \todo refer how to specialize it
80 template <typename Graph>
81 inline int countNodes(const Graph& g) {
82 return _countNodes<Graph>(g);
87 template <typename Graph>
89 typename enable_if<typename Graph::EdgeNumTag, int>::type
90 _countEdges(const Graph &g) {
94 template <typename Graph>
95 inline int _countEdges(Wrap<Graph> w) {
96 return countItems<Graph, typename Graph::EdgeIt>(w.value);
99 /// \brief Function to count the edges in the graph.
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).
105 template <typename Graph>
106 inline int countEdges(const Graph& g) {
107 return _countEdges<Graph>(g);
110 // Undirected edge counting:
112 template <typename Graph>
114 typename enable_if<typename Graph::EdgeNumTag, int>::type
115 _countUndirEdges(const Graph &g) {
116 return g.undirEdgeNum();
119 template <typename Graph>
120 inline int _countUndirEdges(Wrap<Graph> w) {
121 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
124 /// \brief Function to count the undirected edges in the graph.
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).
130 template <typename Graph>
131 inline int countUndirEdges(const Graph& g) {
132 return _countUndirEdges<Graph>(g);
137 template <typename Graph, typename DegIt>
138 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
140 for (DegIt it(_g, _n); it != INVALID; ++it) {
146 /// \brief Function to count the number of the out-edges from node \c n.
148 /// This function counts the number of the out-edges from node \c n
150 template <typename Graph>
151 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
152 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
155 /// \brief Function to count the number of the in-edges to node \c n.
157 /// This function counts the number of the in-edges to node \c n
159 template <typename Graph>
160 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
161 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
165 /// Finds an edge between two nodes of a graph.
167 /// Finds an edge from node \c u to node \c v in graph \c g.
169 /// If \c prev is \ref INVALID (this is the default value), then
170 /// it finds the first edge from \c u to \c v. Otherwise it looks for
171 /// the next edge from \c u to \c v after \c prev.
172 /// \return The found edge or \ref INVALID if there is no such an edge.
174 /// Thus you can iterate through each edge from \c u to \c v as it follows.
176 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
180 /// \todo We may want to use the "GraphBase"
181 /// interface here...
182 /// \bug Untested ...
183 template <typename Graph>
184 typename Graph::Edge findEdge(const Graph &g,
185 typename Graph::Node u, typename Graph::Node v,
186 typename Graph::Edge prev = INVALID)
188 typename Graph::OutEdgeIt e(g,prev);
189 // if(prev==INVALID) g.first(e,u);
190 if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
192 while(e!=INVALID && g.target(e)!=v) ++e;
196 /// \brief Copy the source map to the target map.
198 /// Copy the \c source map to the \c target map. It uses the given iterator
199 /// to iterate on the data structure and it use the \c ref mapping to
200 /// convert the source's keys to the target's keys.
201 template <typename Target, typename Source,
202 typename ItemIt, typename Ref>
203 void copyMap(Target& target, const Source& source,
204 ItemIt it, const Ref& ref) {
205 for (; it != INVALID; ++it) {
206 target[ref[it]] = source[it];
210 /// \brief Copy the source map to the target map.
212 /// Copy the \c source map to the \c target map. It uses the given iterator
213 /// to iterate on the data structure.
214 template <typename Target, typename Source,
216 void copyMap(Target& target, const Source& source, ItemIt it) {
217 for (; it != INVALID; ++it) {
218 target[it] = source[it];
223 /// \brief Class to copy a graph to an other graph.
225 /// Class to copy a graph to an other graph. It can be used easier
226 /// with the \c copyGraph() function.
227 template <typename Target, typename Source>
230 typedef typename Source::Node Node;
231 typedef typename Source::NodeIt NodeIt;
232 typedef typename Source::Edge Edge;
233 typedef typename Source::EdgeIt EdgeIt;
235 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
236 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
238 /// \brief Constructor for the GraphCopy.
240 /// It copies the content of the \c _source graph into the
241 /// \c _target graph. It creates also two references, one beetween
242 /// the two nodeset and one beetween the two edgesets.
243 GraphCopy(Target& _target, const Source& _source)
244 : source(_source), target(_target),
245 nodeRefMap(_source), edgeRefMap(_source) {
246 for (NodeIt it(source); it != INVALID; ++it) {
247 nodeRefMap[it] = target.addNode();
249 for (EdgeIt it(source); it != INVALID; ++it) {
250 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
251 nodeRefMap[source.target(it)]);
255 /// \brief Copies the node references into the given map.
257 /// Copies the node references into the given map.
258 template <typename NodeRef>
259 const GraphCopy& nodeRef(NodeRef& map) const {
260 for (NodeIt it(source); it != INVALID; ++it) {
261 map.set(it, nodeRefMap[it]);
266 /// \brief Reverse and copies the node references into the given map.
268 /// Reverse and copies the node references into the given map.
269 template <typename NodeRef>
270 const GraphCopy& nodeCrossRef(NodeRef& map) const {
271 for (NodeIt it(source); it != INVALID; ++it) {
272 map.set(nodeRefMap[it], it);
277 /// \brief Copies the edge references into the given map.
279 /// Copies the edge references into the given map.
280 template <typename EdgeRef>
281 const GraphCopy& edgeRef(EdgeRef& map) const {
282 for (EdgeIt it(source); it != INVALID; ++it) {
283 map.set(it, edgeRefMap[it]);
288 /// \brief Reverse and copies the edge references into the given map.
290 /// Reverse and copies the edge references into the given map.
291 template <typename EdgeRef>
292 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
293 for (EdgeIt it(source); it != INVALID; ++it) {
294 map.set(edgeRefMap[it], it);
299 /// \brief Make copy of the given map.
301 /// Makes copy of the given map for the newly created graph.
302 /// The new map's key type is the target graph's node type,
303 /// and the copied map's key type is the source graph's node
305 template <typename TargetMap, typename SourceMap>
306 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
307 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
311 /// \brief Make copy of the given map.
313 /// Makes copy of the given map for the newly created graph.
314 /// The new map's key type is the target graph's edge type,
315 /// and the copied map's key type is the source graph's edge
317 template <typename TargetMap, typename SourceMap>
318 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
319 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
323 /// \brief Gives back the stored node references.
325 /// Gives back the stored node references.
326 const NodeRefMap& nodeRef() const {
330 /// \brief Gives back the stored edge references.
332 /// Gives back the stored edge references.
333 const EdgeRefMap& edgeRef() const {
339 const Source& source;
342 NodeRefMap nodeRefMap;
343 EdgeRefMap edgeRefMap;
346 /// \brief Copy a graph to an other graph.
348 /// Copy a graph to an other graph.
349 /// The usage of the function:
352 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
355 /// After the copy the \c nr map will contain the mapping from the
356 /// source graph's nodes to the target graph's nodes and the \c ecr will
357 /// contain the mapping from the target graph's edge to the source's
359 template <typename Target, typename Source>
360 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
361 return GraphCopy<Target, Source>(target, source);
364 template <typename _Graph, typename _Item>
365 class ItemSetTraits {};
367 template <typename _Graph>
368 class ItemSetTraits<_Graph, typename _Graph::Node> {
371 typedef _Graph Graph;
373 typedef typename Graph::Node Item;
374 typedef typename Graph::NodeIt ItemIt;
376 template <typename _Value>
377 class Map : public Graph::template NodeMap<_Value> {
379 typedef typename Graph::template NodeMap<_Value> Parent;
380 typedef typename Parent::Value Value;
382 Map(const Graph& _graph) : Parent(_graph) {}
383 Map(const Graph& _graph, const Value& _value)
384 : Parent(_graph, _value) {}
389 template <typename _Graph>
390 class ItemSetTraits<_Graph, typename _Graph::Edge> {
393 typedef _Graph Graph;
395 typedef typename Graph::Edge Item;
396 typedef typename Graph::EdgeIt ItemIt;
398 template <typename _Value>
399 class Map : public Graph::template EdgeMap<_Value> {
401 typedef typename Graph::template EdgeMap<_Value> Parent;
402 typedef typename Parent::Value Value;
404 Map(const Graph& _graph) : Parent(_graph) {}
405 Map(const Graph& _graph, const Value& _value)
406 : Parent(_graph, _value) {}
411 template <typename _Graph>
412 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
415 typedef _Graph Graph;
417 typedef typename Graph::UndirEdge Item;
418 typedef typename Graph::UndirEdgeIt ItemIt;
420 template <typename _Value>
421 class Map : public Graph::template UndirEdgeMap<_Value> {
423 typedef typename Graph::template UndirEdgeMap<_Value> Parent;
424 typedef typename Parent::Value Value;
426 Map(const Graph& _graph) : Parent(_graph) {}
427 Map(const Graph& _graph, const Value& _value)
428 : Parent(_graph, _value) {}
435 /// \addtogroup graph_maps
438 template <typename Map, typename Enable = void>
439 struct ReferenceMapTraits {
440 typedef typename Map::Value Value;
441 typedef typename Map::Value& Reference;
442 typedef const typename Map::Value& ConstReference;
443 typedef typename Map::Value* Pointer;
444 typedef const typename Map::Value* ConstPointer;
447 template <typename Map>
448 struct ReferenceMapTraits<
450 typename enable_if<typename Map::FullTypeTag, void>::type
452 typedef typename Map::Value Value;
453 typedef typename Map::Reference Reference;
454 typedef typename Map::ConstReference ConstReference;
455 typedef typename Map::Pointer Pointer;
456 typedef typename Map::ConstPointer ConstPointer;
459 /// Provides an immutable and unique id for each item in the graph.
461 /// The IdMap class provides a unique and immutable mapping for each item
464 template <typename _Graph, typename _Item>
467 typedef _Graph Graph;
472 typedef True NeedCopy;
474 /// \brief Constructor.
476 /// Constructor for creating id map.
477 IdMap(const Graph& _graph) : graph(&_graph) {}
479 /// \brief Gives back the \e id of the item.
481 /// Gives back the immutable and unique \e id of the map.
482 int operator[](const Item& item) const { return graph->id(item);}
490 /// \brief The class represents the inverse of the map.
492 /// The class represents the inverse of the map.
497 typedef True NeedCopy;
499 /// \brief Constructor.
501 /// Constructor for creating an id-to-item map.
502 InverseMap(const Graph& _graph) : graph(&_graph) {}
504 /// \brief Constructor.
506 /// Constructor for creating an id-to-item map.
507 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
509 /// \brief Gives back the given item from its id.
511 /// Gives back the given item from its id.
513 Item operator[](int id) const { return graph->fromId(id, Item());}
518 /// \brief Gives back the inverse of the map.
520 /// Gives back the inverse of the map.
521 InverseMap inverse() const { return InverseMap(*graph);}
526 /// \brief General invertable graph-map type.
528 /// This type provides simple invertable map functions.
529 /// The InvertableMap wraps an arbitrary ReadWriteMap
530 /// and if a key is set to a new value then store it
531 /// in the inverse map.
532 /// \param _Graph The graph type.
533 /// \param _Map The map to extend with invertable functionality.
539 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
541 class InvertableMap : protected _Map {
546 typedef _Graph Graph;
548 /// The key type of InvertableMap (Node, Edge, UndirEdge).
549 typedef typename _Map::Key Key;
550 /// The value type of the InvertableMap.
551 typedef typename _Map::Value Value;
553 /// \brief Constructor.
555 /// Construct a new InvertableMap for the graph.
557 InvertableMap(const Graph& graph) : Map(graph) {}
559 /// \brief The setter function of the map.
561 /// Sets the mapped value.
562 void set(const Key& key, const Value& val) {
563 Value oldval = Map::operator[](key);
564 typename Container::iterator it = invMap.find(oldval);
565 if (it != invMap.end() && it->second == key) {
568 invMap.insert(make_pair(val, key));
572 /// \brief The getter function of the map.
574 /// It gives back the value associated with the key.
575 const Value operator[](const Key& key) const {
576 return Map::operator[](key);
581 /// \brief Add a new key to the map.
583 /// Add a new key to the map. It is called by the
584 /// \c AlterationNotifier.
585 virtual void add(const Key& key) {
589 /// \brief Erase the key from the map.
591 /// Erase the key to the map. It is called by the
592 /// \c AlterationNotifier.
593 virtual void erase(const Key& key) {
594 Value val = Map::operator[](key);
595 typename Container::iterator it = invMap.find(val);
596 if (it != invMap.end() && it->second == key) {
602 /// \brief Clear the keys from the map and inverse map.
604 /// Clear the keys from the map and inverse map. It is called by the
605 /// \c AlterationNotifier.
606 virtual void clear() {
613 typedef std::map<Value, Key> Container;
618 /// \brief The inverse map type.
620 /// The inverse of this map. The subscript operator of the map
621 /// gives back always the item what was last assigned to the value.
624 /// \brief Constructor of the InverseMap.
626 /// Constructor of the InverseMap.
627 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
629 /// The value type of the InverseMap.
630 typedef typename InvertableMap::Key Value;
631 /// The key type of the InverseMap.
632 typedef typename InvertableMap::Value Key;
634 /// \brief Subscript operator.
636 /// Subscript operator. It gives back always the item
637 /// what was last assigned to the value.
638 Value operator[](const Key& key) const {
639 typename Container::const_iterator it = inverted.invMap.find(key);
644 const InvertableMap& inverted;
647 /// \brief It gives back the just readeable inverse map.
649 /// It gives back the just readeable inverse map.
650 InverseMap inverse() const {
651 return InverseMap(*this);
658 /// \brief Provides a mutable, continuous and unique descriptor for each
659 /// item in the graph.
661 /// The DescriptorMap class provides a mutable, continuous and immutable
662 /// mapping for each item in the graph. The value for an item may mutated
663 /// on each operation when the an item erased or added to graph.
665 /// \param _Graph The graph class the \c DescriptorMap belongs to.
666 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
668 /// \param _Map A ReadWriteMap mapping from the item type to integer.
673 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
675 class DescriptorMap : protected _Map {
681 /// The graph class of DescriptorMap.
682 typedef _Graph Graph;
684 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
685 typedef typename _Map::Key Key;
686 /// The value type of DescriptorMap.
687 typedef typename _Map::Value Value;
689 /// \brief Constructor.
691 /// Constructor for descriptor map.
692 DescriptorMap(const Graph& _graph) : Map(_graph) {
698 /// \brief Add a new key to the map.
700 /// Add a new key to the map. It is called by the
701 /// \c AlterationNotifier.
702 virtual void add(const Item& item) {
704 Map::set(item, invMap.size());
705 invMap.push_back(item);
708 /// \brief Erase the key from the map.
710 /// Erase the key to the map. It is called by the
711 /// \c AlterationNotifier.
712 virtual void erase(const Item& item) {
713 Map::set(invMap.back(), Map::operator[](item));
714 invMap[Map::operator[](item)] = invMap.back();
719 /// \brief Build the unique map.
721 /// Build the unique map. It is called by the
722 /// \c AlterationNotifier.
723 virtual void build() {
726 const typename Map::Graph* graph = Map::getGraph();
727 for (graph->first(it); it != INVALID; graph->next(it)) {
728 Map::set(it, invMap.size());
729 invMap.push_back(it);
733 /// \brief Clear the keys from the map.
735 /// Clear the keys from the map. It is called by the
736 /// \c AlterationNotifier.
737 virtual void clear() {
742 /// \brief Gives back the \e descriptor of the item.
744 /// Gives back the mutable and unique \e descriptor of the map.
745 int operator[](const Item& item) const {
746 return Map::operator[](item);
751 typedef std::vector<Item> Container;
755 /// \brief The inverse map type.
757 /// The inverse map type.
760 /// \brief Constructor of the InverseMap.
762 /// Constructor of the InverseMap.
763 InverseMap(const DescriptorMap& _inverted)
764 : inverted(_inverted) {}
767 /// The value type of the InverseMap.
768 typedef typename DescriptorMap::Key Value;
769 /// The key type of the InverseMap.
770 typedef typename DescriptorMap::Value Key;
772 /// \brief Subscript operator.
774 /// Subscript operator. It gives back the item
775 /// that the descriptor belongs to currently.
776 Value operator[](const Key& key) const {
777 return inverted.invMap[key];
780 /// \brief Size of the map.
782 /// Returns the size of the map.
783 unsigned size() const {
784 return inverted.invMap.size();
788 const DescriptorMap& inverted;
791 /// \brief Gives back the inverse of the map.
793 /// Gives back the inverse of the map.
794 const InverseMap inverse() const {
795 return InverseMap(*this);
799 /// \brief Returns the source of the given edge.
801 /// The SourceMap gives back the source Node of the given edge.
802 /// \author Balazs Dezso
803 template <typename Graph>
807 typedef True NeedCopy;
809 typedef typename Graph::Node Value;
810 typedef typename Graph::Edge Key;
812 /// \brief Constructor
815 /// \param _graph The graph that the map belongs to.
816 SourceMap(const Graph& _graph) : graph(_graph) {}
818 /// \brief The subscript operator.
820 /// The subscript operator.
821 /// \param edge The edge
822 /// \return The source of the edge
823 Value operator[](const Key& edge) {
824 return graph.source(edge);
831 /// \brief Returns a \ref SourceMap class
833 /// This function just returns an \ref SourceMap class.
834 /// \relates SourceMap
835 template <typename Graph>
836 inline SourceMap<Graph> sourceMap(const Graph& graph) {
837 return SourceMap<Graph>(graph);
840 /// \brief Returns the target of the given edge.
842 /// The TargetMap gives back the target Node of the given edge.
843 /// \author Balazs Dezso
844 template <typename Graph>
848 typedef True NeedCopy;
850 typedef typename Graph::Node Value;
851 typedef typename Graph::Edge Key;
853 /// \brief Constructor
856 /// \param _graph The graph that the map belongs to.
857 TargetMap(const Graph& _graph) : graph(_graph) {}
859 /// \brief The subscript operator.
861 /// The subscript operator.
862 /// \param e The edge
863 /// \return The target of the edge
864 Value operator[](const Key& e) {
865 return graph.target(e);
872 /// \brief Returns a \ref TargetMap class
874 /// This function just returns an \ref TargetMap class.
875 /// \relates TargetMap
876 template <typename Graph>
877 inline TargetMap<Graph> targetMap(const Graph& graph) {
878 return TargetMap<Graph>(graph);
881 /// \brief Returns the "forward" directed edge view of undirected edge.
883 /// Returns the "forward" directed edge view of undirected edge.
884 /// \author Balazs Dezso
885 template <typename Graph>
889 typedef True NeedCopy;
891 typedef typename Graph::Edge Value;
892 typedef typename Graph::UndirEdge Key;
894 /// \brief Constructor
897 /// \param _graph The graph that the map belongs to.
898 ForwardMap(const Graph& _graph) : graph(_graph) {}
900 /// \brief The subscript operator.
902 /// The subscript operator.
903 /// \param key An undirected edge
904 /// \return The "forward" directed edge view of undirected edge
905 Value operator[](const Key& key) const {
906 return graph.edgeWithSource(key, graph.source(key));
913 /// \brief Returns a \ref ForwardMap class
915 /// This function just returns an \ref ForwardMap class.
916 /// \relates ForwardMap
917 template <typename Graph>
918 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
919 return ForwardMap<Graph>(graph);
922 /// \brief Returns the "backward" directed edge view of undirected edge.
924 /// Returns the "backward" directed edge view of undirected edge.
925 /// \author Balazs Dezso
926 template <typename Graph>
929 typedef True NeedCopy;
931 typedef typename Graph::Edge Value;
932 typedef typename Graph::UndirEdge Key;
934 /// \brief Constructor
937 /// \param _graph The graph that the map belongs to.
938 BackwardMap(const Graph& _graph) : graph(_graph) {}
940 /// \brief The subscript operator.
942 /// The subscript operator.
943 /// \param key An undirected edge
944 /// \return The "backward" directed edge view of undirected edge
945 Value operator[](const Key& key) const {
946 return graph.edgeWithSource(key, graph.target(key));
953 /// \brief Returns a \ref BackwardMap class
955 /// This function just returns an \ref BackwardMap class.
956 /// \relates BackwardMap
957 template <typename Graph>
958 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
959 return BackwardMap<Graph>(graph);
962 template <typename _Graph>
966 typedef _Graph Graph;
970 typedef typename Graph::template NodeMap<int> IntNodeMap;
974 /// \brief Map of the node in-degrees.
976 /// This map returns the in-degree of a node. Ones it is constructed,
977 /// the degrees are stored in a standard NodeMap, so each query is done
978 /// in constant time. On the other hand, the values updates automatically
979 /// whenever the graph changes.
983 template <typename _Graph>
985 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
989 typedef _Graph Graph;
991 typedef typename Graph::Node Key;
995 class AutoNodeMap : public Graph::template NodeMap<int> {
998 typedef typename Graph::template NodeMap<int> Parent;
1000 typedef typename Parent::Key Key;
1001 typedef typename Parent::Value Value;
1003 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1005 void add(const Key& key) {
1007 Parent::set(key, 0);
1013 /// \brief Constructor.
1015 /// Constructor for creating in-degree map.
1016 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1017 AlterationNotifier<typename _Graph::Edge>
1018 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1020 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1021 deg[it] = countInEdges(graph, it);
1025 virtual ~InDegMap() {
1026 AlterationNotifier<typename _Graph::Edge>::
1027 ObserverBase::detach();
1030 /// Gives back the in-degree of a Node.
1031 int operator[](const Key& key) const {
1037 typedef typename Graph::Edge Edge;
1039 virtual void add(const Edge& edge) {
1040 ++deg[graph.target(edge)];
1043 virtual void erase(const Edge& edge) {
1044 --deg[graph.target(edge)];
1048 virtual void build() {
1049 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1050 deg[it] = countInEdges(graph, it);
1054 virtual void clear() {
1055 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1061 const _Graph& graph;
1066 /// \brief Map of the node out-degrees.
1068 /// This map returns the out-degree of a node. One it is constructed,
1069 /// the degrees are stored in a standard NodeMap, so each query is done
1070 /// in constant time. On the other hand, the values updates automatically
1071 /// whenever the graph changes.
1075 template <typename _Graph>
1077 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1081 typedef _Graph Graph;
1083 typedef typename Graph::Node Key;
1087 class AutoNodeMap : public Graph::template NodeMap<int> {
1090 typedef typename Graph::template NodeMap<int> Parent;
1092 typedef typename Parent::Key Key;
1093 typedef typename Parent::Value Value;
1095 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1097 void add(const Key& key) {
1099 Parent::set(key, 0);
1105 /// \brief Constructor.
1107 /// Constructor for creating out-degree map.
1108 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1109 AlterationNotifier<typename _Graph::Edge>
1110 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1112 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1113 deg[it] = countOutEdges(graph, it);
1117 virtual ~OutDegMap() {
1118 AlterationNotifier<typename _Graph::Edge>::
1119 ObserverBase::detach();
1122 /// Gives back the in-degree of a Node.
1123 int operator[](const Key& key) const {
1129 typedef typename Graph::Edge Edge;
1131 virtual void add(const Edge& edge) {
1132 ++deg[graph.source(edge)];
1135 virtual void erase(const Edge& edge) {
1136 --deg[graph.source(edge)];
1140 virtual void build() {
1141 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1142 deg[it] = countOutEdges(graph, it);
1146 virtual void clear() {
1147 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1153 const _Graph& graph;
1159 } //END OF NAMESPACE LEMON