[python-graph] r740 committed - Fixed calculation of minimal spanning trees of graphs with negative-we...

[python...@googlecode.com]

Revision: 740
Author: pmatiello
Date: Sat Dec 31 04:43:27 2011
Log: Fixed calculation of minimal spanning trees of graphs with
negative-weighted edges.
http://code.google.com/p/python-graph/source/detail?r=740

Modified:
/trunk/Changelog
/trunk/core/pygraph/algorithms/minmax.py
/trunk/tests/unittests-minmax.py

=======================================
--- /trunk/Changelog Tue Nov 22 16:13:54 2011
+++ /trunk/Changelog Sat Dec 31 04:43:27 2011
@@ -5,7 +5,7 @@
CHANGELOG

-Next Release [??? ??, ????]
+Release 1.8.1 [??? ??, ????]

Enhancements:
Shortest-path now executes in O(n*log(n)) instead of O(n^2).
@@ -16,7 +16,8 @@
Linking, unlinking and relinking a hypernode to hyperedge now works as
expected;
Graph comparison does not raise exceptions anymore;
Fixed undesired sharing of attribute lists;
- Fixed reading of XML-stored graphs with edge attributes.
+ Fixed reading of XML-stored graphs with edge attributes;
+ Fixed calculation of minimal spanning trees of graphs with
negative-weighted edges.

Release 1.8.0 [Oct 01, 2010]
=======================================
--- /trunk/core/pygraph/algorithms/minmax.py Wed Feb 9 09:03:25 2011
+++ /trunk/core/pygraph/algorithms/minmax.py Sat Dec 31 04:43:27 2011
@@ -72,7 +72,7 @@
# Algorithm loop
while (nroot is not None):
ledge = _lightest_edge(graph, visited)
- if (ledge == (-1, -1)):
+ if (ledge == None):
if (root is not None):
break
nroot = _first_unvisited(graph, visited)
@@ -118,13 +118,13 @@
@rtype: tuple
@return: Lightest edge in graph going from a visited node to an
unvisited one.
"""
- lightest_edge = (-1, -1)
- weight = -1
+ lightest_edge = None
+ weight = None
for each in visited:
for other in graph[each]:
if (other not in visited):
w = graph.edge_weight((each, other))
- if (w < weight or weight < 0):
+ if (weight is None or w < weight or weight < 0):
lightest_edge = (each, other)
weight = w
return lightest_edge
=======================================
--- /trunk/tests/unittests-minmax.py Tue Nov 22 16:13:54 2011
+++ /trunk/tests/unittests-minmax.py Sat Dec 31 04:43:27 2011
@@ -115,15 +115,6 @@
add_spanning_tree(gr2, mst_copy)
assert len(depth_first_search(gr2, root=0)[0]) <
len_dfs

- def test_minimal_spanning_tree_with_negative_weigths(self):
- gr = graph()
- gr.add_nodes((0,1,2,3))
- gr.add_edge((0,1), wt=-0.4)
- gr.add_edge((1,2), wt=-0.6)
- gr.add_edge((2,0), wt=-0.5)
- gr.add_edge((3,2), wt=-0.1)
- gr.add_edge((3,1), wt=-0.2)
- print minimal_spanning_tree(gr, 0)

# shortest path tests