topologicalsort source code

1 module topologicalsort;
2 
3 E[] topologicalSort(E)(E[][] verticesList){
4     return verticesList.generateGraphFromVerticesList.kahnSort;
5 }
6 
7 unittest{
8     auto verticesList = [[0, 1], [0, 2], [2, 3], [1, 3]];
9     auto result = verticesList.topologicalSort;
10     assert(result[0] == 0);
11     assert(result[1] == 1 || result[1] == 2 && result[2] == 2 || result[2] == 1);
12     assert(result[3] == 3);
13 
14 }
15 
16 unittest{
17     auto NoDirectedAcyclicGraphVerticesList = [[0, 1], [1, 2], [2, 3], [3, 0]];
18     auto result = NoDirectedAcyclicGraphVerticesList.topologicalSort;
19     assert(result.length == 0);// Error, a directed cycle graph has no solution.
20 }
21 
22 private class Node(T) {
23     T container;
24     Edge!T[] from;
25     Edge!T[] to;
26 }//class Node
27 
28 private class Edge(T) {
29     Node!T from;
30     Node!T to;
31     bool isDeleted = false;
32 }//class Edge
33 
34 import std.algorithm;
35 import std.array;
36 
37 private auto generateGraphFromVerticesList(L)(L list){
38     alias E = typeof(list[0][0]);
39     Node!E[E] nodes;
40 
41     foreach (ref pair; list) {
42         if(!nodes.keys.canFind(pair[0])){
43             auto n = new Node!E();
44             nodes[pair[0]] = n;
45             nodes[pair[0]].container = pair[0];
46         }
47 
48         if(!nodes.keys.canFind(pair[$-1])){
49             auto n = new Node!E();
50             nodes[pair[$-1]] = n;
51             nodes[pair[$-1]].container = pair[$-1];
52         }
53         Edge!E edge = new Edge!E();
54         edge.from = nodes[pair[0]];
55         edge.to   = nodes[pair[$-1]];
56         
57         nodes[pair[0]].to ~= edge;
58         nodes[pair[$-1]].from ~= edge;
59     }
60     return nodes.keys.map!(key => nodes[key])
61               .filter!(node => node.from.length == 0)
62               .array;
63 }
64 
65 unittest{
66     auto list = [[1, 2], [3, 4], [2, 4]];
67     assert(list.generateGraphFromVerticesList.length == 2);
68 }
69 
70 private T[] kahnSort(N:Node!T, T)(N[] graphs){
71     N[] s = graphs;
72     N[] l;
73     while (s.length > 0) {
74         auto n = s[0];
75         if(s.length > 1){
76             s = s[1 .. $];
77         }else{
78             s = [];
79         }
80 
81         l ~= n;
82 
83         foreach (ref e; n.to.filter!(e => !e.isDeleted).array) {
84             e.isDeleted = true;
85             auto m = e.to;
86             if(m.from.filter!(e => !e.isDeleted).array.length == 0) s ~= m;
87         }
88     }
89     foreach (n; l) {
90         if(n.from.filter!(e => !e.isDeleted).array.length > 0 || n.to.filter!(e => !e.isDeleted).array.length > 0) return [];
91     }
92     return l.map!(n => n.container).array;
93 }
94