Topological Sorting

Algorithm

1) Input the node data S of size n
2) Input arc data(n_i, n_j), which is pairs of integers.
3) Lock for a node k without predecessors, output k and mark it. Remove all arcs containning k.
4) Continue step 3) until all node is output, or until there is no unmarked node without predecessors.

Data Structure

Adjacency matrix

Arcs: (1, 0) (2, 4) (1, 3) (3, 2)

	0	1	2	3	4
0	0	0	0	0	0
1	1	0	0	1	0
2	0	0	0	0	1
3	0	0	1	0	0
4	0	0	0	0	0

1) Find out a column n with all 0. -> column 1
2) Output node n, and remove its arcs. Arcs can be found by checking row n. -> row 1: 1 0 0 1 0 -> remove (1, 0) (1, 3)
3) continue 1) until all node is output or there is no unmarked node without predecessors (with all 0)

Result: 1 -> 0 -> 2 -> 3 -> 4

Characteristics

1) Output result: get up -> shower -> kids up -> get dressed -> eat -> depart. Rule: left node can go to right node, but right node can not go to left node.
2) If there is a loop, then topological sorting can not output all nodes, because we can't find a node without predecessor.
3) If there is no loop, maximum number of pairs/arcs will be n take 2, because (3, 7) and (7, 3) cannot occur at the same time.

Reference

http://www.mathsisfun.com/combinatorics/combinations-permutations.html — Combination & Permutation