20390753610

Committed 20 Dec 2025 06:53AM UTC coverage: 82.423% (-1.2%) from 83.666%

Build # 20390753610

Build Type

push

github

Committed by

apowers313

Commit Message

Merge branch 'master' of https://github.com/graphty-org/graphty-element

Run Details

5162 of 6088 branches covered (84.79%)

Branch coverage included in aggregate %.

24775 of 30233 relevant lines covered (81.95%)

6480.4 hits per line

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

98.1

/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;
}

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
     *
     * @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;
    }

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

graphty-org / graphty-element / 20390753610

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