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

95.12

/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 {SuggestedStylesConfig} from "../config";
import {Algorithm} from "./Algorithm";
import {toAlgorithmGraph} from "./utils/graphConverter";

interface PrimOptions {
    /** Optional starting node for the algorithm */
    startNode?: number | string;
}

/**
 * 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 {
    static namespace = "graphty";
    static type = "prim";
    private options: 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
     * @returns This algorithm instance for chaining
     */
    configure(options: PrimOptions): this {
        this.options = options;
        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;
        }

        // 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, this.options?.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
14	import {SuggestedStylesConfig} from "../config";
15	import {Algorithm} from "./Algorithm";	15✔
16	import {toAlgorithmGraph} from "./utils/graphConverter";	15✔
17
18	interface PrimOptions {
19	/** Optional starting node for the algorithm */
20	startNode?: number \| string;
21	}
22
23	/**
24	* Prim's algorithm for finding minimum spanning trees
25	*
26	* Computes the minimum spanning tree of an undirected graph by growing
27	* the tree from a starting node.
28	*/
29	export class PrimAlgorithm extends Algorithm {	15✔
30	static namespace = "graphty";	3✔
31	static type = "prim";	3✔
32	private options: PrimOptions \| null = null;	3✔
33
34	static suggestedStyles = (): SuggestedStylesConfig => ({	119✔
35	layers: [	13✔
36	{	13✔
37	edge: {	13✔
38	selector: "",	13✔
39	style: {enabled: true},	13✔
40	calculatedStyle: {	13✔
41	inputs: ["algorithmResults.graphty.prim.inMST"],	13✔
42	output: "style.line.color",	13✔
43	expr: "{ return StyleHelpers.color.binary.greenSuccess(arguments[0]) }",	13✔
44	},	13✔
45	},	13✔
46	metadata: {	13✔
47	name: "Prim - MST Edges",	13✔
48	description: "Highlights minimum spanning tree edges (green) - colorblind-safe",	13✔
49	},	13✔
50	},	13✔
51	{	13✔
52	edge: {	13✔
53	selector: "algorithmResults.graphty.prim.inMST == `false`",	13✔
54	style: {	13✔
55	enabled: true,	13✔
56	line: {	13✔
57	opacity: 0.3,	13✔
58	},	13✔
59	},	13✔
60	},	13✔
61	metadata: {	13✔
62	name: "Prim - Non-MST Edges",	13✔
63	description: "Dims edges not in minimum spanning tree",	13✔
64	},	13✔
65	},	13✔
66	],	13✔
67	description: "Visualizes minimum spanning tree computed via Prim's algorithm",	13✔
68	category: "path",	13✔
69	});	13✔
70
71	/**
72	* Configure the algorithm with an optional start node
73	* @param options - Configuration options
74	* @returns This algorithm instance for chaining
75	*/
76	configure(options: PrimOptions): this {	18✔
77	this.options = options;	×
78	return this;	×
79	}	×
80
81	/**
82	* Executes Prim's algorithm on the graph
83	*
84	* Computes the minimum spanning tree and marks MST edges.
85	*/
86	async run(): Promise<void> {	18✔
87	const g = this.graph;	2✔
88	const edges = Array.from(g.getDataManager().edges.values());	2✔
89
90	if (edges.length === 0) {	2✔
91	return;	1✔
92	}	1✔
93
94	// Convert to @graphty/algorithms format and run Prim's algorithm
95	// Note: Prim's algorithm requires a truly undirected graph (not a directed graph with reverse edges)
96	const graphData = toAlgorithmGraph(g, {directed: false, addReverseEdges: false});	1✔
97	const mstResult = primMST(graphData, this.options?.startNode);	2!
98
99	// Create set of MST edge keys for fast lookup
100	// Store both directions since the graph is undirected
101	const mstEdgeKeys = new Set<string>();	2✔
102	for (const edge of mstResult.edges) {	2✔
103	mstEdgeKeys.add(`${String(edge.source)}:${String(edge.target)}`);	19✔
104	mstEdgeKeys.add(`${String(edge.target)}:${String(edge.source)}`);	19✔
105	}	19✔
106
107	// Mark each edge as in MST or not
108	for (const edge of edges) {	2✔
109	const edgeKey = `${edge.srcId}:${edge.dstId}`;	29✔
110	const inMST = mstEdgeKeys.has(edgeKey);	29✔
111	this.addEdgeResult(edge, "inMST", inMST);	29✔
112	}	29✔
113
114	// Store graph-level results
115	this.addGraphResult("totalWeight", mstResult.totalWeight);	1✔
116	this.addGraphResult("edgeCount", mstResult.edges.length);	1✔
117	}	2✔
118	}	18✔
119
120	// Auto-register this algorithm when the module is imported
121	Algorithm.register(PrimAlgorithm);	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