Last active
March 5, 2021 05:42
-
-
Save adacola/19f437df3d6912a11a255ff59eb8c686 to your computer and use it in GitHub Desktop.
トポロジカルソートをF#で実装
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://programmingpraxis.com/2010/11/19/topological-sort/ | |
// 上記ページ記載のアルゴリズムを末尾再帰化、効率向上、閉路存在時の例外追加 | |
let topologicalSort edges = | |
let rec loop removed isolated = function | |
| [] -> List.rev removed @ Set.toList isolated | |
| edges -> | |
let src, dst = edges |> List.unzip | |
let dstSet = set dst | |
let noIncomingVertex = | |
src |> List.tryFind (fun s -> Set.contains s dstSet |> not) |> Option.defaultWith (fun() -> | |
invalidArg $"{nameof edges}" $"""閉路が存在します:{edges |> Seq.map string |> String.concat ","}""") | |
let nextRemoved = noIncomingVertex::removed | |
let nextIsolated = Set.remove noIncomingVertex isolated | |
let nextEdges = edges |> List.filter (fst >> (<>) noIncomingVertex) | |
loop nextRemoved nextIsolated nextEdges | |
let dstSet = edges |> List.map snd |> set | |
loop [] dstSet edges | |
let test() = | |
topologicalSort [ | |
(5, 11) | |
(11, 2); (11, 10); (11, 9) | |
(7, 11); (7, 8) | |
(8, 9) | |
(3, 10); (3, 8) | |
] | |
let testCycle() = | |
topologicalSort [ | |
(5, 11) | |
(11, 2); (11, 10); (11, 9) | |
(7, 11); (7, 8) | |
(8, 9) | |
(3, 10); (3, 8) | |
(9, 3) | |
] | |
let test2() = | |
topologicalSort [ | |
(11, 2); (11, 10); (11, 9) | |
] |
Author
adacola
commented
Mar 5, 2021
•
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment