commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1145794 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/collections/FibonacciHeap.java
Date Tue, 12 Jul 2011 22:07:49 GMT
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)}.
      *



Mime
View raw message