直接非循環グラフ上のこのアルゴリズムの名前は何ですか?

私は表示目的のgitブランチの履歴を線形化しようとしています。私はコミット時に与えられた順序で単にコミットを表示する代わりに、コミットをブランチに配置したい。

このグラフ問題では、開始ノードと最終ノードがあり、その間に直接非循環グラフ(DAG)があります。次のようになります。

Example git DAG

1つの解決策は次のとおりです。

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

これは、グラフを上方向に歩き、両方のマージコミットメントを消費します。 b
d1
のようなソース頂点を持つ頂点に到達すると、次のブランチに移動します。ソースの頂点は、すべての子がすでに結果リストに入っているときに結果リストに追加されます。

スキームのコンセプト実装の証明は次のとおりです。

(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)))))))))

このアルゴリズムの名前は何ですか?

ベストアンサー

トポロジカルな並べ替えに関するいくつかの追加の制限があるように私に見えます: https://en.m.wikipedia。
org/wiki/Topological_sorting
を参照してください。 git rev-list
–topo-orderのように、gitは既にこの操作をサポートしています。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です