Topological Ordering and Properties of Directed Acyclic Graphs
Directed Acyclic Graphs (DAGs)
DAGs are pretty self explanatory, but their use cases are vast.
Topological Orderings
A topological ordering of a directed graph is a linear ordering of all its vertices such that for every directed edge , comes before in the ordering if .
Lemma: If has a topological ordering, then is a DAG. Proof: For contradiction, assume has a cycle , as well as a topological ordering.
We can order vertices such that , we have .
Take the smallest in the cycle mentioned previously. Then and violate our ordering, since was the minimum in the topological ordering (so both and are greater).
Lemma: If is a DAG, then has a source vertex (). Proof: Suppose for contradiction that has no source vertex.
i.e.,
Consider an arbitrary vertex . Then has some neighbor(s) with an edge into it. Similarly, has some neighbor(s) with edges coming into it. You can continue this logic, and must eventually find a repeating vertex, since there are finitely many vertices.
Algorithm
def topological_sort(G):
order = []
count = [0] * len(G)
S = { v for v in G if not G[v] }
for v in G
for u in G[v]:
count[u] += 1
while S:
v = S.pop()
order.append(v)
for u in G[v]:
count[u] -= 1
if count[u] == 0:
S.add(u)
return order