Changeset 47:c09d90659170 in lemon-tutorial

Timestamp:

02/22/10 01:59:50 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Write a subsection about Kruskal algorithm

File:

• undir_graphs.dox (modified) (1 diff)

undir_graphs.dox

@@ -132 +132 @@
 [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]