mcs/tools/ictool/depgraph.cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

//
// file:	depgraph.cs
// author:	Dan Lewis (dihlewis@yahoo.co.uk)
// 		(C) 2002
//

using System;
using System.Collections;

class DependencyGraph {
	public DependencyGraph () {
		nodes = new Hashtable ();
	}

	public void AddNode (object o) {
		if (!nodes.Contains (o))
			nodes.Add (o, new Node (o));
	}

	public void AddEdge (object from, object to) {
		if (!nodes.Contains (from))
			AddNode (from);
		if (!nodes.Contains (to))
			AddNode (from);

		Node from_node = (Node)nodes[from];
		Node to_node = (Node)nodes[to];

		from_node.edges.Add (to_node);
	}

	public IList TopologicalSort () {
		foreach (Node node in nodes.Values)
			node.marked = false;

		IList list = new ArrayList ();
		foreach (Node node in nodes.Values) {
			if (!node.marked)
				Visit (node, list);
		}

		return list;
	}

	// private

	private void Visit (Node node, IList list) {
		node.marked = true;
		foreach (Node adj in node.edges) {
			if (!adj.marked)
				Visit (adj, list);
		}

		list.Insert (0, node.value);
	}

	private class Node {
		public Node (object o) {
			this.value = o;
			this.edges = new ArrayList ();
		}

		public object value;
		public ArrayList edges;
		public bool marked;
	}

	private Hashtable nodes;
}