search

wting / python-graph

Automatically exported from code.google.com/p/python-graph
Other
5 stars 4 forks source link

minimum tree function for maximum tree calculation with weights between 0 and 1 not correct #102

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
What steps will reproduce the problem?
1.try to calculate a maximum spanning tree for an undirected tree, by means of 
the minimum spanning tree function
2.to get the maximum spanning tree you need to make the weights negative
3.use weights between 0 and -1 (!!)
4. use another program like matlab to get a reference

What is the expected output? What do you see instead?
in the expected output you should have a tree holding the edge with the 
highest/biggest weight (considering the orgininal positive weights)
I see a wrong tree...

What version of the product are you using? On what operating system?
1.8.0 - Oct 01, 2010

additinal Info:
we were able to get the correct tree (reference matlab), by for example makeing 
the orginal weights negative and add a large numer like 10, so that the weights 
are positive again. I think the problem lies in the _lightest_edge-function, 
where you define weight =-1?

Original issue reported on code.google.com by Anke.Wie...@gmx.net on 11 Nov 2011 at 5:01

GoogleCodeExporter commented 9 years ago 
Can you provide a very small graph (say three nodes or so) for which the 
algorithm produces an incorrect graph?

Original comment by pmatiello on 13 Nov 2011 at 11:52

GoogleCodeExporter commented 9 years ago 
Fixed in r740.

Original comment by pmatiello on 31 Dec 2011 at 12:44

GoogleCodeExporter commented 9 years ago 
If you look at the diff, you will see that there is still an explicit check for 
weight < 0. This may result in correct negative weights being replaced by 
arbitrary weights.

The conditional prior to r740 reads:
"if (w < weight or weight < 0):"

The conditional post r740 reads:
"if (weight is None or w < weight or weight < 0):"

But it should have replaced the weight < 0 check and read:
"if (weight is None or w < weight):"

---Minimal spanning tree is still broken for negative edge weights.---

I encountered this bug under pygraph 1.8.2

Original comment by jsh...@gmail.com on 31 Mar 2013 at 1:05