From 6b33346bf50caac9bdb33405b31b19574a091ef1 Mon Sep 17 00:00:00 2001
From: Unknown <akashl@MSRI-Akashlal.fareast.corp.microsoft.com>
Date: Sun, 26 Jun 2011 00:08:39 +0530
Subject: Added an iterative version of PostOrderVisit (but it is not called)

---
 Source/Graph/Graph.cs | 45 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

(limited to 'Source/Graph')

diff --git a/Source/Graph/Graph.cs b/Source/Graph/Graph.cs
index 9ad1ce22..120cb8f8 100644
--- a/Source/Graph/Graph.cs
+++ b/Source/Graph/Graph.cs
@@ -188,6 +188,7 @@ namespace Graphing {
       int currentNumber = 1;
       Contract.Assume(this.source != null);
       this.PostOrderVisit(this.source, visited, ref currentNumber);
+      //this.PostOrderVisitIterative(this.source);
       this.sourceNum = this.nodeToPostOrderNumber[source];
       //    for (int i = 1; i <= n; i++){ Console.WriteLine(postOrderNumberToNode[i]); }
       this.doms = new int[n + 1]; // 0 is unused: means undefined
@@ -278,6 +279,50 @@ namespace Graphing {
       currentNumber++;
       return;
     }
+    // Iterative version: mimics the above recursive procedure
+    private void PostOrderVisitIterative(Node n)
+    {
+        Contract.Requires(n != null);
+        var visited = new HashSet<Node>();
+        var grey = new HashSet<Node>();
+        var stack = new Stack<Node>();
+
+        int currentNumber = 1;
+
+        stack.Push(n);
+        visited.Add(n);
+
+        while (stack.Count != 0)
+        {
+            var curr = stack.Pop();
+
+            if (grey.Contains(curr))
+            {
+                Contract.Assume(this.postOrderNumberToNode != null);
+                Contract.Assume(this.nodeToPostOrderNumber != null);
+                this.postOrderNumberToNode[currentNumber].Val = curr;
+                this.nodeToPostOrderNumber[curr] = currentNumber;
+                currentNumber++;
+            }
+            else
+            {
+                grey.Add(curr);
+                stack.Push(curr);
+                foreach (Node/*!*/ child in this.graph.Successors(curr))
+                {
+                    Contract.Assert(child != null);
+                    if (!visited.Contains(child))
+                    {
+                        visited.Add(child);
+                        stack.Push(child);
+                    }
+                }
+            }
+
+        }
+
+
+    }
   }
 
   public class Graph<Node> {
-- 
cgit v1.2.3