commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1236387 - in /commons/sandbox/graph/trunk/src: changes/ main/java/org/apache/commons/graph/spanning/ test/java/org/apache/commons/graph/spanning/
Date Thu, 26 Jan 2012 21:26:02 GMT
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



Mime
View raw message