equal
deleted
inserted
replaced
22 #include <algorithm> |
22 #include <algorithm> |
23 #include <vector> |
23 #include <vector> |
24 #include <lemon/unionfind.h> |
24 #include <lemon/unionfind.h> |
25 #include <lemon/bits/utility.h> |
25 #include <lemon/bits/utility.h> |
26 #include <lemon/bits/traits.h> |
26 #include <lemon/bits/traits.h> |
27 #include <lemon/time_measure.h> |
|
28 #include <iostream> |
|
29 |
27 |
30 ///\ingroup spantree |
28 ///\ingroup spantree |
31 ///\file |
29 ///\file |
32 ///\brief Kruskal's algorithm to compute a minimum cost tree |
30 ///\brief Kruskal's algorithm to compute a minimum cost tree |
33 /// |
31 /// |
117 { |
115 { |
118 typedef typename IN::value_type::second_type EdgeCost; |
116 typedef typename IN::value_type::second_type EdgeCost; |
119 typedef typename GR::template NodeMap<int> NodeIntMap; |
117 typedef typename GR::template NodeMap<int> NodeIntMap; |
120 typedef typename GR::Node Node; |
118 typedef typename GR::Node Node; |
121 |
119 |
122 Timer timer; |
|
123 NodeIntMap comp(g); |
120 NodeIntMap comp(g); |
124 UnionFind<Node,NodeIntMap> uf(comp); |
121 UnionFind<Node,NodeIntMap> uf(comp); |
125 for (typename GR::NodeIt it(g); it != INVALID; ++it) { |
122 for (typename GR::NodeIt it(g); it != INVALID; ++it) { |
126 uf.insert(it); |
123 uf.insert(it); |
127 } |
124 } |
136 } |
133 } |
137 else { |
134 else { |
138 out.set((*p).first, false); |
135 out.set((*p).first, false); |
139 } |
136 } |
140 } |
137 } |
141 std::cout << timer << std::endl; |
|
142 return tot_cost; |
138 return tot_cost; |
143 } |
139 } |
144 |
140 |
145 |
141 |
146 /// @} |
142 /// @} |