129 \endcode |
129 \endcode |
130 |
130 |
131 |
131 |
132 [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms |
132 [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms |
133 |
133 |
|
134 \todo This subsection is under construction. |
|
135 |
134 If you would like to design an electric network minimizing the total length |
136 If you would like to design an electric network minimizing the total length |
135 of wires, then you might be looking for a minimum spanning tree in an |
137 of wires, then you might be looking for a minimum spanning tree in an |
136 undirected graph. |
138 undirected graph. |
137 This can be found using the \ref kruskal() "Kruskal" algorithm. |
139 This can be found using the \ref kruskal() "Kruskal" algorithm. |
138 |
140 |
139 Let us suppose that the network is stored in a \ref ListGraph object \c g |
141 Let us suppose that the network is stored in a \ref ListGraph object \c g |
140 with a cost map \c cost. We create a \c bool valued edge map \c tree_map or |
142 with a cost map \c cost. We create a \c bool valued edge map \c tree_map or |
141 a vector \c tree_vector for stroing the tree that is found by the algorithm. |
143 a vector \c tree_vector for storing the tree that is found by the algorithm. |
142 After that, we could call the \ref kruskal() function. It gives back the weight |
144 After that, we could call the \ref kruskal() function. It gives back the weight |
143 of the minimum spanning tree and \c tree_map or \c tree_vector |
145 of the minimum spanning tree and \c tree_map or \c tree_vector |
144 will contain the found spanning tree. |
146 will contain the found spanning tree. |
145 |
147 |
146 If you want to store the arcs in a \c bool valued edge map, then you can use |
148 If you want to store the arcs in a \c bool valued edge map, then you can use |
165 |
167 |
166 \code |
168 \code |
167 // Kruskal algorithm with edge vector |
169 // Kruskal algorithm with edge vector |
168 std::vector<ListGraph::Edge> tree_vector; |
170 std::vector<ListGraph::Edge> tree_vector; |
169 std::cout << "The weight of the minimum spanning tree is " |
171 std::cout << "The weight of the minimum spanning tree is " |
170 << kruskal(g, cost_map, tree_vector) << std::endl; |
172 << kruskal(g, cost_map, std::back_inserter(tree_vector)) |
|
173 << std::endl; |
171 |
174 |
172 // Print the results |
175 // Print the results |
173 std::cout << "Edges of the tree: " << std::endl; |
176 std::cout << "Edges of the tree: " << std::endl; |
174 for (unsigned i = 0; i != tree_vector.size(); ++i) { |
177 for (unsigned i = 0; i != tree_vector.size(); ++i) { |
175 Edge e = tree_vector[i]; |
178 Edge e = tree_vector[i]; |