Issue 102 in python-graph: minimum tree function for maximum tree calculation with weights between 0 and 1 not correct

[python...@googlecode.com]

Status: New
Owner: ----
Labels: Type-Defect Priority-Medium

New issue 102 by Anke.Wie...@uni.lu: minimum tree function for maximum tree
calculation with weights between 0 and 1 not correct
http://code.google.com/p/python-graph/issues/detail?id=102

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?

[python...@googlecode.com]

Updates:
Status: Accepted

Comment #1 on issue 102 by pmatiello: minimum tree function for maximum

tree calculation with weights between 0 and 1 not correct
http://code.google.com/p/python-graph/issues/detail?id=102

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

[python...@googlecode.com]

Updates:
Status: Fixed

Comment #2 on issue 102 by pmatiello: minimum tree function for maximum

tree calculation with weights between 0 and 1 not correct
http://code.google.com/p/python-graph/issues/detail?id=102

Fixed in r740.

[python...@googlecode.com]

Comment #3 on issue 102 by jsh...@gmail.com: minimum tree function for

maximum tree calculation with weights between 0 and 1 not correct
http://code.google.com/p/python-graph/issues/detail?id=102

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

--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings

[Salim Fadhley]

Could you prepare a test + patch for this proposed fix. I will be happy to merge it in.

--

---You received this message because you are subscribed to the Google Groups "python-graph" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python-graph+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.