equal
deleted
inserted
replaced
31 |
31 |
32 #include <lemon/bits/invalid.h> |
32 #include <lemon/bits/invalid.h> |
33 |
33 |
34 namespace lemon { |
34 namespace lemon { |
35 |
35 |
36 //! \addtogroup auxdat |
36 /// \ingroup auxdat |
37 //! @{ |
37 /// |
38 |
|
39 /// \brief A \e Union-Find data structure implementation |
38 /// \brief A \e Union-Find data structure implementation |
40 /// |
39 /// |
41 /// The class implements the \e Union-Find data structure. |
40 /// The class implements the \e Union-Find data structure. |
42 /// The union operation uses rank heuristic, while |
41 /// The union operation uses rank heuristic, while |
43 /// the find operation uses path compression. |
42 /// the find operation uses path compression. |
49 /// cost spanning tree in a graph. |
48 /// cost spanning tree in a graph. |
50 /// \sa kruskal() |
49 /// \sa kruskal() |
51 /// |
50 /// |
52 /// \pre You need to add all the elements by the \ref insert() |
51 /// \pre You need to add all the elements by the \ref insert() |
53 /// method. |
52 /// method. |
54 template <typename Item, typename ItemIntMap> |
53 template <typename _ItemIntMap> |
55 class UnionFind { |
54 class UnionFind { |
56 |
|
57 public: |
55 public: |
58 typedef Item ElementType; |
56 |
|
57 typedef _ItemIntMap ItemIntMap; |
|
58 typedef typename ItemIntMap::Key Item; |
59 |
59 |
60 private: |
60 private: |
61 // If the items vector stores negative value for an item then |
61 // If the items vector stores negative value for an item then |
62 // that item is root item and it has -items[it] component size. |
62 // that item is root item and it has -items[it] component size. |
63 // Else the items[it] contains the index of the parent. |
63 // Else the items[it] contains the index of the parent. |
144 return - items[k]; |
144 return - items[k]; |
145 } |
145 } |
146 |
146 |
147 }; |
147 }; |
148 |
148 |
149 |
149 /// \ingroup auxdat |
|
150 /// |
150 /// \brief A \e Union-Find data structure implementation which |
151 /// \brief A \e Union-Find data structure implementation which |
151 /// is able to enumerate the components. |
152 /// is able to enumerate the components. |
152 /// |
153 /// |
153 /// The class implements a \e Union-Find data structure |
154 /// The class implements a \e Union-Find data structure |
154 /// which is able to enumerate the components and the items in |
155 /// which is able to enumerate the components and the items in |
159 /// the find operation uses path compression. |
160 /// the find operation uses path compression. |
160 /// |
161 /// |
161 /// \pre You need to add all the elements by the \ref insert() |
162 /// \pre You need to add all the elements by the \ref insert() |
162 /// method. |
163 /// method. |
163 /// |
164 /// |
164 template <typename _Item, typename _ItemIntMap> |
165 template <typename _ItemIntMap> |
165 class UnionFindEnum { |
166 class UnionFindEnum { |
166 public: |
167 public: |
167 |
168 |
168 typedef _Item Item; |
|
169 typedef _ItemIntMap ItemIntMap; |
169 typedef _ItemIntMap ItemIntMap; |
170 |
170 typedef typename ItemIntMap::Key Item; |
|
171 |
171 private: |
172 private: |
172 |
173 |
173 // If the parent stores negative value for an item then that item |
174 // If the parent stores negative value for an item then that item |
174 // is root item and it has -items[it].parent component size. Else |
175 // is root item and it has -items[it].parent component size. Else |
175 // the items[it].parent contains the index of the parent. |
176 // the items[it].parent contains the index of the parent. |