From e11d65009d0b4ba1327f5f5dd6b26367330611f0 Mon Sep 17 00:00:00 2001
From: Dan Liew <daniel.liew@imperial.ac.uk>
Date: Sun, 28 Jun 2015 00:46:18 +0100
Subject: Remove dead file.

---
 Source/Core/Graph.as | 352 ---------------------------------------------------
 1 file changed, 352 deletions(-)
 delete mode 100644 Source/Core/Graph.as

diff --git a/Source/Core/Graph.as b/Source/Core/Graph.as
deleted file mode 100644
index 1466c341..00000000
--- a/Source/Core/Graph.as
+++ /dev/null
@@ -1,352 +0,0 @@
-using System.Collections;
-namespace Graphing;
-
-type Node = object;
-type Edge = <Node,Node>;
-
-class PreHeader {
-  Node myHeader;
-  PreHeader(Node h) { myHeader = h; }
-  
-  public override string ToString() { return "#" + myHeader.ToString(); }
-}
-
-public class Graph {
-  private Set<Edge> es;
-  private Set<Node> ns;
-  private Node source;
-  private bool reducible;
-  private Set<Node> headers;
-  private Map<Node,Set<Node>> backEdgeNodes;
-  private Map<Edge,Set<Node>> naturalLoops;
-  private Map<Node,Set<Node>> dominatorMap;
-  private Map<Node,Set<Node>> immediateDominatorMap;
- 
-  public Graph(Set<Edge> edges)
-  {
-    es = edges;
-    ns = Set<Node>{ x : <x,y> in es } + Set<Node>{ y : <x,y> in es };
-  }
-  public Graph()
-  { es = Set<Edge>{}; ns = Set<Node>{}; } 
-  
-  public void AddSource(Node x)
-  {
-    ns += Set<Node>{x};
-    source = x;
-  }
-  public void AddEdge(Node source, Node dest)
-  {
-    es += Set<Edge>{<source,dest>};
-    ns += Set<Node>{source, dest};
-  }
-  
-  public Set<Node> Nodes { get { return ns; } }
-  public Set<Edge> Edges { get { return es; } }
-  
-  public bool Edge(Node x, Node y) { return <x,y> in es; }  
-  Set<Node> predecessors(Node n)
-  {
-    Set<Node> result = Set{ x : x in Nodes, Edge(x,n) };
-    return result;
-  }
-  public override string ToString() { return es.ToString(); }
-  
-  public IEnumerable TopologicalSort()
-  {
-    <bool,Seq<Node>> <res,ns> = TopSort(this);
-    return  res ? ns : null;
-  }
-  public void ComputeLoops()
-  {
-     <bool, Set<Node>, Map<Node,Set<Node>>, Map<Edge,Set<Node>>>
-       <reducible,headers,backEdgeNodes,naturalLoops> = Reducible(this,this.source);
-       this.reducible = reducible;
-       this.headers = headers;
-       this.backEdgeNodes = backEdgeNodes;
-       this.naturalLoops = naturalLoops;
-     return;
-  }
-  public bool Reducible { get { return reducible; } }
-  public IEnumerable Headers { get { return headers; } }
-  public IEnumerable BackEdgeNodes(Node h) { return h in backEdgeNodes ? backEdgeNodes[h] : null; }
-  public IEnumerable NaturalLoops(Node header, Node backEdgeNode)
-  {  Edge e = <backEdgeNode,header>; return e in naturalLoops ? naturalLoops[e] : null; }
-  public bool Acyclic { get { return Acyclic(this,this.source); } }
-  public Map<Node,Set<Node>> DominatorMap
-  {
-    get { 
-      if (dominatorMap == null) dominatorMap = ComputeDominators(this, source);
-      return dominatorMap;
-    }
-  }
-  public Map<Node,Set<Node>> ImmediateDominatorMap
-  {
-    get { 
-      if (immediateDominatorMap == null)
-      {
-        immediateDominatorMap = Map{};
-        foreach(Node y in Nodes)
-        {
-          Set<Node> nodesThatYDominates = Set{ x : x in Nodes, x != y && (y in DominatorMap[x]) };
-          Set<Node> immediateDominatees = Set{ x : x in nodesThatYDominates,
-                                                  !(Exists{ v != y && v != x && (v in DominatorMap[x]) : v in nodesThatYDominates })
-                                               };
-          immediateDominatorMap[y] = immediateDominatees;
-        }
-      }
-      return immediateDominatorMap;
-    }
-  }
-  public Set<Node> ImmediatelyDominatedBy(Node n) { return ImmediateDominatorMap[n]; }
-
-}
-
-// From AsmL distribution example: TopologicalSort
-<bool,Seq<Node>> TopSort(Graph g)
-{
-  Seq<Node> S = Seq{};
-  Set<Node> V = g.Nodes;
-  bool change = true;
-  while ( change )
-  {
-    change = false;
-    Set<Node> X = V - ((Set<Node>) S);
-    if ( X != Set{} )
-    {
-      Node temp = Choose{ v : v in X, !(Exists{ g.Edge(u,v) : u in X }) ifnone null };
-      if ( temp == null )
-      {
-        return <false,Seq<Node>{}>;
-      }
-      else if ( temp != Seq<Node>{} )
-      {
-        S += Seq{temp};
-        change = true;
-      }
-    }
-  }
-  return <true,S>;
-}
-
-bool Acyclic(Graph g, Node source)
-{
-  <bool,Seq<Node>> <acyc,xs> = TopSort(g);
-  return acyc;
-}
-
-//
-// [Dragon, pp. 670--671]
-// returns map D s.t. d in D(n) iff d dom n
-//
-Map<Node,Set<Node>> ComputeDominators(Graph g, Node source) {
-  Set<Node> N = g.Nodes;
-  Set<Node> nonSourceNodes = N - Set{source};
-  Map<Node,Set<Node>> D = Map{};
-  D[source] = Set<Node>{ source };
-  foreach (Node n in nonSourceNodes)
-  {
-    D[n] = N;
-  }
-  bool change = true;
-  while ( change )
-  {
-    change = false;
-    foreach (Node n in nonSourceNodes)
-    {
-      Set<Set<Node>> allPreds = Set{ D[p] : p in g.predecessors(n) };
-      Set<Node> temp = Set<Node>{ n } + BigIntersect(allPreds);
-      if ( temp != D[n] )
-      {
-        change = true;
-        D[n] = temp;
-      }
-    }
-  }
-  return D;
-}
-
-// [Dragon, Fig. 10.15, p. 604. Algorithm for constructing the natural loop.]
-Set<Node> NaturalLoop(Graph g, Edge backEdge)
-{
-  <Node,Node> <n,d> = backEdge;
-  Seq<Node> stack = Seq{};
-  Set<Node> loop = Set{ d };
-  if ( n != d ) // then n is not in loop
-  {
-    loop += Set{ n };
-    stack = Seq{ n } + stack; // push n onto stack
-  }
-  while ( stack != Seq{} ) // not empty
-  {
-    Node m = Head(stack);
-    stack = Tail(stack); // pop stack
-    foreach (Node p in g.predecessors(m))
-    {
-      if ( !(p in loop) )
-      {
-        loop += Set{ p };
-        stack = Seq{ p } + stack; // push p onto stack
-      }
-    }
-  }
-  return loop;
-}
-
-// [Dragon, p. 606]
-<bool, Set<Node>, Map<Node,Set<Node>>, Map<Edge,Set<Node>>>
-  Reducible(Graph g, Node source) {
-  // first, compute the dom relation
-  Map<Node,Set<Node>> D = g.DominatorMap;
-  return Reducible(g,source,D);
-}
-
-// [Dragon, p. 606]
-<bool, Set<Node>, Map<Node,Set<Node>>, Map<Edge,Set<Node>>>
-  Reducible(Graph g, Node source, Map<Node,Set<Node>> DomRelation) {
-
-  Set<Edge> edges = g.Edges;
-  Set<Edge> backEdges = Set{};
-  Set<Edge> nonBackEdges = Set{};
-  foreach (Edge e in edges)
-  {
-    <Node,Node> <x,y> = e; // so there is an edge from x to y
-    if ( y in DomRelation[x] ) // y dom x: which means y dominates x
-    {
-      backEdges += Set{ e };
-    }
-    else
-    {
-      nonBackEdges += Set{ e };
-    }
-  }
-  if ( !Acyclic(new Graph(nonBackEdges), source) )
-  {
-    return <false,Set<Node>{},Map<Node,Set<Node>>{},Map<Edge,Set<Node>>{}>;
-  }
-  else
-  {
-    Set<Node> headers = Set{ d : <n,d> in backEdges };
-    Map<Node,Set<Node>> backEdgeNodes = Map{ h -> bs  : h in headers, bs = Set<Node>{ b : <b,x> in backEdges, x == h } };
-    Map<Edge,Set<Node>> naturalLoops = Map{ e -> NaturalLoop(g,e) : e in backEdges };
-     
-    return <true, headers, backEdgeNodes, naturalLoops>;
-  }
-}
-  
-// [Dragon, p. 606]
-bool OldReducible(Graph g, Node source) {
-  // first, compute the dom relation
-  Map<Node,Set<Node>> D = ComputeDominators(g, source);
-  return OldReducible(g,source,D);
-}
-
-// [Dragon, p. 606]
-bool OldReducible(Graph g, Node source, Map<Node,Set<Node>> DomRelation) {
-
-  Set<Edge> edges = g.Edges;
-  Set<Edge> backEdges = Set{};
-  Set<Edge> nonBackEdges = Set{};
-  foreach (Edge e in edges)
-  {
-    <Node,Node> <x,y> = e;
-    if ( y in DomRelation[x] ) // y dom x
-    {
-      backEdges += Set{ e };
-    }
-    else
-    {
-      nonBackEdges += Set{ e };
-    }
-  }
-  WriteLine("backEdges: " + backEdges);
-  WriteLine("nonBackEdges: " + nonBackEdges);
-  if ( Acyclic(new Graph(nonBackEdges), source) )
-  {
-    foreach(Edge e in backEdges)
-    {
-      Set<Node> naturalLoop = NaturalLoop(g,e);
-      WriteLine("Natural loop for back edge '" + e + "' is: " + naturalLoop);
-    }
-    Set<Node> headers = Set{ d : <n,d> in backEdges };
-    WriteLine("Loop headers = " + headers);
-     
-    edges -= backEdges; // this cuts all of the back edges
-    foreach (Node h in headers)
-    {
-      Set<Edge> bs = Set{ <n,d> : <n,d> in backEdges, d == h };
-      Set<Node> preds = Set<Node>{ p : <p,y> in edges, y == h };
-      Node preheader = new PreHeader(h);
-      edges += Set{ <preheader,h> };
-      foreach (Node p in preds)
-      {
-        edges -= Set{ <p,h> };
-        edges += Set{ <p,preheader> };
-      }
-    }
-    Graph newGraph = new Graph(edges);
-    WriteLine("transformed graph = " + newGraph);
-    return true;
-  }
-  else
-  {
-    return false;
-  }
-}
-
-void Main()
-{
-   Graph g;
-   Map<Node,Set<Node>> D;
-/*   
-   g = new Graph(Set<Edge>{ <1,2>, <1,3>, <2,3> });
-   g.AddSource(1);
-  Map<Node,Set<Node>> doms = ComputeDominators(g,1);
-   WriteLine(doms); 
-*/
-   g = new Graph(Set<Edge>{
-          <1,2>, <1,3>,
-          <2,3>,
-          <3,4>,
-          <4,3>, <4,5>, <4,6>,
-          <5,7>,
-          <6,7>,
-          <7,4>, <7,8>,
-          <8,3>, <8,9>, <8,10>,
-          <9,1>,
-          <10,7>
-          });
-   g.AddSource(1);
-   WriteLine("G = " + g);
-   D = ComputeDominators(g,1);
-   WriteLine("Dom relation: " + D); 
-   WriteLine("G's Dominator Map = " + g.DominatorMap);
-   WriteLine("G's Immediate Dominator Map = " + g.ImmediateDominatorMap);
-   WriteLine("G is reducible: " + OldReducible(g,1,D));
-   g.ComputeLoops();
-   
-   WriteLine("");
-   
-   g = new Graph(Set<Edge>{ <1,2>, <1,3>, <2,3>, <3,2> });
-   g.AddSource(1);
-   WriteLine("G = " + g);
-   D = ComputeDominators(g,1);
-   WriteLine("Dom relation: " + D); 
-   WriteLine("G's Dominator Map = " + g.DominatorMap);
-   WriteLine("G's Immediate Dominator Map = " + g.ImmediateDominatorMap);
-   WriteLine("G is reducible: " + OldReducible(g,1,D));
-   g.ComputeLoops();
- 
-    WriteLine("");
-   
-   g = new Graph(Set<Edge>{ <1,2>, <2,3>, <2,4>, <3,2> });
-   g.AddSource(1);
-   WriteLine("G = " + g);
-   WriteLine("G's Dominator Map = " + g.DominatorMap);
-   WriteLine("G's Immediate Dominator Map = " + g.ImmediateDominatorMap);
-//   D = ComputeDominators(g,1);
-//   WriteLine("Dom relation: " + D); 
-//   WriteLine("G is reducible: " + OldReducible(g,1,D));
-   g.ComputeLoops();
-  
-}
\ No newline at end of file
-- 
cgit v1.2.3