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