Better doc.
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);
162 /// \brief Function to count the number of the in-edges to node \c n.
164 /// This function counts the number of the in-edges to node \c n
166 template <typename Graph>
167 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
168 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
172 template <typename Graph>
174 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
175 _findEdge(const Graph &g,
176 typename Graph::Node u, typename Graph::Node v,
177 typename Graph::Edge prev = INVALID) {
178 return g.findEdge(u, v, prev);
181 template <typename Graph>
182 inline typename Graph::Edge
183 _findEdge(Wrap<Graph> w,
184 typename Graph::Node u,
185 typename Graph::Node v,
186 typename Graph::Edge prev = INVALID) {
187 const Graph& g = w.value;
188 if (prev == INVALID) {
189 typename Graph::OutEdgeIt e(g, u);
190 while (e != INVALID && g.target(e) != v) ++e;
193 typename Graph::OutEdgeIt e(g, prev); ++e;
194 while (e != INVALID && g.target(e) != v) ++e;
199 /// \brief Finds an edge between two nodes of a graph.
201 /// Finds an edge from node \c u to node \c v in graph \c g.
203 /// If \c prev is \ref INVALID (this is the default value), then
204 /// it finds the first edge from \c u to \c v. Otherwise it looks for
205 /// the next edge from \c u to \c v after \c prev.
206 /// \return The found edge or \ref INVALID if there is no such an edge.
208 /// Thus you can iterate through each edge from \c u to \c v as it follows.
210 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
214 // /// \todo We may want to use the "GraphBase"
215 // /// interface here...
216 // /// It would not work with the undirected graphs.
217 template <typename Graph>
218 inline typename Graph::Edge findEdge(const Graph &g,
219 typename Graph::Node u,
220 typename Graph::Node v,
221 typename Graph::Edge prev = INVALID) {
222 return _findEdge<Graph>(g, u, v, prev);
225 /// \brief Iterator for iterating on edges connected the same nodes.
227 /// Iterator for iterating on edges connected the same nodes. It is
228 /// higher level interface for the findEdge() function. You can
229 /// use it the following way:
231 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
236 /// \author Balazs Dezso
237 template <typename _Graph>
238 class ConEdgeIt : public _Graph::Edge {
241 typedef _Graph Graph;
242 typedef typename Graph::Edge Parent;
244 typedef typename Graph::Edge Edge;
245 typedef typename Graph::Node Node;
247 /// \brief Constructor.
249 /// Construct a new ConEdgeIt iterating on the edges which
250 /// connects the \c u and \c v node.
251 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
252 Parent::operator=(findEdge(graph, u, v));
255 /// \brief Constructor.
257 /// Construct a new ConEdgeIt which continues the iterating from
259 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
261 /// \brief Increment operator.
263 /// It increments the iterator and gives back the next edge.
264 ConEdgeIt& operator++() {
265 Parent::operator=(findEdge(graph, graph.source(*this),
266 graph.target(*this), *this));
273 /// \brief Copy a map.
275 /// This function copies the \c source map to the \c target map. It uses the
276 /// given iterator to iterate on the data structure and it uses the \c ref
277 /// mapping to convert the source's keys to the target's keys.
278 template <typename Target, typename Source,
279 typename ItemIt, typename Ref>
280 void copyMap(Target& target, const Source& source,
281 ItemIt it, const Ref& ref) {
282 for (; it != INVALID; ++it) {
283 target[ref[it]] = source[it];
287 /// \brief Copy the source map to the target map.
289 /// Copy the \c source map to the \c target map. It uses the given iterator
290 /// to iterate on the data structure.
291 template <typename Target, typename Source,
293 void copyMap(Target& target, const Source& source, ItemIt it) {
294 for (; it != INVALID; ++it) {
295 target[it] = source[it];
300 /// \brief Class to copy a graph.
302 /// Class to copy a graph to an other graph (duplicate a graph). The
303 /// simplest way of using it is through the \c copyGraph() function.
304 template <typename Target, typename Source>
307 typedef typename Source::Node Node;
308 typedef typename Source::NodeIt NodeIt;
309 typedef typename Source::Edge Edge;
310 typedef typename Source::EdgeIt EdgeIt;
312 typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
313 typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
315 /// \brief Constructor for the GraphCopy.
317 /// It copies the content of the \c _source graph into the
318 /// \c _target graph. It creates also two references, one beetween
319 /// the two nodeset and one beetween the two edgesets.
320 GraphCopy(Target& _target, const Source& _source)
321 : source(_source), target(_target),
322 nodeRefMap(_source), edgeRefMap(_source) {
323 for (NodeIt it(source); it != INVALID; ++it) {
324 nodeRefMap[it] = target.addNode();
326 for (EdgeIt it(source); it != INVALID; ++it) {
327 edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
328 nodeRefMap[source.target(it)]);
332 /// \brief Copies the node references into the given map.
334 /// Copies the node references into the given map.
335 template <typename NodeRef>
336 const GraphCopy& nodeRef(NodeRef& map) const {
337 for (NodeIt it(source); it != INVALID; ++it) {
338 map.set(it, nodeRefMap[it]);
343 /// \brief Reverse and copies the node references into the given map.
345 /// Reverse and copies the node references into the given map.
346 template <typename NodeRef>
347 const GraphCopy& nodeCrossRef(NodeRef& map) const {
348 for (NodeIt it(source); it != INVALID; ++it) {
349 map.set(nodeRefMap[it], it);
354 /// \brief Copies the edge references into the given map.
356 /// Copies the edge references into the given map.
357 template <typename EdgeRef>
358 const GraphCopy& edgeRef(EdgeRef& map) const {
359 for (EdgeIt it(source); it != INVALID; ++it) {
360 map.set(it, edgeRefMap[it]);
365 /// \brief Reverse and copies the edge references into the given map.
367 /// Reverse and copies the edge references into the given map.
368 template <typename EdgeRef>
369 const GraphCopy& edgeCrossRef(EdgeRef& map) const {
370 for (EdgeIt it(source); it != INVALID; ++it) {
371 map.set(edgeRefMap[it], it);
376 /// \brief Make copy of the given map.
378 /// Makes copy of the given map for the newly created graph.
379 /// The new map's key type is the target graph's node type,
380 /// and the copied map's key type is the source graph's node
382 template <typename TargetMap, typename SourceMap>
383 const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
384 copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
388 /// \brief Make copy of the given map.
390 /// Makes copy of the given map for the newly created graph.
391 /// The new map's key type is the target graph's edge type,
392 /// and the copied map's key type is the source graph's edge
394 template <typename TargetMap, typename SourceMap>
395 const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
396 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
400 /// \brief Gives back the stored node references.
402 /// Gives back the stored node references.
403 const NodeRefMap& nodeRef() const {
407 /// \brief Gives back the stored edge references.
409 /// Gives back the stored edge references.
410 const EdgeRefMap& edgeRef() const {
416 const Source& source;
419 NodeRefMap nodeRefMap;
420 EdgeRefMap edgeRefMap;
423 /// \brief Copy a graph to an other graph.
425 /// Copy a graph to an other graph.
426 /// The usage of the function:
429 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
432 /// After the copy the \c nr map will contain the mapping from the
433 /// source graph's nodes to the target graph's nodes and the \c ecr will
434 /// contain the mapping from the target graph's edges to the source's
436 template <typename Target, typename Source>
437 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
438 return GraphCopy<Target, Source>(target, source);
441 template <typename _Graph, typename _Item>
442 class ItemSetTraits {};
444 template <typename _Graph>
445 class ItemSetTraits<_Graph, typename _Graph::Node> {
448 typedef _Graph Graph;
450 typedef typename Graph::Node Item;
451 typedef typename Graph::NodeIt ItemIt;
453 template <typename _Value>
454 class Map : public Graph::template NodeMap<_Value> {
456 typedef typename Graph::template NodeMap<_Value> Parent;
457 typedef typename Parent::Value Value;
459 Map(const Graph& _graph) : Parent(_graph) {}
460 Map(const Graph& _graph, const Value& _value)
461 : Parent(_graph, _value) {}
466 template <typename _Graph>
467 class ItemSetTraits<_Graph, typename _Graph::Edge> {
470 typedef _Graph Graph;
472 typedef typename Graph::Edge Item;
473 typedef typename Graph::EdgeIt ItemIt;
475 template <typename _Value>
476 class Map : public Graph::template EdgeMap<_Value> {
478 typedef typename Graph::template EdgeMap<_Value> Parent;
479 typedef typename Parent::Value Value;
481 Map(const Graph& _graph) : Parent(_graph) {}
482 Map(const Graph& _graph, const Value& _value)
483 : Parent(_graph, _value) {}
488 template <typename _Graph>
489 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
492 typedef _Graph Graph;
494 typedef typename Graph::UndirEdge Item;
495 typedef typename Graph::UndirEdgeIt ItemIt;
497 template <typename _Value>
498 class Map : public Graph::template UndirEdgeMap<_Value> {
500 typedef typename Graph::template UndirEdgeMap<_Value> Parent;
501 typedef typename Parent::Value Value;
503 Map(const Graph& _graph) : Parent(_graph) {}
504 Map(const Graph& _graph, const Value& _value)
505 : Parent(_graph, _value) {}
512 /// \addtogroup graph_maps
515 template <typename Map, typename Enable = void>
516 struct ReferenceMapTraits {
517 typedef typename Map::Value Value;
518 typedef typename Map::Value& Reference;
519 typedef const typename Map::Value& ConstReference;
520 typedef typename Map::Value* Pointer;
521 typedef const typename Map::Value* ConstPointer;
524 template <typename Map>
525 struct ReferenceMapTraits<
527 typename enable_if<typename Map::FullTypeTag, void>::type
529 typedef typename Map::Value Value;
530 typedef typename Map::Reference Reference;
531 typedef typename Map::ConstReference ConstReference;
532 typedef typename Map::Pointer Pointer;
533 typedef typename Map::ConstPointer ConstPointer;
536 /// Provides an immutable and unique id for each item in the graph.
538 /// The IdMap class provides a unique and immutable id for each item of the
539 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
540 /// different items (nodes) get different ids <li>\b immutable: the id of an
541 /// item (node) does not change (even if you delete other nodes). </ul>
542 /// Through this map you get access (i.e. can read) the inner id values of
543 /// the items stored in the graph. This map can be inverted with its member
544 /// class \c InverseMap.
546 template <typename _Graph, typename _Item>
549 typedef _Graph Graph;
554 typedef True NeedCopy;
556 /// \brief Constructor.
558 /// Constructor for creating id map.
559 IdMap(const Graph& _graph) : graph(&_graph) {}
561 /// \brief Gives back the \e id of the item.
563 /// Gives back the immutable and unique \e id of the map.
564 int operator[](const Item& item) const { return graph->id(item);}
572 /// \brief The class represents the inverse of its owner (IdMap).
574 /// The class represents the inverse of its owner (IdMap).
579 typedef True NeedCopy;
581 /// \brief Constructor.
583 /// Constructor for creating an id-to-item map.
584 InverseMap(const Graph& _graph) : graph(&_graph) {}
586 /// \brief Constructor.
588 /// Constructor for creating an id-to-item map.
589 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
591 /// \brief Gives back the given item from its id.
593 /// Gives back the given item from its id.
595 Item operator[](int id) const { return graph->fromId(id, Item());}
600 /// \brief Gives back the inverse of the map.
602 /// Gives back the inverse of the IdMap.
603 InverseMap inverse() const { return InverseMap(*graph);}
608 /// \brief General invertable graph-map type.
610 /// This type provides simple invertable graph-maps.
611 /// The InvertableMap wraps an arbitrary ReadWriteMap
612 /// and if a key is set to a new value then store it
613 /// in the inverse map.
614 /// \param _Graph The graph type.
615 /// \param _Map The map to extend with invertable functionality.
621 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
623 class InvertableMap : protected _Map {
628 typedef _Graph Graph;
630 /// The key type of InvertableMap (Node, Edge, UndirEdge).
631 typedef typename _Map::Key Key;
632 /// The value type of the InvertableMap.
633 typedef typename _Map::Value Value;
635 /// \brief Constructor.
637 /// Construct a new InvertableMap for the graph.
639 InvertableMap(const Graph& graph) : Map(graph) {}
641 /// \brief The setter function of the map.
643 /// Sets the mapped value.
644 void set(const Key& key, const Value& val) {
645 Value oldval = Map::operator[](key);
646 typename Container::iterator it = invMap.find(oldval);
647 if (it != invMap.end() && it->second == key) {
650 invMap.insert(make_pair(val, key));
654 /// \brief The getter function of the map.
656 /// It gives back the value associated with the key.
657 const Value operator[](const Key& key) const {
658 return Map::operator[](key);
663 /// \brief Add a new key to the map.
665 /// Add a new key to the map. It is called by the
666 /// \c AlterationNotifier.
667 virtual void add(const Key& key) {
671 /// \brief Erase the key from the map.
673 /// Erase the key to the map. It is called by the
674 /// \c AlterationNotifier.
675 virtual void erase(const Key& key) {
676 Value val = Map::operator[](key);
677 typename Container::iterator it = invMap.find(val);
678 if (it != invMap.end() && it->second == key) {
684 /// \brief Clear the keys from the map and inverse map.
686 /// Clear the keys from the map and inverse map. It is called by the
687 /// \c AlterationNotifier.
688 virtual void clear() {
695 typedef std::map<Value, Key> Container;
700 /// \brief The inverse map type.
702 /// The inverse of this map. The subscript operator of the map
703 /// gives back always the item what was last assigned to the value.
706 /// \brief Constructor of the InverseMap.
708 /// Constructor of the InverseMap.
709 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
711 /// The value type of the InverseMap.
712 typedef typename InvertableMap::Key Value;
713 /// The key type of the InverseMap.
714 typedef typename InvertableMap::Value Key;
716 /// \brief Subscript operator.
718 /// Subscript operator. It gives back always the item
719 /// what was last assigned to the value.
720 Value operator[](const Key& key) const {
721 typename Container::const_iterator it = inverted.invMap.find(key);
726 const InvertableMap& inverted;
729 /// \brief It gives back the just readeable inverse map.
731 /// It gives back the just readeable inverse map.
732 InverseMap inverse() const {
733 return InverseMap(*this);
740 /// \brief Provides a mutable, continuous and unique descriptor for each
741 /// item in the graph.
743 /// The DescriptorMap class provides a unique and continuous (but mutable)
744 /// descriptor (id) for each item of the same type (e.g. node) in the
745 /// graph. This id is <ul><li>\b unique: different items (nodes) get
746 /// different ids <li>\b continuous: the range of the ids is the set of
747 /// integers between 0 and \c n-1, where \c n is the number of the items of
748 /// this type (e.g. nodes) (so the id of a node can change if you delete an
749 /// other node, i.e. this id is mutable). </ul> This map can be inverted
750 /// with its member class \c InverseMap.
752 /// \param _Graph The graph class the \c DescriptorMap belongs to.
753 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
755 /// \param _Map A ReadWriteMap mapping from the item type to integer.
760 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
762 class DescriptorMap : protected _Map {
768 /// The graph class of DescriptorMap.
769 typedef _Graph Graph;
771 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
772 typedef typename _Map::Key Key;
773 /// The value type of DescriptorMap.
774 typedef typename _Map::Value Value;
776 /// \brief Constructor.
778 /// Constructor for descriptor map.
779 DescriptorMap(const Graph& _graph) : Map(_graph) {
785 /// \brief Add a new key to the map.
787 /// Add a new key to the map. It is called by the
788 /// \c AlterationNotifier.
789 virtual void add(const Item& item) {
791 Map::set(item, invMap.size());
792 invMap.push_back(item);
795 /// \brief Erase the key from the map.
797 /// Erase the key to the map. It is called by the
798 /// \c AlterationNotifier.
799 virtual void erase(const Item& item) {
800 Map::set(invMap.back(), Map::operator[](item));
801 invMap[Map::operator[](item)] = invMap.back();
806 /// \brief Build the unique map.
808 /// Build the unique map. It is called by the
809 /// \c AlterationNotifier.
810 virtual void build() {
813 const typename Map::Graph* graph = Map::getGraph();
814 for (graph->first(it); it != INVALID; graph->next(it)) {
815 Map::set(it, invMap.size());
816 invMap.push_back(it);
820 /// \brief Clear the keys from the map.
822 /// Clear the keys from the map. It is called by the
823 /// \c AlterationNotifier.
824 virtual void clear() {
831 /// \brief Swaps the position of the two items in the map.
833 /// Swaps the position of the two items in the map.
834 void swap(const Item& p, const Item& q) {
835 int pi = Map::operator[](p);
836 int qi = Map::operator[](q);
843 /// \brief Gives back the \e descriptor of the item.
845 /// Gives back the mutable and unique \e descriptor of the map.
846 int operator[](const Item& item) const {
847 return Map::operator[](item);
852 typedef std::vector<Item> Container;
856 /// \brief The inverse map type of DescriptorMap.
858 /// The inverse map type of DescriptorMap.
861 /// \brief Constructor of the InverseMap.
863 /// Constructor of the InverseMap.
864 InverseMap(const DescriptorMap& _inverted)
865 : inverted(_inverted) {}
868 /// The value type of the InverseMap.
869 typedef typename DescriptorMap::Key Value;
870 /// The key type of the InverseMap.
871 typedef typename DescriptorMap::Value Key;
873 /// \brief Subscript operator.
875 /// Subscript operator. It gives back the item
876 /// that the descriptor belongs to currently.
877 Value operator[](const Key& key) const {
878 return inverted.invMap[key];
881 /// \brief Size of the map.
883 /// Returns the size of the map.
885 return inverted.invMap.size();
889 const DescriptorMap& inverted;
892 /// \brief Gives back the inverse of the map.
894 /// Gives back the inverse of the map.
895 const InverseMap inverse() const {
896 return InverseMap(*this);
900 /// \brief Returns the source of the given edge.
902 /// The SourceMap gives back the source Node of the given edge.
903 /// \author Balazs Dezso
904 template <typename Graph>
908 typedef True NeedCopy;
910 typedef typename Graph::Node Value;
911 typedef typename Graph::Edge Key;
913 /// \brief Constructor
916 /// \param _graph The graph that the map belongs to.
917 SourceMap(const Graph& _graph) : graph(_graph) {}
919 /// \brief The subscript operator.
921 /// The subscript operator.
922 /// \param edge The edge
923 /// \return The source of the edge
924 Value operator[](const Key& edge) const {
925 return graph.source(edge);
932 /// \brief Returns a \ref SourceMap class
934 /// This function just returns an \ref SourceMap class.
935 /// \relates SourceMap
936 template <typename Graph>
937 inline SourceMap<Graph> sourceMap(const Graph& graph) {
938 return SourceMap<Graph>(graph);
941 /// \brief Returns the target of the given edge.
943 /// The TargetMap gives back the target Node of the given edge.
944 /// \author Balazs Dezso
945 template <typename Graph>
949 typedef True NeedCopy;
951 typedef typename Graph::Node Value;
952 typedef typename Graph::Edge Key;
954 /// \brief Constructor
957 /// \param _graph The graph that the map belongs to.
958 TargetMap(const Graph& _graph) : graph(_graph) {}
960 /// \brief The subscript operator.
962 /// The subscript operator.
963 /// \param e The edge
964 /// \return The target of the edge
965 Value operator[](const Key& e) const {
966 return graph.target(e);
973 /// \brief Returns a \ref TargetMap class
975 /// This function just returns a \ref TargetMap class.
976 /// \relates TargetMap
977 template <typename Graph>
978 inline TargetMap<Graph> targetMap(const Graph& graph) {
979 return TargetMap<Graph>(graph);
982 /// \brief Returns the "forward" directed edge view of an undirected edge.
984 /// Returns the "forward" directed edge view of an undirected edge.
985 /// \author Balazs Dezso
986 template <typename Graph>
990 typedef True NeedCopy;
992 typedef typename Graph::Edge Value;
993 typedef typename Graph::UndirEdge Key;
995 /// \brief Constructor
998 /// \param _graph The graph that the map belongs to.
999 ForwardMap(const Graph& _graph) : graph(_graph) {}
1001 /// \brief The subscript operator.
1003 /// The subscript operator.
1004 /// \param key An undirected edge
1005 /// \return The "forward" directed edge view of undirected edge
1006 Value operator[](const Key& key) const {
1007 return graph.direct(key, true);
1014 /// \brief Returns a \ref ForwardMap class
1016 /// This function just returns an \ref ForwardMap class.
1017 /// \relates ForwardMap
1018 template <typename Graph>
1019 inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1020 return ForwardMap<Graph>(graph);
1023 /// \brief Returns the "backward" directed edge view of an undirected edge.
1025 /// Returns the "backward" directed edge view of an undirected edge.
1026 /// \author Balazs Dezso
1027 template <typename Graph>
1030 typedef True NeedCopy;
1032 typedef typename Graph::Edge Value;
1033 typedef typename Graph::UndirEdge Key;
1035 /// \brief Constructor
1038 /// \param _graph The graph that the map belongs to.
1039 BackwardMap(const Graph& _graph) : graph(_graph) {}
1041 /// \brief The subscript operator.
1043 /// The subscript operator.
1044 /// \param key An undirected edge
1045 /// \return The "backward" directed edge view of undirected edge
1046 Value operator[](const Key& key) const {
1047 return graph.direct(key, false);
1054 /// \brief Returns a \ref BackwardMap class
1056 /// This function just returns a \ref BackwardMap class.
1057 /// \relates BackwardMap
1058 template <typename Graph>
1059 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1060 return BackwardMap<Graph>(graph);
1063 template <typename _Graph>
1067 typedef _Graph Graph;
1071 typedef typename Graph::template NodeMap<int> IntNodeMap;
1075 /// \brief Map of the node in-degrees.
1077 /// This map returns the in-degree of a node. Once it is constructed,
1078 /// the degrees are stored in a standard NodeMap, so each query is done
1079 /// in constant time. On the other hand, the values are updated automatically
1080 /// whenever the graph changes.
1082 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1083 /// alternative ways to mogify the graph. The correct behavior of InDegMap
1084 /// is not guarantied if these additional featureas are used. For example
1085 /// the funstions \ref ListGraph::changeSource() "changeSource()",
1086 /// \ref ListGraph::changeTarget() "changeTarget()" and
1087 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1088 /// of \ref ListGraph will \e not update the degree values correctly.
1092 template <typename _Graph>
1094 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1098 typedef _Graph Graph;
1100 typedef typename Graph::Node Key;
1104 class AutoNodeMap : public Graph::template NodeMap<int> {
1107 typedef typename Graph::template NodeMap<int> Parent;
1109 typedef typename Parent::Key Key;
1110 typedef typename Parent::Value Value;
1112 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1114 void add(const Key& key) {
1116 Parent::set(key, 0);
1122 /// \brief Constructor.
1124 /// Constructor for creating in-degree map.
1125 InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1126 AlterationNotifier<typename _Graph::Edge>
1127 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1129 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1130 deg[it] = countInEdges(graph, it);
1134 virtual ~InDegMap() {
1135 AlterationNotifier<typename _Graph::Edge>::
1136 ObserverBase::detach();
1139 /// Gives back the in-degree of a Node.
1140 int operator[](const Key& key) const {
1146 typedef typename Graph::Edge Edge;
1148 virtual void add(const Edge& edge) {
1149 ++deg[graph.target(edge)];
1152 virtual void erase(const Edge& edge) {
1153 --deg[graph.target(edge)];
1157 virtual void build() {
1158 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1159 deg[it] = countInEdges(graph, it);
1163 virtual void clear() {
1164 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1170 const _Graph& graph;
1174 /// \brief Map of the node out-degrees.
1176 /// This map returns the out-degree of a node. Once it is constructed,
1177 /// the degrees are stored in a standard NodeMap, so each query is done
1178 /// in constant time. On the other hand, the values are updated automatically
1179 /// whenever the graph changes.
1181 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1182 /// alternative ways to mogify the graph. The correct behavior of OutDegMap
1183 /// is not guarantied if these additional featureas are used. For example
1184 /// the funstions \ref ListGraph::changeSource() "changeSource()",
1185 /// \ref ListGraph::changeTarget() "changeTarget()" and
1186 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1187 /// of \ref ListGraph will \e not update the degree values correctly.
1191 template <typename _Graph>
1193 : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1197 typedef _Graph Graph;
1199 typedef typename Graph::Node Key;
1203 class AutoNodeMap : public Graph::template NodeMap<int> {
1206 typedef typename Graph::template NodeMap<int> Parent;
1208 typedef typename Parent::Key Key;
1209 typedef typename Parent::Value Value;
1211 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1213 void add(const Key& key) {
1215 Parent::set(key, 0);
1221 /// \brief Constructor.
1223 /// Constructor for creating out-degree map.
1224 OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1225 AlterationNotifier<typename _Graph::Edge>
1226 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1228 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1229 deg[it] = countOutEdges(graph, it);
1233 virtual ~OutDegMap() {
1234 AlterationNotifier<typename _Graph::Edge>::
1235 ObserverBase::detach();
1238 /// Gives back the in-degree of a Node.
1239 int operator[](const Key& key) const {
1245 typedef typename Graph::Edge Edge;
1247 virtual void add(const Edge& edge) {
1248 ++deg[graph.source(edge)];
1251 virtual void erase(const Edge& edge) {
1252 --deg[graph.source(edge)];
1256 virtual void build() {
1257 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1258 deg[it] = countOutEdges(graph, it);
1262 virtual void clear() {
1263 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1269 const _Graph& graph;
1275 } //END OF NAMESPACE LEMON