Issue 103 in python-graph: bug in minmax.minimal_spanning_tree
python...@googlecode.com
Owner: ----
Labels: Type-Defect Priority-Medium
New issue 103 by Ben.Sny...@gmail.com: bug in minmax.minimal_spanning_tree
http://code.google.com/p/python-graph/issues/detail?id=103
release 1.8.0
currently the minimal_spanning_tree function breaks when the edge weights
are negative (and returns a random spanning tree, without regard for the
weights). This is undocumented, and unnecessary from an algorithmic
perspective.
The cause is the function: _lightest_edge. Weight is initialized to be
-1, and the loop assumes that when a negative value has been encountered,
we are looking at the first edge. Obviously if the edge weights are
negative, this is a mistaken assumption.
Here is my fix:
def _lightest_edge(graph, visited):
"""
Return the lightest edge in graph going from a visited node to an
unvisited one.
@type graph: graph
@param graph: Graph.
@type visited: list
@param visited: List of nodes.
@rtype: tuple
@return: Lightest edge in graph going from a visited node to an
unvisited one.
"""
lightest_edge = (-1, -1)
weight = None
for each in visited:
for other in graph[each]:
if (other not in visited):
w = graph.edge_weight((each, other))
if weight == None or w < weight:
lightest_edge = (each, other)
weight = w
return lightest_edge
Now, weight is initialized as None.
The corrected file is attached.
Attachments:
minmax.py 15.3 KB
python...@googlecode.com
Status: Accepted
Comment #1 on issue 103 by pmatiello: bug in minmax.minimal_spanning_tree
http://code.google.com/p/python-graph/issues/detail?id=103
(No comment was entered for this change.)
python...@googlecode.com
Status: Fixed
Comment #2 on issue 103 by pmatiello: bug in minmax.minimal_spanning_tree
http://code.google.com/p/python-graph/issues/detail?id=103
Fixed in r740.