37773995795

Committed 08 Oct 2026 11:51AM UTC coverage: 92.684% (+0.03%) from 92.65%

Build # 37773995795

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1538 from graphty-org/fix/visual-review-incomplete-capture-flake

test(visual-review): pin that a held git call does not freeze the server

Coverage Stats

57092 of 63648 branches covered (89.7%)

Branch coverage included in aggregate %.

87329 of 92173 relevant lines covered (94.74%)

298887.48 hits per line

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

90.0

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

import { spectralClustering } from "@graphty/algorithms";
import { z } from "zod/v4";

import { defineOptions, type OptionsSchema as ZodOptionsSchema } from "../config";
import type { ResultElementValues } from "../session/results";
import { caveat } from "../session/runs/caveatFacts";
import { Algorithm } from "./Algorithm";
import { type ScopeInputDeclaration, scopeNodeIds } from "./input/ScopedInput";
import {
    type AlgorithmOutput,
    type AlgorithmRunContext,
    communityFieldSpecs,
    DeclaredAlgorithm,
    declaredCaveats,
    forEachChunked,
} from "./results";
import type { OptionsSchema } from "./types/OptionSchema";

const CLUSTERS_DESCRIPTION = "How many clusters to split the nodes into, at most";
const LAPLACIAN_DESCRIPTION = "Which graph Laplacian the embedding comes from";
const MAX_ITERATIONS_DESCRIPTION = "Maximum k-means rounds";
const SEED_DESCRIPTION = "Seed of the k-means start: one seed gives one result";

const LAPLACIANS = ["normalized", "unnormalized", "randomWalk"] as const;

const spectralClusteringOptionsSchema = defineOptions({
    clusters: {
        schema: z.number().int().min(1).max(100).default(2),
        meta: { label: "Clusters", description: CLUSTERS_DESCRIPTION },
    },
    laplacian: {
        schema: z.enum(LAPLACIANS).default("normalized"),
        meta: { label: "Laplacian", description: LAPLACIAN_DESCRIPTION, advanced: true },
    },
    maxIterations: {
        schema: z.number().int().min(1).max(1000).default(100),
        meta: { label: "Max Iterations", description: MAX_ITERATIONS_DESCRIPTION, advanced: true },
    },
    seed: {
        schema: z.number().int().min(0).max(2147483647).default(42),
        meta: { label: "Random Seed", description: SEED_DESCRIPTION, advanced: true },
    },
});

/** Options for spectral clustering. */
interface SpectralClusteringOptions extends Record<string, unknown> {
    /** Number of clusters asked for. */
    clusters: number;
    /** Which Laplacian the embedding comes from. */
    laplacian: (typeof LAPLACIANS)[number];
    /** Cap on k-means rounds. */
    maxIterations: number;
    /** Seed of the k-means start. */
    seed: number;
}

/**
 * Spectral clustering: the eigenvectors of the graph Laplacian place every node as a point, and
 * k-means splits the points into at most `clusters` groups.
 *
 * Publishes a group per node. It does not score its own partition, so it reports no modularity.
 * Fewer groups than asked for come back when k-means leaves a cluster empty.
 */
export class SpectralClusteringAlgorithm extends DeclaredAlgorithm<SpectralClusteringOptions> {
    static readonly namespace = "graphty";
    static readonly type = "spectral-clustering";
    /** Groups over the run's scope: the node list and the graph both come from the input. */
    static readonly scopeInput: ScopeInputDeclaration = "subgraph";

    static readonly zodOptionsSchema: ZodOptionsSchema = spectralClusteringOptionsSchema;

    static readonly optionsSchema: OptionsSchema = {
        clusters: {
            type: "integer",
            default: 2,
            label: "Clusters",
            description: CLUSTERS_DESCRIPTION,
            min: 1,
            max: 100,
        },
        laplacian: {
            type: "select",
            default: "normalized",
            label: "Laplacian",
            description: LAPLACIAN_DESCRIPTION,
            options: LAPLACIANS.map((value) => ({ value, label: value })),
            advanced: true,
        },
        maxIterations: {
            type: "integer",
            default: 100,
            label: "Max Iterations",
            description: MAX_ITERATIONS_DESCRIPTION,
            min: 1,
            max: 1000,
            advanced: true,
        },
        seed: {
            type: "integer",
            default: 42,
            label: "Random Seed",
            description: SEED_DESCRIPTION,
            min: 0,
            max: 2147483647,
            advanced: true,
        },
    };

    /**
     * Split the nodes into clusters from the Laplacian's eigenvectors.
     * @param context - What the element gave the run.
     * @returns The community result, or null when there are no nodes to group.
     */
    async compute(context: AlgorithmRunContext): Promise<AlgorithmOutput | null> {
        const input = this.input("undirected");
        const nodeIds = scopeNodeIds(input);

        if (nodeIds.length === 0) {
            return null;
        }

        // Undirected: the Laplacian is symmetric. No accelerator implements spectral clustering.
        const { snapshot } = input.derived();
        const { clusters, laplacian, maxIterations, seed } = this.schemaOptions;

        context.report({ phase: "Embedding nodes", total: null });
        const value = spectralClustering(snapshot, { k: clusters, laplacianType: laplacian, maxIterations, seed });
        context.signal.throwIfAborted();

        const nodes: ResultElementValues[] = [];
        await forEachChunked(context, "Grouping nodes", nodeIds, (nodeId) => {
            nodes.push({ id: nodeId, values: { group: value.labels[snapshot.ids.indexOf(nodeId)] ?? 0 } });
        });

        return {
            shape: "community",
            fields: communityFieldSpecs(false),
            nodes,
            caveats: declaredCaveats({
                method: "spectral-clustering",
                direction: "undirected",
                weight: { attribute: "weight", meaning: "strength" },
                converged: value.converged,
                seed,
                facts: [caveat("partition.unscored", { algorithm: "spectral-clustering" })],
            }),
        };
    }
}

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

1	import { spectralClustering } from "@graphty/algorithms";
2	import { z } from "zod/v4";
3
4	import { defineOptions, type OptionsSchema as ZodOptionsSchema } from "../config";
5	import type { ResultElementValues } from "../session/results";
6	import { caveat } from "../session/runs/caveatFacts";
7	import { Algorithm } from "./Algorithm";
8	import { type ScopeInputDeclaration, scopeNodeIds } from "./input/ScopedInput";
9	import {
10	type AlgorithmOutput,
11	type AlgorithmRunContext,
12	communityFieldSpecs,
13	DeclaredAlgorithm,
14	declaredCaveats,
15	forEachChunked,
16	} from "./results";
17	import type { OptionsSchema } from "./types/OptionSchema";
18
19	const CLUSTERS_DESCRIPTION = "How many clusters to split the nodes into, at most";	516 ✔
20	const LAPLACIAN_DESCRIPTION = "Which graph Laplacian the embedding comes from";	516 ✔
21	const MAX_ITERATIONS_DESCRIPTION = "Maximum k-means rounds";	516 ✔
22	const SEED_DESCRIPTION = "Seed of the k-means start: one seed gives one result";	516 ✔
23
24	const LAPLACIANS = ["normalized", "unnormalized", "randomWalk"] as const;	516 ✔
25
26	const spectralClusteringOptionsSchema = defineOptions({	516 ✔
27	clusters: {
28	schema: z.number().int().min(1).max(100).default(2),
29	meta: { label: "Clusters", description: CLUSTERS_DESCRIPTION },
30	},
31	laplacian: {
32	schema: z.enum(LAPLACIANS).default("normalized"),
33	meta: { label: "Laplacian", description: LAPLACIAN_DESCRIPTION, advanced: true },
34	},
35	maxIterations: {
36	schema: z.number().int().min(1).max(1000).default(100),
37	meta: { label: "Max Iterations", description: MAX_ITERATIONS_DESCRIPTION, advanced: true },
38	},
39	seed: {
40	schema: z.number().int().min(0).max(2147483647).default(42),
41	meta: { label: "Random Seed", description: SEED_DESCRIPTION, advanced: true },
42	},
43	});
44
45	/** Options for spectral clustering. */
46	interface SpectralClusteringOptions extends Record<string, unknown> {
47	/** Number of clusters asked for. */
48	clusters: number;
49	/** Which Laplacian the embedding comes from. */
50	laplacian: (typeof LAPLACIANS)[number];
51	/** Cap on k-means rounds. */
52	maxIterations: number;
53	/** Seed of the k-means start. */
54	seed: number;
55	}
56
57	/**
58	* Spectral clustering: the eigenvectors of the graph Laplacian place every node as a point, and
59	* k-means splits the points into at most `clusters` groups.
60	*
61	* Publishes a group per node. It does not score its own partition, so it reports no modularity.
62	* Fewer groups than asked for come back when k-means leaves a cluster empty.
63	*/
64	export class SpectralClusteringAlgorithm extends DeclaredAlgorithm<SpectralClusteringOptions> {
65	static readonly namespace = "graphty";	516 ✔
66	static readonly type = "spectral-clustering";	516 ✔
67	/** Groups over the run's scope: the node list and the graph both come from the input. */
68	static readonly scopeInput: ScopeInputDeclaration = "subgraph";	516 ✔
69
70	static readonly zodOptionsSchema: ZodOptionsSchema = spectralClusteringOptionsSchema;	516 ✔
71
72	static readonly optionsSchema: OptionsSchema = {	516 ✔
73	clusters: {
74	type: "integer",
75	default: 2,
76	label: "Clusters",
77	description: CLUSTERS_DESCRIPTION,
78	min: 1,
79	max: 100,
80	},
81	laplacian: {
82	type: "select",
83	default: "normalized",
84	label: "Laplacian",
85	description: LAPLACIAN_DESCRIPTION,
86	options: LAPLACIANS.map((value) => ({ value, label: value })),	1,548 ✔
87	advanced: true,
88	},
89	maxIterations: {
90	type: "integer",
91	default: 100,
92	label: "Max Iterations",
93	description: MAX_ITERATIONS_DESCRIPTION,
94	min: 1,
95	max: 1000,
96	advanced: true,
97	},
98	seed: {
99	type: "integer",
100	default: 42,
101	label: "Random Seed",
102	description: SEED_DESCRIPTION,
103	min: 0,
104	max: 2147483647,
105	advanced: true,
106	},
107	};
108
109	/**
110	* Split the nodes into clusters from the Laplacian's eigenvectors.
111	* @param context - What the element gave the run.
112	* @returns The community result, or null when there are no nodes to group.
113	*/
114	async compute(context: AlgorithmRunContext): Promise<AlgorithmOutput \| null> {
115	const input = this.input("undirected");	15 ✔
116	const nodeIds = scopeNodeIds(input);	15 ✔
117
118	if (nodeIds.length === 0) {	15 !
119	return null;	×
120	}
121
122	// Undirected: the Laplacian is symmetric. No accelerator implements spectral clustering.
123	const { snapshot } = input.derived();	15 ✔
124	const { clusters, laplacian, maxIterations, seed } = this.schemaOptions;	15 ✔
125
126	context.report({ phase: "Embedding nodes", total: null });	15 ✔
127	const value = spectralClustering(snapshot, { k: clusters, laplacianType: laplacian, maxIterations, seed });	15 ✔
128	context.signal.throwIfAborted();	15 ✔
129
130	const nodes: ResultElementValues[] = [];	15 ✔
131	await forEachChunked(context, "Grouping nodes", nodeIds, (nodeId) => {	15 ✔
132	nodes.push({ id: nodeId, values: { group: value.labels[snapshot.ids.indexOf(nodeId)] ?? 0 } });	83 !
133	});
134
135	return {	14 ✔
136	shape: "community",
137	fields: communityFieldSpecs(false),
138	nodes,
139	caveats: declaredCaveats({
140	method: "spectral-clustering",
141	direction: "undirected",
142	weight: { attribute: "weight", meaning: "strength" },
143	converged: value.converged,
144	seed,
145	facts: [caveat("partition.unscored", { algorithm: "spectral-clustering" })],
146	}),
147	};
148	}
149	}
150
151	// Auto-register this algorithm when the module is imported
152	Algorithm.register(SpectralClusteringAlgorithm);	516 ✔

graphty-org / graphty-monorepo / 37773995795

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