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/26 22:26:02 UTC
svn commit: r1236387 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/spanning/
test/java/org/apache/commons/graph/spanning/
Author: simonetripodi
Date: Thu Jan 26 21:26:02 2012
New Revision: 1236387
URL: http://svn.apache.org/viewvc?rev=1236387&view=rev
Log:
[SANDBOX-350] Provide a Reverse-delete algorithm implementation - patch provided by Marco Speranza
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java (with props)
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.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
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/SpanningTreeSourceSelector.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=1236387&r1=1236386&r2=1236387&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Thu Jan 26 21:26:02 2012
@@ -47,6 +47,9 @@
<action dev="simonetripodi" type="update" issue="SANDBOX-356" due-to="Claudio Squarcella">
Generic weight types and algorithms implementations based on wighted graphes.
</action>
+ <action dev="simonetripodi" type="fix" issue="SANDBOX-350" due-to="Marco Speranza">
+ Provide a Reverse-delete algorithm implementation
+ </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=1236387&r1=1236386&r2=1236387&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 Thu Jan 26 21:26:02 2012
@@ -19,7 +19,6 @@ package org.apache.commons.graph.spannin
* under the License.
*/
-import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
@@ -58,7 +57,6 @@ final class DefaultSpanningTreeAlgorithm
/**
* {@inheritDoc}
*/
- @Override
public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( OM orderedMonoid )
{
// TODO Boruvka still needs to be implemented
@@ -68,7 +66,6 @@ final class DefaultSpanningTreeAlgorithm
/**
* {@inheritDoc}
*/
- @Override
public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( OM orderedMonoid )
{
final Set<V> settledNodes = new HashSet<V>();
@@ -112,27 +109,9 @@ final class DefaultSpanningTreeAlgorithm
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 );
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=1236387&r1=1236386&r2=1236387&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 Thu Jan 26 21:26:02 2012
@@ -19,11 +19,23 @@ package org.apache.commons.graph.spannin
* under the License.
*/
+import static java.util.Collections.reverseOrder;
+import static java.util.Collections.sort;
+import static org.apache.commons.graph.shortestpath.Dijkstra.findShortestPath;
import static org.apache.commons.graph.utils.Assertions.checkNotNull;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
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.model.MutableSpanningTree;
+import org.apache.commons.graph.shortestpath.PathNotFoundException;
+import org.apache.commons.graph.weight.OrderedMonoid;
/**
* {@link SpanningTreeSourceSelector} implementation.
@@ -61,4 +73,58 @@ public final class DefaultSpanningTreeSo
return new DefaultSpanningTreeAlgorithmSelector<V, W, WE, G>( graph, source );
}
+ /**
+ * {@inheritDoc}
+ */
+ public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( OM orderedMonoid )
+ {
+ final List<WE> sortedEdge = new ArrayList<WE>();
+ final List<WE> visitedEdge = new ArrayList<WE>();
+
+ Iterable<WE> edges = graph.getEdges();
+ for ( WE we : edges )
+ {
+ sortedEdge.add( we );
+ }
+
+ sort( sortedEdge, reverseOrder( new WeightedEdgesComparator<W, WE>( orderedMonoid ) ) );
+
+ Graph<V, WE> tmpGraph = new ReverseDeleteGraph<V, WE, W>( graph, sortedEdge, visitedEdge );
+
+ for ( Iterator<WE> iterator = sortedEdge.iterator(); iterator.hasNext(); )
+ {
+ WE we = iterator.next();
+ iterator.remove();
+
+ VertexPair<V> vertices = graph.getVertices( we );
+
+ try
+ {
+ findShortestPath( tmpGraph, vertices.getHead(), vertices.getTail(), orderedMonoid );
+ }
+ catch ( PathNotFoundException ex )
+ {
+ // only if a path doesn't exist
+ visitedEdge.add( we );
+ }
+ }
+
+ final MutableSpanningTree<V, WE, W> res = new MutableSpanningTree<V, WE, W>( orderedMonoid );
+ for ( V v : graph.getVertices() )
+ {
+ res.addVertex( v );
+ }
+
+ for ( WE we : edges )
+ {
+ VertexPair<V> pair = tmpGraph.getVertices( we );
+ if ( pair != null )
+ {
+ res.addEdge( pair.getHead(), we, pair.getTail() );
+ }
+ }
+
+ return res;
+ }
+
}
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java?rev=1236387&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java Thu Jan 26 21:26:02 2012
@@ -0,0 +1,135 @@
+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.GraphException;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ *
+ * @param <V>
+ * @param <WE>
+ * @param <W>
+ */
+final class ReverseDeleteGraph<V extends Vertex, WE extends WeightedEdge<W>, W>
+ implements Graph<V, WE>
+{
+
+ private final Graph<V, WE> graph;
+
+ private final List<WE> sortedEdge;
+
+ private final List<WE> visitedEdge;
+
+ public ReverseDeleteGraph( Graph<V, WE> graph, List<WE> sortedEdge, List<WE> visitedEdge )
+ {
+ this.graph = graph;
+ this.sortedEdge = sortedEdge;
+ this.visitedEdge = visitedEdge;
+ }
+
+ public Iterable<V> getVertices()
+ {
+ return graph.getVertices();
+ }
+
+ public int getOrder()
+ {
+ return graph.getOrder();
+ }
+
+ public Iterable<WE> getEdges()
+ {
+ List<WE> e = new ArrayList<WE>();
+ e.addAll( sortedEdge );
+ e.addAll( visitedEdge );
+ return e;
+ }
+
+ public int getSize()
+ {
+ return sortedEdge.size() + visitedEdge.size();
+ }
+
+ public int getDegree( V v )
+ {
+ throw new GraphException( "Unused Method" );
+ }
+
+ public Iterable<V> getConnectedVertices( V v )
+ {
+
+ List<V> tmp = new ArrayList<V>();
+ for ( V originalVertex : graph.getConnectedVertices( v ) )
+ {
+ if ( getEdge( v, originalVertex ) != null )
+ {
+ tmp.add( originalVertex );
+ }
+ }
+
+ return tmp;
+ }
+
+ public WE getEdge( V source, V target )
+ {
+ WE edge = graph.getEdge( source, target );
+ if ( sortedEdge.contains( edge ) )
+ {
+ return edge;
+ }
+
+ if ( visitedEdge.contains( edge ) )
+ {
+ return edge;
+ }
+ return null;
+ }
+
+ public VertexPair<V> getVertices( WE e )
+ {
+ for ( WE edge : sortedEdge )
+ {
+ if ( edge.equals( e ) )
+ {
+ return graph.getVertices( e );
+
+ }
+ }
+
+ if ( sortedEdge.contains( e ) )
+ {
+ return graph.getVertices( e );
+ }
+
+ if ( visitedEdge.contains( e ) )
+ {
+ return graph.getVertices( e );
+ }
+ return null;
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: 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=1236387&r1=1236386&r2=1236387&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java Thu Jan 26 21:26:02 2012
@@ -20,8 +20,10 @@ package org.apache.commons.graph.spannin
*/
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;
/**
* Spanning Tree source selector.
@@ -49,4 +51,25 @@ public interface SpanningTreeSourceSelec
*/
SpanningTreeAlgorithmSelector<V, W, WE, G> fromSource( V source );
+ /**
+ * Applies the <a href="http://en.wikipedia.org/wiki/Reverse-Delete_algorithm">Reverse-Delete</a> algorithm.
+ *
+ * <pre>
+ * function ReverseDelete(edges[] E)
+ * sort E in decreasing order
+ * Define an index i = 0
+ * while i < size(E)
+ * Define edge temp = E[i]
+ * delete E[i]
+ * if temp.v1 is not connected to temp.v2
+ * E[i] = temp
+ * i = i + 1
+ * return edges[] E
+ * </pre>
+ *
+ * @param orderedMonoid the graph weights monoid
+ * @return the calculated spanning tree
+ */
+ <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( OM orderedMonoid );
+
}
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java?rev=1236387&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java Thu Jan 26 21:26:02 2012
@@ -0,0 +1,48 @@
+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.WeightedEdge;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+import java.util.Comparator;
+
+/**
+ *
+ * @param <W>
+ * @param <WE>
+ */
+public 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() );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java?rev=1236387&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java Thu Jan 26 21:26:02 2012
@@ -0,0 +1,193 @@
+package org.apache.commons.graph.spanning;
+
+import static junit.framework.Assert.assertEquals;
+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 class ReverseDeleteTestCase
+{
+
+ /**
+ * Test Graph and Reverse-Delete Algorithm
+ */
+ @Test
+ public void verifyMinimumSpanningTree()
+ {
+ 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" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 7D ), b );
+ input.addEdge( b, new BaseLabeledWeightedEdge<Double>( "b <-> c", 21D ), c );
+ input.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> a", 4D ), a );
+
+ // 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( c, new BaseLabeledWeightedEdge<Double>( "c <-> a", 4D ), a );
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
+ minimumSpanningTree( input ).applyingReverseDeleteAlgorithm( new DoubleWeight() );
+ assertEquals( expected, actual );
+ }
+
+ /**
+ * Test Graph and Reverse-Delete Algorithm
+ */
+ @Test
+ public void verifyNotConnectGraph()
+ {
+ 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" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+
+ // expected
+
+ MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> expected =
+ new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>( new DoubleWeight() );
+
+ for ( BaseLabeledVertex vertex : input.getVertices() )
+ {
+ expected.addVertex( vertex );
+ }
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
+ minimumSpanningTree( input ).applyingReverseDeleteAlgorithm( new DoubleWeight() );
+ assertEquals( expected, actual );
+ }
+
+ /**
+ * Test Graph and Reverse-Delete Algorithm
+ */
+ @Test
+ public void verifyNotConnectGraph2()
+ {
+ 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" );
+
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+ input.addVertex( d );
+ input.addVertex( e );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 7D ), b );
+ input.addEdge( b, new BaseLabeledWeightedEdge<Double>( "b <-> c", 21D ), c );
+ input.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> a", 4D ), a );
+
+ input.addEdge( d, new BaseLabeledWeightedEdge<Double>( "d <-> e", 4D ), e );
+
+ // 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( c, new BaseLabeledWeightedEdge<Double>( "c <-> a", 4D ), a );
+
+ expected.addEdge( d, new BaseLabeledWeightedEdge<Double>( "d <-> e", 4D ), e );
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
+ minimumSpanningTree( input ).applyingReverseDeleteAlgorithm( new DoubleWeight() );
+ assertEquals( expected, actual );
+ }
+
+
+ /**
+ * Test Graph and Reverse-Delete Algorithm
+ */
+ @Test
+ public void verifyNotConnectGraph3()
+ {
+ 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" );
+
+
+ input.addVertex( a );
+ input.addVertex( b );
+ input.addVertex( c );
+ input.addVertex( d );
+ input.addVertex( e );
+ input.addVertex( f );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 7D ), b );
+ input.addEdge( b, new BaseLabeledWeightedEdge<Double>( "b <-> c", 21D ), c );
+ input.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> a", 4D ), a );
+
+ input.addEdge( d, new BaseLabeledWeightedEdge<Double>( "d <-> e", 7D ), e );
+ input.addEdge( e, new BaseLabeledWeightedEdge<Double>( "e <-> f", 21D ), f );
+ input.addEdge( f, new BaseLabeledWeightedEdge<Double>( "f <-> d", 4D ), d );
+
+ // 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( c, new BaseLabeledWeightedEdge<Double>( "c <-> a", 4D ), a );
+
+ expected.addEdge( d, new BaseLabeledWeightedEdge<Double>( "d <-> e", 4D ), e );
+ expected.addEdge( f, new BaseLabeledWeightedEdge<Double>( "f <-> d", 4D ), d );
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
+ minimumSpanningTree( input ).applyingReverseDeleteAlgorithm( new DoubleWeight() );
+ assertEquals( expected, actual );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain