Minimum spanning tree is wrongly calculated

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Create the following graph:
    <node id="1"/>
    <node id="2"/>
    <node id="3"/>
    <edge from="1" label="M1" to="2" wt="277317"/>
    <edge from="3" label="M6" to="2" wt="112344"/>
    <edge from="1" label="M3" to="3" wt="478726"/>
    <edge from="3" label="M4" to="1" wt="930382"/>
    <edge from="2" label="M2" to="1" wt="26247"/>
    <edge from="2" label="M5" to="3" wt="370287"/>
2. Run minimal_spanning_tree () on it

What is the expected output? What do you see instead?
This is what we get:
    <node id="1"/>
    <node id="2"/>
    <node id="3"/>
    <edge from="2" label="" to="3" wt="1"/>
    <edge from="2" label="" to="1" wt="1"/>

Original weights are lost! Plus this is not really the MST for the above graph!

What version of the product are you using? On what operating system?
python_graph-1.4.2 on Python 2.5.1

Original issue reported on code.google.com by sukkopera on 1 Apr 2009 at 10:26

[GoogleCodeExporter]

Thank you for your report.

I suppose you created the second graph from the spanning tree returned by
graph.minimal_spanning_tree(), right? Well, the spanning tree does not contains 
any
weight information (it's just a pairing between nodes, nothing else). so this 
is the
intended behavior.

About the generated spanning tree not being minimal, you are right. We are using
Prim's algorithm to calculate the minimal spanning trees, but it should only be 
used
against graphs, not digraphs. I'm removing it from the digraph class.

Original comment by pmatiello on 2 Apr 2009 at 12:12

• Changed state: Fixed

[GoogleCodeExporter]

I think there should be an easy way to get the MST of a graph as a copy of the
original graph with all the edges not belonging to the MST removed. I think 
this is
needed quite commonly, and this was what I meant with my report.

Yes, I was using digraph, this was the cause of the issue. I am sorry, but I 
have
just started handling graphs again after many years ;). Anyway I know that a few
algorithms to get the MST of a digraph exist. Is there any chance that they get
implemented?

Original comment by sukkopera on 2 Apr 2009 at 8:50

[GoogleCodeExporter]

About the copying thing, I'll consider if and how it should be added to the 
library.

About MST for digraphs, well, it's my intention. But it's likely to take some 
time as
I'm a too busy by now.

Original comment by pmatiello on 2 Apr 2009 at 11:55