tools/ictool/depgraph.cs

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