【C#】トポロジカルソートを実装してみる

はじめに

今回はトポロジカルソートを実装していきたいと思います。

ja.wikipedia.org

トポロジカルソートとは有向非巡回グラフ(DAG)においてどのノードもその出力辺の先のノードより前にくるように並べるアルゴリズムのことです。

f:id:hanaaaaaachiru:20200810200624p:plain

トポロジカルソート

アルゴリズムの仕組みはWikipediaに乗っていた擬似コードがすごく分かりやすかったので引用させていただきます。
ja.wikipedia.org

// 深さ優先探索を用いたもの
L ← トポロジカルソートされた結果の入る空の連結リスト

for each ノード n do
    visit(n)

function visit(Node n)
    if n をまだ訪れていなければ then
        n を訪問済みとして印を付ける
        for each n の出力辺 e とその先のノード m do
            visit(m)
        n を L の先頭に追加

// 閉路検知の機能をつけたもの
L ← トポロジカルソートされた結果の入る空の連結リスト

for each ノード n do
    if n に印が付いていない then
        visit(n)

function visit(Node n)
    if n に「一時的」の印が付いている then
        閉路があり DAG でないので中断
    else if n に印が付いていない then
        n に「一時的」の印を付ける
        for each n の出力辺 e とその先のノード m do
            visit(m)
        n に「恒久的」の印を付ける
        n を L の先頭に追加

コード

public static class TopologicalSort<T>
{
    public static IEnumerable<T> Excute(Graph<T> graph, Action OnDetectCircle = null)
    {
        // 入力されたノード
        var nodes = graph.Nodes;

        // 一度訪れたノード (閉路を検出するために「一時的な」印, 「恒久的な」印)
        var seenNodes = new Dictionary<T, (bool, bool)>();

        // 最終的に出力するノード
        var sortedNodes = new Stack<T>(nodes.Count);
        bool hasCircle = false;

        foreach (var node in nodes)
            Visit(node.Key, nodes, seenNodes, sortedNodes, ref hasCircle);

        if (hasCircle)
        {
            // 閉路を検知
            OnDetectCircle?.Invoke();
            yield break;
        }

        foreach (var node in sortedNodes)
            yield return node;
    }

    private static void Visit(T node, Dictionary<T, List<T>> nodes, Dictionary<T, (bool, bool)> seenNodes, Stack<T> sortedNodes, ref bool hasCycle)
    {
        // 閉路が検出されたら、探索を強制終了する
        if (hasCycle) return;

        // 「一時的」の印がついている箇所を訪れた、つまり閉路を検出したか
        if (seenNodes.ContainsKey(node) && seenNodes[node].Item1)
        {
            hasCycle = true;
            return;
        }

        // まだ通っていない
        if (!seenNodes.ContainsKey(node) || !seenNodes[node].Item2)
        {
            // 一時的な印をつける
            seenNodes[node] = (true, false);

            foreach (var to in nodes[node])
                Visit(to, nodes, seenNodes, sortedNodes, ref hasCycle);

            // 恒久的な印をつける
            seenNodes[node] = (false, true);
            sortedNodes.Push(node);
        }
    }
}

public class Graph<T>
{
    // <頂点, 接続先の頂点>
    public Dictionary<T, List<T>> Nodes { get; private set; }

    /// <summary>
    /// グラフ作成
    /// </summary>
    /// <param name="nodes">頂点のラベルのコレクション</param>
    public Graph(IEnumerable<T> nodes)
    {
        Nodes = new Dictionary<T, List<T>>();
        foreach (var node in nodes)
            Nodes[node] = new List<T>();
    }

    /// <summary>
    /// 辺を追加する
    /// </summary>
    /// <param name="from">接続元の頂点</param>
    /// <param name="to">接続先の頂点</param>
    /// <returns>追加できたか</returns>
    public bool AddEdges(T from, T to)
    {
        if (!Nodes.ContainsKey(from) || !Nodes.ContainsKey(to)) return false;

        Nodes[from].Add(to);
        return true;
    }
}

このコードは閉路検知の機能もついた奴ですね。

とりあえず動作はしました。

使い方

static void Main(string[] args)
{
    // 0, ... , 5のラベルがついた頂点
    var graph = new Graph<int>(Enumerable.Range(0, 6));

    graph.AddEdges(0, 1);
    graph.AddEdges(1, 2);
    graph.AddEdges(3, 1);
    graph.AddEdges(3, 4);
    graph.AddEdges(4, 5);
    graph.AddEdges(5, 2);

    foreach (var node in TopologicalSort<int>.Excute(graph))
        Console.WriteLine(node);
}