COIN-OR::LEMON - Graph Library

Changeset 47:c09d90659170 in lemon-tutorial


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • undir_graphs.dox

    r46 r47  
    132132[SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms
    133133
    134 \todo This subsection is under construction.
     134If you would like to design an electric network minimizing the total length
     135of wires, then you might be looking for a minimum spanning tree in an
     136undirected graph.
     137This can be found using the \ref kruskal() "Kruskal" algorithm.
    135138
    136 See \ref spantree for the minimum spanning tree algorithms and
    137 \ref matching for matching algorithms.
     139Let us suppose that the network is stored in a \ref ListGraph object \c g
     140with a cost map \c cost. We create a \c bool valued edge map \c tree_map or
     141a vector \c tree_vector for stroing the tree that is found by the algorithm.
     142After that, we could call the \ref kruskal() function. It gives back the weight
     143of the minimum spanning tree and \c tree_map or \c tree_vector
     144will contain the found spanning tree.
     145
     146If you want to store the arcs in a \c bool valued edge map, then you can use
     147the 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
     163If you would like to store the edges in a standard container, you can
     164do 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".
    138181
    139182[TRAILER]
Note: See TracChangeset for help on using the changeset viewer.