1.1 --- a/undir_graphs.dox	Mon Feb 22 00:46:59 2010 +0100
     1.2 +++ b/undir_graphs.dox	Mon Feb 22 01:59:50 2010 +0100
     1.3 @@ -131,10 +131,53 @@
     1.4  
     1.5  [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms
     1.6  
     1.7 -\todo This subsection is under construction.
     1.8 +If you would like to design an electric network minimizing the total length
     1.9 +of wires, then you might be looking for a minimum spanning tree in an
    1.10 +undirected graph.
    1.11 +This can be found using the \ref kruskal() "Kruskal" algorithm.
    1.12  
    1.13 -See \ref spantree for the minimum spanning tree algorithms and
    1.14 -\ref matching for matching algorithms.
    1.15 +Let us suppose that the network is stored in a \ref ListGraph object \c g
    1.16 +with a cost map \c cost. We create a \c bool valued edge map \c tree_map or
    1.17 +a vector \c tree_vector for stroing the tree that is found by the algorithm.
    1.18 +After that, we could call the \ref kruskal() function. It gives back the weight
    1.19 +of the minimum spanning tree and \c tree_map or \c tree_vector
    1.20 +will contain the found spanning tree.
    1.21 +
    1.22 +If you want to store the arcs in a \c bool valued edge map, then you can use
    1.23 +the function as follows.
    1.24 +
    1.25 +\code
    1.26 +  // Kruskal algorithm with edge map
    1.27 +  ListGraph::EdgeMap<bool> tree_map(g);
    1.28 +  std::cout << "The weight of the minimum spanning tree is "
    1.29 +            << kruskal(g, cost_map, tree_map) << std::endl;
    1.30 +
    1.31 +  // Print the results
    1.32 +  std::cout << "Edges of the tree: " << std::endl;
    1.33 +  for (ListGraph::EdgeIt e(g); e != INVALID; ++e) {
    1.34 +    if (!tree_map[e]) continue;
    1.35 +    std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
    1.36 +  }
    1.37 +\endcode
    1.38 +
    1.39 +If you would like to store the edges in a standard container, you can
    1.40 +do it like this.
    1.41 +
    1.42 +\code
    1.43 +  // Kruskal algorithm with edge vector
    1.44 +  std::vector<ListGraph::Edge> tree_vector;
    1.45 +  std::cout << "The weight of the minimum spanning tree is "
    1.46 +            << kruskal(g, cost_map, tree_vector) << std::endl;
    1.47 +
    1.48 +  // Print the results
    1.49 +  std::cout << "Edges of the tree: " << std::endl;
    1.50 +  for (unsigned i = 0; i != tree_vector.size(); ++i) {
    1.51 +    Edge e = tree_vector[i];
    1.52 +    std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
    1.53 +  }
    1.54 +\endcode
    1.55 +
    1.56 +\todo \ref matching "matching algorithms".
    1.57  
    1.58  [TRAILER]
    1.59  */