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

94.86

/src/algorithms/DijkstraAlgorithm.ts

import {dijkstra, dijkstraPath} from "@graphty/algorithms";
import {z} from "zod/v4";

import {defineOptions, type OptionsSchema as ZodOptionsSchema, type SuggestedStylesConfig} from "../config";
import {Algorithm} from "./Algorithm";
import {type OptionsSchema} from "./types/OptionSchema";
import {toAlgorithmGraph} from "./utils/graphConverter";

/**
 * Zod-based options schema for Dijkstra algorithm
 */
export const dijkstraOptionsSchema = defineOptions({
    source: {
        schema: z.union([z.string(), z.number()]).nullable().default(null),
        meta: {
            label: "Source Node",
            description: "Starting node for shortest path (uses first node if not set)",
        },
    },
    target: {
        schema: z.union([z.string(), z.number()]).nullable().default(null),
        meta: {
            label: "Target Node",
            description: "Destination node for shortest path (uses last node if not set)",
        },
    },
    bidirectional: {
        schema: z.boolean().default(true),
        meta: {
            label: "Bidirectional Search",
            description: "Use bidirectional search optimization for faster point-to-point queries",
            advanced: true,
        },
    },
});

/**
 * Options for Dijkstra algorithm
 */
export interface DijkstraOptions extends Record<string, unknown> {
    /** Starting node for shortest path (defaults to first node if not provided) */
    source: number | string | null;
    /** Destination node for shortest path (defaults to last node if not provided) */
    target: number | string | null;
    /** Use bidirectional search optimization for point-to-point queries */
    bidirectional: boolean;
}

/**
 * Dijkstra's algorithm for finding shortest paths
 *
 * Computes shortest paths from a source node to all other nodes using
 * non-negative edge weights. Supports bidirectional search optimization.
 */
export class DijkstraAlgorithm extends Algorithm<DijkstraOptions> {
    static namespace = "graphty";
    static type = "dijkstra";

    static zodOptionsSchema: ZodOptionsSchema = dijkstraOptionsSchema;

    /**
     * Options schema for Dijkstra algorithm
     */
    static optionsSchema: OptionsSchema = {
        source: {
            type: "nodeId",
            default: null,
            label: "Source Node",
            description: "Starting node for shortest path (uses first node if not set)",
            required: false,
        },
        target: {
            type: "nodeId",
            default: null,
            label: "Target Node",
            description: "Destination node for shortest path (uses last node if not set)",
            required: false,
        },
        bidirectional: {
            type: "boolean",
            default: true,
            label: "Bidirectional Search",
            description: "Use bidirectional search optimization for faster point-to-point queries",
            advanced: true,
        },
    };

    /**
     * Legacy options set via configure() for backward compatibility
     */
    private legacyOptions: {source: number | string, target?: number | string} | null = null;

    static suggestedStyles = (): SuggestedStylesConfig => ({
        layers: [
            {
                edge: {
                    selector: "",
                    style: {enabled: true},
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.dijkstra.isInPath"],
                        output: "style.line.color",
                        expr: "{ return StyleHelpers.color.binary.blueHighlight(arguments[0]) }",
                    },
                },
                metadata: {
                    name: "Dijkstra - Path Edges",
                    description: "Highlights edges that are part of the shortest path (blue) - colorblind-safe",
                },
            },
            {
                node: {
                    selector: "",
                    style: {enabled: true},
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.dijkstra.isInPath"],
                        output: "style.texture.color",
                        expr: "{ return StyleHelpers.color.binary.blueHighlight(arguments[0]) }",
                    },
                },
                metadata: {
                    name: "Dijkstra - Path Nodes",
                    description: "Highlights nodes that are part of the shortest path (blue) - colorblind-safe",
                },
            },
        ],
        description: "Visualizes shortest path by highlighting path edges and nodes",
        category: "path",
    });

    /**
     * Configure the algorithm with source and optional target nodes
     * @param options - Configuration options
     * @param options.source - The source node for shortest path computation
     * @param options.target - The target node (optional)
     * @returns This algorithm instance for chaining
     * @deprecated Use constructor options instead. This method is kept for backward compatibility.
     */
    configure(options: {source: number | string, target?: number | string}): this {
        this.legacyOptions = options;
        return this;
    }

    /**
     * Executes Dijkstra's algorithm on the graph
     *
     * Computes shortest path distances and highlights the path from source to target.
     */
    async run(): Promise<void> {
        const g = this.graph;
        const nodes = Array.from(g.getDataManager().nodes.keys());
        const n = nodes.length;

        if (n === 0) {
            return;
        }

        // Get source and target from legacy options, schema options, or use defaults
        // Legacy configure() takes precedence for backward compatibility
        const source = this.legacyOptions?.source ?? this._schemaOptions.source ?? nodes[0];
        const target = this.legacyOptions?.target ?? this._schemaOptions.target ?? nodes[nodes.length - 1];
        const {bidirectional} = this._schemaOptions;

        // Convert to @graphty/algorithms format (undirected for path finding)
        const graphData = toAlgorithmGraph(g);

        // Run Dijkstra to get path from source to target
        const pathResult = dijkstraPath(graphData, source, target, {bidirectional});
        const path = pathResult?.path ?? [];

        // Run Dijkstra once from source to get all distances
        const allDistances = dijkstra(graphData, source);

        // Store path information on nodes
        const pathNodeSet = new Set(path);
        for (const nodeId of nodes) {
            const isInPath = pathNodeSet.has(nodeId);
            this.addNodeResult(nodeId, "isInPath", isInPath);

            // Get distance from the single Dijkstra run
            const nodeResult = allDistances.get(nodeId);
            const distance = nodeResult?.distance ?? Infinity;
            this.addNodeResult(nodeId, "distance", distance);
        }

        // Store path information on edges
        const pathEdges = this.getPathEdges(path);
        for (const edge of g.getDataManager().edges.values()) {
            const edgeKey = `${edge.srcId}:${edge.dstId}`;
            const reverseEdgeKey = `${edge.dstId}:${edge.srcId}`;
            const isInPath = pathEdges.has(edgeKey) || pathEdges.has(reverseEdgeKey);
            this.addEdgeResult(edge, "isInPath", isInPath);
        }
    }

    /**
     * Get set of edge keys that are part of the path
     * @param path - Array of node IDs representing the path
     * @returns Set of edge keys in "srcId:dstId" format
     */
    private getPathEdges(path: (number | string)[]): Set<string> {
        const edges = new Set<string>();

        for (let i = 0; i < path.length - 1; i++) {
            edges.add(`${path[i]}:${path[i + 1]}`);
        }

        return edges;
    }
}

// Auto-register this algorithm when the module is imported
Algorithm.register(DijkstraAlgorithm);

1	import {dijkstra, dijkstraPath} from "@graphty/algorithms";	15✔
2	import {z} from "zod/v4";	15✔
3
4	import {defineOptions, type OptionsSchema as ZodOptionsSchema, type SuggestedStylesConfig} from "../config";	15✔
5	import {Algorithm} from "./Algorithm";	15✔
6	import {type OptionsSchema} from "./types/OptionSchema";
7	import {toAlgorithmGraph} from "./utils/graphConverter";	15✔
8
9	/**
10	* Zod-based options schema for Dijkstra algorithm
11	*/
12	export const dijkstraOptionsSchema = defineOptions({	15✔
13	source: {	15✔
14	schema: z.union([z.string(), z.number()]).nullable().default(null),	15✔
15	meta: {	15✔
16	label: "Source Node",	15✔
17	description: "Starting node for shortest path (uses first node if not set)",	15✔
18	},	15✔
19	},	15✔
20	target: {	15✔
21	schema: z.union([z.string(), z.number()]).nullable().default(null),	15✔
22	meta: {	15✔
23	label: "Target Node",	15✔
24	description: "Destination node for shortest path (uses last node if not set)",	15✔
25	},	15✔
26	},	15✔
27	bidirectional: {	15✔
28	schema: z.boolean().default(true),	15✔
29	meta: {	15✔
30	label: "Bidirectional Search",	15✔
31	description: "Use bidirectional search optimization for faster point-to-point queries",	15✔
32	advanced: true,	15✔
33	},	15✔
34	},	15✔
35	});	15✔
36
37	/**
38	* Options for Dijkstra algorithm
39	*/
40	export interface DijkstraOptions extends Record<string, unknown> {
41	/** Starting node for shortest path (defaults to first node if not provided) */
42	source: number \| string \| null;
43	/** Destination node for shortest path (defaults to last node if not provided) */
44	target: number \| string \| null;
45	/** Use bidirectional search optimization for point-to-point queries */
46	bidirectional: boolean;
47	}
48
49	/**
50	* Dijkstra's algorithm for finding shortest paths
51	*
52	* Computes shortest paths from a source node to all other nodes using
53	* non-negative edge weights. Supports bidirectional search optimization.
54	*/
55	export class DijkstraAlgorithm extends Algorithm<DijkstraOptions> {	15✔
56	static namespace = "graphty";	11✔
57	static type = "dijkstra";	11✔
58
59	static zodOptionsSchema: ZodOptionsSchema = dijkstraOptionsSchema;	11✔
60
61	/**
62	* Options schema for Dijkstra algorithm
63	*/
64	static optionsSchema: OptionsSchema = {	11✔
65	source: {	11✔
66	type: "nodeId",	11✔
67	default: null,	11✔
68	label: "Source Node",	11✔
69	description: "Starting node for shortest path (uses first node if not set)",	11✔
70	required: false,	11✔
71	},	11✔
72	target: {	11✔
73	type: "nodeId",	11✔
74	default: null,	11✔
75	label: "Target Node",	11✔
76	description: "Destination node for shortest path (uses last node if not set)",	11✔
77	required: false,	11✔
78	},	11✔
79	bidirectional: {	11✔
80	type: "boolean",	11✔
81	default: true,	11✔
82	label: "Bidirectional Search",	11✔
83	description: "Use bidirectional search optimization for faster point-to-point queries",	11✔
84	advanced: true,	11✔
85	},	11✔
86	};	11✔
87
88	/**
89	* Legacy options set via configure() for backward compatibility
90	*/
91	private legacyOptions: {source: number \| string, target?: number \| string} \| null = null;	11✔
92
93	static suggestedStyles = (): SuggestedStylesConfig => ({	120✔
94	layers: [	14✔
95	{	14✔
96	edge: {	14✔
97	selector: "",	14✔
98	style: {enabled: true},	14✔
99	calculatedStyle: {	14✔
100	inputs: ["algorithmResults.graphty.dijkstra.isInPath"],	14✔
101	output: "style.line.color",	14✔
102	expr: "{ return StyleHelpers.color.binary.blueHighlight(arguments[0]) }",	14✔
103	},	14✔
104	},	14✔
105	metadata: {	14✔
106	name: "Dijkstra - Path Edges",	14✔
107	description: "Highlights edges that are part of the shortest path (blue) - colorblind-safe",	14✔
108	},	14✔
109	},	14✔
110	{	14✔
111	node: {	14✔
112	selector: "",	14✔
113	style: {enabled: true},	14✔
114	calculatedStyle: {	14✔
115	inputs: ["algorithmResults.graphty.dijkstra.isInPath"],	14✔
116	output: "style.texture.color",	14✔
117	expr: "{ return StyleHelpers.color.binary.blueHighlight(arguments[0]) }",	14✔
118	},	14✔
119	},	14✔
120	metadata: {	14✔
121	name: "Dijkstra - Path Nodes",	14✔
122	description: "Highlights nodes that are part of the shortest path (blue) - colorblind-safe",	14✔
123	},	14✔
124	},	14✔
125	],	14✔
126	description: "Visualizes shortest path by highlighting path edges and nodes",	14✔
127	category: "path",	14✔
128	});	14✔
129
130	/**
131	* Configure the algorithm with source and optional target nodes
132	* @param options - Configuration options
133	* @param options.source - The source node for shortest path computation
134	* @param options.target - The target node (optional)
135	* @returns This algorithm instance for chaining
136	* @deprecated Use constructor options instead. This method is kept for backward compatibility.
137	*/
138	configure(options: {source: number \| string, target?: number \| string}): this {	19✔
139	this.legacyOptions = options;	1✔
140	return this;	1✔
141	}	1✔
142
143	/**
144	* Executes Dijkstra's algorithm on the graph
145	*
146	* Computes shortest path distances and highlights the path from source to target.
147	*/
148	async run(): Promise<void> {	19✔
149	const g = this.graph;	7✔
150	const nodes = Array.from(g.getDataManager().nodes.keys());	7✔
151	const n = nodes.length;	7✔
152
153	if (n === 0) {	7!
154	return;	×
155	}	×
156
157	// Get source and target from legacy options, schema options, or use defaults
158	// Legacy configure() takes precedence for backward compatibility
159	const source = this.legacyOptions?.source ?? this._schemaOptions.source ?? nodes[0];	7!
160	const target = this.legacyOptions?.target ?? this._schemaOptions.target ?? nodes[nodes.length - 1];	7!
161	const {bidirectional} = this._schemaOptions;	7✔
162
163	// Convert to @graphty/algorithms format (undirected for path finding)
164	const graphData = toAlgorithmGraph(g);	7✔
165
166	// Run Dijkstra to get path from source to target
167	const pathResult = dijkstraPath(graphData, source, target, {bidirectional});	7✔
168	const path = pathResult?.path ?? [];	7!
169
170	// Run Dijkstra once from source to get all distances
171	const allDistances = dijkstra(graphData, source);	7✔
172
173	// Store path information on nodes
174	const pathNodeSet = new Set(path);	7✔
175	for (const nodeId of nodes) {	7✔
176	const isInPath = pathNodeSet.has(nodeId);	90✔
177	this.addNodeResult(nodeId, "isInPath", isInPath);	90✔
178
179	// Get distance from the single Dijkstra run
180	const nodeResult = allDistances.get(nodeId);	90✔
181	const distance = nodeResult?.distance ?? Infinity;	90!
182	this.addNodeResult(nodeId, "distance", distance);	90✔
183	}	90✔
184
185	// Store path information on edges
186	const pathEdges = this.getPathEdges(path);	7✔
187	for (const edge of g.getDataManager().edges.values()) {	7✔
188	const edgeKey = `${edge.srcId}:${edge.dstId}`;	94✔
189	const reverseEdgeKey = `${edge.dstId}:${edge.srcId}`;	94✔
190	const isInPath = pathEdges.has(edgeKey) \|\| pathEdges.has(reverseEdgeKey);	94✔
191	this.addEdgeResult(edge, "isInPath", isInPath);	94✔
192	}	94✔
193	}	7✔
194
195	/**
196	* Get set of edge keys that are part of the path
197	* @param path - Array of node IDs representing the path
198	* @returns Set of edge keys in "srcId:dstId" format
199	*/
200	private getPathEdges(path: (number \| string)[]): Set<string> {	19✔
201	const edges = new Set<string>();	7✔
202
203	for (let i = 0; i < path.length - 1; i++) {	7✔
204	edges.add(`${path[i]}:${path[i + 1]}`);	10✔
205	}	10✔
206
207	return edges;	7✔
208	}	7✔
209	}	19✔
210
211	// Auto-register this algorithm when the module is imported
212	Algorithm.register(DijkstraAlgorithm);	15✔

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