diff options
Diffstat (limited to 'subprojects/frontend/src/graph/dotSource.ts')
-rw-r--r-- | subprojects/frontend/src/graph/dotSource.ts | 309 |
1 files changed, 309 insertions, 0 deletions
diff --git a/subprojects/frontend/src/graph/dotSource.ts b/subprojects/frontend/src/graph/dotSource.ts new file mode 100644 index 00000000..bf45d303 --- /dev/null +++ b/subprojects/frontend/src/graph/dotSource.ts | |||
@@ -0,0 +1,309 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | |||
7 | import type { | ||
8 | NodeMetadata, | ||
9 | RelationMetadata, | ||
10 | } from '../xtext/xtextServiceResults'; | ||
11 | |||
12 | import type GraphStore from './GraphStore'; | ||
13 | |||
14 | const EDGE_WEIGHT = 1; | ||
15 | const CONTAINMENT_WEIGHT = 5; | ||
16 | const UNKNOWN_WEIGHT_FACTOR = 0.5; | ||
17 | |||
18 | function nodeName({ simpleName, kind }: NodeMetadata): string { | ||
19 | switch (kind) { | ||
20 | case 'INDIVIDUAL': | ||
21 | return `<b>${simpleName}</b>`; | ||
22 | case 'NEW': | ||
23 | return `<i>${simpleName}</i>`; | ||
24 | default: | ||
25 | return simpleName; | ||
26 | } | ||
27 | } | ||
28 | |||
29 | function relationName({ simpleName, detail }: RelationMetadata): string { | ||
30 | if (detail.type === 'class' && detail.abstractClass) { | ||
31 | return `<i>${simpleName}</i>`; | ||
32 | } | ||
33 | if (detail.type === 'reference' && detail.containment) { | ||
34 | return `<b>${simpleName}</b>`; | ||
35 | } | ||
36 | return simpleName; | ||
37 | } | ||
38 | |||
39 | interface NodeData { | ||
40 | exists: string; | ||
41 | equalsSelf: string; | ||
42 | unaryPredicates: Map<RelationMetadata, string>; | ||
43 | } | ||
44 | |||
45 | function computeNodeData(graph: GraphStore): NodeData[] { | ||
46 | const { | ||
47 | semantics: { nodes, relations, partialInterpretation }, | ||
48 | } = graph; | ||
49 | |||
50 | const nodeData = Array.from(Array(nodes.length)).map(() => ({ | ||
51 | exists: 'FALSE', | ||
52 | equalsSelf: 'FALSE', | ||
53 | unaryPredicates: new Map(), | ||
54 | })); | ||
55 | |||
56 | relations.forEach((relation) => { | ||
57 | if (relation.arity !== 1) { | ||
58 | return; | ||
59 | } | ||
60 | const visibility = graph.getVisiblity(relation.name); | ||
61 | if (visibility === 'none') { | ||
62 | return; | ||
63 | } | ||
64 | const interpretation = partialInterpretation[relation.name] ?? []; | ||
65 | interpretation.forEach(([index, value]) => { | ||
66 | if ( | ||
67 | typeof index === 'number' && | ||
68 | typeof value === 'string' && | ||
69 | (visibility === 'all' || value !== 'UNKNOWN') | ||
70 | ) { | ||
71 | nodeData[index]?.unaryPredicates?.set(relation, value); | ||
72 | } | ||
73 | }); | ||
74 | }); | ||
75 | |||
76 | partialInterpretation['builtin::exists']?.forEach(([index, value]) => { | ||
77 | if (typeof index === 'number' && typeof value === 'string') { | ||
78 | const data = nodeData[index]; | ||
79 | if (data !== undefined) { | ||
80 | data.exists = value; | ||
81 | } | ||
82 | } | ||
83 | }); | ||
84 | |||
85 | partialInterpretation['builtin::equals']?.forEach(([index, other, value]) => { | ||
86 | if ( | ||
87 | typeof index === 'number' && | ||
88 | index === other && | ||
89 | typeof value === 'string' | ||
90 | ) { | ||
91 | const data = nodeData[index]; | ||
92 | if (data !== undefined) { | ||
93 | data.equalsSelf = value; | ||
94 | } | ||
95 | } | ||
96 | }); | ||
97 | |||
98 | return nodeData; | ||
99 | } | ||
100 | |||
101 | function createNodes(graph: GraphStore, lines: string[]): void { | ||
102 | const nodeData = computeNodeData(graph); | ||
103 | const { | ||
104 | semantics: { nodes }, | ||
105 | } = graph; | ||
106 | |||
107 | nodes.forEach((node, i) => { | ||
108 | const data = nodeData[i]; | ||
109 | if (data === undefined) { | ||
110 | return; | ||
111 | } | ||
112 | const classes = [ | ||
113 | `node-${node.kind} node-exists-${data.exists} node-equalsSelf-${data.equalsSelf}`, | ||
114 | ].join(' '); | ||
115 | const name = nodeName(node); | ||
116 | const border = node.kind === 'INDIVIDUAL' ? 2 : 1; | ||
117 | lines.push(`n${i} [id="${node.name}", class="${classes}", label=< | ||
118 | <table border="${border}" cellborder="0" cellspacing="0" style="rounded" bgcolor="white"> | ||
119 | <tr><td cellpadding="4.5" width="32" bgcolor="green">${name}</td></tr>`); | ||
120 | if (data.unaryPredicates.size > 0) { | ||
121 | lines.push( | ||
122 | '<hr/><tr><td cellpadding="4.5"><table fixedsize="TRUE" align="left" border="0" cellborder="0" cellspacing="0" cellpadding="1.5">', | ||
123 | ); | ||
124 | data.unaryPredicates.forEach((value, relation) => { | ||
125 | lines.push( | ||
126 | `<tr> | ||
127 | <td><img src="#${value}"/></td> | ||
128 | <td width="1.5"></td> | ||
129 | <td align="left" href="#${value}" id="${node.name},${ | ||
130 | relation.name | ||
131 | },label">${relationName(relation)}</td> | ||
132 | </tr>`, | ||
133 | ); | ||
134 | }); | ||
135 | lines.push('</table></td></tr>'); | ||
136 | } | ||
137 | lines.push('</table>>]'); | ||
138 | }); | ||
139 | } | ||
140 | |||
141 | function compare( | ||
142 | a: readonly (number | string)[], | ||
143 | b: readonly number[], | ||
144 | ): number { | ||
145 | if (a.length !== b.length + 1) { | ||
146 | throw new Error('Tuple length mismatch'); | ||
147 | } | ||
148 | for (let i = 0; i < b.length; i += 1) { | ||
149 | const aItem = a[i]; | ||
150 | const bItem = b[i]; | ||
151 | if (typeof aItem !== 'number' || typeof bItem !== 'number') { | ||
152 | throw new Error('Invalid tuple'); | ||
153 | } | ||
154 | if (aItem < bItem) { | ||
155 | return -1; | ||
156 | } | ||
157 | if (aItem > bItem) { | ||
158 | return 1; | ||
159 | } | ||
160 | } | ||
161 | return 0; | ||
162 | } | ||
163 | |||
164 | function binarySerach( | ||
165 | tuples: readonly (readonly (number | string)[])[], | ||
166 | key: readonly number[], | ||
167 | ): string | undefined { | ||
168 | let lower = 0; | ||
169 | let upper = tuples.length - 1; | ||
170 | while (lower <= upper) { | ||
171 | const middle = Math.floor((lower + upper) / 2); | ||
172 | const tuple = tuples[middle]; | ||
173 | if (tuple === undefined) { | ||
174 | throw new Error('Range error'); | ||
175 | } | ||
176 | const result = compare(tuple, key); | ||
177 | if (result === 0) { | ||
178 | const found = tuple[key.length]; | ||
179 | if (typeof found !== 'string') { | ||
180 | throw new Error('Invalid tuple value'); | ||
181 | } | ||
182 | return found; | ||
183 | } | ||
184 | if (result < 0) { | ||
185 | lower = middle + 1; | ||
186 | } else { | ||
187 | // result > 0 | ||
188 | upper = middle - 1; | ||
189 | } | ||
190 | } | ||
191 | return undefined; | ||
192 | } | ||
193 | |||
194 | function createRelationEdges( | ||
195 | graph: GraphStore, | ||
196 | relation: RelationMetadata, | ||
197 | showUnknown: boolean, | ||
198 | lines: string[], | ||
199 | ): void { | ||
200 | const { | ||
201 | semantics: { nodes, partialInterpretation }, | ||
202 | } = graph; | ||
203 | const { detail } = relation; | ||
204 | |||
205 | let constraint: 'true' | 'false' = 'true'; | ||
206 | let weight = EDGE_WEIGHT; | ||
207 | let penwidth = 1; | ||
208 | let label = `"${relation.simpleName}"`; | ||
209 | if (detail.type === 'reference' && detail.containment) { | ||
210 | weight = CONTAINMENT_WEIGHT; | ||
211 | label = `<<b>${relation.simpleName}</b>>`; | ||
212 | penwidth = 2; | ||
213 | } else if ( | ||
214 | detail.type === 'opposite' && | ||
215 | graph.getVisiblity(detail.opposite) !== 'none' | ||
216 | ) { | ||
217 | constraint = 'false'; | ||
218 | weight = 0; | ||
219 | } | ||
220 | |||
221 | const tuples = partialInterpretation[relation.name] ?? []; | ||
222 | tuples.forEach(([from, to, value]) => { | ||
223 | const isUnknown = value === 'UNKNOWN'; | ||
224 | if ( | ||
225 | (!showUnknown && isUnknown) || | ||
226 | typeof from !== 'number' || | ||
227 | typeof to !== 'number' || | ||
228 | typeof value !== 'string' | ||
229 | ) { | ||
230 | return; | ||
231 | } | ||
232 | |||
233 | const fromNode = nodes[from]; | ||
234 | const toNode = nodes[to]; | ||
235 | if (fromNode === undefined || toNode === undefined) { | ||
236 | return; | ||
237 | } | ||
238 | |||
239 | let dir = 'forward'; | ||
240 | let edgeConstraint = constraint; | ||
241 | let edgeWeight = weight; | ||
242 | const opposite = binarySerach(tuples, [to, from]); | ||
243 | const oppositeUnknown = opposite === 'UNKNOWN'; | ||
244 | const oppositeSet = opposite !== undefined; | ||
245 | const oppositeVisible = oppositeSet && (showUnknown || !oppositeUnknown); | ||
246 | if (opposite === value) { | ||
247 | if (to < from) { | ||
248 | // We already added this edge in the reverse direction. | ||
249 | return; | ||
250 | } | ||
251 | if (to > from) { | ||
252 | dir = 'both'; | ||
253 | } | ||
254 | } else if (oppositeVisible && to < from) { | ||
255 | // Let the opposite edge drive the graph layout. | ||
256 | edgeConstraint = 'false'; | ||
257 | edgeWeight = 0; | ||
258 | } else if (isUnknown && (!oppositeSet || oppositeUnknown)) { | ||
259 | // Only apply the UNKNOWN value penalty if we aren't the opposite | ||
260 | // edge driving the graph layout from above, or the penalty would | ||
261 | // be applied anyway. | ||
262 | edgeWeight *= UNKNOWN_WEIGHT_FACTOR; | ||
263 | } | ||
264 | |||
265 | lines.push(`n${from} -> n${to} [ | ||
266 | id="${fromNode.name},${toNode.name},${relation.name}", | ||
267 | dir="${dir}", | ||
268 | constraint=${edgeConstraint}, | ||
269 | weight=${edgeWeight}, | ||
270 | xlabel=${label}, | ||
271 | penwidth=${penwidth}, | ||
272 | style="${isUnknown ? 'dashed' : 'solid'}", | ||
273 | class="edge-${value}" | ||
274 | ]`); | ||
275 | }); | ||
276 | } | ||
277 | |||
278 | function createEdges(graph: GraphStore, lines: string[]): void { | ||
279 | const { | ||
280 | semantics: { relations }, | ||
281 | } = graph; | ||
282 | relations.forEach((relation) => { | ||
283 | if (relation.arity !== 2) { | ||
284 | return; | ||
285 | } | ||
286 | const visibility = graph.getVisiblity(relation.name); | ||
287 | if (visibility !== 'none') { | ||
288 | createRelationEdges(graph, relation, visibility === 'all', lines); | ||
289 | } | ||
290 | }); | ||
291 | } | ||
292 | |||
293 | export default function dotSource( | ||
294 | graph: GraphStore | undefined, | ||
295 | ): string | undefined { | ||
296 | if (graph === undefined) { | ||
297 | return undefined; | ||
298 | } | ||
299 | const lines = [ | ||
300 | 'digraph {', | ||
301 | 'graph [bgcolor=transparent];', | ||
302 | `node [fontsize=12, shape=plain, fontname="OpenSans"];`, | ||
303 | 'edge [fontsize=10.5, color=black, fontname="OpenSans"];', | ||
304 | ]; | ||
305 | createNodes(graph, lines); | ||
306 | createEdges(graph, lines); | ||
307 | lines.push('}'); | ||
308 | return lines.join('\n'); | ||
309 | } | ||