[Lemon-user] number of STATE_TREE vars at end of network simplex (on connected graph)

[Matthew Galati]

> Not really. You can use kruskal in two different ways.
>      * You can pass the arc cost in a Graph::ArcMap<NumType>. In this
>        case the algorithm sets up an std::vector<
>        std::pair<Arc,NumType> >, puts all the arcs and costs into it,
>        then _sorts_ the vector according the costs, then proceed as for
>        the second case.
>      * You can give an std::vector< std::pair<Arc,NumType> > directly
>        to kruskal(). Then it will _not_ sort it but will assume it is
>        already sorted. Thus, it picks the arcs one-by-one and adds to
>        the chosen arcs if it is does not form a cycle. The cost are
>        only used for counting the total cost of the solution and for
>        nothing else.
>
> Rational: Sorting is a costly operational, in fact it is costlier than
> finding the minimum spanning tree afterward. Therefore you have an
> option to skip the sorting if you have already know the right order.
>
> >  How can you be sure that those arcs are chosen first by Kruskal's -
> > since the algorithm will choose based on weight? To be safe, maybe we
> > should put an artificially low weight on those tree arcs in the arcs
> > object?
>
> Yes, you can set them 0 for the 'not-on-border' arcs and to 1 for the
> others. But you can safely assume that kruskal() works as detailed
> above.
>
> The fact that the second mode does not use the cost (just sums the
> values) makes it possible for finding the min.cost tree according to a
> cost function and computing its cost according to another.
>
> Regards,
> Alpar
>
>


Ok. That makes sense! Thank you very much. I will try this.

Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100309/85542e05/attachment.html>