Topological Ordering and Properties of Directed Acyclic Graphs

Category: Algorithms ..

Directed Acyclic Graphs (DAGs)

DAGs are pretty self explanatory, but their use cases are vast.

Topological Orderings

A topological ordering of a directed graph G=(V,E)G = (V, E) is a linear ordering of all its vertices such that for every directed edge (vi,vj)E(v_i, v_j) \in E, viv_i comes before vjv_j in the ordering if vi<vjv_i < v_j.

Lemma: If GG has a topological ordering, then GG is a DAG. Proof: For contradiction, assume GG has a cycle v0,,vkv_0, \ldots , v_k, as well as a topological ordering.

We can order vertices u1,,unu_1, \ldots, u_n such that  directed edges ij\forall \text{ directed edges } i \to j, we have i<ji < j.

Take the smallest ui=vju_i = v_j in the cycle mentioned previously. Then vj1vjv_{j - 1} \to v_{j} and vjvj+1v_{j} \to v_{j + 1} violate our ordering, since vjv_j was the minimum in the topological ordering (so both v(j1)modkv_{(j - 1) \mod k} and v(j+1)modkv_{(j + 1) \mod k} are greater).

Lemma: If GG is a DAG, then GG has a source vertex (indeg(v)=0indeg(v) = 0). Proof: Suppose for contradiction that GG has no source vertex.

i.e., vV,indeg(v)1\forall v \in V, \, indeg(v) \ge 1

Consider an arbitrary vertex v1v_1. Then v1v_1 has some neighbor(s) v2,v_2, \ldots with an edge into it. Similarly, v2v_2 has some neighbor(s) vi,v_i, \ldots 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