graph source code

1 module graph;
2 
3 import std.algorithm;
4 import std.range;
5 import std.typecons;
6 
7 alias Dependency = Tuple!(string, "client", string, "supplier");
8 
9 void write(Output)(auto ref Output output, const 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 unittest
29 {
30     import std.array : appender;
31     import std.string : outdent, stripLeft;
32 
33     auto output = appender!string;
34     const dependencies = [Dependency("a", "b")];
35 
36     output.write(dependencies);
37 
38     const expected = `
39         digraph Dependencies {
40         node [shape=box];
41         "a"
42         "b"
43         "a" -> "b"
44         }
45         `;
46 
47     assert(output.data == outdent(expected).stripLeft);
48 }
49 
50 void transitiveClosure(ref Dependency[] dependencies)
51 {
52     string[] elements = dependencies.elements;
53 
54     foreach (element; elements)
55         foreach (client; elements)
56             if (dependencies.canFind(Dependency(client, element)))
57                 foreach (supplier; elements)
58                     if (dependencies.canFind(Dependency(element, supplier)))
59                         dependencies.add(Dependency(client, supplier));
60 }
61 
62 Dependency[] transitiveReduction(ref Dependency[] dependencies)
63 {
64     bool[string] mark = null;
65     Dependency[] cyclicDependencies = null;
66 
67     void traverse(string node)
68     {
69         import std.array : array;
70 
71         mark[node] = true;
72         foreach (outEdge; dependencies.filter!(a => a.client == node).array)
73         {
74             if (!dependencies.canFind(outEdge))
75                 continue;
76             if (mark.get(outEdge.supplier, false))
77             {
78                 cyclicDependencies.add(outEdge);
79                 continue;
80             }
81             foreach (inEdge; dependencies.filter!(a => a.supplier == outEdge.supplier).array)
82             {
83                 if (inEdge == outEdge)
84                     continue;
85                 if (mark.get(inEdge.client, false))
86                     dependencies = dependencies.remove!(a => a == inEdge);
87             }
88             traverse(outEdge.supplier);
89         }
90         mark[node] = false;
91     }
92 
93     foreach (element; dependencies.elements)
94         traverse(element);
95 
96     return cyclicDependencies;
97 }
98 
99 // transitive reduction
100 unittest
101 {
102     auto dependencies = [Dependency("a", "b"), Dependency("b", "c"), Dependency("a", "c")];
103     auto cyclicDependencies = transitiveReduction(dependencies);
104 
105     assert(dependencies == [Dependency("a", "b"), Dependency("b", "c")]);
106     assert(cyclicDependencies.empty);
107 }
108 
109 // transitive reduction with cyclic dependencies
110 unittest
111 {
112     auto dependencies = [Dependency("a", "b"), Dependency("b", "c"), Dependency("c", "a")];
113     auto cyclicDependencies = transitiveReduction(dependencies);
114 
115     assert(dependencies == [Dependency("a", "b"), Dependency("b", "c"), Dependency("c", "a")]);
116     assert(equal(cyclicDependencies.sort, dependencies));
117 }
118 
119 string[] elements(in Dependency[] dependencies)
120 {
121     string[] elements = null;
122 
123     foreach (dependency; dependencies)
124     {
125         elements.add(dependency.client);
126         elements.add(dependency.supplier);
127     }
128     return elements;
129 }
130 
131 void add(Element)(ref Element[] elements, Element element)
132 {
133     if (!elements.canFind(element))
134         elements ~= element;
135 }