はじめに
今回はトポロジカルソートを実装していきたいと思います。
トポロジカルソートとは有向非巡回グラフ(DAG)においてどのノードもその出力辺の先のノードより前にくるように並べるアルゴリズムのことです。
トポロジカルソート
アルゴリズムの仕組みは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); }
閉路を検出したときになにかしたいときは、コールバックを設定してみてください。
さいごに
こちらのサイトでも高度なテストができるみたいです。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=jp
ただC#
のバージョンが古くタプルが使えないみたいなので、こちらを使う時は少し書き換える必要があります。
ではまた。