<p>Looks to me like some additional restrictions on a topological sort: <a href="https://en.m.wikipedia.org/wiki/Topological_sorting" rel="nofollow noreferrer">https://en.m.wikipedia.org/wiki/Topological_sorting</a> .
Also git already supports this operation for instance git rev-list --topo-order .</p>

CC BY-SA 3.0
2018-02-17T13:35:59.687Z
2018-02-17T14:35:49.390Z
2018-02-17T14:35:49.390Z
Max New
<p>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. </p>

<p>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:</p>

<p><a href="https://i.sstatic.net/8En1I.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8En1I.png" alt="Example git DAG"></a></p>

<p>One possible solution is the following:</p>

<pre><code>a0 a b d1 x2 x1 d2 d3 c3 c1 e c2 f z1 z2 z3 g h i j k
</code></pre>

<p>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 <code>b</code> and <code>d1</code>. A source vertices is added to the result list when all it children are already in the result list.</p>

<p>Here is a proof of concept implementation in scheme:</p>

<pre><code>(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)))))))))
</code></pre>

<p>What is the name of this algorithm?</p>

CC BY-SA 3.0
2018-02-23T14:28:31.843Z
This seems to be some variant of topological sort.
András Salamon
<reference-request><graph-algorithms><terminology><directed-acyclic-graph>
What is the name of this algorithm on direct acyclic graph?
amirouche
# What is the name of this algorithm on direct acyclic graph?

(Asked by: username_0 on 2018-02-17)

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?

**Tags:** reference-request, graph-algorithms, terminology, directed-acyclic-graph

> **Comments:**
> **username_1**: This seems to be some variant of topological sort.  

---

## 1 answers

### Answer by username_2 on 2018-02-17. Score: 4 | Accepted answer

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 .


---

