Return-Path: 
 <commits-return-25033-apmail-commons-commits-archive=commons.apache.org@commons.apache.org>
X-Original-To: apmail-commons-commits-archive@minotaur.apache.org
Delivered-To: apmail-commons-commits-archive@minotaur.apache.org
Received: from mail.apache.org (hermes.apache.org [140.211.11.3])
	by minotaur.apache.org (Postfix) with SMTP id 69D2B9D0E
	for <apmail-commons-commits-archive@minotaur.apache.org>;
 Tue, 31 Jan 2012 16:50:59 +0000 (UTC)
Received: (qmail 76739 invoked by uid 500); 31 Jan 2012 16:50:59 -0000
Delivered-To: apmail-commons-commits-archive@commons.apache.org
Received: (qmail 76617 invoked by uid 500); 31 Jan 2012 16:50:58 -0000
Mailing-List: contact commits-help@commons.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:commits-help@commons.apache.org>
List-Unsubscribe: <mailto:commits-unsubscribe@commons.apache.org>
List-Post: <mailto:commits@commons.apache.org>
List-Id: <commits.commons.apache.org>
Reply-To: dev@commons.apache.org
Delivered-To: mailing list commits@commons.apache.org
Received: (qmail 76610 invoked by uid 99); 31 Jan 2012 16:50:58 -0000
Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136)
    by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 31 Jan 2012 16:50:58 +0000
X-ASF-Spam-Status: No, hits=-2000.0 required=5.0
	tests=ALL_TRUSTED
X-Spam-Check-By: apache.org
Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4)
    by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 31 Jan 2012 16:50:56 +0000
Received: from eris.apache.org (localhost [127.0.0.1])
	by eris.apache.org (Postfix) with ESMTP id 9AC7423889B8
	for <commits@commons.apache.org>; Tue, 31 Jan 2012 16:50:36 +0000 (UTC)
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: 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
Date: Tue, 31 Jan 2012 16:50:36 -0000
To: commits@commons.apache.org
From: simonetripodi@apache.org
X-Mailer: svnmailer-1.0.8-patched
Message-Id: <20120131165036.9AC7423889B8@eris.apache.org>

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