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 17:50:36 UTC
svn commit: r1238692 - 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/BoruvkaTestCase.java
Author: simonetripodi
Date: Tue Jan 31 16:50:35 2012
New Revision: 1238692
URL: http://svn.apache.org/viewvc?rev=1238692&view=rev
Log:
[SANDBOX-348] Implement the Boruvka's algorithm - patch provided by Marco Speranza
Added:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java (with props)
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.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=1238692&r1=1238691&r2=1238692&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Tue Jan 31 16:50:35 2012
@@ -62,6 +62,9 @@
<action dev="simonetripodi" type="fix" issue="SANDBOX-350" due-to="Marco Speranza">
Provide a Reverse-delete algorithm implementation
</action>
+ <action dev="simonetripodi" type="fix" issue="SANDBOX-348" due-to="Marco Speranza">
+ Implement the Boruvka's algorithm
+ </action>
<action dev="simonetripodi" type="update" issue="SANDBOX-346" due-to="Claudio Squarcella">
DotExporter only exports weights that extend Number.
</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=1238692&r1=1238691&r2=1238692&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 16:50:35 2012
@@ -19,7 +19,16 @@ package org.apache.commons.graph.spannin
* under the License.
*/
+import static java.util.Collections.sort;
+import static org.apache.commons.graph.CommonsGraph.findConnectedComponent;
+import static org.apache.commons.graph.utils.Assertions.checkNotNull;
+import static org.apache.commons.graph.utils.Assertions.checkState;
+
+import java.util.ArrayList;
+import java.util.Collection;
import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
@@ -59,8 +68,93 @@ final class DefaultSpanningTreeAlgorithm
*/
public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( OM orderedMonoid )
{
- // TODO Boruvka still needs to be implemented
- return null;
+ /*
+ * <pre>
+ * procedure Boruvka MST(G(V; E)):
+ * T <= V
+ * while |T| < n 1 do
+ * for all connected component C in T do
+ * e <= the smallest-weight edge from C to another component in T
+ * if e not exists in T then
+ * T <= T U {e}
+ * end if
+ * end for
+ * end while
+ *
+ * <pre>
+ */
+
+ Collection<List<V>> connectedComponents =
+ findConnectedComponent( graph ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm();
+
+ checkNotNull( connectedComponents, "Connectivity algorithms returns a null pointer" );
+ checkState( connectedComponents.size() == 1, "Boruvka's Algorithm cannot be calculated on not-connected graph." );
+
+ final List<WE> sortedEdge = new ArrayList<WE>();
+
+ for ( WE we : graph.getEdges() )
+ {
+ sortedEdge.add( we );
+ }
+
+ sort( sortedEdge, new WeightedEdgesComparator<W, WE>( orderedMonoid ) );
+
+ final MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
+
+ for ( V v : graph.getVertices() )
+ {
+ spanningTree.addVertex( v );
+ }
+
+ // find connected component into spanning tree.
+ connectedComponents = findConnectedComponent( spanningTree ).includingAllVertices().applyingMinimumSpanningTreeAlgorithm();
+ do
+ {
+ Iterator<WE> it = sortedEdge.iterator();
+
+ while ( it.hasNext() )
+ {
+ WE edge = it.next();
+ VertexPair<V> pair = graph.getVertices( edge );
+ // find the vertices into the connected component.
+ for ( List<V> list : connectedComponents )
+ {
+ boolean listContainsHead = list.contains( pair.getHead() );
+ boolean listContainsTail = list.contains( pair.getTail() );
+
+ if ( listContainsHead && listContainsTail )
+ {
+ // this edge is included into a connected component.
+ it.remove();
+ break;
+ }
+ else if ( listContainsHead )
+ {
+ spanningTree.addEdge( pair.getHead(), edge, pair.getTail() );
+ it.remove();
+
+ for ( List<V> l : connectedComponents )
+ {
+ if ( l == list )
+ {
+ continue;
+ }
+
+ if ( l.contains( pair.getTail() ) )
+ {
+ list.addAll( l );
+ l.clear();
+ break;
+ }
+ }
+ break;
+ }
+ }
+ }
+ }
+ while ( spanningTree.getSize() < spanningTree.getOrder() - 1 );
+
+ return spanningTree;
}
/**
@@ -82,13 +176,13 @@ final class DefaultSpanningTreeAlgorithm
final MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
- //fill the spanning tree with vertices.
+ // fill the spanning tree with vertices.
for ( V v : graph.getVertices() )
{
spanningTree.addVertex( v );
}
- while ( !orderedEdges.isEmpty() && settledNodes.size() < graph.getOrder() )
+ while ( !orderedEdges.isEmpty() && settledNodes.size() < graph.getOrder() )
{
WE edge = orderedEdges.remove();
@@ -129,9 +223,9 @@ 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 )
+ // if the edge has not been already visited and its weight is
+ // less then the current Vertex weight
+ boolean weightLessThanCurrent = !shortestEdges.hasWeight( v )
|| orderedMonoid.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
if ( settledEdges.add( edge ) && weightLessThanCurrent )
{
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java?rev=1238692&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java Tue Jan 31 16:50:35 2012
@@ -0,0 +1,134 @@
+package org.apache.commons.graph.spanning;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.fail;
+import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
+
+import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.model.MutableSpanningTree;
+import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
+import org.junit.Test;
+
+public final class BoruvkaTestCase
+{
+
+ /**
+ * Test Graph and boruvka's solution can be seen on
+ */
+ @Test
+ public void verifyWikipediaMinimumSpanningTree()
+ {
+ 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" );
+ BaseLabeledVertex e = new BaseLabeledVertex( "E" );
+ BaseLabeledVertex f = new BaseLabeledVertex( "F" );
+ BaseLabeledVertex g = new BaseLabeledVertex( "G" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+ input.addVertex( d );
+ input.addVertex( e );
+ input.addVertex( f );
+ input.addVertex( g );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 7D ), b );
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> c", 14D ), c );
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> d", 30D ), d );
+
+ input.addEdge( b, new BaseLabeledWeightedEdge<Double>( "b <-> c", 21D ), c );
+
+ input.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> d", 10D ), d );
+ input.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> e", 1D ), e );
+
+ input.addEdge( e, new BaseLabeledWeightedEdge<Double>( "e <-> f", 6D ), f );
+ input.addEdge( e, new BaseLabeledWeightedEdge<Double>( "e <-> g", 9D ), g );
+
+ input.addEdge( f, new BaseLabeledWeightedEdge<Double>( "f <-> g", 4D ), g );
+
+ // 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 );
+ expected.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> c", 14D ), c );
+ expected.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> d", 10D ), d );
+ expected.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> e", 1D ), e );
+ expected.addEdge( e, new BaseLabeledWeightedEdge<Double>( "e <-> f", 6D ), f );
+ expected.addEdge( f, new BaseLabeledWeightedEdge<Double>( "e <-> g", 9D ), g );
+
+ // Actual
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
+ minimumSpanningTree( input ).fromArbitrarySource().applyingBoruvkaAlgorithm( new DoubleWeight() );
+
+ // assert!
+
+ assertEquals( expected, actual );
+ }
+
+ /**
+ * Test Boruvka's solution on a not-connected graph.
+ */
+ @Test( expected = IllegalStateException.class )
+ public void verifySparseGraphMinimumSpanningTree()
+ {
+ 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" );
+ BaseLabeledVertex e = new BaseLabeledVertex( "E" );
+ BaseLabeledVertex f = new BaseLabeledVertex( "F" );
+ BaseLabeledVertex g = new BaseLabeledVertex( "G" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+ input.addVertex( d );
+ input.addVertex( e );
+ input.addVertex( f );
+ input.addVertex( g );
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
+ minimumSpanningTree( input ).fromArbitrarySource().applyingBoruvkaAlgorithm( new DoubleWeight() );
+
+ fail( "Exception not thrown!. Boruvka's algorithm cannot be calculated on a not-connected graph." );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain