Author: simonetripodi
Date: Tue Jul 5 15:19:02 2011
New Revision: 1143097
URL: http://svn.apache.org/viewvc?rev=1143097&view=rev
Log:
fixed Prim's algorithm implementation + TestCase
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
(with props)
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
(with props)
Modified:
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/spanning/Prim.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java?rev=1143097&r1=1143096&r2=1143097&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java
(original)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java
Tue Jul 5 15:19:02 2011
@@ -23,11 +23,11 @@ import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
-import org.apache.commons.graph.DirectedGraph;
+import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.UndirectedGraph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedGraph;
-import org.apache.commons.graph.shared.ShortestDistances;
/**
* Prim's algorithm is a greedy algorithm that finds a minimum spanning tree
for a connected weighted undirected graph.
@@ -43,47 +43,39 @@ public final class Prim
* @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> WeightedGraph<V,
WE> minimumSpanningTree( WeightedGraph<V, WE> graph,
-
V source )
+ public static <V extends Vertex, WE extends WeightedEdge, G extends
WeightedGraph<V, WE> & UndirectedGraph<V, WE>> SpanningTree<V, WE>
minimumSpanningTree( G graph,
+
V source )
{
- final ShortestDistances<V> shortestDistances = new
ShortestDistances<V>();
- shortestDistances.setWeight( source, 0D );
+ final ShortestEdges<V, WE> shortesEdges = new ShortestEdges<V, WE>(
graph, source );
- final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>(
graph.getOrder(), shortestDistances );
+ final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>(
graph.getOrder(), shortesEdges );
unsettledNodes.offer( source );
- final Set<V> settledNodes = new HashSet<V>();
+ final Set<WE> settledEdges = new HashSet<WE>();
// extract the node with the shortest distance
while ( !unsettledNodes.isEmpty() )
{
V vertex = unsettledNodes.poll();
- @SuppressWarnings( "unchecked" ) // Vertex/Edge type driven by
input class
- Iterable<V> connectedVertices = ( graph instanceof DirectedGraph )
- ? ( ( DirectedGraph<V, WE> ) graph
).getOutbound( vertex )
- : graph.getConnectedVertices(
vertex );
-
- for ( V v : connectedVertices )
+ for ( V v : graph.getConnectedVertices( vertex ) )
{
- // skip node already settled
- if ( !settledNodes.contains( v ) )
- {
- WE edge = graph.getEdge( vertex, v );
+ WE edge = graph.getEdge( vertex, v );
- if ( edge.getWeight().compareTo(
shortestDistances.getWeight( v ) ) < 0 )
+ // if the edge has not been already visited and its weight is
less then the current Vertex weight
+ if ( settledEdges.add( edge ) && edge.getWeight().compareTo(
shortesEdges.getWeight( v ) ) < 0 )
+ {
+ if ( !unsettledNodes.contains( v ) )
{
- // assign new shortest distance and mark unsettled
- shortestDistances.setWeight( v, edge.getWeight() );
unsettledNodes.offer( v );
-
- // TODO assign predecessor in shortest path
}
+
+ shortesEdges.addPredecessor( v, edge );
}
}
}
- return null;
+ return shortesEdges.createSpanningTree();
}
}
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java?rev=1143097&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
(added)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
Tue Jul 5 15:19:02 2011
@@ -0,0 +1,157 @@
+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.Comparator;
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.GraphException;
+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.model.MutableSpanningTree;
+
+/**
+ * The predecessor list is a list of {@link Vertex} of a {@link
org.apache.commons.graph.Graph}.
+ * Each {@link Vertex}' entry contains the index of its predecessor in a path
through the graph.
+ *
+ * @param <V> the Graph vertices type
+ * @param <E> the Graph edges type
+ */
+final class ShortestEdges<V extends Vertex, WE extends WeightedEdge>
+ implements Comparator<V>
+{
+
+ private final Map<V, WE> predecessors = new HashMap<V, WE>();
+
+ private final Graph<V, WE> graph;
+
+ private final V source;
+
+ public ShortestEdges(Graph<V, WE> graph, V source )
+ {
+ this.graph = graph;
+ this.source = source;
+ }
+
+ /**
+ * Add an {@link Edge} in the predecessor list associated to the input
{@link Vertex}.
+ *
+ * @param tail the predecessor vertex
+ * @param head the edge that succeeds to the input vertex
+ */
+ public void addPredecessor( V tail, WE head )
+ {
+ predecessors.put( tail, head );
+ }
+
+ /**
+ *
+ *
+ * @return
+ */
+ public SpanningTree<V, WE> createSpanningTree()
+ {
+ MutableSpanningTree<V, WE> spanningTree = new MutableSpanningTree<V,
WE>();
+
+ for ( WE edge : this.predecessors.values() )
+ {
+ VertexPair<V> vertices = graph.getVertices( edge );
+
+ V head = vertices.getHead();
+ V tail = vertices.getTail();
+
+ addEdgeIgnoringExceptions( head, spanningTree );
+ addEdgeIgnoringExceptions( tail, spanningTree );
+
+ spanningTree.addEdge( head, graph.getEdge( head, tail ), tail );
+ }
+
+ return spanningTree;
+ }
+
+ private static <V extends Vertex, WE extends WeightedEdge> void
addEdgeIgnoringExceptions( V vertex,
+
MutableSpanningTree<V, WE> spanningTree )
+ {
+ try
+ {
+ spanningTree.addVertex( vertex );
+ }
+ catch ( GraphException e )
+ {
+ // just swallow it
+ }
+ }
+
+ /**
+ * Checks the predecessor list has no elements.
+ *
+ * @return true, if the predecessor list has no elements, false otherwise.
+ */
+ public boolean isEmpty()
+ {
+ return predecessors.isEmpty();
+ }
+
+ /**
+ * Returns the distance related to input vertex, or {@code INFINITY} if it
wasn't previously visited.
+ *
+ * @param vertex the vertex for which the distance has to be retrieved
+ * @return the distance related to input vertex, or {@code INFINITY} if it
wasn't previously visited.
+ */
+ public Double getWeight( V vertex )
+ {
+ if ( source.equals( vertex ) )
+ {
+ return 0D;
+ }
+
+ WE edge = predecessors.get( vertex );
+
+ if ( edge == null )
+ {
+ return Double.POSITIVE_INFINITY;
+ }
+
+ return edge.getWeight();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int compare( V left, V right )
+ {
+ return getWeight( left ).compareTo( getWeight( right ) );
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public String toString()
+ {
+ return predecessors.toString();
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added:
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=1143097&view=auto
==============================================================================
---
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
(added)
+++
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
Tue Jul 5 15:19:02 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.Prim.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 PrimTestCase
+{
+
+ /**
+ * Test Graph and Prim's solution can be seen on these
+ * <a
href="http://gauguin.info.uniroma2.it/~italiano/Teaching/Algoritmi/Lezioni/cap12.pdf";>slides</a>
+ */
+ @Test
+ public void verifyMinimumSpanningTree2()
+ {
+ 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 <-> c", 14D ), c );
+ input.addEdge( a, new BaseLabeledWeightedEdge( "a <-> d", 30D ), d );
+
+ input.addEdge( b, new BaseLabeledWeightedEdge( "b <-> c", 21D ), c );
+
+ input.addEdge( c, new BaseLabeledWeightedEdge( "c <-> d", 10D ), d );
+ input.addEdge( c, new BaseLabeledWeightedEdge( "c <-> e", 1D ), e );
+
+ input.addEdge( e, new BaseLabeledWeightedEdge( "e <-> f", 6D ), f );
+ input.addEdge( e, new BaseLabeledWeightedEdge( "e <-> g", 9D ), g );
+
+ input.addEdge( f, new BaseLabeledWeightedEdge( "f <-> g", 4D ), 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 <-> c", 14D ), c
);
+
+ expected.addEdge( c, new BaseLabeledWeightedEdge( "c <-> d", 10D ), d
);
+ expected.addEdge( c, new BaseLabeledWeightedEdge( "c <-> e", 1D ), e );
+
+ expected.addEdge( e, new BaseLabeledWeightedEdge( "e <-> f", 6D ), f );
+
+ expected.addEdge( f, new BaseLabeledWeightedEdge( "f <-> g", 4D ), g );
+
+ // actual
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual =
minimumSpanningTree( input, a );
+
+ // assert!
+
+ assertEquals( expected, actual );
+ }
+
+}
Propchange:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
