Topological Sorting

# Algorithm

1) Input the node data S of size n
2) Input arc data(ni, nj), 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

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

page revision: 12, last edited: 29 Apr 2010 03:05