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. |
134 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 |
|
136 undirected graph. |
|
137 This can be found using the \ref kruskal() "Kruskal" algorithm. |
135 |
138 |
136 See \ref spantree for the minimum spanning tree algorithms and |
139 Let us suppose that the network is stored in a \ref ListGraph object \c g |
137 \ref matching for matching algorithms. |
140 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. |
|
142 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 |
|
144 will contain the found spanning tree. |
|
145 |
|
146 If you want to store the arcs in a \c bool valued edge map, then you can use |
|
147 the function as follows. |
|
148 |
|
149 \code |
|
150 // Kruskal algorithm with edge map |
|
151 ListGraph::EdgeMap<bool> tree_map(g); |
|
152 std::cout << "The weight of the minimum spanning tree is " |
|
153 << kruskal(g, cost_map, tree_map) << std::endl; |
|
154 |
|
155 // Print the results |
|
156 std::cout << "Edges of the tree: " << std::endl; |
|
157 for (ListGraph::EdgeIt e(g); e != INVALID; ++e) { |
|
158 if (!tree_map[e]) continue; |
|
159 std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n"; |
|
160 } |
|
161 \endcode |
|
162 |
|
163 If you would like to store the edges in a standard container, you can |
|
164 do it like this. |
|
165 |
|
166 \code |
|
167 // Kruskal algorithm with edge vector |
|
168 std::vector<ListGraph::Edge> tree_vector; |
|
169 std::cout << "The weight of the minimum spanning tree is " |
|
170 << kruskal(g, cost_map, tree_vector) << std::endl; |
|
171 |
|
172 // Print the results |
|
173 std::cout << "Edges of the tree: " << std::endl; |
|
174 for (unsigned i = 0; i != tree_vector.size(); ++i) { |
|
175 Edge e = tree_vector[i]; |
|
176 std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n"; |
|
177 } |
|
178 \endcode |
|
179 |
|
180 \todo \ref matching "matching algorithms". |
138 |
181 |
139 [TRAILER] |
182 [TRAILER] |
140 */ |
183 */ |
141 } |
184 } |