Author: simonetripodi Date: Wed Jul 6 01:18:25 2011 New Revision: 1143237 URL: http://svn.apache.org/viewvc?rev=1143237&view=rev Log: added Kruskal's algorithm implementation, optimized by a simple DisjointSet (find-union) implementation as described on wikipedia [http://en.wikipedia.org/wiki/Disjoint-set_data_structure]
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java (with props) commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java (with props) commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java (with props) Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java?rev=1143237&view=auto ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java (added) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java Wed Jul 6 01:18:25 2011 @@ -0,0 +1,117 @@ +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 java.util.HashMap; +import java.util.Map; + +import org.apache.commons.graph.Vertex; + +/** + * Simple <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint-set</a> implementation. + * + * @param <V> the Graph vertices type. + */ +final class DisjointSet<V extends Vertex> +{ + + private final Map<V, DisjointSetNode<V>> disjointSets = new HashMap<V, DisjointSetNode<V>>(); + + /** + * Performs the find applying the <i>path compression</i>. + * + * @param vertex + * @return + */ + public V find( V vertex ) + { + DisjointSetNode<V> vertexNode = find( getNode( vertex ) ); + + if ( vertexNode == vertexNode.getParent() ) + { + return vertexNode.getVertex(); + } + + vertexNode.setParent( find( vertexNode.getParent() ) ); + + return vertexNode.getParent().getVertex(); + } + + /** + * Performs the find applying the <i>path compression</i>. + * + * @param node + * @return + */ + private DisjointSetNode<V> find( DisjointSetNode<V> node ) + { + if ( node == node.getParent() ) + { + return node; + } + return find( node.getParent() ); + } + + /** + * Performs the merge by applying the <i>union by rank</i>. + * + * @param u + * @param v + */ + public void union( V u, V v ) + { + DisjointSetNode<V> uRoot = find( getNode( u ) ); + DisjointSetNode<V> vRoot = find( getNode( v ) ); + + if ( uRoot == vRoot ) + { + return; + } + + int comparison = uRoot.compareTo( vRoot ); + if ( comparison < 0 ) + { + uRoot.setParent( vRoot ); + } + else if ( comparison > 0 ) + { + vRoot.setParent( uRoot ); + } + else + { + vRoot.setParent( uRoot ); + uRoot.increaseRank(); + } + } + + private DisjointSetNode<V> getNode( V vertex ) + { + DisjointSetNode<V> node = disjointSets.get( vertex ); + + if ( node == null ) + { + node = new DisjointSetNode<V>( vertex ); + disjointSets.put( vertex, node ); + } + + return node; + } + +} Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java ------------------------------------------------------------------------------ svn:keywords = Date Author Id Revision HeadURL Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSet.java ------------------------------------------------------------------------------ svn:mime-type = text/plain Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java?rev=1143237&view=auto ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java (added) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java Wed Jul 6 01:18:25 2011 @@ -0,0 +1,87 @@ +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.Vertex; + +/** + * The {@link DisjointSet} internal node representation. + * + * @param <V> the Graph vertices type. + */ +final class DisjointSetNode<V extends Vertex> + implements Comparable<DisjointSetNode<V>> +{ + + private final V vertex; + + private DisjointSetNode<V> parent = this; + + private Integer rank = 0; + + /** + * + * + * @param vertex + */ + public DisjointSetNode( V vertex ) + { + this.vertex = vertex; + } + + public V getVertex() + { + return vertex; + } + + public DisjointSetNode<V> getParent() + { + return parent; + } + + public void setParent( DisjointSetNode<V> parent ) + { + this.parent = parent; + } + + public Integer getRank() + { + return rank; + } + + public void increaseRank() + { + rank++; + } + + public void setRank( int rank ) + { + this.rank = rank; + } + + /** + * {@inheritDoc} + */ + public int compareTo( DisjointSetNode<V> o ) + { + return rank.compareTo( o.getRank() ); + } + +} Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java ------------------------------------------------------------------------------ svn:keywords = Date Author Id Revision HeadURL Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DisjointSetNode.java ------------------------------------------------------------------------------ svn:mime-type = text/plain Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java?rev=1143237&r1=1143236&r2=1143237&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java (original) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java Wed Jul 6 01:18:25 2011 @@ -19,10 +19,16 @@ package org.apache.commons.graph.spannin * under the License. */ -import org.apache.commons.graph.Graph; +import java.util.HashSet; +import java.util.PriorityQueue; +import java.util.Set; + +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.WeightedGraph; +import org.apache.commons.graph.model.MutableSpanningTree; /** * Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree @@ -39,9 +45,46 @@ public final class Kruskal * @param graph the Graph for which minimum spanning tree (or forest) has to be calculated. * @return the minimum spanning tree (or forest) of the input Graph. */ - public static <V extends Vertex, WE extends WeightedEdge> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph ) + public static <V extends Vertex, WE extends WeightedEdge> SpanningTree<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph ) { - return null; + final Set<V> settledNodes = new HashSet<V>(); + + final PriorityQueue<WE> orderedEdges = new PriorityQueue<WE>( graph.getSize() ); + + for ( WE edge : graph.getEdges() ) + { + orderedEdges.add( edge ); + } + + final DisjointSet<V> disjointSet = new DisjointSet<V>(); + + MutableSpanningTree<V, WE> spanningTree = new MutableSpanningTree<V, WE>(); + + while ( settledNodes.size() < graph.getOrder() ) + { + WE edge = orderedEdges.poll(); + + 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; } } Added: 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=1143237&view=auto ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java (added) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java Wed Jul 6 01:18:25 2011 @@ -0,0 +1,104 @@ +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 org.apache.commons.graph.spanning.Kruskal.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.junit.Test; + +public final class KruskalTestCase +{ + + /** + * Test Graph and Prim's solution can be seen on + * <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm">Wikipedia</a> + */ + @Test + public void verifyWikipediaMinimumSpanningTree() + { + UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> input + = new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>(); + + 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( "a <-> b", 7D ), b ); + input.addEdge( a, new BaseLabeledWeightedEdge( "a <-> d", 5D ), d ); + + input.addEdge( b, new BaseLabeledWeightedEdge( "b <-> c", 8D ), c ); + input.addEdge( b, new BaseLabeledWeightedEdge( "b <-> d", 9D ), d ); + input.addEdge( b, new BaseLabeledWeightedEdge( "b <-> e", 7D ), e ); + + input.addEdge( c, new BaseLabeledWeightedEdge( "c <-> e", 5D ), e ); + + input.addEdge( d, new BaseLabeledWeightedEdge( "d <-> e", 15D ), e ); + input.addEdge( d, new BaseLabeledWeightedEdge( "d <-> f", 6D ), f ); + + input.addEdge( e, new BaseLabeledWeightedEdge( "e <-> f", 8D ), f ); + input.addEdge( e, new BaseLabeledWeightedEdge( "e <-> g", 9D ), g ); + + input.addEdge( f, new BaseLabeledWeightedEdge( "f <-> g", 11D ), g ); + + // expected + + MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> expected = + new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge>(); + + for ( BaseLabeledVertex vertex : input.getVertices() ) + { + expected.addVertex( vertex ); + } + + expected.addEdge( a, new BaseLabeledWeightedEdge( "a <-> b", 7D ), b ); + expected.addEdge( a, new BaseLabeledWeightedEdge( "a <-> d", 5D ), d ); + expected.addEdge( b, new BaseLabeledWeightedEdge( "b <-> e", 9D ), e ); + expected.addEdge( c, new BaseLabeledWeightedEdge( "c <-> e", 5D ), e ); + expected.addEdge( d, new BaseLabeledWeightedEdge( "d <-> f", 6D ), f ); + expected.addEdge( e, new BaseLabeledWeightedEdge( "e <-> g", 9D ), g ); + + // Actual + + SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = minimumSpanningTree( input ); + + // assert! + + assertEquals( expected, actual ); + } + +} Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java ------------------------------------------------------------------------------ svn:keywords = Date Author Id Revision HeadURL Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java ------------------------------------------------------------------------------ svn:mime-type = text/plain