commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1296618 - in /commons/sandbox/graph/trunk/src: benchmarks/java/org/apache/commons/graph/spanning/ main/java/org/apache/commons/graph/spanning/
Date Sat, 03 Mar 2012 13:00:49 GMT
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;
     }
 
 }



Mime
View raw message