mcs/tools/ictool/depgraph.cs

   1 //\r
   2 // file:        depgraph.cs\r
   3 // author:      Dan Lewis (dihlewis@yahoo.co.uk)\r
   4 //              (C) 2002\r
   5 //\r
   6 \r
   7 using System;\r
   8 using System.Collections;\r
   9 \r
  10 class DependencyGraph {\r
  11         public DependencyGraph () {\r
  12                 nodes = new Hashtable ();\r
  13         }\r
  14 \r
  15         public void AddNode (object o) {\r
  16                 if (!nodes.Contains (o))\r
  17                         nodes.Add (o, new Node (o));\r
  18         }\r
  19 \r
  20         public void AddEdge (object from, object to) {\r
  21                 if (!nodes.Contains (from))\r
  22                         AddNode (from);\r
  23                 if (!nodes.Contains (to))\r
  24                         AddNode (from);\r
  25 \r
  26                 Node from_node = (Node)nodes[from];\r
  27                 Node to_node = (Node)nodes[to];\r
  28 \r
  29                 from_node.edges.Add (to_node);\r
  30         }\r
  31 \r
  32         public IList TopologicalSort () {\r
  33                 foreach (Node node in nodes.Values)\r
  34                         node.marked = false;\r
  35 \r
  36                 IList list = new ArrayList ();\r
  37                 foreach (Node node in nodes.Values) {\r
  38                         if (!node.marked)\r
  39                                 Visit (node, list);\r
  40                 }\r
  41 \r
  42                 return list;\r
  43         }\r
  44 \r
  45         // private\r
  46 \r
  47         private void Visit (Node node, IList list) {\r
  48                 node.marked = true;\r
  49                 foreach (Node adj in node.edges) {\r
  50                         if (!adj.marked)\r
  51                                 Visit (adj, list);\r
  52                 }\r
  53 \r
  54                 list.Insert (0, node.value);\r
  55         }\r
  56 \r
  57         private class Node {\r
  58                 public Node (object o) {\r
  59                         this.value = o;\r
  60                         this.edges = new ArrayList ();\r
  61                 }\r
  62 \r
  63                 public object value;\r
  64                 public ArrayList edges;\r
  65                 public bool marked;\r
  66         }\r
  67 \r
  68         private Hashtable nodes;\r
  69 }\r