20690039805

Committed 04 Jan 2026 08:00AM UTC coverage: 77.552% (-0.4%) from 77.925%

Build # 20690039805

Build Type

push

github

Committed by

apowers313

Commit Message

chore: merge master into graphty algorithms and fix errors

Run Details

13487 of 17880 branches covered (75.43%)

Branch coverage included in aggregate %.

107 of 108 new or added lines in 23 files covered. (99.07%)

245 existing lines in 9 files now uncovered.

41791 of 53399 relevant lines covered (78.26%)

142735.49 hits per line

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

96.3

/graphty-element/src/algorithms/PrimAlgorithm.ts

/**
 * @file Prim's Minimum Spanning Tree Algorithm wrapper
 *
 * This algorithm finds the minimum spanning tree of an undirected graph
 * using Prim's algorithm. It marks edges that are part of the MST
 * and stores graph-level results (total weight, edge count).
 *
 * Unlike Kruskal's which processes edges globally, Prim's grows the tree
 * from a starting node, which can be optionally configured.
 */

import { primMST } 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 Prim algorithm
 */
export const primOptionsSchema = defineOptions({
    startNode: {
        schema: z.union([z.string(), z.number()]).nullable().default(null),
        meta: {
            label: "Start Node",
            description: "Starting node for MST growth (uses first node if not set)",
        },
    },
});

/**
 * Options for Prim algorithm
 */
interface PrimOptions extends Record<string, unknown> {
    /** Optional starting node for the algorithm */
    startNode: number | string | null;
}

/**
 * Prim's algorithm for finding minimum spanning trees
 *
 * Computes the minimum spanning tree of an undirected graph by growing
 * the tree from a starting node.
 */
export class PrimAlgorithm extends Algorithm<PrimOptions> {
    static namespace = "graphty";
    static type = "prim";

    static zodOptionsSchema: ZodOptionsSchema = primOptionsSchema;

    static optionsSchema: OptionsSchema = {
        startNode: {
            type: "nodeId",
            default: null,
            label: "Start Node",
            description: "Starting node for MST growth (uses first node if not set)",
            required: false,
        },
    };

    /**
     * Legacy options set via configure() for backward compatibility
     */
    private legacyOptions: PrimOptions | null = null;

    static suggestedStyles = (): SuggestedStylesConfig => ({
        layers: [
            {
                edge: {
                    selector: "",
                    style: { enabled: true },
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.prim.inMST"],
                        output: "style.line.color",
                        expr: "{ return StyleHelpers.color.binary.greenSuccess(arguments[0]) }",
                    },
                },
                metadata: {
                    name: "Prim - MST Edges",
                    description: "Highlights minimum spanning tree edges (green) - colorblind-safe",
                },
            },
            {
                edge: {
                    selector: "algorithmResults.graphty.prim.inMST == `false`",
                    style: {
                        enabled: true,
                        line: {
                            opacity: 0.3,
                        },
                    },
                },
                metadata: {
                    name: "Prim - Non-MST Edges",
                    description: "Dims edges not in minimum spanning tree",
                },
            },
        ],
        description: "Visualizes minimum spanning tree computed via Prim's algorithm",
        category: "path",
    });

    /**
     * Configure the algorithm with an optional start node
     * @param options - Configuration options
     * @param options.startNode - The optional start node ID
     * @returns This algorithm instance for chaining
     * @deprecated Use constructor options instead. This method is kept for backward compatibility.
     */
    configure(options: { startNode?: number | string }): this {
        this.legacyOptions = { startNode: options.startNode ?? null };
        return this;
    }

    /**
     * Executes Prim's algorithm on the graph
     *
     * Computes the minimum spanning tree and marks MST edges.
     */
    async run(): Promise<void> {
        const g = this.graph;
        const edges = Array.from(g.getDataManager().edges.values());

        if (edges.length === 0) {
            return;
        }

        // Get startNode from legacy options, schema options, or use undefined (algorithm will pick first node)
        // Legacy configure() takes precedence for backward compatibility
        const startNode = this.legacyOptions?.startNode ?? this._schemaOptions.startNode ?? undefined;

        // Convert to @graphty/algorithms format and run Prim's algorithm
        // Note: Prim's algorithm requires a truly undirected graph (not a directed graph with reverse edges)
        const graphData = toAlgorithmGraph(g, { directed: false, addReverseEdges: false });
        const mstResult = primMST(graphData, startNode);

        // Create set of MST edge keys for fast lookup
        // Store both directions since the graph is undirected
        const mstEdgeKeys = new Set<string>();
        for (const edge of mstResult.edges) {
            mstEdgeKeys.add(`${String(edge.source)}:${String(edge.target)}`);
            mstEdgeKeys.add(`${String(edge.target)}:${String(edge.source)}`);
        }

        // Mark each edge as in MST or not
        for (const edge of edges) {
            const edgeKey = `${edge.srcId}:${edge.dstId}`;
            const inMST = mstEdgeKeys.has(edgeKey);
            this.addEdgeResult(edge, "inMST", inMST);
        }

        // Store graph-level results
        this.addGraphResult("totalWeight", mstResult.totalWeight);
        this.addGraphResult("edgeCount", mstResult.edges.length);
    }
}

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

1	/**
2	* @file Prim's Minimum Spanning Tree Algorithm wrapper
3	*
4	* This algorithm finds the minimum spanning tree of an undirected graph
5	* using Prim's algorithm. It marks edges that are part of the MST
6	* and stores graph-level results (total weight, edge count).
7	*
8	* Unlike Kruskal's which processes edges globally, Prim's grows the tree
9	* from a starting node, which can be optionally configured.
10	*/
11
12	import { primMST } from "@graphty/algorithms";	15✔
13	import { z } from "zod/v4";	15✔
14
15	import { defineOptions, type OptionsSchema as ZodOptionsSchema, type SuggestedStylesConfig } from "../config";	15✔
16	import { Algorithm } from "./Algorithm";	15✔
17	import type { OptionsSchema } from "./types/OptionSchema";
18	import { toAlgorithmGraph } from "./utils/graphConverter";	15✔
19
20	/**
21	* Zod-based options schema for Prim algorithm
22	*/
23	export const primOptionsSchema = defineOptions({	15✔
24	startNode: {	15✔
25	schema: z.union([z.string(), z.number()]).nullable().default(null),	15✔
26	meta: {	15✔
27	label: "Start Node",	15✔
28	description: "Starting node for MST growth (uses first node if not set)",	15✔
29	},	15✔
30	},	15✔
31	});	15✔
32
33	/**
34	* Options for Prim algorithm
35	*/
36	interface PrimOptions extends Record<string, unknown> {
37	/** Optional starting node for the algorithm */
38	startNode: number \| string \| null;
39	}
40
41	/**
42	* Prim's algorithm for finding minimum spanning trees
43	*
44	* Computes the minimum spanning tree of an undirected graph by growing
45	* the tree from a starting node.
46	*/
47	export class PrimAlgorithm extends Algorithm<PrimOptions> {	15✔
48	static namespace = "graphty";	5✔
49	static type = "prim";	5✔
50
51	static zodOptionsSchema: ZodOptionsSchema = primOptionsSchema;	5✔
52
53	static optionsSchema: OptionsSchema = {	5✔
54	startNode: {	5✔
55	type: "nodeId",	5✔
56	default: null,	5✔
57	label: "Start Node",	5✔
58	description: "Starting node for MST growth (uses first node if not set)",	5✔
59	required: false,	5✔
60	},	5✔
61	};	5✔
62
63	/**
64	* Legacy options set via configure() for backward compatibility
65	*/
66	private legacyOptions: PrimOptions \| null = null;	5✔
67
68	static suggestedStyles = (): SuggestedStylesConfig => ({	120✔
69	layers: [	13✔
70	{	13✔
71	edge: {	13✔
72	selector: "",	13✔
73	style: { enabled: true },	13✔
74	calculatedStyle: {	13✔
75	inputs: ["algorithmResults.graphty.prim.inMST"],	13✔
76	output: "style.line.color",	13✔
77	expr: "{ return StyleHelpers.color.binary.greenSuccess(arguments[0]) }",	13✔
78	},	13✔
79	},	13✔
80	metadata: {	13✔
81	name: "Prim - MST Edges",	13✔
82	description: "Highlights minimum spanning tree edges (green) - colorblind-safe",	13✔
83	},	13✔
84	},	13✔
85	{	13✔
86	edge: {	13✔
87	selector: "algorithmResults.graphty.prim.inMST == `false`",	13✔
88	style: {	13✔
89	enabled: true,	13✔
90	line: {	13✔
91	opacity: 0.3,	13✔
92	},	13✔
93	},	13✔
94	},	13✔
95	metadata: {	13✔
96	name: "Prim - Non-MST Edges",	13✔
97	description: "Dims edges not in minimum spanning tree",	13✔
98	},	13✔
99	},	13✔
100	],	13✔
101	description: "Visualizes minimum spanning tree computed via Prim's algorithm",	13✔
102	category: "path",	13✔
103	});	13✔
104
105	/**
106	* Configure the algorithm with an optional start node
107	* @param options - Configuration options
108	* @param options.startNode - The optional start node ID
109	* @returns This algorithm instance for chaining
110	* @deprecated Use constructor options instead. This method is kept for backward compatibility.
111	*/
112	configure(options: { startNode?: number \| string }): this {	19✔
UNCOV 113	this.legacyOptions = { startNode: options.startNode ?? null };	×
UNCOV 114	return this;	×
UNCOV 115	}	×
116
117	/**
118	* Executes Prim's algorithm on the graph
119	*
120	* Computes the minimum spanning tree and marks MST edges.
121	*/
122	async run(): Promise<void> {	19✔
123	const g = this.graph;	4✔
124	const edges = Array.from(g.getDataManager().edges.values());	4✔
125
126	if (edges.length === 0) {	4✔
127	return;	1✔
128	}	1✔
129
130	// Get startNode from legacy options, schema options, or use undefined (algorithm will pick first node)
131	// Legacy configure() takes precedence for backward compatibility
132	const startNode = this.legacyOptions?.startNode ?? this._schemaOptions.startNode ?? undefined;	4!
133
134	// Convert to @graphty/algorithms format and run Prim's algorithm
135	// Note: Prim's algorithm requires a truly undirected graph (not a directed graph with reverse edges)
136	const graphData = toAlgorithmGraph(g, { directed: false, addReverseEdges: false });	4✔
137	const mstResult = primMST(graphData, startNode);	4✔
138
139	// Create set of MST edge keys for fast lookup
140	// Store both directions since the graph is undirected
141	const mstEdgeKeys = new Set<string>();	4✔
142	for (const edge of mstResult.edges) {	4✔
143	mstEdgeKeys.add(`${String(edge.source)}:${String(edge.target)}`);	25✔
144	mstEdgeKeys.add(`${String(edge.target)}:${String(edge.source)}`);	25✔
145	}	25✔
146
147	// Mark each edge as in MST or not
148	for (const edge of edges) {	4✔
149	const edgeKey = `${edge.srcId}:${edge.dstId}`;	37✔
150	const inMST = mstEdgeKeys.has(edgeKey);	37✔
151	this.addEdgeResult(edge, "inMST", inMST);	37✔
152	}	37✔
153
154	// Store graph-level results
155	this.addGraphResult("totalWeight", mstResult.totalWeight);	3✔
156	this.addGraphResult("edgeCount", mstResult.edges.length);	3✔
157	}	4✔
158	}	19✔
159
160	// Auto-register this algorithm when the module is imported
161	Algorithm.register(PrimAlgorithm);	15✔

graphty-org / graphty-monorepo / 20690039805

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