I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit.
In this graph problem, there is a start node and an final node and in between there is a direct acyclic graph (DAG). It looks like the following:
One possible solution is the following:
a0 a b d1 x2 x1 d2 d3 c3 c1 e c2 f z1 z2 z3 g h i j k
It walks the graph upward, consuming both branches of merge commmits. It moves to the next branch, when it meets a vertex that has several outgoings vertices - a source vertex like b and d1. A source vertices is added to the result list when all it children are already in the result list.
Here is a proof of concept implementation in scheme:
(define (linearize graph start)
(let loop ((todos (list start))
(out '()))
(pk 'todos todos)
(if (null? todos)
out
(let ((todo (car todos))
(rest (cdr todos)))
(let ((incomings (ref-incomings graph todo)))
(case (length incomings)
((0) (loop '() (cons todo out)))
((1) (if (null? rest)
(loop (reverse incomings) (cons todo out))
(if (eq? (length (ref-outgoings graph (car incomings))) 1)
(loop (append incomings rest) (cons todo out))
(loop rest (cons todo out)))))
(else (loop (append (reverse incomings) rest) (cons todo out)))))))))
What is the name of this algorithm?
