# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1266800390 -3600
# Node ID c09d906591705caa28ef1ef4fed0c85a6b4c10ab
# Parent  58557724a13975fa09aeb06d1b7b17311f553be2
Write a subsection about Kruskal algorithm

diff -r 58557724a139 -r c09d90659170 undir_graphs.dox
--- a/undir_graphs.dox	Mon Feb 22 00:46:59 2010 +0100
+++ b/undir_graphs.dox	Mon Feb 22 01:59:50 2010 +0100
@@ -131,10 +131,53 @@
 
 [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms
 
-\todo This subsection is under construction.
+If you would like to design an electric network minimizing the total length
+of wires, then you might be looking for a minimum spanning tree in an
+undirected graph.
+This can be found using the \ref kruskal() "Kruskal" algorithm.
 
-See \ref spantree for the minimum spanning tree algorithms and
-\ref matching for matching algorithms.
+Let us suppose that the network is stored in a \ref ListGraph object \c g
+with a cost map \c cost. We create a \c bool valued edge map \c tree_map or
+a vector \c tree_vector for stroing the tree that is found by the algorithm.
+After that, we could call the \ref kruskal() function. It gives back the weight
+of the minimum spanning tree and \c tree_map or \c tree_vector
+will contain the found spanning tree.
+
+If you want to store the arcs in a \c bool valued edge map, then you can use
+the function as follows.
+
+\code
+  // Kruskal algorithm with edge map
+  ListGraph::EdgeMap<bool> tree_map(g);
+  std::cout << "The weight of the minimum spanning tree is "
+            << kruskal(g, cost_map, tree_map) << std::endl;
+
+  // Print the results
+  std::cout << "Edges of the tree: " << std::endl;
+  for (ListGraph::EdgeIt e(g); e != INVALID; ++e) {
+    if (!tree_map[e]) continue;
+    std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
+  }
+\endcode
+
+If you would like to store the edges in a standard container, you can
+do it like this.
+
+\code
+  // Kruskal algorithm with edge vector
+  std::vector<ListGraph::Edge> tree_vector;
+  std::cout << "The weight of the minimum spanning tree is "
+            << kruskal(g, cost_map, tree_vector) << std::endl;
+
+  // Print the results
+  std::cout << "Edges of the tree: " << std::endl;
+  for (unsigned i = 0; i != tree_vector.size(); ++i) {
+    Edge e = tree_vector[i];
+    std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
+  }
+\endcode
+
+\todo \ref matching "matching algorithms".
 
 [TRAILER]
 */