20661584252

Committed 02 Jan 2026 03:50PM UTC coverage: 77.924% (+7.3%) from 70.62%

Build # 20661584252

Build Type

push

github

Committed by

apowers313

Commit Message

ci: fix flakey performance test

Run Details

13438 of 17822 branches covered (75.4%)

Branch coverage included in aggregate %.

41247 of 52355 relevant lines covered (78.78%)

145534.85 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

86.4

/graphty-element/src/layout/D3GraphLayoutEngine.ts

import {
    Edge as D3Edge,
    forceCenter,
    forceLink,
    forceManyBody,
    forceSimulation,
    InputEdge as D3InputEdge,
    Node as D3Node,
} from "d3-force-3d";
import { z } from "zod/v4";

import { defineOptions, type OptionsSchema } from "../config";
import type { Edge } from "../Edge";
import type { Node, NodeIdType } from "../Node";
import { EdgePosition, LayoutEngine, Position } from "./LayoutEngine";

/**
 * Zod-based options schema for D3 Force Layout
 */
export const d3LayoutOptionsSchema = defineOptions({
    alphaMin: {
        schema: z.number().positive().default(0.1),
        meta: {
            label: "Alpha Min",
            description: "Minimum alpha before simulation stops",
            step: 0.01,
            advanced: true,
        },
    },
    alphaTarget: {
        schema: z.number().min(0).default(0),
        meta: {
            label: "Alpha Target",
            description: "Target alpha value",
            step: 0.01,
            advanced: true,
        },
    },
    alphaDecay: {
        schema: z.number().positive().default(0.0228),
        meta: {
            label: "Alpha Decay",
            description: "Rate of alpha decay per tick",
            step: 0.001,
            advanced: true,
        },
    },
    velocityDecay: {
        schema: z.number().positive().default(0.4),
        meta: {
            label: "Velocity Decay",
            description: "Velocity damping factor",
            step: 0.05,
        },
    },
});

interface D3InputNode extends Partial<D3Node> {
    id: NodeIdType;
}

function isD3Node(n: unknown): n is D3Node {
    if (
        typeof n === "object" &&
        n !== null &&
        "index" in n &&
        typeof n.index === "number" &&
        "x" in n &&
        typeof n.x === "number" &&
        "y" in n &&
        typeof n.y === "number" &&
        "z" in n &&
        typeof n.z === "number" &&
        "vx" in n &&
        typeof n.vx === "number" &&
        "vy" in n &&
        typeof n.vy === "number" &&
        "vz" in n &&
        typeof n.vz === "number"
    ) {
        return true;
    }

    return false;
}

export const D3LayoutConfig = z.strictObject({
    alphaMin: z.number().positive().default(0.1),
    alphaTarget: z.number().min(0).default(0),
    alphaDecay: z.number().positive().default(0.0228),
    velocityDecay: z.number().positive().default(0.4),
});

export type D3LayoutOptions = Partial<z.infer<typeof D3LayoutConfig>>;

function isD3Edge(e: unknown): e is D3Edge {
    if (
        typeof e === "object" &&
        e !== null &&
        Object.hasOwn(e, "index") &&
        "index" in e &&
        typeof e.index === "number" &&
        "source" in e &&
        isD3Node(e.source) &&
        "target" in e &&
        isD3Node(e.target)
    ) {
        return true;
    }

    return false;
}

/**
 * D3 force-directed layout engine using d3-force-3d simulation
 */
export class D3GraphEngine extends LayoutEngine {
    static type = "d3";
    static maxDimensions = 3;
    static zodOptionsSchema: OptionsSchema = d3LayoutOptionsSchema;
    d3ForceLayout: ReturnType<typeof forceSimulation>;
    d3AlphaMin: number;
    d3AlphaTarget: number;
    d3AlphaDecay: number;
    d3VelocityDecay: number;
    nodeMapping = new Map<Node, D3Node>();
    edgeMapping = new Map<Edge, D3Edge>();
    newNodeMap = new Map<Node, D3InputNode>();
    newEdgeMap = new Map<Edge, D3InputEdge>();
    reheat = false;

    /**
     * Check if there are pending nodes or edges to be processed
     * @returns True if the graph needs to be refreshed
     */
    get graphNeedsRefresh(): boolean {
        return !!this.newNodeMap.size || !!this.newEdgeMap.size;
    }

    /**
     * Create a D3 force-directed layout engine
     * @param anyOpts - Configuration options for the D3 simulation
     */
    constructor(anyOpts: D3LayoutOptions = {}) {
        super();

        const opts = D3LayoutConfig.parse(anyOpts);
        this.d3AlphaMin = opts.alphaMin;
        this.d3AlphaTarget = opts.alphaTarget;
        this.d3AlphaDecay = opts.alphaDecay;
        this.d3VelocityDecay = opts.velocityDecay;

        // https://github.com/vasturiano/d3-force-3d?tab=readme-ov-file#links
        const fl = forceLink();
        fl.strength(0.9);
        this.d3ForceLayout = forceSimulation()
            .numDimensions(3)
            .alpha(1)
            .force("link", fl)
            .force("charge", forceManyBody())
            .force("center", forceCenter())
            .force("dagRadial", null)
            .stop();
        this.d3ForceLayout.force("link").id((d) => (d as D3InputNode).id);
    }

    /**
     * Initialize the layout engine
     *
     * D3 force simulation is initialized in the constructor and doesn't require
     * additional async initialization.
     */
    async init(): Promise<void> {
        // No-op - D3 simulation is ready after construction
    }

    /**
     * Refresh the D3 simulation with pending nodes and edges
     */
    refresh(): void {
        if (this.graphNeedsRefresh || this.reheat) {
            // update nodes
            let nodeList: (D3Node | D3InputNode)[] = [...this.nodeMapping.values()];
            nodeList = nodeList.concat([...this.newNodeMap.values()]);
            this.d3ForceLayout
                .alpha(1) // re-heat the simulation
                .nodes(nodeList)
                .stop();

            // copy over new nodes
            for (const entry of this.newNodeMap.entries()) {
                const n = entry[0];
                const d3node = entry[1];
                if (!isD3Node(d3node)) {
                    throw new Error("Internal error: Node is not settled as a complete D3 Node");
                }

                this.nodeMapping.set(n, d3node);
            }
            this.newNodeMap.clear();

            // update edges
            let linkList: (D3Edge | D3InputEdge)[] = [...this.edgeMapping.values()];
            linkList = linkList.concat([...this.newEdgeMap.values()]);
            this.d3ForceLayout.force("link").links(linkList);

            // copy over new edges
            for (const entry of this.newEdgeMap.entries()) {
                const e = entry[0];
                const d3edge = entry[1];
                if (!isD3Edge(d3edge)) {
                    throw new Error("Internal error: Edge is not settled as a complete D3 Edge");
                }

                this.edgeMapping.set(e, d3edge);
            }
            this.newEdgeMap.clear();
        }
    }

    /**
     * Advance the D3 simulation by one tick
     */
    step(): void {
        this.refresh();
        this.d3ForceLayout.tick();
    }

    /**
     * Check if the simulation has settled below alpha minimum
     * @returns True if the simulation has settled
     */
    get isSettled(): boolean {
        // If there are pending nodes/edges to be processed, we're not settled
        if (this.graphNeedsRefresh) {
            return false;
        }

        return this.d3ForceLayout.alpha() < this.d3AlphaMin;
    }

    /**
     * Add a node to the D3 simulation
     * @param n - The node to add
     */
    addNode(n: Node): void {
        this.newNodeMap.set(n, { id: n.id });
    }

    /**
     * Add an edge to the D3 simulation
     * @param e - The edge to add
     */
    addEdge(e: Edge): void {
        this.newEdgeMap.set(e, {
            source: e.srcId,
            target: e.dstId,
        });
    }

    /**
     * Get all nodes in the simulation
     * @returns Iterable of nodes
     */
    get nodes(): Iterable<Node> {
        return this.nodeMapping.keys();
    }

    /**
     * Get all edges in the simulation
     * @returns Iterable of edges
     */
    get edges(): Iterable<Edge> {
        return this.edgeMapping.keys();
    }

    /**
     * Get the current position of a node in the simulation
     * @param n - The node to get position for
     * @returns The node's position coordinates
     */
    getNodePosition(n: Node): Position {
        const d3node = this._getMappedNode(n);
        // if (d3node.x === undefined || d3node.y === undefined || d3node.z === undefined) {
        //     throw new Error("Internal error: Node not initialized in D3GraphEngine");
        // }

        return {
            x: d3node.x,
            y: d3node.y,
            z: d3node.z,
        };
    }

    /**
     * Set a node's position in the simulation
     * @param n - The node to set position for
     * @param newPos - The new position coordinates
     */
    setNodePosition(n: Node, newPos: Position): void {
        const d3node = this._getMappedNode(n);
        d3node.x = newPos.x;
        d3node.y = newPos.y;
        d3node.z = newPos.z ?? 0;
        this.reheat = true;
    }

    /**
     * Get the position of an edge based on its endpoint positions
     * @param e - The edge to get position for
     * @returns The edge's source and destination positions
     */
    getEdgePosition(e: Edge): EdgePosition {
        const d3edge = this._getMappedEdge(e);

        return {
            src: {
                x: d3edge.source.x,
                y: d3edge.source.y,
                z: d3edge.source.z,
            },
            dst: {
                x: d3edge.target.x,
                y: d3edge.target.y,
                z: d3edge.target.z,
            },
        };
    }

    /**
     * Pin a node to its current position
     * @param n - The node to pin
     */
    pin(n: Node): void {
        const d3node = this._getMappedNode(n);

        d3node.fx = d3node.x;
        d3node.fy = d3node.y;
        d3node.fz = d3node.z;
        this.reheat = true; // TODO: is this necessary?
    }

    /**
     * Unpin a node to allow it to move freely
     * @param n - The node to unpin
     */
    unpin(n: Node): void {
        const d3node = this._getMappedNode(n);

        d3node.fx = undefined;
        d3node.fy = undefined;
        d3node.fz = undefined;
        this.reheat = true; // TODO: is this necessary?
    }

    private _getMappedNode(n: Node): D3Node {
        this.refresh(); // ensure consistent state

        const d3node = this.nodeMapping.get(n);
        if (!d3node) {
            throw new Error("Internal error: Node not found in D3GraphEngine");
        }

        return d3node;
    }

    private _getMappedEdge(e: Edge): D3Edge {
        this.refresh(); // ensure consistent state

        const d3edge = this.edgeMapping.get(e);
        if (!d3edge) {
            throw new Error("Internal error: Edge not found in D3GraphEngine");
        }

        return d3edge;
    }
}

1	import {	14!
2	Edge as D3Edge,
3	forceCenter,	14✔
4	forceLink,	14✔
5	forceManyBody,	14✔
6	forceSimulation,	14✔
7	InputEdge as D3InputEdge,
8	Node as D3Node,
9	} from "d3-force-3d";	14✔
10	import { z } from "zod/v4";	14✔
11
12	import { defineOptions, type OptionsSchema } from "../config";	14✔
13	import type { Edge } from "../Edge";
14	import type { Node, NodeIdType } from "../Node";
15	import { EdgePosition, LayoutEngine, Position } from "./LayoutEngine";	14✔
16
17	/**
18	* Zod-based options schema for D3 Force Layout
19	*/
20	export const d3LayoutOptionsSchema = defineOptions({	14✔
21	alphaMin: {	14✔
22	schema: z.number().positive().default(0.1),	14✔
23	meta: {	14✔
24	label: "Alpha Min",	14✔
25	description: "Minimum alpha before simulation stops",	14✔
26	step: 0.01,	14✔
27	advanced: true,	14✔
28	},	14✔
29	},	14✔
30	alphaTarget: {	14✔
31	schema: z.number().min(0).default(0),	14✔
32	meta: {	14✔
33	label: "Alpha Target",	14✔
34	description: "Target alpha value",	14✔
35	step: 0.01,	14✔
36	advanced: true,	14✔
37	},	14✔
38	},	14✔
39	alphaDecay: {	14✔
40	schema: z.number().positive().default(0.0228),	14✔
41	meta: {	14✔
42	label: "Alpha Decay",	14✔
43	description: "Rate of alpha decay per tick",	14✔
44	step: 0.001,	14✔
45	advanced: true,	14✔
46	},	14✔
47	},	14✔
48	velocityDecay: {	14✔
49	schema: z.number().positive().default(0.4),	14✔
50	meta: {	14✔
51	label: "Velocity Decay",	14✔
52	description: "Velocity damping factor",	14✔
53	step: 0.05,	14✔
54	},	14✔
55	},	14✔
56	});	14✔
57
58	interface D3InputNode extends Partial<D3Node> {
59	id: NodeIdType;
60	}
61
62	function isD3Node(n: unknown): n is D3Node {	639✔
63	if (	639✔
64	typeof n === "object" &&	639✔
65	n !== null &&	639✔
66	"index" in n &&	639✔
67	typeof n.index === "number" &&	639✔
68	"x" in n &&	639✔
69	typeof n.x === "number" &&	639✔
70	"y" in n &&	639✔
71	typeof n.y === "number" &&	639✔
72	"z" in n &&	639✔
73	typeof n.z === "number" &&	639✔
74	"vx" in n &&	639✔
75	typeof n.vx === "number" &&	639✔
76	"vy" in n &&	639✔
77	typeof n.vy === "number" &&	639✔
78	"vz" in n &&	639✔
79	typeof n.vz === "number"	639✔
80	) {	639✔
81	return true;	639✔
82	}	639!
83
84	return false;	×
85	}	×
86
87	export const D3LayoutConfig = z.strictObject({	14✔
88	alphaMin: z.number().positive().default(0.1),	14✔
89	alphaTarget: z.number().min(0).default(0),	14✔
90	alphaDecay: z.number().positive().default(0.0228),	14✔
91	velocityDecay: z.number().positive().default(0.4),	14✔
92	});	14✔
93
94	export type D3LayoutOptions = Partial<z.infer<typeof D3LayoutConfig>>;
95
96	function isD3Edge(e: unknown): e is D3Edge {	271✔
97	if (	271✔
98	typeof e === "object" &&	271✔
99	e !== null &&	271✔
100	Object.hasOwn(e, "index") &&	271✔
101	"index" in e &&	271✔
102	typeof e.index === "number" &&	271✔
103	"source" in e &&	271✔
104	isD3Node(e.source) &&	271✔
105	"target" in e &&	271✔
106	isD3Node(e.target)	271✔
107	) {	271✔
108	return true;	271✔
109	}	271!
110
111	return false;	×
112	}	×
113
114	/**
115	* D3 force-directed layout engine using d3-force-3d simulation
116	*/
117	export class D3GraphEngine extends LayoutEngine {	14✔
118	static type = "d3";	14✔
119	static maxDimensions = 3;	14✔
120	static zodOptionsSchema: OptionsSchema = d3LayoutOptionsSchema;	14✔
121	d3ForceLayout: ReturnType<typeof forceSimulation>;
122	d3AlphaMin: number;
123	d3AlphaTarget: number;
124	d3AlphaDecay: number;
125	d3VelocityDecay: number;
126	nodeMapping = new Map<Node, D3Node>();	14✔
127	edgeMapping = new Map<Edge, D3Edge>();	14✔
128	newNodeMap = new Map<Node, D3InputNode>();	14✔
129	newEdgeMap = new Map<Edge, D3InputEdge>();	14✔
130	reheat = false;	14✔
131
132	/**
133	* Check if there are pending nodes or edges to be processed
134	* @returns True if the graph needs to be refreshed
135	*/
136	get graphNeedsRefresh(): boolean {	14✔
137	return !!this.newNodeMap.size \|\| !!this.newEdgeMap.size;	24,215✔
138	}	24,215✔
139
140	/**
141	* Create a D3 force-directed layout engine
142	* @param anyOpts - Configuration options for the D3 simulation
143	*/
144	constructor(anyOpts: D3LayoutOptions = {}) {	14✔
145	super();	6✔
146
147	const opts = D3LayoutConfig.parse(anyOpts);	6✔
148	this.d3AlphaMin = opts.alphaMin;	6✔
149	this.d3AlphaTarget = opts.alphaTarget;	6✔
150	this.d3AlphaDecay = opts.alphaDecay;	6✔
151	this.d3VelocityDecay = opts.velocityDecay;	6✔
152
153	// https://github.com/vasturiano/d3-force-3d?tab=readme-ov-file#links
154	const fl = forceLink();	6✔
155	fl.strength(0.9);	6✔
156	this.d3ForceLayout = forceSimulation()	6✔
157	.numDimensions(3)	6✔
158	.alpha(1)	6✔
159	.force("link", fl)	6✔
160	.force("charge", forceManyBody())	6✔
161	.force("center", forceCenter())	6✔
162	.force("dagRadial", null)	6✔
163	.stop();	6✔
164	this.d3ForceLayout.force("link").id((d) => (d as D3InputNode).id);	6✔
165	}	6✔
166
167	/**
168	* Initialize the layout engine
169	*
170	* D3 force simulation is initialized in the constructor and doesn't require
171	* additional async initialization.
172	*/
173	async init(): Promise<void> {	14✔
174	// No-op - D3 simulation is ready after construction
175	}	6✔
176
177	/**
178	* Refresh the D3 simulation with pending nodes and edges
179	*/
180	refresh(): void {	14✔
181	if (this.graphNeedsRefresh \|\| this.reheat) {	22,790✔
182	// update nodes
183	let nodeList: (D3Node \| D3InputNode)[] = [...this.nodeMapping.values()];	6✔
184	nodeList = nodeList.concat([...this.newNodeMap.values()]);	6✔
185	this.d3ForceLayout	6✔
186	.alpha(1) // re-heat the simulation	6✔
187	.nodes(nodeList)	6✔
188	.stop();	6✔
189
190	// copy over new nodes
191	for (const entry of this.newNodeMap.entries()) {	6✔
192	const n = entry[0];	97✔
193	const d3node = entry[1];	97✔
194	if (!isD3Node(d3node)) {	97!
195	throw new Error("Internal error: Node is not settled as a complete D3 Node");	×
196	}	×
197
198	this.nodeMapping.set(n, d3node);	97✔
199	}	97✔
200	this.newNodeMap.clear();	6✔
201
202	// update edges
203	let linkList: (D3Edge \| D3InputEdge)[] = [...this.edgeMapping.values()];	6✔
204	linkList = linkList.concat([...this.newEdgeMap.values()]);	6✔
205	this.d3ForceLayout.force("link").links(linkList);	6✔
206
207	// copy over new edges
208	for (const entry of this.newEdgeMap.entries()) {	6✔
209	const e = entry[0];	271✔
210	const d3edge = entry[1];	271✔
211	if (!isD3Edge(d3edge)) {	271!
212	throw new Error("Internal error: Edge is not settled as a complete D3 Edge");	×
213	}	×
214
215	this.edgeMapping.set(e, d3edge);	271✔
216	}	271✔
217	this.newEdgeMap.clear();	6✔
218	}	6✔
219	}	22,790✔
220
221	/**
222	* Advance the D3 simulation by one tick
223	*/
224	step(): void {	14✔
225	this.refresh();	374✔
226	this.d3ForceLayout.tick();	374✔
227	}	374✔
228
229	/**
230	* Check if the simulation has settled below alpha minimum
231	* @returns True if the simulation has settled
232	*/
233	get isSettled(): boolean {	14✔
234	// If there are pending nodes/edges to be processed, we're not settled
235	if (this.graphNeedsRefresh) {	1,425✔
236	return false;	7✔
237	}	7✔
238
239	return this.d3ForceLayout.alpha() < this.d3AlphaMin;	1,418✔
240	}	1,425✔
241
242	/**
243	* Add a node to the D3 simulation
244	* @param n - The node to add
245	*/
246	addNode(n: Node): void {	14✔
247	this.newNodeMap.set(n, { id: n.id });	97✔
248	}	97✔
249
250	/**
251	* Add an edge to the D3 simulation
252	* @param e - The edge to add
253	*/
254	addEdge(e: Edge): void {	14✔
255	this.newEdgeMap.set(e, {	271✔
256	source: e.srcId,	271✔
257	target: e.dstId,	271✔
258	});	271✔
259	}	271✔
260
261	/**
262	* Get all nodes in the simulation
263	* @returns Iterable of nodes
264	*/
265	get nodes(): Iterable<Node> {	14✔
266	return this.nodeMapping.keys();	266✔
267	}	266✔
268
269	/**
270	* Get all edges in the simulation
271	* @returns Iterable of edges
272	*/
273	get edges(): Iterable<Edge> {	14✔
274	return this.edgeMapping.keys();	574✔
275	}	574✔
276
277	/**
278	* Get the current position of a node in the simulation
279	* @param n - The node to get position for
280	* @returns The node's position coordinates
281	*/
282	getNodePosition(n: Node): Position {	14✔
283	const d3node = this._getMappedNode(n);	5,783✔
284	// if (d3node.x === undefined \|\| d3node.y === undefined \|\| d3node.z === undefined) {
285	// throw new Error("Internal error: Node not initialized in D3GraphEngine");
286	// }
287
288	return {	5,783✔
289	x: d3node.x,	5,783✔
290	y: d3node.y,	5,783✔
291	z: d3node.z,	5,783✔
292	};	5,783✔
293	}	5,783✔
294
295	/**
296	* Set a node's position in the simulation
297	* @param n - The node to set position for
298	* @param newPos - The new position coordinates
299	*/
300	setNodePosition(n: Node, newPos: Position): void {	14✔
301	const d3node = this._getMappedNode(n);	×
302	d3node.x = newPos.x;	×
303	d3node.y = newPos.y;	×
304	d3node.z = newPos.z ?? 0;	×
305	this.reheat = true;	×
306	}	×
307
308	/**
309	* Get the position of an edge based on its endpoint positions
310	* @param e - The edge to get position for
311	* @returns The edge's source and destination positions
312	*/
313	getEdgePosition(e: Edge): EdgePosition {	14✔
314	const d3edge = this._getMappedEdge(e);	16,633✔
315
316	return {	16,633✔
317	src: {	16,633✔
318	x: d3edge.source.x,	16,633✔
319	y: d3edge.source.y,	16,633✔
320	z: d3edge.source.z,	16,633✔
321	},	16,633✔
322	dst: {	16,633✔
323	x: d3edge.target.x,	16,633✔
324	y: d3edge.target.y,	16,633✔
325	z: d3edge.target.z,	16,633✔
326	},	16,633✔
327	};	16,633✔
328	}	16,633✔
329
330	/**
331	* Pin a node to its current position
332	* @param n - The node to pin
333	*/
334	pin(n: Node): void {	14✔
335	const d3node = this._getMappedNode(n);	×
336
337	d3node.fx = d3node.x;	×
338	d3node.fy = d3node.y;	×
339	d3node.fz = d3node.z;	×
340	this.reheat = true; // TODO: is this necessary?	×
341	}	×
342
343	/**
344	* Unpin a node to allow it to move freely
345	* @param n - The node to unpin
346	*/
347	unpin(n: Node): void {	14✔
348	const d3node = this._getMappedNode(n);	×
349
350	d3node.fx = undefined;	×
351	d3node.fy = undefined;	×
352	d3node.fz = undefined;	×
353	this.reheat = true; // TODO: is this necessary?	×
354	}	×
355
356	private _getMappedNode(n: Node): D3Node {	14✔
357	this.refresh(); // ensure consistent state	5,783✔
358
359	const d3node = this.nodeMapping.get(n);	5,783✔
360	if (!d3node) {	5,783!
361	throw new Error("Internal error: Node not found in D3GraphEngine");	×
362	}	×
363
364	return d3node;	5,783✔
365	}	5,783✔
366
367	private _getMappedEdge(e: Edge): D3Edge {	14✔
368	this.refresh(); // ensure consistent state	16,633✔
369
370	const d3edge = this.edgeMapping.get(e);	16,633✔
371	if (!d3edge) {	16,633!
372	throw new Error("Internal error: Edge not found in D3GraphEngine");	×
373	}	×
374
375	return d3edge;	16,633✔
376	}	16,633✔
377	}	14✔

graphty-org / graphty-monorepo / 20661584252

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous