diff options
| author |  Unknown <akashl@MSRI-Akashlal.fareast.corp.microsoft.com> | 2011-06-26 00:08:39 +0530 |
|---|---|---|
| committer | Unknown <akashl@MSRI-Akashlal.fareast.corp.microsoft.com> | 2011-06-26 00:08:39 +0530 |
| commit | 6b33346bf50caac9bdb33405b31b19574a091ef1 (patch) | |
| tree | 491d7c173af145dec9b8e61e640979e727922118 /Source/Graph | |
| parent | 3f4c65b26ce7771eeb1ef738eb65ef63be62a617 (diff) | |
Added an iterative version of PostOrderVisit (but it is not called)
Diffstat (limited to 'Source/Graph')
| -rw-r--r-- | Source/Graph/Graph.cs | 45 |
1 files changed, 45 insertions, 0 deletions
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> {
|