COIN-OR::LEMON - Graph Library

Changeset 1578:1d3a1bcbc874 in lemon-0.x for doc


Ignore:
Timestamp:
07/21/05 00:36:37 (14 years ago)
Author:
zsuzska
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2079
Message:

kruskal_demo corrected, quicktour filled with kruskal

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/quicktour.dox

    r1541 r1578  
    142142
    143143
    144 <li> If you want to design a network and want to minimize the total length
    145 of wires then you might be looking for a <b>minimum spanning tree</b> in
    146 an undirected graph. This can be found using the Kruskal algorithm: the
    147 function \ref lemon::kruskal "LEMON Kruskal ..." does this job for you.
    148 The following code fragment shows an example:
    149 
    150 Ide Zsuzska fog irni!
     144<li> If you want to design a network and want to minimize the total
     145length of wires then you might be looking for a <b>minimum spanning
     146tree</b> in an undirected graph. This can be found using the Kruskal
     147algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does
     148this job for you.  After we had a graph \c g and a cost map \c
     149edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree, if the costs are uniform:
     150
     151\dontinclude kruskal_demo.cc
     152\skip std::cout
     153\until kruskal
     154
     155It gives back a edge bool map, which contains the edges of the tree.
     156If the costs are non-uniform, for example  the cost is given by \c
     157edge_cost_map_2 , or the edges of the tree are have to be given in a
     158vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of
     159an edge bool map:
     160
     161\skip edge_cost_map_2
     162\until edge_cost_map_2, std::back_inserter
     163
     164And finally the next fragment shows how to use the functions \c makeKruskalMapInput and \c makeKruskalSequenceOutPut:
     165
     166\skip makeKruskalSequenceOutput
     167\until tree_edge_vec
     168
     169See the whole program in \ref kruskal_demo.cc.
     170
     171
    151172
    152173<li>Many problems in network optimization can be formalized by means
Note: See TracChangeset for help on using the changeset viewer.