Online Topological Sort

Online topological sort maintains an ordering of a directed acyclic graph while updates arrive over time. Unlike ordinary topological sort, the graph is not fixed before the algorithm starts.

You use it when dependencies are discovered incrementally, such as build systems, schedulers, package managers, and dynamic workflow engines.

Problem

Given a directed graph ( G = (V, E) ), maintain an ordering ( \pi ) such that for every edge:

[ u \to v ]

vertex ( u ) appears before vertex ( v ) in ( \pi ).

When a new edge or vertex is added, update the ordering without recomputing everything from scratch.

Algorithm (Simple Reordering)

When adding edge ( u \to v ):

1. If ( u ) already appears before ( v ), the order remains valid
2. Otherwise, find the affected region between ( v ) and ( u )
3. Move vertices reachable from ( v ) after ( u ), preserving relative order
4. If ( u ) is reachable from ( v ), the new edge creates a cycle

online_topological_sort_add_edge(G, order, u, v):
    add edge u -> v to G

    if position(order, u) < position(order, v):
        return order

    affected = vertices between position(v) and position(u)

    if reachable(G, v, u):
        error "cycle detected"

    move = vertices in affected reachable from v
    stay = affected - move

    order = prefix_before(v)
          + stay
          + [u and vertices after u as needed]
          + move
          + suffix_after(u)

    return order

Example

Current order:

[ [A, B, C, D] ]

Add edge:

[ D \to B ]

This violates the order because ( D ) appears after ( B ). The algorithm checks the affected region:

[ [B, C, D] ]

Then it moves affected vertices as needed so ( D ) appears before ( B ), unless doing so creates a cycle.

One valid updated order may be:

[ [A, D, B, C] ]

Correctness

A topological order is valid when every directed edge points forward in the ordering. If a new edge already points forward, no update is needed.

If the new edge points backward, only vertices in the interval between the two endpoints can be affected. Reordering that interval while preserving all dependency constraints restores the topological order. If the destination can already reach the source, adding the edge creates a directed cycle, so no topological order exists.

Complexity

The cost depends on the update strategy.

Space:

[ O(|V| + |E|) ]

Cycle Detection

When adding ( u \to v ), a cycle appears exactly when ( v ) can already reach ( u ).

if reachable(G, v, u):
    report cycle
else:
    accept edge

When to Use

Use online topological sort when:

• dependencies arrive incrementally
• recomputing from scratch is too costly
• a valid order must be available after each update
• cycle detection is required during updates

For static graphs, ordinary DFS based or Kahn based topological sort is simpler.