You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/03/03 14:00:49 UTC
svn commit: r1296618 - in /commons/sandbox/graph/trunk/src:
benchmarks/java/org/apache/commons/graph/spanning/
main/java/org/apache/commons/graph/spanning/
Author: tn
Date: Sat Mar 3 13:00:48 2012
New Revision: 1296618
URL: http://svn.apache.org/viewvc?rev=1296618&view=rev
Log:
improved Boruvkas MST algo, improved MST benchmark, minor formatting fixes
Modified:
commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
Modified: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java?rev=1296618&r1=1296617&r2=1296618&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/spanning/MinimumSpanningTreeBenchmarkTestCase.java Sat Mar 3 13:00:48 2012
@@ -22,10 +22,16 @@ package org.apache.commons.graph.spannin
import static java.lang.String.format;
import static java.lang.String.valueOf;
import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
+import static org.apache.commons.graph.CommonsGraph.newUndirectedMutableWeightedGraph;
import static org.junit.Assert.assertTrue;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
import org.apache.commons.graph.GraphException;
import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.builder.AbstractGraphConnection;
import org.apache.commons.graph.model.BaseLabeledVertex;
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
@@ -42,51 +48,67 @@ import com.carrotsearch.junitbenchmarks.
@BenchmarkMethodChart( filePrefix = "minimum-spanning-tree" )
public final class MinimumSpanningTreeBenchmarkTestCase
{
+ private static final int NODES = 1000;
+ private static final int EDGES = 6000;
@Rule
public BenchmarkRule benchmarkRun = new BenchmarkRule();
- private static final UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> G
- = new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>();
+ private static UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> graph;
@BeforeClass
public static void setUp()
{
- for ( int i = 0; i < 1000; i++ )
+ graph = newUndirectedMutableWeightedGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
{
- BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) );
- G.addVertex( v );
- }
+ Random r = new Random();
- for ( BaseLabeledVertex v1 : G.getVertices() )
- {
- int cnt = 0;
- for ( BaseLabeledVertex v2 : G.getVertices() )
+ public void connect()
{
- if (cnt++ > 20)
+ List<BaseLabeledVertex> vertices = new ArrayList<BaseLabeledVertex>();
+ for ( int i = 0; i < NODES; i++ )
{
- break;
+ BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) );
+ addVertex( v );
+ vertices.add( v );
}
- if ( !v1.equals( v2 ) )
+
+ // form a connected graph
+ for ( int i = 0; i < NODES - 1; i++ )
{
- try
- {
- G.addEdge( v1, new BaseLabeledWeightedEdge<Double>( format( "%s -> %s", v1, v2 ), 7D ), v2 );
- }
- catch ( GraphException e )
- {
- // ignore
+ addEdge( vertices.get( i ), vertices.get( i + 1 ) );
+ }
+
+ addEdge( vertices.get( NODES - 1 ) , vertices.get( 0 ) );
+ // we have already created #NODES edges
+ int maxEdges = Math.max(0, EDGES - NODES);
+ for ( int i = 0; i < maxEdges; i++)
+ {
+ while ( ! addEdge( vertices.get( r.nextInt(NODES) ), vertices.get( r.nextInt(NODES) ) ) ) {
+ // do nothing
}
}
}
- }
+
+ private boolean addEdge( BaseLabeledVertex src, BaseLabeledVertex dst )
+ {
+ try {
+ addEdge( new BaseLabeledWeightedEdge<Double>( format( "%s -> %s", src, dst ),
+ (double) r.nextInt(10) ) ).from( src ).to( dst );
+ return true;
+ } catch (GraphException e) {
+ // ignore duplicate edge exceptions
+ return false;
+ }
+ }
+ } );
}
@Test
public void performBoruvka()
{
SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
- minimumSpanningTree( G ).fromArbitrarySource().applyingBoruvkaAlgorithm( new DoubleWeightBaseOperations() );
+ minimumSpanningTree( graph ).fromArbitrarySource().applyingBoruvkaAlgorithm( new DoubleWeightBaseOperations() );
assertTrue( actual.getSize() > 0 );
}
@@ -95,7 +117,7 @@ public final class MinimumSpanningTreeBe
public void performKruskal()
{
SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
- minimumSpanningTree( G ).fromArbitrarySource().applyingKruskalAlgorithm( new DoubleWeightBaseOperations() );
+ minimumSpanningTree( graph ).fromArbitrarySource().applyingKruskalAlgorithm( new DoubleWeightBaseOperations() );
assertTrue( actual.getSize() > 0 );
}
@@ -104,7 +126,7 @@ public final class MinimumSpanningTreeBe
public void performPrim()
{
SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
- minimumSpanningTree( G ).fromArbitrarySource().applyingPrimAlgorithm( new DoubleWeightBaseOperations() );
+ minimumSpanningTree( graph ).fromArbitrarySource().applyingPrimAlgorithm( new DoubleWeightBaseOperations() );
assertTrue( actual.getSize() > 0 );
}
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=1296618&r1=1296617&r2=1296618&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 Sat Mar 3 13:00:48 2012
@@ -69,17 +69,19 @@ final class DefaultSpanningTreeAlgorithm
* <pre>
* procedure Boruvka MST(G(V; E)):
* T <= V
- * while |T| < n 1 do
+ * while |T| < n 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}
+ * T <= T u {e}
* end if
* end for
* end while
* <pre>
*/
+
checkNotNull( weightOperations, "The Boruvka algorithm cannot be calculated with null weight operations" );
+
final MutableSpanningTree<V, WE, W> spanningTree =
new MutableSpanningTree<V, WE, W>( weightOperations );
@@ -94,20 +96,23 @@ final class DefaultSpanningTreeAlgorithm
// create a super vertex for each vertex
final SuperVertex<V, W, WE, G, WO> sv =
new SuperVertex<V, W, WE, G, WO>( v, graph, weightOperations );
+
components.add( sv );
+
// add a mapping for each vertex to its corresponding super vertex
mapping.put( v, sv );
+
// add each vertex to the spanning tree
spanningTree.addVertex( v );
}
while ( components.size() > 1 )
{
- List<WE> edges = new LinkedList<WE>();
- for ( SuperVertex<V, W, WE, G, WO> v : components )
+ final List<WE> edges = new LinkedList<WE>();
+ for ( SuperVertex<V, W, WE, G, WO> sv : components )
{
// get the minimum edge for each component to any other component
- WE edge = v.getMinimumWeightEdge();
+ final WE edge = sv.getMinimumWeightEdge();
if ( edge != null )
{
edges.add( edge );
@@ -118,29 +123,29 @@ final class DefaultSpanningTreeAlgorithm
// the graph is unconnected
checkState( !edges.isEmpty() || components.size() == 1, "unconnected graph" );
- for ( WE edge : edges )
+ for ( final WE edge : edges )
{
- VertexPair<V> pair = graph.getVertices( edge );
- V head = pair.getHead();
- V tail = pair.getTail();
+ final VertexPair<V> pair = graph.getVertices( edge );
+ final V head = pair.getHead();
+ final V tail = pair.getTail();
// find the super vertices corresponding to this edge
- SuperVertex<V, W, WE, G, WO> headSuper = mapping.get( head );
- SuperVertex<V, W, WE, G, WO> tailSuper = mapping.get( tail );
+ final SuperVertex<V, W, WE, G, WO> headSv = mapping.get( head );
+ final SuperVertex<V, W, WE, G, WO> tailSv = mapping.get( tail );
// merge them, if they are not the same
- if ( headSuper != tailSuper )
+ if ( headSv != tailSv )
{
- headSuper.merge( tailSuper );
+ headSv.merge( tailSv );
// update the mapping for each merged vertex
- for ( V v : tailSuper )
+ for ( final V v : tailSv )
{
- mapping.put( v, headSuper );
+ mapping.put( v, headSv );
}
// remove the merged super vertex from the components set
- components.remove( tailSuper );
+ components.remove( tailSv );
// add the edge to the spanning tree
if ( spanningTree.getVertices( edge ) == null )
@@ -159,7 +164,6 @@ final class DefaultSpanningTreeAlgorithm
*/
public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( WO weightOperations )
{
-
checkNotNull( weightOperations, "The Kruskal algorithm cannot be calculated with null weight operations" );
final Set<V> settledNodes = new HashSet<V>();
@@ -207,7 +211,7 @@ final class DefaultSpanningTreeAlgorithm
public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( WO weightOperations )
{
checkNotNull( weightOperations, "The Prim algorithm cannot be calculated with null weight operations" );
-
+
final ShortestEdges<V, WE, W> shortestEdges = new ShortestEdges<V, WE, W>( graph, source, weightOperations );
final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( graph.getOrder(), shortestEdges );
@@ -226,8 +230,8 @@ final class DefaultSpanningTreeAlgorithm
// if the edge has not been already visited and its weight is
// less then the current Vertex weight
- boolean weightLessThanCurrent = !shortestEdges.hasWeight( v )
- || weightOperations.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
+ boolean weightLessThanCurrent = !shortestEdges.hasWeight( v ) ||
+ weightOperations.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
if ( settledEdges.add( edge ) && weightLessThanCurrent )
{
if ( !unsettledNodes.contains( v ) )
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java?rev=1296618&r1=1296617&r2=1296618&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java Sat Mar 3 13:00:48 2012
@@ -82,9 +82,9 @@ public final class DefaultSpanningTreeSo
*/
public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations )
{
-
+
checkNotNull( weightOperations, "The Reverse-Delete algorithm cannot be calulated with null weight operations" );
-
+
final List<WE> sortedEdge = new ArrayList<WE>();
final List<WE> visitedEdge = new ArrayList<WE>();
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java?rev=1296618&r1=1296617&r2=1296618&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java Sat Mar 3 13:00:48 2012
@@ -38,7 +38,7 @@ import org.apache.commons.graph.Weighted
* @param <W> the weight type
* @param <WE> the Graph weighted edges type
* @param <G> the input Graph type
- * @param <WC> the weight operations
+ * @param <WC> the weight operations
*/
class SuperVertex<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>, WC extends Comparator<W>>
implements Iterable<V> {
@@ -69,7 +69,7 @@ class SuperVertex<V extends Vertex, W, W
orderedEdges = new TreeSet<WE>( new WeightedEdgesComparator<W, WE>( weightComparator ) );
// add all edges for this vertex to the sorted set
- for ( V w : graph.getConnectedVertices( source )) {
+ for ( final V w : graph.getConnectedVertices( source )) {
WE edge = graph.getEdge( source, w );
orderedEdges.add( edge );
}
@@ -88,14 +88,13 @@ class SuperVertex<V extends Vertex, W, W
* @param other the {@link SuperVertex} to be merged into this
*/
public void merge( final SuperVertex<V, W, WE, G, WC> other ) {
- for ( V v : other.vertices ) {
+ for ( final V v : other.vertices ) {
vertices.add(v);
}
- for (WE edge : other.orderedEdges) {
- VertexPair<V> pair = graph.getVertices( edge );
- if ( !vertices.contains(pair.getHead()) ||
- !vertices.contains(pair.getTail()) ) {
+ for ( final WE edge : other.orderedEdges) {
+ final VertexPair<V> pair = graph.getVertices( edge );
+ if ( ! vertices.contains(pair.getHead()) || ! vertices.contains(pair.getTail()) ) {
orderedEdges.add( edge );
}
}
@@ -105,10 +104,19 @@ class SuperVertex<V extends Vertex, W, W
* Returns the edge with the minimum weight to other {@link SuperVertex}
* instances.
*
- * @return the minimum weight edge
+ * @return the minimum weight edge or <code>null</code> if there is no edge
*/
public WE getMinimumWeightEdge() {
- return orderedEdges.pollFirst();
+ boolean found = false;
+ WE edge = null;
+ while ( ! found && ! orderedEdges.isEmpty() ) {
+ edge = orderedEdges.pollFirst();
+ VertexPair<V> pair = graph.getVertices( edge );
+ if ( ! vertices.contains( pair.getHead() ) || ! vertices.contains( pair.getTail() ) ) {
+ found = true;
+ }
+ }
+ return edge;
}
}