17.6 KB630 lines
Blame
1import type { LayoutData } from 'mermaid';
2import type { Bounds, Point } from 'mermaid/src/types.js';
3import { BoundingBox, Layout } from 'non-layered-tidy-tree-layout';
4import type {
5 Edge,
6 LayoutResult,
7 Node,
8 PositionedEdge,
9 PositionedNode,
10 TidyTreeNode,
11} from './types.js';
12
13/**
14 * Execute the tidy-tree layout algorithm on generic layout data
15 *
16 * This function takes layout data and uses the non-layered-tidy-tree-layout
17 * algorithm to calculate optimal node positions for tree structures.
18 *
19 * @param data - The layout data containing nodes, edges, and configuration
20 * @param config - Mermaid configuration object
21 * @returns Promise resolving to layout result with positioned nodes and edges
22 */
23export function executeTidyTreeLayout(data: LayoutData): Promise<LayoutResult> {
24 let intersectionShift = 50;
25
26 return new Promise((resolve, reject) => {
27 try {
28 if (!data.nodes || !Array.isArray(data.nodes) || data.nodes.length === 0) {
29 throw new Error('No nodes found in layout data');
30 }
31
32 if (!data.edges || !Array.isArray(data.edges)) {
33 data.edges = [];
34 }
35
36 const { leftTree, rightTree, rootNode } = convertToDualTreeFormat(data);
37
38 const gap = 20;
39 const bottomPadding = 40;
40 intersectionShift = 30;
41
42 const bb = new BoundingBox(gap, bottomPadding);
43 const layout = new Layout(bb);
44
45 let leftResult = null;
46 let rightResult = null;
47
48 if (leftTree) {
49 const leftLayoutResult = layout.layout(leftTree);
50 leftResult = leftLayoutResult.result;
51 }
52
53 if (rightTree) {
54 const rightLayoutResult = layout.layout(rightTree);
55 rightResult = rightLayoutResult.result;
56 }
57
58 const positionedNodes = combineAndPositionTrees(rootNode, leftResult, rightResult);
59 const positionedEdges = calculateEdgePositions(
60 data.edges,
61 positionedNodes,
62 intersectionShift
63 );
64 resolve({
65 nodes: positionedNodes,
66 edges: positionedEdges,
67 });
68 } catch (error) {
69 reject(error);
70 }
71 });
72}
73
74/**
75 * Convert LayoutData to dual-tree format (left and right trees)
76 *
77 * This function builds two separate tree structures from the nodes and edges,
78 * alternating children between left and right trees.
79 */
80function convertToDualTreeFormat(data: LayoutData): {
81 leftTree: TidyTreeNode | null;
82 rightTree: TidyTreeNode | null;
83 rootNode: TidyTreeNode;
84} {
85 const { nodes, edges } = data;
86
87 const nodeMap = new Map<string, Node>();
88 nodes.forEach((node) => nodeMap.set(node.id, node));
89
90 const children = new Map<string, string[]>();
91 const parents = new Map<string, string>();
92
93 edges.forEach((edge) => {
94 const parentId = edge.start;
95 const childId = edge.end;
96
97 if (parentId && childId) {
98 if (!children.has(parentId)) {
99 children.set(parentId, []);
100 }
101 children.get(parentId)!.push(childId);
102 parents.set(childId, parentId);
103 }
104 });
105
106 const rootNodeData = nodes.find((node) => !parents.has(node.id));
107 if (!rootNodeData && nodes.length === 0) {
108 throw new Error('No nodes available to create tree');
109 }
110
111 const actualRoot = rootNodeData ?? nodes[0];
112
113 const rootNode: TidyTreeNode = {
114 id: actualRoot.id,
115 width: actualRoot.width ?? 100,
116 height: actualRoot.height ?? 50,
117 _originalNode: actualRoot,
118 };
119
120 const rootChildren = children.get(actualRoot.id) ?? [];
121 const leftChildren: string[] = [];
122 const rightChildren: string[] = [];
123
124 rootChildren.forEach((childId, index) => {
125 if (index % 2 === 0) {
126 leftChildren.push(childId);
127 } else {
128 rightChildren.push(childId);
129 }
130 });
131
132 const leftTree = leftChildren.length > 0 ? buildSubTree(leftChildren, children, nodeMap) : null;
133
134 const rightTree =
135 rightChildren.length > 0 ? buildSubTree(rightChildren, children, nodeMap) : null;
136
137 return { leftTree, rightTree, rootNode };
138}
139
140/**
141 * Build a subtree from a list of root children
142 * For horizontal trees, we need to transpose width/height since the tree will be rotated 90°
143 */
144function buildSubTree(
145 rootChildren: string[],
146 children: Map<string, string[]>,
147 nodeMap: Map<string, Node>
148): TidyTreeNode {
149 const virtualRoot: TidyTreeNode = {
150 id: `virtual-root-${Math.random()}`,
151 width: 1,
152 height: 1,
153 children: rootChildren
154 .map((childId) => nodeMap.get(childId))
155 .filter((child): child is Node => child !== undefined)
156 .map((child) => convertNodeToTidyTreeTransposed(child, children, nodeMap)),
157 };
158
159 return virtualRoot;
160}
161
162/**
163 * Recursively convert a node and its children to tidy-tree format
164 * This version transposes width/height for horizontal tree layout
165 */
166function convertNodeToTidyTreeTransposed(
167 node: Node,
168 children: Map<string, string[]>,
169 nodeMap: Map<string, Node>
170): TidyTreeNode {
171 const childIds = children.get(node.id) ?? [];
172 const childNodes = childIds
173 .map((childId) => nodeMap.get(childId))
174 .filter((child): child is Node => child !== undefined)
175 .map((child) => convertNodeToTidyTreeTransposed(child, children, nodeMap));
176
177 return {
178 id: node.id,
179 width: node.height ?? 50,
180 height: node.width ?? 100,
181 children: childNodes.length > 0 ? childNodes : undefined,
182 _originalNode: node,
183 };
184}
185/**
186 * Combine and position the left and right trees around the root node
187 * Creates a bidirectional layout where left tree grows left and right tree grows right
188 */
189function combineAndPositionTrees(
190 rootNode: TidyTreeNode,
191 leftResult: TidyTreeNode | null,
192 rightResult: TidyTreeNode | null
193): PositionedNode[] {
194 const positionedNodes: PositionedNode[] = [];
195
196 const rootX = 0;
197 const rootY = 0;
198
199 const treeSpacing = rootNode.width / 2 + 30;
200 const leftTreeNodes: PositionedNode[] = [];
201 const rightTreeNodes: PositionedNode[] = [];
202
203 if (leftResult?.children) {
204 positionLeftTreeBidirectional(leftResult.children, leftTreeNodes, rootX - treeSpacing, rootY);
205 }
206
207 if (rightResult?.children) {
208 positionRightTreeBidirectional(
209 rightResult.children,
210 rightTreeNodes,
211 rootX + treeSpacing,
212 rootY
213 );
214 }
215
216 let leftTreeCenterY = 0;
217 let rightTreeCenterY = 0;
218
219 if (leftTreeNodes.length > 0) {
220 const leftTreeXPositions = [...new Set(leftTreeNodes.map((node) => node.x))].sort(
221 (a, b) => b - a
222 );
223 const firstLevelLeftX = leftTreeXPositions[0];
224 const firstLevelLeftNodes = leftTreeNodes.filter((node) => node.x === firstLevelLeftX);
225
226 if (firstLevelLeftNodes.length > 0) {
227 const leftMinY = Math.min(
228 ...firstLevelLeftNodes.map((node) => node.y - (node.height ?? 50) / 2)
229 );
230 const leftMaxY = Math.max(
231 ...firstLevelLeftNodes.map((node) => node.y + (node.height ?? 50) / 2)
232 );
233 leftTreeCenterY = (leftMinY + leftMaxY) / 2;
234 }
235 }
236
237 if (rightTreeNodes.length > 0) {
238 const rightTreeXPositions = [...new Set(rightTreeNodes.map((node) => node.x))].sort(
239 (a, b) => a - b
240 );
241 const firstLevelRightX = rightTreeXPositions[0];
242 const firstLevelRightNodes = rightTreeNodes.filter((node) => node.x === firstLevelRightX);
243
244 if (firstLevelRightNodes.length > 0) {
245 const rightMinY = Math.min(
246 ...firstLevelRightNodes.map((node) => node.y - (node.height ?? 50) / 2)
247 );
248 const rightMaxY = Math.max(
249 ...firstLevelRightNodes.map((node) => node.y + (node.height ?? 50) / 2)
250 );
251 rightTreeCenterY = (rightMinY + rightMaxY) / 2;
252 }
253 }
254
255 const leftTreeOffset = -leftTreeCenterY;
256 const rightTreeOffset = -rightTreeCenterY;
257
258 positionedNodes.push({
259 id: String(rootNode.id),
260 x: rootX,
261 y: rootY + 20,
262 section: 'root',
263 width: rootNode._originalNode?.width ?? rootNode.width,
264 height: rootNode._originalNode?.height ?? rootNode.height,
265 originalNode: rootNode._originalNode,
266 });
267
268 const leftTreeNodesWithOffset = leftTreeNodes.map((node) => ({
269 id: node.id,
270 x: node.x - (node.width ?? 0) / 2,
271 y: node.y + leftTreeOffset + (node.height ?? 0) / 2,
272 section: 'left' as const,
273 width: node.width,
274 height: node.height,
275 originalNode: node.originalNode,
276 }));
277
278 const rightTreeNodesWithOffset = rightTreeNodes.map((node) => ({
279 id: node.id,
280 x: node.x + (node.width ?? 0) / 2,
281 y: node.y + rightTreeOffset + (node.height ?? 0) / 2,
282 section: 'right' as const,
283 width: node.width,
284 height: node.height,
285 originalNode: node.originalNode,
286 }));
287
288 positionedNodes.push(...leftTreeNodesWithOffset);
289 positionedNodes.push(...rightTreeNodesWithOffset);
290
291 return positionedNodes;
292}
293
294/**
295 * Position nodes from the left tree in a bidirectional layout (grows to the left)
296 * Rotates the tree 90 degrees counterclockwise so it grows horizontally to the left
297 */
298function positionLeftTreeBidirectional(
299 nodes: TidyTreeNode[],
300 positionedNodes: PositionedNode[],
301 offsetX: number,
302 offsetY: number
303): void {
304 nodes.forEach((node) => {
305 const distanceFromRoot = node.y ?? 0;
306 const verticalPosition = node.x ?? 0;
307
308 const originalWidth = node._originalNode?.width ?? 100;
309 const originalHeight = node._originalNode?.height ?? 50;
310
311 const adjustedY = offsetY + verticalPosition;
312
313 positionedNodes.push({
314 id: String(node.id),
315 x: offsetX - distanceFromRoot,
316 y: adjustedY,
317 width: originalWidth,
318 height: originalHeight,
319 originalNode: node._originalNode,
320 });
321
322 if (node.children) {
323 positionLeftTreeBidirectional(node.children, positionedNodes, offsetX, offsetY);
324 }
325 });
326}
327
328/**
329 * Position nodes from the right tree in a bidirectional layout (grows to the right)
330 * Rotates the tree 90 degrees clockwise so it grows horizontally to the right
331 */
332function positionRightTreeBidirectional(
333 nodes: TidyTreeNode[],
334 positionedNodes: PositionedNode[],
335 offsetX: number,
336 offsetY: number
337): void {
338 nodes.forEach((node) => {
339 const distanceFromRoot = node.y ?? 0;
340 const verticalPosition = node.x ?? 0;
341
342 const originalWidth = node._originalNode?.width ?? 100;
343 const originalHeight = node._originalNode?.height ?? 50;
344
345 const adjustedY = offsetY + verticalPosition;
346
347 positionedNodes.push({
348 id: String(node.id),
349 x: offsetX + distanceFromRoot,
350 y: adjustedY,
351 width: originalWidth,
352 height: originalHeight,
353 originalNode: node._originalNode,
354 });
355
356 if (node.children) {
357 positionRightTreeBidirectional(node.children, positionedNodes, offsetX, offsetY);
358 }
359 });
360}
361
362/**
363 * Calculate the intersection point of a line with a circle
364 * @param circle - Circle coordinates and radius
365 * @param lineStart - Starting point of the line
366 * @param lineEnd - Ending point of the line
367 * @returns The intersection point
368 */
369function computeCircleEdgeIntersection(circle: Bounds, lineStart: Point, lineEnd: Point): Point {
370 const radius = Math.min(circle.width, circle.height) / 2;
371
372 const dx = lineEnd.x - lineStart.x;
373 const dy = lineEnd.y - lineStart.y;
374 const length = Math.sqrt(dx * dx + dy * dy);
375
376 if (length === 0) {
377 return lineStart;
378 }
379
380 const nx = dx / length;
381 const ny = dy / length;
382
383 return {
384 x: circle.x - nx * radius,
385 y: circle.y - ny * radius,
386 };
387}
388
389function intersection(node: PositionedNode, outsidePoint: Point, insidePoint: Point): Point {
390 const x = node.x;
391 const y = node.y;
392
393 if (!node.width || !node.height) {
394 return { x: outsidePoint.x, y: outsidePoint.y };
395 }
396 const dx = Math.abs(x - insidePoint.x);
397 const w = node?.width / 2;
398 let r = insidePoint.x < outsidePoint.x ? w - dx : w + dx;
399 const h = node.height / 2;
400
401 const Q = Math.abs(outsidePoint.y - insidePoint.y);
402 const R = Math.abs(outsidePoint.x - insidePoint.x);
403
404 if (Math.abs(y - outsidePoint.y) * w > Math.abs(x - outsidePoint.x) * h) {
405 // Intersection is top or bottom of rect.
406 const q = insidePoint.y < outsidePoint.y ? outsidePoint.y - h - y : y - h - outsidePoint.y;
407 r = (R * q) / Q;
408 const res = {
409 x: insidePoint.x < outsidePoint.x ? insidePoint.x + r : insidePoint.x - R + r,
410 y: insidePoint.y < outsidePoint.y ? insidePoint.y + Q - q : insidePoint.y - Q + q,
411 };
412
413 if (r === 0) {
414 res.x = outsidePoint.x;
415 res.y = outsidePoint.y;
416 }
417 if (R === 0) {
418 res.x = outsidePoint.x;
419 }
420 if (Q === 0) {
421 res.y = outsidePoint.y;
422 }
423
424 return res;
425 } else {
426 if (insidePoint.x < outsidePoint.x) {
427 r = outsidePoint.x - w - x;
428 } else {
429 r = x - w - outsidePoint.x;
430 }
431 const q = (Q * r) / R;
432 let _x = insidePoint.x < outsidePoint.x ? insidePoint.x + R - r : insidePoint.x - R + r;
433 let _y = insidePoint.y < outsidePoint.y ? insidePoint.y + q : insidePoint.y - q;
434
435 if (r === 0) {
436 _x = outsidePoint.x;
437 _y = outsidePoint.y;
438 }
439 if (R === 0) {
440 _x = outsidePoint.x;
441 }
442 if (Q === 0) {
443 _y = outsidePoint.y;
444 }
445
446 return { x: _x, y: _y };
447 }
448}
449
450/**
451 * Calculate edge positions based on positioned nodes
452 * Now includes tree membership and node dimensions for precise edge calculations
453 * Edges now stop at shape boundaries instead of extending to centers
454 */
455function calculateEdgePositions(
456 edges: Edge[],
457 positionedNodes: PositionedNode[],
458 intersectionShift: number
459): PositionedEdge[] {
460 const nodeInfo = new Map<string, PositionedNode>();
461 positionedNodes.forEach((node) => {
462 nodeInfo.set(node.id, node);
463 });
464
465 return edges.map((edge) => {
466 const sourceNode = nodeInfo.get(edge.start ?? '');
467 const targetNode = nodeInfo.get(edge.end ?? '');
468
469 if (!sourceNode || !targetNode) {
470 return {
471 id: edge.id,
472 source: edge.start ?? '',
473 target: edge.end ?? '',
474 startX: 0,
475 startY: 0,
476 midX: 0,
477 midY: 0,
478 endX: 0,
479 endY: 0,
480 points: [{ x: 0, y: 0 }],
481 sourceSection: undefined,
482 targetSection: undefined,
483 sourceWidth: undefined,
484 sourceHeight: undefined,
485 targetWidth: undefined,
486 targetHeight: undefined,
487 };
488 }
489
490 const sourceCenter = { x: sourceNode.x, y: sourceNode.y };
491 const targetCenter = { x: targetNode.x, y: targetNode.y };
492
493 const isSourceRound = ['circle', 'cloud', 'bang'].includes(
494 sourceNode.originalNode?.shape ?? ''
495 );
496 const isTargetRound = ['circle', 'cloud', 'bang'].includes(
497 targetNode.originalNode?.shape ?? ''
498 );
499
500 let startPos = isSourceRound
501 ? computeCircleEdgeIntersection(
502 {
503 x: sourceNode.x,
504 y: sourceNode.y,
505 width: sourceNode.width ?? 100,
506 height: sourceNode.height ?? 100,
507 },
508 targetCenter,
509 sourceCenter
510 )
511 : intersection(sourceNode, sourceCenter, targetCenter);
512
513 let endPos = isTargetRound
514 ? computeCircleEdgeIntersection(
515 {
516 x: targetNode.x,
517 y: targetNode.y,
518 width: targetNode.width ?? 100,
519 height: targetNode.height ?? 100,
520 },
521 sourceCenter,
522 targetCenter
523 )
524 : intersection(targetNode, targetCenter, sourceCenter);
525
526 const midX = (startPos.x + endPos.x) / 2;
527 const midY = (startPos.y + endPos.y) / 2;
528
529 const points = [startPos];
530 if (sourceNode.section === 'left') {
531 points.push({
532 x: sourceNode.x - (sourceNode.width ?? 0) / 2 - intersectionShift,
533 y: sourceNode.y,
534 });
535 } else if (sourceNode.section === 'right') {
536 points.push({
537 x: sourceNode.x + (sourceNode.width ?? 0) / 2 + intersectionShift,
538 y: sourceNode.y,
539 });
540 }
541 if (targetNode.section === 'left') {
542 points.push({
543 x: targetNode.x + (targetNode.width ?? 0) / 2 + intersectionShift,
544 y: targetNode.y,
545 });
546 } else if (targetNode.section === 'right') {
547 points.push({
548 x: targetNode.x - (targetNode.width ?? 0) / 2 - intersectionShift,
549 y: targetNode.y,
550 });
551 }
552
553 points.push(endPos);
554
555 const secondPoint = points.length > 1 ? points[1] : targetCenter;
556 startPos = isSourceRound
557 ? computeCircleEdgeIntersection(
558 {
559 x: sourceNode.x,
560 y: sourceNode.y,
561 width: sourceNode.width ?? 100,
562 height: sourceNode.height ?? 100,
563 },
564 secondPoint,
565 sourceCenter
566 )
567 : intersection(sourceNode, secondPoint, sourceCenter);
568 points[0] = startPos;
569
570 const secondLastPoint = points.length > 1 ? points[points.length - 2] : sourceCenter;
571 endPos = isTargetRound
572 ? computeCircleEdgeIntersection(
573 {
574 x: targetNode.x,
575 y: targetNode.y,
576 width: targetNode.width ?? 100,
577 height: targetNode.height ?? 100,
578 },
579 secondLastPoint,
580 targetCenter
581 )
582 : intersection(targetNode, secondLastPoint, targetCenter);
583 points[points.length - 1] = endPos;
584
585 return {
586 id: edge.id,
587 source: edge.start ?? '',
588 target: edge.end ?? '',
589 startX: startPos.x,
590 startY: startPos.y,
591 midX,
592 midY,
593 endX: endPos.x,
594 endY: endPos.y,
595 points,
596 sourceSection: sourceNode?.section,
597 targetSection: targetNode?.section,
598 sourceWidth: sourceNode?.width,
599 sourceHeight: sourceNode?.height,
600 targetWidth: targetNode?.width,
601 targetHeight: targetNode?.height,
602 };
603 });
604}
605
606/**
607 * Validate layout data structure
608 * @param data - The data to validate
609 * @returns True if data is valid, throws error otherwise
610 */
611export function validateLayoutData(data: LayoutData): boolean {
612 if (!data) {
613 throw new Error('Layout data is required');
614 }
615
616 if (!data.config) {
617 throw new Error('Configuration is required in layout data');
618 }
619
620 if (!Array.isArray(data.nodes)) {
621 throw new Error('Nodes array is required in layout data');
622 }
623
624 if (!Array.isArray(data.edges)) {
625 throw new Error('Edges array is required in layout data');
626 }
627
628 return true;
629}
630