28 |
28 |
29 ///\ingroup gutils |
29 ///\ingroup gutils |
30 ///\file |
30 ///\file |
31 ///\brief Graph utilities. |
31 ///\brief Graph utilities. |
32 /// |
32 /// |
33 ///\todo Please |
|
34 ///revise the documentation. |
|
35 /// |
33 /// |
36 |
34 |
37 |
35 |
38 namespace lemon { |
36 namespace lemon { |
39 |
37 |
40 /// \addtogroup gutils |
38 /// \addtogroup gutils |
41 /// @{ |
39 /// @{ |
42 |
40 |
43 /// \brief Function to count the items in the graph. |
41 /// \brief Function to count the items in the graph. |
44 /// |
42 /// |
45 /// This function counts the items in the graph. |
43 /// This function counts the items (nodes, edges etc) in the graph. |
46 /// The complexity of the function is O(n) because |
44 /// The complexity of the function is O(n) because |
47 /// it iterates on all of the items. |
45 /// it iterates on all of the items. |
48 |
46 |
49 template <typename Graph, typename ItemIt> |
47 template <typename Graph, typename ItemIt> |
50 inline int countItems(const Graph& g) { |
48 inline int countItems(const Graph& g) { |
123 |
121 |
124 /// \brief Function to count the undirected edges in the graph. |
122 /// \brief Function to count the undirected edges in the graph. |
125 /// |
123 /// |
126 /// This function counts the undirected edges in the graph. |
124 /// This function counts the undirected edges in the graph. |
127 /// The complexity of the function is O(e) but for some |
125 /// The complexity of the function is O(e) but for some |
128 /// graph structure it is specialized to run in O(1). |
126 /// graph structures it is specialized to run in O(1). |
129 |
127 |
130 template <typename Graph> |
128 template <typename Graph> |
131 inline int countUndirEdges(const Graph& g) { |
129 inline int countUndirEdges(const Graph& g) { |
132 return _countUndirEdges<Graph>(g); |
130 return _countUndirEdges<Graph>(g); |
133 } |
131 } |
191 else ++e; |
189 else ++e; |
192 while(e!=INVALID && g.target(e)!=v) ++e; |
190 while(e!=INVALID && g.target(e)!=v) ++e; |
193 return e; |
191 return e; |
194 } |
192 } |
195 |
193 |
196 /// \brief Copy the source map to the target map. |
194 /// \brief Copy a map. |
197 /// |
195 /// |
198 /// Copy the \c source map to the \c target map. It uses the given iterator |
196 /// Thsi function copies the \c source map to the \c target map. It uses the |
199 /// to iterate on the data structure and it use the \c ref mapping to |
197 /// given iterator to iterate on the data structure and it uses the \c ref |
200 /// convert the source's keys to the target's keys. |
198 /// mapping to convert the source's keys to the target's keys. |
201 template <typename Target, typename Source, |
199 template <typename Target, typename Source, |
202 typename ItemIt, typename Ref> |
200 typename ItemIt, typename Ref> |
203 void copyMap(Target& target, const Source& source, |
201 void copyMap(Target& target, const Source& source, |
204 ItemIt it, const Ref& ref) { |
202 ItemIt it, const Ref& ref) { |
205 for (; it != INVALID; ++it) { |
203 for (; it != INVALID; ++it) { |
218 target[it] = source[it]; |
216 target[it] = source[it]; |
219 } |
217 } |
220 } |
218 } |
221 |
219 |
222 |
220 |
223 /// \brief Class to copy a graph to an other graph. |
221 /// \brief Class to copy a graph. |
224 /// |
222 /// |
225 /// Class to copy a graph to an other graph. It can be used easier |
223 /// Class to copy a graph to an other graph (duplicate a graph). The |
226 /// with the \c copyGraph() function. |
224 /// simplest way of using it is through the \c copyGraph() function. |
227 template <typename Target, typename Source> |
225 template <typename Target, typename Source> |
228 class GraphCopy { |
226 class GraphCopy { |
229 public: |
227 public: |
230 typedef typename Source::Node Node; |
228 typedef typename Source::Node Node; |
231 typedef typename Source::NodeIt NodeIt; |
229 typedef typename Source::NodeIt NodeIt; |
352 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); |
350 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); |
353 /// \endcode |
351 /// \endcode |
354 /// |
352 /// |
355 /// After the copy the \c nr map will contain the mapping from the |
353 /// 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 |
354 /// 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 |
355 /// contain the mapping from the target graph's edges to the source's |
358 /// edges. |
356 /// edges. |
359 template <typename Target, typename Source> |
357 template <typename Target, typename Source> |
360 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) { |
358 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) { |
361 return GraphCopy<Target, Source>(target, source); |
359 return GraphCopy<Target, Source>(target, source); |
362 } |
360 } |
456 typedef typename Map::ConstPointer ConstPointer; |
454 typedef typename Map::ConstPointer ConstPointer; |
457 }; |
455 }; |
458 |
456 |
459 /// Provides an immutable and unique id for each item in the graph. |
457 /// Provides an immutable and unique id for each item in the graph. |
460 |
458 |
461 /// The IdMap class provides a unique and immutable mapping for each item |
459 /// The IdMap class provides a unique and immutable id for each item of the |
462 /// in the graph. |
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. |
463 /// |
466 /// |
464 template <typename _Graph, typename _Item> |
467 template <typename _Graph, typename _Item> |
465 class IdMap { |
468 class IdMap { |
466 public: |
469 public: |
467 typedef _Graph Graph; |
470 typedef _Graph Graph; |
515 const Graph* graph; |
518 const Graph* graph; |
516 }; |
519 }; |
517 |
520 |
518 /// \brief Gives back the inverse of the map. |
521 /// \brief Gives back the inverse of the map. |
519 /// |
522 /// |
520 /// Gives back the inverse of the map. |
523 /// Gives back the inverse of the IdMap. |
521 InverseMap inverse() const { return InverseMap(*graph);} |
524 InverseMap inverse() const { return InverseMap(*graph);} |
522 |
525 |
523 }; |
526 }; |
524 |
527 |
525 |
528 |
526 /// \brief General invertable graph-map type. |
529 /// \brief General invertable graph-map type. |
527 |
530 |
528 /// This type provides simple invertable map functions. |
531 /// This type provides simple invertable graph-maps. |
529 /// The InvertableMap wraps an arbitrary ReadWriteMap |
532 /// The InvertableMap wraps an arbitrary ReadWriteMap |
530 /// and if a key is set to a new value then store it |
533 /// and if a key is set to a new value then store it |
531 /// in the inverse map. |
534 /// in the inverse map. |
532 /// \param _Graph The graph type. |
535 /// \param _Graph The graph type. |
533 /// \param _Map The map to extend with invertable functionality. |
536 /// \param _Map The map to extend with invertable functionality. |
656 }; |
659 }; |
657 |
660 |
658 /// \brief Provides a mutable, continuous and unique descriptor for each |
661 /// \brief Provides a mutable, continuous and unique descriptor for each |
659 /// item in the graph. |
662 /// item in the graph. |
660 /// |
663 /// |
661 /// The DescriptorMap class provides a mutable, continuous and immutable |
664 /// The DescriptorMap class provides a unique and continuous (but mutable) |
662 /// mapping for each item in the graph. The value for an item may mutated |
665 /// descriptor (id) for each item of the same type (e.g. node) in the |
663 /// on each operation when the an item erased or added to graph. |
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. |
664 /// |
672 /// |
665 /// \param _Graph The graph class the \c DescriptorMap belongs to. |
673 /// \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 |
674 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or |
667 /// UndirEdge. |
675 /// UndirEdge. |
668 /// \param _Map A ReadWriteMap mapping from the item type to integer. |
676 /// \param _Map A ReadWriteMap mapping from the item type to integer. |
752 |
760 |
753 typedef std::vector<Item> Container; |
761 typedef std::vector<Item> Container; |
754 Container invMap; |
762 Container invMap; |
755 |
763 |
756 public: |
764 public: |
757 /// \brief The inverse map type. |
765 /// \brief The inverse map type of DescriptorMap. |
758 /// |
766 /// |
759 /// The inverse map type. |
767 /// The inverse map type of DescriptorMap. |
760 class InverseMap { |
768 class InverseMap { |
761 public: |
769 public: |
762 /// \brief Constructor of the InverseMap. |
770 /// \brief Constructor of the InverseMap. |
763 /// |
771 /// |
764 /// Constructor of the InverseMap. |
772 /// Constructor of the InverseMap. |
871 const Graph& graph; |
879 const Graph& graph; |
872 }; |
880 }; |
873 |
881 |
874 /// \brief Returns a \ref TargetMap class |
882 /// \brief Returns a \ref TargetMap class |
875 /// |
883 /// |
876 /// This function just returns an \ref TargetMap class. |
884 /// This function just returns a \ref TargetMap class. |
877 /// \relates TargetMap |
885 /// \relates TargetMap |
878 template <typename Graph> |
886 template <typename Graph> |
879 inline TargetMap<Graph> targetMap(const Graph& graph) { |
887 inline TargetMap<Graph> targetMap(const Graph& graph) { |
880 return TargetMap<Graph>(graph); |
888 return TargetMap<Graph>(graph); |
881 } |
889 } |
882 |
890 |
883 /// \brief Returns the "forward" directed edge view of undirected edge. |
891 /// \brief Returns the "forward" directed edge view of an undirected edge. |
884 /// |
892 /// |
885 /// Returns the "forward" directed edge view of undirected edge. |
893 /// Returns the "forward" directed edge view of an undirected edge. |
886 /// \author Balazs Dezso |
894 /// \author Balazs Dezso |
887 template <typename Graph> |
895 template <typename Graph> |
888 class ForwardMap { |
896 class ForwardMap { |
889 public: |
897 public: |
890 |
898 |
919 template <typename Graph> |
927 template <typename Graph> |
920 inline ForwardMap<Graph> forwardMap(const Graph& graph) { |
928 inline ForwardMap<Graph> forwardMap(const Graph& graph) { |
921 return ForwardMap<Graph>(graph); |
929 return ForwardMap<Graph>(graph); |
922 } |
930 } |
923 |
931 |
924 /// \brief Returns the "backward" directed edge view of undirected edge. |
932 /// \brief Returns the "backward" directed edge view of an undirected edge. |
925 /// |
933 /// |
926 /// Returns the "backward" directed edge view of undirected edge. |
934 /// Returns the "backward" directed edge view of an undirected edge. |
927 /// \author Balazs Dezso |
935 /// \author Balazs Dezso |
928 template <typename Graph> |
936 template <typename Graph> |
929 class BackwardMap { |
937 class BackwardMap { |
930 public: |
938 public: |
931 typedef True NeedCopy; |
939 typedef True NeedCopy; |
952 const Graph& graph; |
960 const Graph& graph; |
953 }; |
961 }; |
954 |
962 |
955 /// \brief Returns a \ref BackwardMap class |
963 /// \brief Returns a \ref BackwardMap class |
956 |
964 |
957 /// This function just returns an \ref BackwardMap class. |
965 /// This function just returns a \ref BackwardMap class. |
958 /// \relates BackwardMap |
966 /// \relates BackwardMap |
959 template <typename Graph> |
967 template <typename Graph> |
960 inline BackwardMap<Graph> backwardMap(const Graph& graph) { |
968 inline BackwardMap<Graph> backwardMap(const Graph& graph) { |
961 return BackwardMap<Graph>(graph); |
969 return BackwardMap<Graph>(graph); |
962 } |
970 } |
973 |
981 |
974 }; |
982 }; |
975 |
983 |
976 /// \brief Map of the node in-degrees. |
984 /// \brief Map of the node in-degrees. |
977 /// |
985 /// |
978 /// This map returns the in-degree of a node. Ones it is constructed, |
986 /// This map returns the in-degree of a node. Once it is constructed, |
979 /// the degrees are stored in a standard NodeMap, so each query is done |
987 /// the degrees are stored in a standard NodeMap, so each query is done |
980 /// in constant time. On the other hand, the values updates automatically |
988 /// in constant time. On the other hand, the values are updated automatically |
981 /// whenever the graph changes. |
989 /// whenever the graph changes. |
982 /// |
990 /// |
983 /// \sa OutDegMap |
991 /// \sa OutDegMap |
984 |
992 |
985 template <typename _Graph> |
993 template <typename _Graph> |
1065 }; |
1073 }; |
1066 |
1074 |
1067 |
1075 |
1068 /// \brief Map of the node out-degrees. |
1076 /// \brief Map of the node out-degrees. |
1069 /// |
1077 /// |
1070 /// This map returns the out-degree of a node. One it is constructed, |
1078 /// This map returns the out-degree of a node. Once it is constructed, |
1071 /// the degrees are stored in a standard NodeMap, so each query is done |
1079 /// the degrees are stored in a standard NodeMap, so each query is done |
1072 /// in constant time. On the other hand, the values updates automatically |
1080 /// in constant time. On the other hand, the values are updated automatically |
1073 /// whenever the graph changes. |
1081 /// whenever the graph changes. |
1074 /// |
1082 /// |
1075 /// \sa OutDegMap |
1083 /// \sa OutDegMap |
1076 |
1084 |
1077 template <typename _Graph> |
1085 template <typename _Graph> |