Uploaded image for project: 'Commons Sandbox'
  1. Commons Sandbox
  2. SANDBOX-374

Kruskal's algorithm doesn't accept sparse graph

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Graph
    • Labels:
      None

      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

        Attachments

          Activity

            People

            • Assignee:
              simone.tripodi Simone Tripodi
              Reporter:
              marco.speranza Marco Speranza
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: