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

[![Example git DAG](https://i.sstatic.net/8En1I.png)](https://i.sstatic.net/8En1I.png)

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 .


---

