[SANDBOX-374] Kruskal's algorithm doesn't accept sparse graph

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Component/s: Graph
• Assignee: Simone Tripodi
• Reporter: Marco Speranza
• Created: 30/Jan/12 22:29
• Updated: 31/Jan/12 10:07
• Resolved: 31/Jan/12 10:07

Description

Hi guys,

I found a little problem into Kruskal's algorithm when the input graph is not connected and/or it's a graph without the edges.

I created a test case that produces the follow error:

Running org.apache.commons.graph.spanning.KruskalTestCase
Tests run: 2, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 0.096 sec <<< FAILURE!
verifyNotConnectedMinimumSpanningTree(org.apache.commons.graph.spanning.KruskalTestCase)  Time elapsed: 0.007 sec  <<< ERROR!
java.util.NoSuchElementException
        at java.util.AbstractQueue.remove(AbstractQueue.java:90)
        at org.apache.commons.graph.spanning.DefaultSpanningTreeAlgorithmSelector.applyingKruskalAlgorithm(DefaultSpanningTreeAlgorithmSelector.java:87)

ciao
Marco