COIN-OR::LEMON - Graph Library

Changeset 1584:cf4bc8d477f4 in lemon-0.x for doc


Ignore:
Timestamp:
07/22/05 18:57:07 (19 years ago)
Author:
zsuzska
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2087
Message:

corrections

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/quicktour.dox

    r1580 r1584  
    144144length of wires then you might be looking for a <b>minimum spanning
    145145tree</b> in an undirected graph. This can be found using the Kruskal
    146 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does
    147 this job for you.  After we had a graph \c g and a cost map \c
    148 edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree (in this first example the costs are uniform; this is of course not the case in real life applications):
     146algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does this
     147job for you. 
     148
     149First make a graph \c g and a cost map \c
     150edge_cost_map, then make a bool edgemap \c tree_map or a vector \c
     151tree_edge_vec for the algorithm output. After calling the function it
     152gives back the weight of the minimum spanning tree and the \c tree_map or
     153the \c tree_edge_vec contains the edges of the tree.
     154
     155If you want to store the edges in a bool edgemap, then use the
     156function as follows:
    149157
    150158\dontinclude kruskal_demo.cc
    151 \skip std::cout
    152 \until kruskal
    153 
    154 In the variable \c tree_map the function gives back an edge bool map, which contains the edges of the found tree.
    155 
    156 If the costs are non-uniform, for example  the cost is given by \c
    157 edge_cost_map_2 , or the edges of the tree  have to be given in a
    158 vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of
    159 an edge bool map:
    160 
    161 \skip edge_cost_map_2
    162 \until edge_cost_map_2, std::back_inserter
    163 
    164 And finally the next fragment shows how to use the functions \c makeKruskalMapInput and \c makeKruskalSequenceOutPut:
    165 
    166 \skip makeKruskalSequenceOutput
    167 \until tree_edge_vec
     159\skip Kruskal with boolmap;
     160\until  std::endl
     161
     162And if you rather use a vector instead of a bool map:
     163
     164\skip Kruskal with vector;
     165\until std::endl
    168166
    169167See the whole program in \ref kruskal_demo.cc.
Note: See TracChangeset for help on using the changeset viewer.