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 ← 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 );
