2
$\begingroup$

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:

Example git DAG

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?

$\endgroup$
  • $\begingroup$ This seems to be some variant of topological sort. $\endgroup$ – András Salamon Feb 23 '18 at 14:28
4
$\begingroup$

Looks to me like some additional restrictions on a topological sort: https://en.m.wikipedia.org/wiki/Topological_sorting . Also git already supports this operation for instance git rev-list --topo-order .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.