equal
deleted
inserted
replaced
58 |
58 |
59 }; |
59 }; |
60 |
60 |
61 } |
61 } |
62 |
62 |
63 /// \ingroup spantree |
|
64 /// |
|
65 /// \brief Default traits class of Kruskal class. |
63 /// \brief Default traits class of Kruskal class. |
66 /// |
64 /// |
67 /// Default traits class of Kruskal class. |
65 /// Default traits class of Kruskal class. |
68 /// \param _UGraph Undirected graph type. |
66 /// \param _UGraph Undirected graph type. |
69 /// \param _CostMap Type of cost map. |
67 /// \param _CostMap Type of cost map. |
105 std::sort(begin, end, comp); |
103 std::sort(begin, end, comp); |
106 } |
104 } |
107 |
105 |
108 }; |
106 }; |
109 |
107 |
|
108 ///\ingroup spantree |
|
109 /// |
110 /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. |
110 /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. |
111 /// |
111 /// |
112 /// This class implements Kruskal's algorithm to find a minimum cost |
112 /// This class implements Kruskal's algorithm to find a minimum cost |
113 /// spanning tree. The |
113 /// spanning tree. The |
114 /// |
114 /// |
296 } |
296 } |
297 |
297 |
298 /// \brief Initialize the algorithm |
298 /// \brief Initialize the algorithm |
299 /// |
299 /// |
300 /// This member function initializes the unionfind data structure |
300 /// This member function initializes the unionfind data structure |
301 /// and sets the edge order to the given sequence. The given |
301 /// and sets the tree to empty. It does not change the order of |
302 /// sequence should be a valid STL range of undirected edges. |
302 /// the edges, it uses the order of the previous running. |
303 void reinit() { |
303 void reinit() { |
304 initStructures(); |
304 initStructures(); |
305 initUnionFind(); |
305 initUnionFind(); |
306 for (UEdgeIt e(graph); e != INVALID; ++e) { |
306 for (UEdgeIt e(graph); e != INVALID; ++e) { |
307 _tree->set(e, false); |
307 _tree->set(e, false); |