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.
38 /// \addtogroup gutils
41 /// \brief Function to count the items in the graph.
43 /// This function counts the items (nodes, edges etc) in the graph.
44 /// The complexity of the function is O(n) because
45 /// it iterates on all of the items.
47 template <typename Graph, typename ItemIt>
48 inline int countItems(const Graph& g) {
50 for (ItemIt it(g); it != INVALID; ++it) {
58 template <typename Graph>
60 typename enable_if<typename Graph::NodeNumTag, int>::type
61 _countNodes(const Graph &g) {
65 template <typename Graph>
66 inline int _countNodes(Wrap<Graph> w) {
67 return countItems<Graph, typename Graph::NodeIt>(w.value);
70 /// \brief Function to count the nodes in the graph.
72 /// This function counts the nodes in the graph.
73 /// The complexity of the function is O(n) but for some
74 /// graph structures it is specialized to run in O(1).
76 /// \todo refer how to specialize it
78 template <typename Graph>
79 inline int countNodes(const Graph& g) {
80 return _countNodes<Graph>(g);
85 template <typename Graph>
87 typename enable_if<typename Graph::EdgeNumTag, int>::type
88 _countEdges(const Graph &g) {
92 template <typename Graph>
93 inline int _countEdges(Wrap<Graph> w) {
94 return countItems<Graph, typename Graph::EdgeIt>(w.value);
97 /// \brief Function to count the edges in the graph.
99 /// This function counts the edges in the graph.
100 /// The complexity of the function is O(e) but for some
101 /// graph structures it is specialized to run in O(1).
103 template <typename Graph>
104 inline int countEdges(const Graph& g) {
105 return _countEdges<Graph>(g);
108 // Undirected edge counting:
110 template <typename Graph>
112 typename enable_if<typename Graph::EdgeNumTag, int>::type
113 _countUndirEdges(const Graph &g) {
114 return g.undirEdgeNum();
117 template <typename Graph>
118 inline int _countUndirEdges(Wrap<Graph> w) {
119 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
122 /// \brief Function to count the undirected edges in the graph.
124 /// This function counts the undirected edges in the graph.
125 /// The complexity of the function is O(e) but for some
126 /// graph structures it is specialized to run in O(1).
128 template <typename Graph>
129 inline int countUndirEdges(const Graph& g) {
130 return _countUndirEdges<Graph>(g);
135 template <typename Graph, typename DegIt>
136 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
138 for (DegIt it(_g, _n); it != INVALID; ++it) {
144 /// \brief Function to count the number of the out-edges from node \c n.
146 /// This function counts the number of the out-edges from node \c n
148 template <typename Graph>
149 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) {
150 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
153 /// \brief Function to count the number of the in-edges to node \c n.
155 /// This function counts the number of the in-edges to node \c n
157 template <typename Graph>
158 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) {
159 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
163 /// Finds an edge between two nodes of a graph.
165 /// Finds an edge from node \c u to node \c v in graph \c g.
167 /// If \c prev is \ref INVALID (this is the default value), then
168 /// it finds the first edge from \c u to \c v. Otherwise it looks for
169 /// the next edge from \c u to \c v after \c prev.
170 /// \return The found edge or \ref INVALID if there is no such an edge.
172 /// Thus you can iterate through each edge from \c u to \c v as it follows.
174 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
178 /// \todo We may want to use the "GraphBase"
179 /// interface here...
180 /// \bug Untested ...
181 template <typename Graph>
182 typename Graph::Edge findEdge(const Graph &g,
183 typename Graph::Node u, typename Graph::Node v,
184 typename Graph::Edge prev = INVALID)
186 typename Graph::OutEdgeIt e(g,prev);
187 // if(prev==INVALID) g.first(e,u);
188 if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
190 while(e!=INVALID && g.target(e)!=v) ++e;
194 /// \brief Copy a map.
196 /// This function copies the \c source map to the \c target map. It uses the
197 /// given iterator to iterate on the data structure and it uses the \c ref
198 /// mapping to convert the source's keys to the target's keys.
199 template <typename Target, typename Source,
200 typename ItemIt, typename Ref>
201 void copyMap(Target& target, const Source& source,
202 ItemIt it, const Ref& ref) {
203 for (; it != INVALID; ++it) {
204 target[ref[it]] = source[it];
208 /// \brief Copy the source map to the target map.
210 /// Copy the \c source map to the \c target map. It uses the given iterator
211 /// to iterate on the data structure.
212 template <typename Target, typename Source,
214 void copyMap(Target& target, const Source& source, ItemIt it) {
215 for (; it != INVALID; ++it) {
216 target[it] = source[it];
221 /// \brief Class to copy a graph.
223 /// Class to copy a graph to an other graph (duplicate a graph). The
224 /// simplest way of using it is through the \c copyGraph() function.
225 template <typename Target, typename Source>
228 typedef typename Source::Node Node;
229 typedef typename Source::NodeIt NodeIt;
230 typedef typename Source::Edge Edge;
231 typedef typename Source::EdgeIt EdgeIt;
233 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
234 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
236 /// \brief Constructor for the GraphCopy.
238 /// It copies the content of the \c _source graph into the
239 /// \c _target graph. It creates also two references, one beetween
240 /// the two nodeset and one beetween the two edgesets.
241 GraphCopy(Target& _target, const Source& _source)
242 : source(_source), target(_target),
243 nodeRefMap(_source), edgeRefMap(_source) {
244 for (NodeIt it(source); it != INVALID; ++it) {
245 nodeRefMap[it] = target.addNode();
247 for (EdgeIt it(source); it != INVALID; ++it) {
248 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
249 nodeRefMap[source.target(it)]);
253 /// \brief Copies the node references into the given map.
255 /// Copies the node references into the given map.
256 template <typename NodeRef>
257 const GraphCopy& nodeRef(NodeRef& map) const {
258 for (NodeIt it(source); it != INVALID; ++it) {
259 map.set(it, nodeRefMap[it]);
264 /// \brief Reverse and copies the node references into the given map.
266 /// Reverse and copies the node references into the given map.
267 template <typename NodeRef>
268 const GraphCopy& nodeCrossRef(NodeRef& map) const {
269 for (NodeIt it(source); it != INVALID; ++it) {
270 map.set(nodeRefMap[it], it);
275 /// \brief Copies the edge references into the given map.
277 /// Copies the edge references into the given map.
278 template <typename EdgeRef>
279 const GraphCopy& edgeRef(EdgeRef& map) const {
280 for (EdgeIt it(source); it != INVALID; ++it) {
281 map.set(it, edgeRefMap[it]);
286 /// \brief Reverse and copies the edge references into the given map.
288 /// Reverse and copies the edge references into the given map.
289 template <typename EdgeRef>
290 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
291 for (EdgeIt it(source); it != INVALID; ++it) {
292 map.set(edgeRefMap[it], it);
297 /// \brief Make copy of the given map.
299 /// Makes copy of the given map for the newly created graph.
300 /// The new map's key type is the target graph's node type,
301 /// and the copied map's key type is the source graph's node
303 template <typename TargetMap, typename SourceMap>
304 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
305 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
309 /// \brief Make copy of the given map.
311 /// Makes copy of the given map for the newly created graph.
312 /// The new map's key type is the target graph's edge type,
313 /// and the copied map's key type is the source graph's edge
315 template <typename TargetMap, typename SourceMap>
316 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
317 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
321 /// \brief Gives back the stored node references.
323 /// Gives back the stored node references.
324 const NodeRefMap& nodeRef() const {
328 /// \brief Gives back the stored edge references.
330 /// Gives back the stored edge references.
331 const EdgeRefMap& edgeRef() const {
337 const Source& source;
340 NodeRefMap nodeRefMap;
341 EdgeRefMap edgeRefMap;
344 /// \brief Copy a graph to an other graph.
346 /// Copy a graph to an other graph.
347 /// The usage of the function:
350 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
353 /// After the copy the \c nr map will contain the mapping from the
354 /// source graph's nodes to the target graph's nodes and the \c ecr will
355 /// contain the mapping from the target graph's edges to the source's
357 template <typename Target, typename Source>
358 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
359 return GraphCopy<Target, Source>(target, source);
362 template <typename _Graph, typename _Item>
363 class ItemSetTraits {};
365 template <typename _Graph>
366 class ItemSetTraits<_Graph, typename _Graph::Node> {
369 typedef _Graph Graph;
371 typedef typename Graph::Node Item;
372 typedef typename Graph::NodeIt ItemIt;
374 template <typename _Value>
375 class Map : public Graph::template NodeMap<_Value> {
377 typedef typename Graph::template NodeMap<_Value> Parent;
378 typedef typename Parent::Value Value;
380 Map(const Graph& _graph) : Parent(_graph) {}
381 Map(const Graph& _graph, const Value& _value)
382 : Parent(_graph, _value) {}
387 template <typename _Graph>
388 class ItemSetTraits<_Graph, typename _Graph::Edge> {
391 typedef _Graph Graph;
393 typedef typename Graph::Edge Item;
394 typedef typename Graph::EdgeIt ItemIt;
396 template <typename _Value>
397 class Map : public Graph::template EdgeMap<_Value> {
399 typedef typename Graph::template EdgeMap<_Value> Parent;
400 typedef typename Parent::Value Value;
402 Map(const Graph& _graph) : Parent(_graph) {}
403 Map(const Graph& _graph, const Value& _value)
404 : Parent(_graph, _value) {}
409 template <typename _Graph>
410 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
413 typedef _Graph Graph;
415 typedef typename Graph::UndirEdge Item;
416 typedef typename Graph::UndirEdgeIt ItemIt;
418 template <typename _Value>
419 class Map : public Graph::template UndirEdgeMap<_Value> {
421 typedef typename Graph::template UndirEdgeMap<_Value> Parent;
422 typedef typename Parent::Value Value;
424 Map(const Graph& _graph) : Parent(_graph) {}
425 Map(const Graph& _graph, const Value& _value)
426 : Parent(_graph, _value) {}
433 /// \addtogroup graph_maps
436 template <typename Map, typename Enable = void>
437 struct ReferenceMapTraits {
438 typedef typename Map::Value Value;
439 typedef typename Map::Value& Reference;
440 typedef const typename Map::Value& ConstReference;
441 typedef typename Map::Value* Pointer;
442 typedef const typename Map::Value* ConstPointer;
445 template <typename Map>
446 struct ReferenceMapTraits<
448 typename enable_if<typename Map::FullTypeTag, void>::type
450 typedef typename Map::Value Value;
451 typedef typename Map::Reference Reference;
452 typedef typename Map::ConstReference ConstReference;
453 typedef typename Map::Pointer Pointer;
454 typedef typename Map::ConstPointer ConstPointer;
457 /// Provides an immutable and unique id for each item in the graph.
459 /// The IdMap class provides a unique and immutable id for each item of the
460 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
461 /// different items (nodes) get different ids <li>\b immutable: the id of an
462 /// item (node) does not change (even if you delete other nodes). </ul>
463 /// Through this map you get access (i.e. can read) the inner id values of
464 /// the items stored in the graph. This map can be inverted with its member
465 /// class \c InverseMap.
467 template <typename _Graph, typename _Item>
470 typedef _Graph Graph;
475 typedef True NeedCopy;
477 /// \brief Constructor.
479 /// Constructor for creating id map.
480 IdMap(const Graph& _graph) : graph(&_graph) {}
482 /// \brief Gives back the \e id of the item.
484 /// Gives back the immutable and unique \e id of the map.
485 int operator[](const Item& item) const { return graph->id(item);}
493 /// \brief The class represents the inverse of its owner (IdMap).
495 /// The class represents the inverse of its owner (IdMap).
500 typedef True NeedCopy;
502 /// \brief Constructor.
504 /// Constructor for creating an id-to-item map.
505 InverseMap(const Graph& _graph) : graph(&_graph) {}
507 /// \brief Constructor.
509 /// Constructor for creating an id-to-item map.
510 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
512 /// \brief Gives back the given item from its id.
514 /// Gives back the given item from its id.
516 Item operator[](int id) const { return graph->fromId(id, Item());}
521 /// \brief Gives back the inverse of the map.
523 /// Gives back the inverse of the IdMap.
524 InverseMap inverse() const { return InverseMap(*graph);}
529 /// \brief General invertable graph-map type.
531 /// This type provides simple invertable graph-maps.
532 /// The InvertableMap wraps an arbitrary ReadWriteMap
533 /// and if a key is set to a new value then store it
534 /// in the inverse map.
535 /// \param _Graph The graph type.
536 /// \param _Map The map to extend with invertable functionality.
542 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
544 class InvertableMap : protected _Map {
549 typedef _Graph Graph;
551 /// The key type of InvertableMap (Node, Edge, UndirEdge).
552 typedef typename _Map::Key Key;
553 /// The value type of the InvertableMap.
554 typedef typename _Map::Value Value;
556 /// \brief Constructor.
558 /// Construct a new InvertableMap for the graph.
560 InvertableMap(const Graph& graph) : Map(graph) {}
562 /// \brief The setter function of the map.
564 /// Sets the mapped value.
565 void set(const Key& key, const Value& val) {
566 Value oldval = Map::operator[](key);
567 typename Container::iterator it = invMap.find(oldval);
568 if (it != invMap.end() && it->second == key) {
571 invMap.insert(make_pair(val, key));
575 /// \brief The getter function of the map.
577 /// It gives back the value associated with the key.
578 const Value operator[](const Key& key) const {
579 return Map::operator[](key);
584 /// \brief Add a new key to the map.
586 /// Add a new key to the map. It is called by the
587 /// \c AlterationNotifier.
588 virtual void add(const Key& key) {
592 /// \brief Erase the key from the map.
594 /// Erase the key to the map. It is called by the
595 /// \c AlterationNotifier.
596 virtual void erase(const Key& key) {
597 Value val = Map::operator[](key);
598 typename Container::iterator it = invMap.find(val);
599 if (it != invMap.end() && it->second == key) {
605 /// \brief Clear the keys from the map and inverse map.
607 /// Clear the keys from the map and inverse map. It is called by the
608 /// \c AlterationNotifier.
609 virtual void clear() {
616 typedef std::map<Value, Key> Container;
621 /// \brief The inverse map type.
623 /// The inverse of this map. The subscript operator of the map
624 /// gives back always the item what was last assigned to the value.
627 /// \brief Constructor of the InverseMap.
629 /// Constructor of the InverseMap.
630 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
632 /// The value type of the InverseMap.
633 typedef typename InvertableMap::Key Value;
634 /// The key type of the InverseMap.
635 typedef typename InvertableMap::Value Key;
637 /// \brief Subscript operator.
639 /// Subscript operator. It gives back always the item
640 /// what was last assigned to the value.
641 Value operator[](const Key& key) const {
642 typename Container::const_iterator it = inverted.invMap.find(key);
647 const InvertableMap& inverted;
650 /// \brief It gives back the just readeable inverse map.
652 /// It gives back the just readeable inverse map.
653 InverseMap inverse() const {
654 return InverseMap(*this);
661 /// \brief Provides a mutable, continuous and unique descriptor for each
662 /// item in the graph.
664 /// The DescriptorMap class provides a unique and continuous (but mutable)
665 /// descriptor (id) for each item of the same type (e.g. node) in the
666 /// graph. This id is <ul><li>\b unique: different items (nodes) get
667 /// different ids <li>\b continuous: the range of the ids is the set of
668 /// integers between 0 and \c n-1, where \c n is the number of the items of
669 /// this type (e.g. nodes) (so the id of a node can change if you delete an
670 /// other node, i.e. this id is mutable). </ul> This map can be inverted
671 /// with its member class \c InverseMap.
673 /// \param _Graph The graph class the \c DescriptorMap belongs to.
674 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
676 /// \param _Map A ReadWriteMap mapping from the item type to integer.
681 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
683 class DescriptorMap : protected _Map {
689 /// The graph class of DescriptorMap.
690 typedef _Graph Graph;
692 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
693 typedef typename _Map::Key Key;
694 /// The value type of DescriptorMap.
695 typedef typename _Map::Value Value;
697 /// \brief Constructor.
699 /// Constructor for descriptor map.
700 DescriptorMap(const Graph& _graph) : Map(_graph) {
706 /// \brief Add a new key to the map.
708 /// Add a new key to the map. It is called by the
709 /// \c AlterationNotifier.
710 virtual void add(const Item& item) {
712 Map::set(item, invMap.size());
713 invMap.push_back(item);
716 /// \brief Erase the key from the map.
718 /// Erase the key to the map. It is called by the
719 /// \c AlterationNotifier.
720 virtual void erase(const Item& item) {
721 Map::set(invMap.back(), Map::operator[](item));
722 invMap[Map::operator[](item)] = invMap.back();
727 /// \brief Build the unique map.
729 /// Build the unique map. It is called by the
730 /// \c AlterationNotifier.
731 virtual void build() {
734 const typename Map::Graph* graph = Map::getGraph();
735 for (graph->first(it); it != INVALID; graph->next(it)) {
736 Map::set(it, invMap.size());
737 invMap.push_back(it);
741 /// \brief Clear the keys from the map.
743 /// Clear the keys from the map. It is called by the
744 /// \c AlterationNotifier.
745 virtual void clear() {
752 /// \brief Swaps the position of the two items in the map.
754 /// Swaps the position of the two items in the map.
755 void swap(const Item& p, const Item& q) {
756 int pi = Map::operator[](p);
757 int qi = Map::operator[](q);
764 /// \brief Gives back the \e descriptor of the item.
766 /// Gives back the mutable and unique \e descriptor of the map.
767 int operator[](const Item& item) const {
768 return Map::operator[](item);
773 typedef std::vector<Item> Container;
777 /// \brief The inverse map type of DescriptorMap.
779 /// The inverse map type of DescriptorMap.
782 /// \brief Constructor of the InverseMap.
784 /// Constructor of the InverseMap.
785 InverseMap(const DescriptorMap& _inverted)
786 : inverted(_inverted) {}
789 /// The value type of the InverseMap.
790 typedef typename DescriptorMap::Key Value;
791 /// The key type of the InverseMap.
792 typedef typename DescriptorMap::Value Key;
794 /// \brief Subscript operator.
796 /// Subscript operator. It gives back the item
797 /// that the descriptor belongs to currently.
798 Value operator[](const Key& key) const {
799 return inverted.invMap[key];
802 /// \brief Size of the map.
804 /// Returns the size of the map.
806 return inverted.invMap.size();
810 const DescriptorMap& inverted;
813 /// \brief Gives back the inverse of the map.
815 /// Gives back the inverse of the map.
816 const InverseMap inverse() const {
817 return InverseMap(*this);
821 /// \brief Returns the source of the given edge.
823 /// The SourceMap gives back the source Node of the given edge.
824 /// \author Balazs Dezso
825 template <typename Graph>
829 typedef True NeedCopy;
831 typedef typename Graph::Node Value;
832 typedef typename Graph::Edge Key;
834 /// \brief Constructor
837 /// \param _graph The graph that the map belongs to.
838 SourceMap(const Graph& _graph) : graph(_graph) {}
840 /// \brief The subscript operator.
842 /// The subscript operator.
843 /// \param edge The edge
844 /// \return The source of the edge
845 Value operator[](const Key& edge) {
846 return graph.source(edge);
853 /// \brief Returns a \ref SourceMap class
855 /// This function just returns an \ref SourceMap class.
856 /// \relates SourceMap
857 template <typename Graph>
858 inline SourceMap<Graph> sourceMap(const Graph& graph) {
859 return SourceMap<Graph>(graph);
862 /// \brief Returns the target of the given edge.
864 /// The TargetMap gives back the target Node of the given edge.
865 /// \author Balazs Dezso
866 template <typename Graph>
870 typedef True NeedCopy;
872 typedef typename Graph::Node Value;
873 typedef typename Graph::Edge Key;
875 /// \brief Constructor
878 /// \param _graph The graph that the map belongs to.
879 TargetMap(const Graph& _graph) : graph(_graph) {}
881 /// \brief The subscript operator.
883 /// The subscript operator.
884 /// \param e The edge
885 /// \return The target of the edge
886 Value operator[](const Key& e) {
887 return graph.target(e);
894 /// \brief Returns a \ref TargetMap class
896 /// This function just returns a \ref TargetMap class.
897 /// \relates TargetMap
898 template <typename Graph>
899 inline TargetMap<Graph> targetMap(const Graph& graph) {
900 return TargetMap<Graph>(graph);
903 /// \brief Returns the "forward" directed edge view of an undirected edge.
905 /// Returns the "forward" directed edge view of an undirected edge.
906 /// \author Balazs Dezso
907 template <typename Graph>
911 typedef True NeedCopy;
913 typedef typename Graph::Edge Value;
914 typedef typename Graph::UndirEdge Key;
916 /// \brief Constructor
919 /// \param _graph The graph that the map belongs to.
920 ForwardMap(const Graph& _graph) : graph(_graph) {}
922 /// \brief The subscript operator.
924 /// The subscript operator.
925 /// \param key An undirected edge
926 /// \return The "forward" directed edge view of undirected edge
927 Value operator[](const Key& key) const {
928 return graph.edgeWithSource(key, graph.source(key));
935 /// \brief Returns a \ref ForwardMap class
937 /// This function just returns an \ref ForwardMap class.
938 /// \relates ForwardMap
939 template <typename Graph>
940 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
941 return ForwardMap<Graph>(graph);
944 /// \brief Returns the "backward" directed edge view of an undirected edge.
946 /// Returns the "backward" directed edge view of an undirected edge.
947 /// \author Balazs Dezso
948 template <typename Graph>
951 typedef True NeedCopy;
953 typedef typename Graph::Edge Value;
954 typedef typename Graph::UndirEdge Key;
956 /// \brief Constructor
959 /// \param _graph The graph that the map belongs to.
960 BackwardMap(const Graph& _graph) : graph(_graph) {}
962 /// \brief The subscript operator.
964 /// The subscript operator.
965 /// \param key An undirected edge
966 /// \return The "backward" directed edge view of undirected edge
967 Value operator[](const Key& key) const {
968 return graph.edgeWithSource(key, graph.target(key));
975 /// \brief Returns a \ref BackwardMap class
977 /// This function just returns a \ref BackwardMap class.
978 /// \relates BackwardMap
979 template <typename Graph>
980 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
981 return BackwardMap<Graph>(graph);
984 template <typename _Graph>
988 typedef _Graph Graph;
992 typedef typename Graph::template NodeMap<int> IntNodeMap;
996 /// \brief Map of the node in-degrees.
998 /// This map returns the in-degree of a node. Once it is constructed,
999 /// the degrees are stored in a standard NodeMap, so each query is done
1000 /// in constant time. On the other hand, the values are updated automatically
1001 /// whenever the graph changes.
1005 template <typename _Graph>
1007 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1011 typedef _Graph Graph;
1013 typedef typename Graph::Node Key;
1017 class AutoNodeMap : public Graph::template NodeMap<int> {
1020 typedef typename Graph::template NodeMap<int> Parent;
1022 typedef typename Parent::Key Key;
1023 typedef typename Parent::Value Value;
1025 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1027 void add(const Key& key) {
1029 Parent::set(key, 0);
1035 /// \brief Constructor.
1037 /// Constructor for creating in-degree map.
1038 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1039 AlterationNotifier<typename _Graph::Edge>
1040 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1042 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1043 deg[it] = countInEdges(graph, it);
1047 virtual ~InDegMap() {
1048 AlterationNotifier<typename _Graph::Edge>::
1049 ObserverBase::detach();
1052 /// Gives back the in-degree of a Node.
1053 int operator[](const Key& key) const {
1059 typedef typename Graph::Edge Edge;
1061 virtual void add(const Edge& edge) {
1062 ++deg[graph.target(edge)];
1065 virtual void erase(const Edge& edge) {
1066 --deg[graph.target(edge)];
1070 virtual void build() {
1071 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1072 deg[it] = countInEdges(graph, it);
1076 virtual void clear() {
1077 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1083 const _Graph& graph;
1088 /// \brief Map of the node out-degrees.
1090 /// This map returns the out-degree of a node. Once it is constructed,
1091 /// the degrees are stored in a standard NodeMap, so each query is done
1092 /// in constant time. On the other hand, the values are updated automatically
1093 /// whenever the graph changes.
1097 template <typename _Graph>
1099 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1103 typedef _Graph Graph;
1105 typedef typename Graph::Node Key;
1109 class AutoNodeMap : public Graph::template NodeMap<int> {
1112 typedef typename Graph::template NodeMap<int> Parent;
1114 typedef typename Parent::Key Key;
1115 typedef typename Parent::Value Value;
1117 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1119 void add(const Key& key) {
1121 Parent::set(key, 0);
1127 /// \brief Constructor.
1129 /// Constructor for creating out-degree map.
1130 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1131 AlterationNotifier<typename _Graph::Edge>
1132 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1134 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1135 deg[it] = countOutEdges(graph, it);
1139 virtual ~OutDegMap() {
1140 AlterationNotifier<typename _Graph::Edge>::
1141 ObserverBase::detach();
1144 /// Gives back the in-degree of a Node.
1145 int operator[](const Key& key) const {
1151 typedef typename Graph::Edge Edge;
1153 virtual void add(const Edge& edge) {
1154 ++deg[graph.source(edge)];
1157 virtual void erase(const Edge& edge) {
1158 --deg[graph.source(edge)];
1162 virtual void build() {
1163 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1164 deg[it] = countOutEdges(graph, it);
1168 virtual void clear() {
1169 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1175 const _Graph& graph;
1181 } //END OF NAMESPACE LEMON