Some bug fix.
Added: Concept check for maps and IdReader/Writer classes
Some runtime check
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 structure 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 structure 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 edges in the graph.
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).
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 /// Finds an edge between two nodes of a graph.
148 /// Finds an edge from node \c u to node \c v in graph \c g.
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.
155 /// Thus you can iterate through each edge from \c u to \c v as it follows.
157 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
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)
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);
173 while(e!=INVALID && g.target(e)!=v) ++e;
179 ///\todo Please document.
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);
188 ///\todo Please document.
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);
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();
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)]);
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);
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>
242 typedef _DestinationGraph DestinationGraph;
243 typedef _SourceGraph SourceGraph;
245 typedef _NodeBijection NodeBijection;
246 typedef _EdgeBijection EdgeBijection;
250 NodeBijection node_bijection;
251 EdgeBijection edge_bijection;
255 GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
256 copyGraph(_d, _s, node_bijection, edge_bijection);
259 const NodeBijection& getNodeBijection() const {
260 return node_bijection;
263 const EdgeBijection& getEdgeBijection() const {
264 return edge_bijection;
270 template <typename _Graph, typename _Item>
271 class ItemSetTraits {};
273 template <typename _Graph>
274 class ItemSetTraits<_Graph, typename _Graph::Node> {
277 typedef _Graph Graph;
279 typedef typename Graph::Node Item;
280 typedef typename Graph::NodeIt ItemIt;
282 template <typename _Value>
283 class Map : public Graph::template NodeMap<_Value> {
285 typedef typename Graph::template NodeMap<_Value> Parent;
286 typedef typename Parent::Value Value;
288 Map(const Graph& _graph) : Parent(_graph) {}
289 Map(const Graph& _graph, const Value& _value)
290 : Parent(_graph, _value) {}
295 template <typename _Graph>
296 class ItemSetTraits<_Graph, typename _Graph::Edge> {
299 typedef _Graph Graph;
301 typedef typename Graph::Edge Item;
302 typedef typename Graph::EdgeIt ItemIt;
304 template <typename _Value>
305 class Map : public Graph::template EdgeMap<_Value> {
307 typedef typename Graph::template EdgeMap<_Value> Parent;
308 typedef typename Parent::Value Value;
310 Map(const Graph& _graph) : Parent(_graph) {}
311 Map(const Graph& _graph, const Value& _value)
312 : Parent(_graph, _value) {}
317 template <typename _Graph>
318 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
321 typedef _Graph Graph;
323 typedef typename Graph::UndirEdge Item;
324 typedef typename Graph::UndirEdgeIt ItemIt;
326 template <typename _Value>
327 class Map : public Graph::template UndirEdgeMap<_Value> {
329 typedef typename Graph::template UndirEdgeMap<_Value> Parent;
330 typedef typename Parent::Value Value;
332 Map(const Graph& _graph) : Parent(_graph) {}
333 Map(const Graph& _graph, const Value& _value)
334 : Parent(_graph, _value) {}
341 /// \addtogroup graph_maps
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;
353 template <typename Map>
354 struct ReferenceMapTraits<
356 typename enable_if<typename Map::FullTypeTag, void>::type
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;
365 /// Provides an immutable and unique id for each item in the graph.
367 /// The IdMap class provides an unique and immutable mapping for each item
370 template <typename _Graph, typename _Item>
373 typedef _Graph Graph;
378 typedef True NeedCopy;
380 /// \brief Constructor.
382 /// Constructor for creating id map.
383 IdMap(const Graph& _graph) : graph(&_graph) {}
385 /// \brief Gives back the \e id of the item.
387 /// Gives back the immutable and unique \e id of the map.
388 int operator[](const Item& item) const { return graph->id(item);}
396 /// \brief The class represents the inverse of the map.
398 /// The class represents the inverse of the map.
403 typedef True NeedCopy;
405 /// \brief Constructor.
407 /// Constructor for creating an id-to-item map.
408 InverseMap(const Graph& _graph) : graph(&_graph) {}
410 /// \brief Constructor.
412 /// Constructor for creating an id-to-item map.
413 InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
415 /// \brief Gives back the given item from its id.
417 /// Gives back the given item from its id.
419 Item operator[](int id) const { return graph->fromId(id, Item());}
424 /// \brief Gives back the inverse of the map.
426 /// Gives back the inverse of the map.
427 InverseMap inverse() const { return InverseMap(*graph);}
432 /// \brief General inversable graph-map type.
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.
445 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
447 class InvertableMap : protected _Map {
452 typedef _Graph Graph;
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;
459 /// \brief Constructor.
461 /// Construct a new InvertableMap for the graph.
463 InvertableMap(const Graph& graph) : Map(graph) {}
465 /// \brief The setter function of the map.
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) {
474 invMap.insert(make_pair(val, key));
478 /// \brief The getter function of the map.
480 /// It gives back the value associated with the key.
481 const Value operator[](const Key& key) const {
482 return Map::operator[](key);
485 /// \brief Add a new key to the map.
487 /// Add a new key to the map. It is called by the
488 /// \c AlterationNotifier.
489 virtual void add(const Key& key) {
493 /// \brief Erase the key from the map.
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) {
506 /// \brief Clear the keys from the map and inverse map.
508 /// Clear the keys from the map and inverse map. It is called by the
509 /// \c AlterationNotifier.
510 virtual void clear() {
517 typedef std::map<Value, Key> Container;
522 /// \brief The inverse map type.
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.
528 /// \brief Constructor of the InverseMap.
530 /// Constructor of the InverseMap.
531 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
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;
538 /// \brief Subscript operator.
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);
548 const InvertableMap& inverted;
551 /// \brief It gives back the just readeable inverse map.
553 /// It gives back the just readeable inverse map.
554 InverseMap inverse() const {
555 return InverseMap(*this);
562 /// \brief Provides a mutable, continuous and unique descriptor for each
563 /// item in the graph.
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.
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
572 /// \param _Map A ReadWriteMap mapping from the item type to integer.
577 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
579 class DescriptorMap : protected _Map {
585 /// The graph class of DescriptorMap.
586 typedef _Graph Graph;
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;
593 /// \brief Constructor.
595 /// Constructor for descriptor map.
596 DescriptorMap(const Graph& _graph) : Map(_graph) {
600 /// \brief Add a new key to the map.
602 /// Add a new key to the map. It is called by the
603 /// \c AlterationNotifier.
604 virtual void add(const Item& item) {
606 Map::set(item, invMap.size());
607 invMap.push_back(item);
610 /// \brief Erase the key from the map.
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();
621 /// \brief Build the unique map.
623 /// Build the unique map. It is called by the
624 /// \c AlterationNotifier.
625 virtual void build() {
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);
635 /// \brief Clear the keys from the map.
637 /// Clear the keys from the map. It is called by the
638 /// \c AlterationNotifier.
639 virtual void clear() {
644 /// \brief Gives back the \e descriptor of the item.
646 /// Gives back the mutable and unique \e descriptor of the map.
647 int operator[](const Item& item) const {
648 return Map::operator[](item);
653 typedef std::vector<Item> Container;
657 /// \brief The inverse map type.
659 /// The inverse map type.
662 /// \brief Constructor of the InverseMap.
664 /// Constructor of the InverseMap.
665 InverseMap(const DescriptorMap& _inverted)
666 : inverted(_inverted) {}
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;
674 /// \brief Subscript operator.
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];
682 /// \brief Size of the map.
684 /// Returns the size of the map.
685 unsigned size() const {
686 return inverted.invMap.size();
690 const DescriptorMap& inverted;
693 /// \brief Gives back the inverse of the map.
695 /// Gives back the inverse of the map.
696 const InverseMap inverse() const {
697 return InverseMap(*this);
701 /// \brief Returns the source of the given edge.
703 /// The SourceMap gives back the source Node of the given edge.
704 /// \author Balazs Dezso
705 template <typename Graph>
709 typedef True NeedCopy;
711 typedef typename Graph::Node Value;
712 typedef typename Graph::Edge Key;
714 /// \brief Constructor
717 /// \param _graph The graph that the map belongs to.
718 SourceMap(const Graph& _graph) : graph(_graph) {}
720 /// \brief The subscript operator.
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);
733 /// \brief Returns a \ref SourceMap class
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);
742 /// \brief Returns the target of the given edge.
744 /// The TargetMap gives back the target Node of the given edge.
745 /// \author Balazs Dezso
746 template <typename Graph>
750 typedef True NeedCopy;
752 typedef typename Graph::Node Value;
753 typedef typename Graph::Edge Key;
755 /// \brief Constructor
758 /// \param _graph The graph that the map belongs to.
759 TargetMap(const Graph& _graph) : graph(_graph) {}
761 /// \brief The subscript operator.
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);
774 /// \brief Returns a \ref TargetMap class
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);
783 /// \brief Returns the "forward" directed edge view of undirected edge.
785 /// Returns the "forward" directed edge view of undirected edge.
786 /// \author Balazs Dezso
787 template <typename Graph>
791 typedef True NeedCopy;
793 typedef typename Graph::Edge Value;
794 typedef typename Graph::UndirEdge Key;
796 /// \brief Constructor
799 /// \param _graph The graph that the map belongs to.
800 ForwardMap(const Graph& _graph) : graph(_graph) {}
802 /// \brief The subscript operator.
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));
815 /// \brief Returns a \ref ForwardMap class
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);
824 /// \brief Returns the "backward" directed edge view of undirected edge.
826 /// Returns the "backward" directed edge view of undirected edge.
827 /// \author Balazs Dezso
828 template <typename Graph>
831 typedef True NeedCopy;
833 typedef typename Graph::Edge Value;
834 typedef typename Graph::UndirEdge Key;
836 /// \brief Constructor
839 /// \param _graph The graph that the map belongs to.
840 BackwardMap(const Graph& _graph) : graph(_graph) {}
842 /// \brief The subscript operator.
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));
855 /// \brief Returns a \ref BackwardMap class
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);
866 /// Map of the node in-degrees.
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.
874 template <typename _Graph>
876 protected _Graph::template NodeMap<int>,
877 protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
882 typedef typename _Graph::Node Key;
884 /// \brief Constructor.
886 /// Constructor for creating in-degree map.
887 InDegMap(const _Graph& _graph) :
888 _Graph::template NodeMap<int>(_graph,0),
891 AlterationNotifier<typename _Graph::Edge>
892 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
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))++;
901 AlterationNotifier<typename _Graph::Edge>::
902 ObserverBase::detach();
905 /// Gives back the in-degree of a Node.
906 int operator[](const Key& k) const {
907 return _Graph::template NodeMap<int>::operator[](k);
911 virtual void add(const typename _Graph::Node& n) {
912 _Graph::template NodeMap<int>::add(n);
913 _Graph::template NodeMap<int>::operator[](n)=0;
915 virtual void erase(const typename _Graph::Node&n)
917 _Graph::template NodeMap<int>::erase(n);
919 virtual void add(const typename _Graph::Edge& e) {
920 _Graph::template NodeMap<int>::operator[](graph.target(e))++;
922 virtual void erase(const typename _Graph::Edge& e) {
923 _Graph::template NodeMap<int>::operator[](graph.target(e))--;
926 virtual void build() {}
927 virtual void clear() {}
932 /// Map of the node out-degrees.
934 ///This map returns the out-degree of a node. One it is constructed,
935 ///the degrees are stored in a standard NodeMap, so each query is done
936 ///in constant time. On the other hand, the values updates automatically
937 ///whenever the graph changes.
940 template <typename _Graph>
942 protected _Graph::template NodeMap<int>,
943 protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
948 typedef typename _Graph::Node Key;
950 /// \brief Constructor.
952 /// Constructor for creating out-degree map.
953 OutDegMap(const _Graph& _graph) :
954 _Graph::template NodeMap<int>(_graph,0),
957 AlterationNotifier<typename _Graph::Edge>
958 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
960 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
961 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
962 _Graph::template NodeMap<int>::operator[](graph.source(e))++;
967 AlterationNotifier<typename _Graph::Edge>::
968 ObserverBase::detach();
971 /// Gives back the in-degree of a Node.
972 int operator[](const Key& k) const {
973 return _Graph::template NodeMap<int>::operator[](k);
977 virtual void add(const typename _Graph::Node& n) {
978 _Graph::template NodeMap<int>::add(n);
979 _Graph::template NodeMap<int>::operator[](n)=0;
981 virtual void erase(const typename _Graph::Node&n)
983 _Graph::template NodeMap<int>::erase(n);
985 virtual void add(const typename _Graph::Edge& e) {
986 _Graph::template NodeMap<int>::operator[](graph.source(e))++;
988 virtual void erase(const typename _Graph::Edge& e) {
989 _Graph::template NodeMap<int>::operator[](graph.source(e))--;
992 virtual void build() {}
993 virtual void clear() {}
1002 } //END OF NAMESPACE LEMON