svn commit: r1354928 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java

[si...@apache.org]

Author: simonetripodi
Date: Thu Jun 28 11:17:53 2012
New Revision: 1354928

URL: http://svn.apache.org/viewvc?rev=1354928&view=rev
Log:
more inline comments on cut() and cascadingCut() methods

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=1354928&r1=1354927&r2=1354928&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 Thu Jun 28 11:17:53 2012
@@ -474,6 +474,12 @@ public final class FibonacciHeap<E>
     /**
      * Implements the {@code CUT(H,x,y)} function.
      *
+     * <pre>CUT(H,x,y)
+     * 1  remove x from the child list of y, decrementing degree[y]
+     * 2  add x to the root list of H
+     * 3  p[x] &lt;- NIL
+     * 4  mark[x] &lt;- FALSE</pre>
+     *
      * @param x the node has to be removed from {@code y} children
      * @param y the node has to be updated
      */
@@ -484,6 +490,9 @@ public final class FibonacciHeap<E>
         x.getRight().setLeft( x.getLeft() );
         y.decraeseDegree();
 
+        // add x to the root list of H
+        // TODO!!!
+
         // p[x] <- NIL
         x.setParent( null );
 
@@ -494,6 +503,14 @@ public final class FibonacciHeap<E>
     /**
      * Implements the {@code CASCADING-CUT(H,y)} function.
      *
+     * <pre>CASCADING-CUT(H,y)
+     * 1  z  p[y]
+     * 2  if z  NIL
+     * 3     then if mark[y] = FALSE
+     * 4             then mark[y]  TRUE
+     * 5             else CUT(H,y,z)
+     * 6                  CASCADING-CUT(H,z)</pre>
+     *
      * @param y the target node to apply CASCADING-CUT
      */
     private void cascadingCut( FibonacciHeapNode<E> y )