Author: simonetripodi
Date: Tue Jul 12 22:07:49 2011
New Revision: 1145794
URL: http://svn.apache.org/viewvc?rev=1145794&view=rev
Log:
added CASCADING-CUT(H,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=1145794&r1=1145793&r2=1145794&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 22:07:49 2011
@@ -418,6 +418,32 @@ public final class FibonacciHeap<E>
}
/**
+ * Implements the {@code CASCADING-CUT(H,y)} function.
+ *
+ * @param y
+ */
+ private void cascadingCut( FibonacciHeapNode<E> y )
+ {
+ // z <- p[y]
+ FibonacciHeapNode<E> z = y.getParent();
+
+ // if z <- NIL
+ if ( z != null )
+ {
+ // mark[y] = FALSE
+ if ( !y.isMarked() )
+ {
+ y.setMarked( true );
+ }
+ else
+ {
+ cut( y, z );
+ cascadingCut( z );
+ }
+ }
+ }
+
+ /**
* The potential of Fibonacci heap {@code H} is then defined by
* {@code t(H) + 2m(H)}.
*
