Changeset 47:c09d90659170 in lemontutorial
 Timestamp:
 02/22/10 01:59:50 (13 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

undir_graphs.dox
r46 r47 132 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 137 \ref matching for matching algorithms. 139 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 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 182 [TRAILER]
Note: See TracChangeset
for help on using the changeset viewer.