commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From marcospera...@apache.org
Subject svn commit: r1360092 - in /commons/sandbox/graph/trunk/src: changes/ main/java/org/apache/commons/graph/collections/ main/java/org/apache/commons/graph/spanning/ test/java/org/apache/commons/graph/collections/ test/java/org/apache/commons/graph/spanning/
Date Wed, 11 Jul 2012 09:59:01 GMT
Author: marcosperanza
Date: Wed Jul 11 09:59:00 2012
New Revision: 1360092

URL: http://svn.apache.org/viewvc?rev=1360092&view=rev
Log:
- Fixed SANDBOX-425: FibonacciHeap enters in an infinite loop when applying SpannigTree algorithms
- Added some unit tests to FibonacciHeap
- Moved Spannong tree algo to fibonacci heap

Modified:
    commons/sandbox/graph/trunk/src/changes/changes.xml
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.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=1360092&r1=1360091&r2=1360092&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Wed Jul 11 09:59:00 2012
@@ -23,6 +23,9 @@
   </properties>
   <body>
   <release version="0.1" date="201?-??-??" description="First release.">
+    <action dev="marcosperanza" type="fix" issue="SANDBOX-425">
+      FibonacciHeap enters in an infinite loop when applying SpannigTree algorithms
+    </action>
     <action dev="marcosperanza" type="fix" issue="SANDBOX-386">
       Make Graph components Serializable
     </action>

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java?rev=1360092&r1=1360091&r2=1360092&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
Wed Jul 11 09:59:00 2012
@@ -34,6 +34,7 @@ import java.util.List;
 import java.util.NoSuchElementException;
 import java.util.Queue;
 import java.util.Set;
+import java.util.Stack;
 
 /**
  * A Fibonacci Heap implementation based on
@@ -124,10 +125,10 @@ public final class FibonacciHeap<E>
         else
         {
             // 7 concatenate the root list containing x with root list H
-            minimumNode.getLeft().setRight( node );
-            node.setLeft( minimumNode.getLeft() );
-            node.setRight( minimumNode );
-            minimumNode.setLeft( node );
+            node.setLeft( minimumNode );
+            node.setRight( minimumNode.getRight() );
+            minimumNode.setRight( node );
+            node.getRight().setLeft( node );
 
             // 8''  if key[x] < key[min[H]]
             if ( compare( node, minimumNode ) < 0 )
@@ -354,33 +355,31 @@ public final class FibonacciHeap<E>
 
         // 1  z <- min[H]
         FibonacciHeapNode<E> z = minimumNode;
+        int numOfKids = z.getDegree(); 
+        
+        FibonacciHeapNode<E> x = z.getChild();
+        FibonacciHeapNode<E> tempRight;
+        
+        while ( numOfKids > 0 )
+        {
+            // 3  for each child x of z
+            tempRight = x.getRight();
+
+            // 4  do add x to the root list of H
+            x.getLeft().setRight( x.getRight() );
+            x.getRight().setLeft( x.getLeft() );
+
+            // 4  add x to the root list of H
+            x.setLeft( minimumNode );
+            x.setRight( minimumNode.getRight() );
+            minimumNode.setRight( x );
+            x.getRight().setLeft( x );
 
-        // 3  for each child x of z
-        if ( z.getDegree() > 0 )
-        {
-            FibonacciHeapNode<E> x = z.getChild();
-            FibonacciHeapNode<E> tempRight;
-
-            do
-            {
-                tempRight = x.getRight();
+            // 5  p[x] <- NIL
+            x.setParent( null );
 
-                // 4  do add x to the root list of H
-                x.getLeft().setRight( x.getRight() );
-                x.getRight().setLeft( x.getLeft() );
-
-                // 4  add x to the root list of H
-                z.getLeft().setRight( x );
-                x.setLeft( z.getLeft() );
-                z.setLeft( x );
-                x.setRight( z );
-
-                // 5  p[x] <- NIL
-                x.setParent( null );
-
-                x = tempRight;
-            }
-            while ( x != z.getChild() );
+            x = tempRight;
+            numOfKids--;
         }
 
         // 6  remove z from the root list of H
@@ -469,14 +468,32 @@ public final class FibonacciHeap<E>
             nodeSequence.add( i, null );
         }
 
+        int numRoots = 0;
+        
         // 3  for each node x in the root list of H
         // 4  do x &larr; w
         FibonacciHeapNode<E> x = minimumNode;
-        do
+        
+        if ( x != null ) 
+        {
+            numRoots++;
+            x = x.getRight();
+            
+            while ( x != minimumNode )
+            {
+                numRoots++;
+                x = x.getRight();
+            }
+        }
+        
+        
+        while ( numRoots > 0 )
         {
             // 5  d <- degree[x]
             int degree = x.getDegree();
+            FibonacciHeapNode<E> next = x.getRight();
 
+            
             // 6  while A[d] != NIL
             while ( nodeSequence.get( degree ) != null )
             {
@@ -505,9 +522,10 @@ public final class FibonacciHeap<E>
             // 13  A[d] <- x
             nodeSequence.set( degree, x );
 
-            x = x.getRight();
+            x = next;
+            numRoots--;
         }
-        while ( x != minimumNode );
+        
 
         // 14  min[H] <- NIL
         minimumNode = null;
@@ -515,9 +533,20 @@ public final class FibonacciHeap<E>
         // 15  for i <- 0 to D(n[H])
         for ( FibonacciHeapNode<E> pointer : nodeSequence )
         {
+            if ( pointer == null ) continue;
+            if ( minimumNode == null )
+            {
+                minimumNode = pointer;
+            }
+             
             // 16 if A[i] != NIL
-            if ( pointer != null )
+            // We've got a live one, add it to root list.
+            if ( minimumNode != null )
             {
+                //  First remove node from root list.
+                pointer.getLeft().setRight( pointer.getRight() );
+                pointer.getRight().setLeft( pointer.getLeft() );
+                
                 moveToRoot( pointer );
             }
         }
@@ -536,16 +565,30 @@ public final class FibonacciHeap<E>
      */
     private void link( FibonacciHeapNode<E> y, FibonacciHeapNode<E> x )
     {
-        // 1  remove y from the root list of H
+        // 1 remove y from the root list of H
         y.getLeft().setRight( y.getRight() );
         y.getRight().setLeft( y.getLeft() );
 
-        // 2  make y a child of x, incrementing degree[x]
-        x.setChild( y );
         y.setParent( x );
-        x.incraeseDegree();
 
-        // 3  mark[y] <- FALSE
+        if ( x.getChild() == null )
+        {
+            // 2 make y a child of x, incrementing degree[x]
+            x.setChild( y );
+            y.setRight( y );
+            y.setLeft( y );
+        }
+        else
+        {
+            y.setLeft( x.getChild() );
+            y.setRight( x.getChild().getRight() );
+            x.getChild().setRight( y );
+            y.getRight().setLeft( y );
+        }
+        
+        x.incraeseDegree();
+        
+        // 3 mark[y] <- FALSE
         y.setMarked( false );
         markedNodes++;
     }
@@ -648,5 +691,60 @@ public final class FibonacciHeap<E>
         Comparable<? super E> o1Comparable = (Comparable<? super E>) o1.getElement();
         return o1Comparable.compareTo( o2.getElement() );
     }
+    
+    
+    /**
+    * Creates a String representation of this Fibonacci heap.
+    *
+    * @return String of this.
+    */
+    public String toString()
+    {
+        if ( minimumNode == null )
+        {
+            return "FibonacciHeap=[]";
+        }
+
+        // create a new stack and put root on it
+        Stack<FibonacciHeapNode<E>> stack = new Stack<FibonacciHeapNode<E>>();
+        stack.push( minimumNode );
+
+        StringBuffer buf = new StringBuffer( 512 );
+        buf.append( "FibonacciHeap=[" );
+
+        // do a simple breadth-first traversal on the tree
+        while ( !stack.empty() )
+        {
+            FibonacciHeapNode<E> curr = stack.pop();
+            buf.append( curr );
+            buf.append( ", " );
+
+            if ( curr.getChild() != null )
+            {
+                stack.push( curr.getChild() );
+            }
+
+            FibonacciHeapNode<E> start = curr;
+            curr = curr.getRight();
+
+            while ( curr != start )
+            {
+                buf.append( curr );
+                buf.append( ", " );
+
+                if ( curr.getChild() != null )
+                {
+                    stack.push( curr.getChild() );
+                }
+
+                curr = curr.getRight();
+            }
+        }
+
+        buf.append( ']' );
+
+        return buf.toString();
+    }
+
 
 }

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=1360092&r1=1360091&r2=1360092&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
Wed Jul 11 09:59:00 2012
@@ -27,7 +27,6 @@ import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
-import java.util.PriorityQueue;
 import java.util.Set;
 
 import org.apache.commons.graph.Graph;
@@ -35,6 +34,7 @@ import org.apache.commons.graph.Mapper;
 import org.apache.commons.graph.SpanningTree;
 import org.apache.commons.graph.VertexPair;
 import org.apache.commons.graph.collections.DisjointSet;
+import org.apache.commons.graph.collections.FibonacciHeap;
 import org.apache.commons.graph.model.MutableSpanningTree;
 import org.apache.commons.graph.weight.OrderedMonoid;
 
@@ -172,8 +172,8 @@ final class DefaultSpanningTreeAlgorithm
         checkNotNull( weightOperations, "The Kruskal algorithm cannot be calculated with
null weight operations" );
         final Set<V> settledNodes = new HashSet<V>();
 
-        final PriorityQueue<WE> orderedEdges =
-            new PriorityQueue<WE>( graph.getSize(), new WeightedEdgesComparator<W,
WE>( weightOperations, weightedEdges ) );
+        final FibonacciHeap<WE> orderedEdges =
+                        new FibonacciHeap<WE>( new WeightedEdgesComparator<W, WE>(
weightOperations, weightedEdges ) );
 
         for ( WE edge : graph.getEdges() )
         {
@@ -219,7 +219,7 @@ final class DefaultSpanningTreeAlgorithm
 
         final ShortestEdges<V, WE, W> shortestEdges = new ShortestEdges<V, WE, W>(
graph, source, weightOperations, weightedEdges );
 
-        final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( graph.getOrder(),
shortestEdges );
+        final FibonacciHeap<V> unsettledNodes = new FibonacciHeap<V>( shortestEdges
);
         unsettledNodes.add( source );
 
         final Set<WE> settledEdges = new HashSet<WE>();
@@ -232,7 +232,6 @@ final class DefaultSpanningTreeAlgorithm
             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 ) ||
@@ -248,7 +247,7 @@ final class DefaultSpanningTreeAlgorithm
                 }
             }
         }
-
+        
         return shortestEdges.createSpanningTree();
     }
 

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java?rev=1360092&r1=1360091&r2=1360092&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java
(original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/collections/FibonacciHeapTestCase.java
Wed Jul 11 09:59:00 2012
@@ -22,7 +22,11 @@ package org.apache.commons.graph.collect
 import static org.hamcrest.CoreMatchers.is;
 import static org.junit.Assert.assertThat;
 
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
 import java.util.Queue;
+import java.util.Random;
 
 import org.junit.After;
 import org.junit.Before;
@@ -90,5 +94,49 @@ public final class FibonacciHeapTestCase
         assertThat( queue.poll(), is( 100 ) );
         assertThat( queue.isEmpty(), is( true ) );
     }
+    
+    @Test
+    public void insertSingleItem()
+    {
+        queue.add( 50 );
+
+        assertThat( queue.poll(), is( 50 ) );
+        assertThat( queue.isEmpty(), is( true ) );
+    }
+    
+    @Test
+    public void insertSameValuesAndReturnsOrderedItems()
+    {
+        queue.add( 50 );
+        queue.add( 100 );
+        queue.add( 50 );
+
 
+        assertThat( queue.poll(), is( 50 ) );
+        assertThat( queue.poll(), is( 50 ) );
+        assertThat( queue.poll(), is( 100 ) );
+        assertThat( queue.isEmpty(), is( true ) );
+    }
+
+    @Test
+    public void returnsOrderedItemsFromRandomInsert()
+    {
+        final Random r = new Random( System.currentTimeMillis() );
+        final List<Integer> expected = new ArrayList<Integer>();
+        
+        for ( int i = 0; i < 1000; i++ )
+        {
+            Integer number = new Integer( r.nextInt(10000) );
+            expected.add( number );
+            
+            queue.add( number );
+        }
+        Collections.sort( expected );
+        
+        for ( Integer integer : expected )
+        {
+            Integer i = queue.poll();
+            assertThat( i, is( integer ) );
+        }
+    }
 }

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=1360092&r1=1360091&r2=1360092&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 Jul 11 09:59:00 2012
@@ -220,7 +220,7 @@ public final class PrimTestCase
 
         expected.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b",
7D ), b );
         expected.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> d",
5D ), d );
-        expected.addEdge( b, new BaseLabeledWeightedEdge<Double>( "b <-> e",
9D ), e );
+        expected.addEdge( b, new BaseLabeledWeightedEdge<Double>( "b <-> e",
7D ), e );
         expected.addEdge( c, new BaseLabeledWeightedEdge<Double>( "c <-> e",
5D ), e );
         expected.addEdge( d, new BaseLabeledWeightedEdge<Double>( "d <-> f",
6D ), f );
         expected.addEdge( e, new BaseLabeledWeightedEdge<Double>( "e <-> g",
9D ), g );



Mime
View raw message