You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2012/01/31 11:06:25 UTC
svn commit: r1238355 - in /commons/sandbox/graph/trunk/src:
changes/changes.xml
main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
Author: simonetripodi
Date: Tue Jan 31 10:06:25 2012
New Revision: 1238355
URL: http://svn.apache.org/viewvc?rev=1238355&view=rev
Log:
[SANDBOX-374] Kruskal's algorithm doesn't accept sparse graph - patch submitted by Marco Speranza
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
Modified: commons/sandbox/graph/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1238355&r1=1238354&r2=1238355&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Tue Jan 31 10:06:25 2012
@@ -23,6 +23,9 @@
</properties>
<body>
<release version="0.1" date="201?-??-??" description="First release.">
+ <action dev="simonetripodi" type="fix" issue="SANDBOX-374" due-to="Marco Speranza">
+ Kruskal's algorithm doesn't accept sparse graph
+ </action>
<action dev="simonetripodi" type="update" issue="SANDBOX-372">
Make the org.apache.commons.graph.visit.GraphVisitHandler able to return objects
</action>
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java?rev=1238355&r1=1238354&r2=1238355&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java Tue Jan 31 10:06:25 2012
@@ -70,8 +70,8 @@ final class DefaultSpanningTreeAlgorithm
{
final Set<V> settledNodes = new HashSet<V>();
- final PriorityQueue<WE> orderedEdges = new PriorityQueue<WE>( graph.getSize(),
- new WeightedEdgesComparator<W, WE>( orderedMonoid ) );
+ final PriorityQueue<WE> orderedEdges =
+ new PriorityQueue<WE>( graph.getSize(), new WeightedEdgesComparator<W, WE>( orderedMonoid ) );
for ( WE edge : graph.getEdges() )
{
@@ -80,24 +80,23 @@ final class DefaultSpanningTreeAlgorithm
final DisjointSet<V> disjointSet = new DisjointSet<V>();
- MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
+ final MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
- while ( settledNodes.size() < graph.getOrder() )
+ //fill the spanning tree with vertices.
+ for ( V v : graph.getVertices() )
+ {
+ spanningTree.addVertex( v );
+ }
+
+ while ( !orderedEdges.isEmpty() && settledNodes.size() < graph.getOrder() )
{
WE edge = orderedEdges.remove();
VertexPair<V> vertices = graph.getVertices( edge );
V head = vertices.getHead();
V tail = vertices.getTail();
-
- if ( settledNodes.add( head ) )
- {
- spanningTree.addVertex( head );
- }
- if ( settledNodes.add( tail ) )
- {
- spanningTree.addVertex( tail );
- }
+ settledNodes.add( head );
+ settledNodes.add( tail );
if ( !disjointSet.find( head ).equals( disjointSet.find( tail ) ) )
{
@@ -131,7 +130,8 @@ final class DefaultSpanningTreeAlgorithm
WE edge = graph.getEdge( vertex, v );
// if the edge has not been already visited and its weight is less then the current Vertex weight
- boolean weightLessThanCurrent = !shortestEdges.hasWeight( v )
+ boolean weightLessThanCurrent =
+ !shortestEdges.hasWeight( v )
|| orderedMonoid.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
if ( settledEdges.add( edge ) && weightLessThanCurrent )
{
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java?rev=1238355&r1=1238354&r2=1238355&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java Tue Jan 31 10:06:25 2012
@@ -51,6 +51,7 @@ public final class KruskalTestCase
BaseLabeledVertex f = new BaseLabeledVertex( "F" );
BaseLabeledVertex g = new BaseLabeledVertex( "G" );
+
input.addVertex( a );
input.addVertex( b );
input.addVertex( c );
@@ -59,6 +60,7 @@ public final class KruskalTestCase
input.addVertex( f );
input.addVertex( g );
+
input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 7D ), b );
input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> d", 5D ), d );
@@ -102,4 +104,49 @@ public final class KruskalTestCase
assertEquals( expected, actual );
}
+
+ /**
+ * Test Graph and Prim's solution can be seen on
+ * <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm">Wikipedia</a>
+ */
+ @Test
+ public void verifyNotConnectedMinimumSpanningTree()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> input
+ = new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>();
+
+ BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+ BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+ BaseLabeledVertex c = new BaseLabeledVertex( "C" );
+ BaseLabeledVertex d = new BaseLabeledVertex( "D" );
+
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+ input.addVertex( d );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 7D ), b );
+
+
+ // expected
+
+ MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> expected =
+ new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>( new DoubleWeight() );
+
+ for ( BaseLabeledVertex vertex : input.getVertices() )
+ {
+ expected.addVertex( vertex );
+ }
+ expected.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 7D ), b );
+
+ // Actual
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual = minimumSpanningTree( input ).fromArbitrarySource().applyingKruskalAlgorithm( new DoubleWeight() );
+
+ // assert!
+
+ assertEquals( expected, actual );
+ }
+
}