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/25 20:43:55 UTC
svn commit: r1235883 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/
main/java/org/apache/commons/graph/spanning/
test/java/org/apache/commons/graph/spanning/
Author: simonetripodi
Date: Wed Jan 25 19:43:54 2012
New Revision: 1235883
URL: http://svn.apache.org/viewvc?rev=1235883&view=rev
Log:
moved spanning tree algorithms to fluent APIs
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java (with props)
Removed:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Boruvka.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java?rev=1235883&r1=1235882&r2=1235883&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java Wed Jan 25 19:43:54 2012
@@ -36,6 +36,8 @@ import org.apache.commons.graph.model.Un
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
import org.apache.commons.graph.scc.DefaultSccAlgorithmSelector;
import org.apache.commons.graph.scc.SccAlgorithmSelector;
+import org.apache.commons.graph.spanning.DefaultSpanningTreeSourceSelector;
+import org.apache.commons.graph.spanning.SpanningTreeSourceSelector;
import org.apache.commons.graph.visit.DefaultVisitSourceSelector;
import org.apache.commons.graph.visit.VisitSourceSelector;
@@ -79,6 +81,17 @@ public final class CommonsGraph<V extend
}
/**
+ *
+ * @param graph
+ * @return
+ */
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>> SpanningTreeSourceSelector<V, W, WE, G> minimumSpanningTree( G graph )
+ {
+ graph = checkNotNull( graph, "Minimum spanning tree can not be calculated on null graph" );
+ return new DefaultSpanningTreeSourceSelector<V, W, WE, G>( graph );
+ }
+
+ /**
* Calculates the input graph Strongly Connected Component.
*
* @param <V> the Graph vertices type.
Added: 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=1235883&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java Wed Jan 25 19:43:54 2012
@@ -0,0 +1,145 @@
+package org.apache.commons.graph.spanning;
+
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.PriorityQueue;
+import java.util.Set;
+
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.collections.DisjointSet;
+import org.apache.commons.graph.model.MutableSpanningTree;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+final class DefaultSpanningTreeAlgorithmSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+ implements SpanningTreeAlgorithmSelector<V, W, WE, G>
+{
+
+ private final G graph;
+
+ private final V source;
+
+ public DefaultSpanningTreeAlgorithmSelector( G graph, V source )
+ {
+ this.graph = graph;
+ this.source = source;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( OM orderedMonoid )
+ {
+ // TODO Boruvka still needs to be implemented
+ return null;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( OM orderedMonoid )
+ {
+ final Set<V> settledNodes = new HashSet<V>();
+
+ final PriorityQueue<WE> orderedEdges = new PriorityQueue<WE>( graph.getSize(),
+ new WeightedEdgesComparator<W, WE>( orderedMonoid ) );
+
+ for ( WE edge : graph.getEdges() )
+ {
+ orderedEdges.add( edge );
+ }
+
+ final DisjointSet<V> disjointSet = new DisjointSet<V>();
+
+ MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
+
+ while ( 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 );
+ }
+
+ if ( !disjointSet.find( head ).equals( disjointSet.find( tail ) ) )
+ {
+ disjointSet.union( head, tail );
+ spanningTree.addEdge( head, edge, tail );
+ }
+ }
+
+ return spanningTree;
+ }
+
+ private static class WeightedEdgesComparator<W, WE extends WeightedEdge<W>> implements Comparator<WE>
+ {
+
+ private final OrderedMonoid<W> orderedMonoid;
+
+ public WeightedEdgesComparator( OrderedMonoid<W> orderedMonoid )
+ {
+ this.orderedMonoid = orderedMonoid;
+ }
+
+ public int compare( WE o1, WE o2 )
+ {
+ return orderedMonoid.compare( o1.getWeight(), o2.getWeight() );
+ }
+
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( OM orderedMonoid )
+ {
+ final ShortestEdges<V, WE, W> shortestEdges = new ShortestEdges<V, WE, W>( graph, source, orderedMonoid );
+
+ final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( graph.getOrder(), shortestEdges );
+ unsettledNodes.add( source );
+
+ final Set<WE> settledEdges = new HashSet<WE>();
+
+ // extract the node with the shortest distance
+ while ( !unsettledNodes.isEmpty() )
+ {
+ V vertex = unsettledNodes.remove();
+
+ for ( V v : graph.getConnectedVertices( vertex ) )
+ {
+ 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 )
+ || orderedMonoid.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
+ if ( settledEdges.add( edge ) && weightLessThanCurrent )
+ {
+ if ( !unsettledNodes.contains( v ) )
+ {
+ unsettledNodes.add( v );
+ }
+
+ shortestEdges.addPredecessor( v, edge );
+ }
+ }
+ }
+
+ return shortestEdges.createSpanningTree();
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: 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=1235883&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java Wed Jan 25 19:43:54 2012
@@ -0,0 +1,39 @@
+package org.apache.commons.graph.spanning;
+
+import static org.apache.commons.graph.utils.Assertions.checkNotNull;
+
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+
+public final class DefaultSpanningTreeSourceSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+ implements SpanningTreeSourceSelector<V, W, WE, G>
+{
+
+ private final G graph;
+
+ public DefaultSpanningTreeSourceSelector( G graph )
+ {
+ this.graph = graph;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public SpanningTreeAlgorithmSelector<V, W, WE, G> fromArbitrarySource()
+ {
+ return fromSource( graph.getVertices().iterator().next() );
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public SpanningTreeAlgorithmSelector<V, W, WE, G> fromSource( V source )
+ {
+ source = checkNotNull( source, "Spanning tree cannot be calculated without expressing the source vertex" );
+ return new DefaultSpanningTreeAlgorithmSelector<V, W, WE, G>( graph, source );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java?rev=1235883&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java Wed Jan 25 19:43:54 2012
@@ -0,0 +1,37 @@
+package org.apache.commons.graph.spanning;
+
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+/*
+ * 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.
+ */
+
+public interface SpanningTreeAlgorithmSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+{
+
+ <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( OM orderedMonoid );
+
+ <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( OM orderedMonoid );
+
+ <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( OM orderedMonoid );
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java?rev=1235883&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java Wed Jan 25 19:43:54 2012
@@ -0,0 +1,33 @@
+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 org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+
+public interface SpanningTreeSourceSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+{
+
+ SpanningTreeAlgorithmSelector<V, W, WE, G> fromArbitrarySource();
+
+ SpanningTreeAlgorithmSelector<V, W, WE, G> fromSource( V source );
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
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=1235883&r1=1235882&r2=1235883&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 Wed Jan 25 19:43:54 2012
@@ -20,7 +20,7 @@ package org.apache.commons.graph.spannin
*/
import static junit.framework.Assert.assertEquals;
-import static org.apache.commons.graph.spanning.Kruskal.minimumSpanningTree;
+import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
import org.apache.commons.graph.SpanningTree;
import org.apache.commons.graph.model.BaseLabeledVertex;
@@ -95,8 +95,8 @@ public final class KruskalTestCase
// Actual
- SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual = minimumSpanningTree( input );
-
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual = minimumSpanningTree( input ).fromArbitrarySource().applyingKruskalAlgorithm( new DoubleWeight() );
+
// assert!
assertEquals( expected, actual );
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java?rev=1235883&r1=1235882&r2=1235883&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java Wed Jan 25 19:43:54 2012
@@ -20,7 +20,7 @@ package org.apache.commons.graph.spannin
*/
import static junit.framework.Assert.assertEquals;
-import static org.apache.commons.graph.spanning.Prim.minimumSpanningTree;
+import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
import org.apache.commons.graph.SpanningTree;
import org.apache.commons.graph.model.BaseLabeledVertex;
@@ -165,7 +165,7 @@ public final class PrimTestCase
{
// actual
- SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual = minimumSpanningTree( input, source );
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual = minimumSpanningTree( input ).fromSource( source ).applyingPrimAlgorithm( new DoubleWeight() );
// assert!