bug in minmax.minimal_spanning_tree

[GoogleCodeExporter]

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.

Original issue reported on code.google.com by Ben.Sny...@gmail.com on 9 Dec 2011 at 11:54

Attachments:

• minmax.py

[GoogleCodeExporter]

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

• Changed state: Accepted

[GoogleCodeExporter]

Fixed in r740.

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

• Changed state: Fixed