Author: simonetripodi
Date: Tue Jul 12 21:43:00 2011
New Revision: 1145783
URL: http://svn.apache.org/viewvc?rev=1145783&view=rev
Log:
added CUT(H,x,y) method implementation
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
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=1145783&r1=1145782&r2=1145783&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
Tue Jul 12 21:43:00 2011
@@ -398,6 +398,26 @@ public final class FibonacciHeap<E>
}
/**
+ * Implements the {@code CUT(H,x,y)} function.
+ *
+ * @param x
+ * @param y
+ */
+ private void cut( FibonacciHeapNode<E> x, FibonacciHeapNode<E> y )
+ {
+ // remove x from the child list of y, decrementing degree[y]
+ x.getLeft().setRight( x.getRight() );
+ x.getRight().setLeft( x.getLeft() );
+ y.decraeseDegree();
+
+ // p[x] <- NIL
+ x.setParent( null );
+
+ // mark[x] <- FALSE
+ x.setMarked( false );
+ }
+
+ /**
* The potential of Fibonacci heap {@code H} is then defined by
* {@code t(H) + 2m(H)}.
*
