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> |
27 |
29 |
28 ///\ingroup spantree |
30 ///\ingroup spantree |
29 ///\file |
31 ///\file |
30 ///\brief Kruskal's algorithm to compute a minimum cost tree |
32 ///\brief Kruskal's algorithm to compute a minimum cost tree |
31 /// |
33 /// |
115 { |
117 { |
116 typedef typename IN::value_type::second_type EdgeCost; |
118 typedef typename IN::value_type::second_type EdgeCost; |
117 typedef typename GR::template NodeMap<int> NodeIntMap; |
119 typedef typename GR::template NodeMap<int> NodeIntMap; |
118 typedef typename GR::Node Node; |
120 typedef typename GR::Node Node; |
119 |
121 |
120 NodeIntMap comp(g, -1); |
122 Timer timer; |
121 UnionFind<Node,NodeIntMap> uf(comp); |
123 NodeIntMap comp(g); |
|
124 UnionFind<Node,NodeIntMap> uf(comp); |
|
125 for (typename GR::NodeIt it(g); it != INVALID; ++it) { |
|
126 uf.insert(it); |
|
127 } |
122 |
128 |
123 EdgeCost tot_cost = 0; |
129 EdgeCost tot_cost = 0; |
124 for (typename IN::const_iterator p = in.begin(); |
130 for (typename IN::const_iterator p = in.begin(); |
125 p!=in.end(); ++p ) { |
131 p!=in.end(); ++p ) { |
126 if ( uf.join(g.target((*p).first), |
132 if ( uf.join(g.target((*p).first), |
130 } |
136 } |
131 else { |
137 else { |
132 out.set((*p).first, false); |
138 out.set((*p).first, false); |
133 } |
139 } |
134 } |
140 } |
|
141 std::cout << timer << std::endl; |
135 return tot_cost; |
142 return tot_cost; |
136 } |
143 } |
137 |
144 |
138 |
145 |
139 /// @} |
146 /// @} |