20514590651

Committed 26 Dec 2025 02:37AM UTC coverage: 70.559% (-0.3%) from 70.836%

Build # 20514590651

Build Type

push

github

Committed by

apowers313

Commit Message

ci: fix npm ci

Run Details

9591 of 13363 branches covered (71.77%)

Branch coverage included in aggregate %.

25136 of 35854 relevant lines covered (70.11%)

6233.71 hits per line

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

86.3

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

graphty-org / graphty-element / 20514590651

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