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

Coverage Stats

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