Now You’re Cooking with DAGs!

Vaibhav Sagar

@vbhvsgr

Drawing a Git repository

All Git commit graphs are DAGs

Here’s a DAG

Here’s a not-DAG

What I need

Determinining DAGness

Highlighting not-DAG bits

Processing vertices in some order

How???

Topological sort

Source: https://stackoverflow.com/questions/583876/how-do-i-check-if-a-directed-graph-is-acyclic

Topological sort

Source: https://upload.wikimedia.org/wikipedia/commons/c/c6/Topological_Ordering.svg

SCCs

Source: https://stackoverflow.com/questions/583876/how-do-i-check-if-a-directed-graph-is-acyclic

SCCs

Source: https://upload.wikimedia.org/wikipedia/commons/5/5c/Scc.png

Tarjan’s Algorithm

(Reverse) topological sort

Linear time!

Demonstration

  • stack:
  • output:

  • stack: [ 1 ]
  • output:

  • stack: [ 2, 1 ]
  • output:

  • stack: [ 3, 2, 1 ]
  • output:

  • stack: [ 3, 2, 1 ]
  • output:

  • stack: [ 3, 2, 1 ]
  • output:

  • stack: [ 3, 2, 1 ]
  • output:

  • stack:
  • output: [ [3, 2, 1] ]

  • stack: [ 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 6, 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 6, 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 7, 6, 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 7, 6, 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 7, 6, 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 7, 6, 5, 4 ]
  • output: [ [3, 2, 1] ]

  • stack: [ 5, 4 ]
  • output: [ [3, 2, 1], [ 7, 6 ] ]

  • stack: [ 5, 4 ]
  • output: [ [3, 2, 1], [ 7, 6 ] ]

  • stack: [ 5, 4 ]
  • output: [ [3, 2, 1], [ 7, 6 ] ]

  • stack:
  • output: [ [3, 2, 1], [ 7, 6 ], [ 5, 4 ] ]

  • stack: [ 8 ]
  • output: [ [3, 2, 1], [ 7, 6 ], [ 5, 4 ] ]

  • stack: [ 8 ]
  • output: [ [3, 2, 1], [ 7, 6 ], [ 5, 4 ] ]

  • stack:
  • output: [ [3, 2, 1], [ 7, 6 ], [ 5, 4 ], [ 8 ] ]

Applications

Build tools

Dataflow processing

Dataflow processing

2-SAT

Takeaways

Reverse topological sort

Strongly connected components

Tarjan’s Algorithm

Thanks!