• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

graphty-org / graphty-monorepo / 20690039805

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

push

github

apowers313
chore: merge master into graphty algorithms and fix errors

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
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✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc