1 module graph; 2 3 import model; 4 import std.algorithm; 5 import std.range; 6 import std.typecons; 7 version (unittest) import unit_threaded; 8 9 void write(Output)(auto ref Output output, Dependency[] dependencies) 10 { 11 import std.format : formattedWrite; 12 13 output.put("digraph Dependencies {\n"); 14 output.put("node [shape=box];\n"); 15 foreach (element; dependencies.elements) 16 { 17 output.formattedWrite!(`"%s"`)(element); 18 output.put('\n'); 19 } 20 foreach (dependency; dependencies) 21 { 22 output.formattedWrite!(`"%s" -> "%s"`)(dependency.client, dependency.supplier); 23 output.put('\n'); 24 } 25 output.put("}\n"); 26 } 27 28 @("write dependency graph in the DOT language") 29 unittest 30 { 31 import std.array : appender; 32 import std..string : outdent, stripLeft; 33 34 auto output = appender!string; 35 auto dependencies = [Dependency("a", "b")]; 36 37 output.write(dependencies); 38 39 const expected = ` 40 digraph Dependencies { 41 node [shape=box]; 42 "a" 43 "b" 44 "a" -> "b" 45 } 46 `; 47 48 output.data.should.be == outdent(expected).stripLeft; 49 } 50 51 void transitiveClosure(ref Dependency[] dependencies) 52 { 53 FullyQualifiedName[] elements = dependencies.elements; 54 55 foreach (element; elements) 56 foreach (client; elements) 57 if (dependencies.canFind(Dependency(client, element))) 58 foreach (supplier; elements) 59 if (dependencies.canFind(Dependency(element, supplier))) 60 dependencies.add(Dependency(client, supplier)); 61 } 62 63 Dependency[] transitiveReduction(ref Dependency[] dependencies) 64 { 65 bool[FullyQualifiedName] mark = null; 66 Dependency[] cyclicDependencies = null; 67 68 void traverse(FullyQualifiedName node) 69 { 70 import std.array : array; 71 72 mark[node] = true; 73 foreach (outEdge; dependencies.filter!(a => a.client == node).array) 74 { 75 if (!dependencies.canFind(outEdge)) 76 continue; 77 if (mark.get(outEdge.supplier, false)) 78 { 79 cyclicDependencies.add(outEdge); 80 continue; 81 } 82 foreach (inEdge; dependencies.filter!(a => a.supplier == outEdge.supplier).array) 83 { 84 if (inEdge == outEdge) 85 continue; 86 if (mark.get(inEdge.client, false)) 87 dependencies = dependencies.remove!(a => a == inEdge); 88 } 89 traverse(outEdge.supplier); 90 } 91 mark[node] = false; 92 } 93 94 foreach (element; dependencies.elements) 95 traverse(element); 96 97 return cyclicDependencies; 98 } 99 100 @("apply transitive reduction") 101 unittest 102 { 103 auto dependencies = [Dependency("a", "b"), Dependency("b", "c"), Dependency("a", "c")]; 104 auto cyclicDependencies = transitiveReduction(dependencies); 105 106 dependencies.should.be == [Dependency("a", "b"), Dependency("b", "c")]; 107 cyclicDependencies.shouldBeEmpty; 108 } 109 110 @("apply transitive reduction to cyclic dependencies") 111 unittest 112 { 113 auto dependencies = [Dependency("a", "b"), Dependency("b", "c"), Dependency("c", "a")]; 114 auto cyclicDependencies = transitiveReduction(dependencies); 115 116 dependencies.should.be == [Dependency("a", "b"), Dependency("b", "c"), Dependency("c", "a")]; 117 cyclicDependencies.sort.should.be == dependencies; 118 } 119 120 FullyQualifiedName[] elements(Dependency[] dependencies) 121 { 122 FullyQualifiedName[] elements = null; 123 124 foreach (dependency; dependencies) 125 { 126 elements.add(dependency.client); 127 elements.add(dependency.supplier); 128 } 129 return elements; 130 } 131 132 void add(Element)(ref Element[] elements, Element element) 133 { 134 if (!elements.canFind(element)) 135 elements ~= element; 136 }