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

88.11

/src/algorithms/GirvanNewmanAlgorithm.ts

import {girvanNewman} 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 Girvan-Newman algorithm
 */
export const girvanNewmanOptionsSchema = defineOptions({
    maxCommunities: {
        schema: z.number().int().min(0).max(100).default(0),
        meta: {
            label: "Max Communities",
            description: "Stop when this many communities reached (0 = find optimal)",
        },
    },
    minCommunitySize: {
        schema: z.number().int().min(1).max(100).default(1),
        meta: {
            label: "Min Community Size",
            description: "Minimum nodes per community",
            advanced: true,
        },
    },
    maxIterations: {
        schema: z.number().int().min(1).max(10000).default(1000),
        meta: {
            label: "Max Iterations",
            description: "Maximum edge removal iterations before stopping",
            advanced: true,
        },
    },
});

/**
 * Options for the Girvan-Newman community detection algorithm
 */
export interface GirvanNewmanOptions extends Record<string, unknown> {
    /** Stop when this many communities reached (0 = find optimal) */
    maxCommunities: number;
    /** Minimum nodes per community */
    minCommunitySize: number;
    /** Maximum edge removal iterations before stopping */
    maxIterations: number;
}

/**
 *
 */
export class GirvanNewmanAlgorithm extends Algorithm<GirvanNewmanOptions> {
    static namespace = "graphty";
    static type = "girvan-newman";

    static zodOptionsSchema: ZodOptionsSchema = girvanNewmanOptionsSchema;

    static optionsSchema: OptionsSchema = {
        maxCommunities: {
            type: "integer",
            default: 0,
            label: "Max Communities",
            description: "Stop when this many communities reached (0 = find optimal)",
            min: 0,
            max: 100,
        },
        minCommunitySize: {
            type: "integer",
            default: 1,
            label: "Min Community Size",
            description: "Minimum nodes per community",
            min: 1,
            max: 100,
            advanced: true,
        },
        maxIterations: {
            type: "integer",
            default: 1000,
            label: "Max Iterations",
            description: "Maximum edge removal iterations before stopping",
            min: 1,
            max: 10000,
            advanced: true,
        },
    };

    static suggestedStyles = (): SuggestedStylesConfig => ({
        layers: [
            {
                node: {
                    selector: "",
                    style: {
                        enabled: true,
                    },
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.girvan-newman.communityId"],
                        output: "style.texture.color",
                        expr: "{ return StyleHelpers.color.categorical.tolVibrant(arguments[0] ?? 0) }",
                    },
                },
                metadata: {
                    name: "Girvan-Newman - Vibrant Colors",
                    description: "7 high-saturation community colors",
                },
            },
        ],
        description: "Visualizes communities detected via edge betweenness removal",
        category: "grouping",
    });

    /**
     * Executes the Girvan-Newman algorithm on the graph
     *
     * Detects communities by iteratively removing edges with highest betweenness.
     */
    async run(): Promise<void> {
        const g = this.graph;
        const nodes = Array.from(g.getDataManager().nodes.keys());

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

        // Get options from schema
        const {maxCommunities, minCommunitySize, maxIterations} = this.schemaOptions;

        // Convert to @graphty/algorithms format (truly undirected for community detection)
        // addReverseEdges: false creates an undirected graph required by girvanNewman
        const graphData = toAlgorithmGraph(g, {addReverseEdges: false});

        // Run Girvan-Newman algorithm - returns CommunityResult[] (dendrogram)
        // Pass maxCommunities only if > 0 (0 means find optimal)
        const results = girvanNewman(graphData, {
            maxCommunities: maxCommunities > 0 ? maxCommunities : undefined,
            minCommunitySize,
            maxIterations,
        });

        // Handle empty results (e.g., graph with no edges)
        if (results.length === 0) {
            // Assign each node to its own community
            for (let i = 0; i < nodes.length; i++) {
                this.addNodeResult(nodes[i], "communityId", i);
            }
            this.addGraphResult("modularity", 0);
            this.addGraphResult("communityCount", nodes.length);
            return;
        }

        // Find the result with highest modularity
        let bestResult = results[0];
        for (const result of results) {
            if (result.modularity > bestResult.modularity) {
                bestResult = result;
            }
        }

        // Store community assignments for each node
        const communityMap = new Map<number | string, number>();
        for (let i = 0; i < bestResult.communities.length; i++) {
            for (const nodeId of bestResult.communities[i]) {
                communityMap.set(nodeId, i);
            }
        }

        // Store results on nodes
        for (const nodeId of nodes) {
            const communityId = communityMap.get(nodeId) ?? 0;
            this.addNodeResult(nodeId, "communityId", communityId);
        }

        // Store graph-level results
        this.addGraphResult("modularity", bestResult.modularity);
        this.addGraphResult("communityCount", bestResult.communities.length);
    }
}

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

1	import {girvanNewman} from "@graphty/algorithms";	15✔
2	import {z} from "zod/v4";	15✔
3
4	import {defineOptions, type OptionsSchema as ZodOptionsSchema, type SuggestedStylesConfig} from "../config";	15✔
5	import {Algorithm} from "./Algorithm";	15✔
6	import type {OptionsSchema} from "./types/OptionSchema";
7	import {toAlgorithmGraph} from "./utils/graphConverter";	15✔
8
9	/**
10	* Zod-based options schema for Girvan-Newman algorithm
11	*/
12	export const girvanNewmanOptionsSchema = defineOptions({	15✔
13	maxCommunities: {	15✔
14	schema: z.number().int().min(0).max(100).default(0),	15✔
15	meta: {	15✔
16	label: "Max Communities",	15✔
17	description: "Stop when this many communities reached (0 = find optimal)",	15✔
18	},	15✔
19	},	15✔
20	minCommunitySize: {	15✔
21	schema: z.number().int().min(1).max(100).default(1),	15✔
22	meta: {	15✔
23	label: "Min Community Size",	15✔
24	description: "Minimum nodes per community",	15✔
25	advanced: true,	15✔
26	},	15✔
27	},	15✔
28	maxIterations: {	15✔
29	schema: z.number().int().min(1).max(10000).default(1000),	15✔
30	meta: {	15✔
31	label: "Max Iterations",	15✔
32	description: "Maximum edge removal iterations before stopping",	15✔
33	advanced: true,	15✔
34	},	15✔
35	},	15✔
36	});	15✔
37
38	/**
39	* Options for the Girvan-Newman community detection algorithm
40	*/
41	export interface GirvanNewmanOptions extends Record<string, unknown> {
42	/** Stop when this many communities reached (0 = find optimal) */
43	maxCommunities: number;
44	/** Minimum nodes per community */
45	minCommunitySize: number;
46	/** Maximum edge removal iterations before stopping */
47	maxIterations: number;
48	}
49
50	/**
51	*
52	*/
53	export class GirvanNewmanAlgorithm extends Algorithm<GirvanNewmanOptions> {	15✔
54	static namespace = "graphty";	19✔
55	static type = "girvan-newman";	120✔
56
57	static zodOptionsSchema: ZodOptionsSchema = girvanNewmanOptionsSchema;	120✔
58
59	static optionsSchema: OptionsSchema = {	120✔
60	maxCommunities: {	120✔
61	type: "integer",	120✔
62	default: 0,	120✔
63	label: "Max Communities",	120✔
64	description: "Stop when this many communities reached (0 = find optimal)",	120✔
65	min: 0,	120✔
66	max: 100,	120✔
67	},	120✔
68	minCommunitySize: {	120✔
69	type: "integer",	120✔
70	default: 1,	120✔
71	label: "Min Community Size",	120✔
72	description: "Minimum nodes per community",	120✔
73	min: 1,	120✔
74	max: 100,	120✔
75	advanced: true,	120✔
76	},	120✔
77	maxIterations: {	120✔
78	type: "integer",	120✔
79	default: 1000,	120✔
80	label: "Max Iterations",	120✔
81	description: "Maximum edge removal iterations before stopping",	120✔
82	min: 1,	120✔
83	max: 10000,	120✔
84	advanced: true,	120✔
85	},	120✔
86	};	120✔
87
88	static suggestedStyles = (): SuggestedStylesConfig => ({	120✔
89	layers: [	11✔
90	{	11✔
91	node: {	11✔
92	selector: "",	11✔
93	style: {	11✔
94	enabled: true,	11✔
95	},	11✔
96	calculatedStyle: {	11✔
97	inputs: ["algorithmResults.graphty.girvan-newman.communityId"],	11✔
98	output: "style.texture.color",	11✔
99	expr: "{ return StyleHelpers.color.categorical.tolVibrant(arguments[0] ?? 0) }",	11✔
100	},	11✔
101	},	11✔
102	metadata: {	11✔
103	name: "Girvan-Newman - Vibrant Colors",	11✔
104	description: "7 high-saturation community colors",	11✔
105	},	11✔
106	},	11✔
107	],	11✔
108	description: "Visualizes communities detected via edge betweenness removal",	11✔
109	category: "grouping",	11✔
110	});	11✔
111
112	/**
113	* Executes the Girvan-Newman algorithm on the graph
114	*
115	* Detects communities by iteratively removing edges with highest betweenness.
116	*/
117	async run(): Promise<void> {	19✔
118	const g = this.graph;	3✔
119	const nodes = Array.from(g.getDataManager().nodes.keys());	3✔
120
121	if (nodes.length === 0) {	3!
122	return;	×
123	}	×
124
125	// Get options from schema
126	const {maxCommunities, minCommunitySize, maxIterations} = this.schemaOptions;	3✔
127
128	// Convert to @graphty/algorithms format (truly undirected for community detection)
129	// addReverseEdges: false creates an undirected graph required by girvanNewman
130	const graphData = toAlgorithmGraph(g, {addReverseEdges: false});	3✔
131
132	// Run Girvan-Newman algorithm - returns CommunityResult[] (dendrogram)
133	// Pass maxCommunities only if > 0 (0 means find optimal)
134	const results = girvanNewman(graphData, {	3✔
135	maxCommunities: maxCommunities > 0 ? maxCommunities : undefined,	3!
136	minCommunitySize,	3✔
137	maxIterations,	3✔
138	});	3✔
139
140	// Handle empty results (e.g., graph with no edges)
141	if (results.length === 0) {	3!
142	// Assign each node to its own community
143	for (let i = 0; i < nodes.length; i++) {	×
144	this.addNodeResult(nodes[i], "communityId", i);	×
145	}	×
146	this.addGraphResult("modularity", 0);	×
147	this.addGraphResult("communityCount", nodes.length);	×
148	return;	×
149	}	×
150
151	// Find the result with highest modularity
152	let bestResult = results[0];	3✔
153	for (const result of results) {	3✔
154	if (result.modularity > bestResult.modularity) {	15!
155	bestResult = result;	×
156	}	×
157	}	15✔
158
159	// Store community assignments for each node
160	const communityMap = new Map<number \| string, number>();	3✔
161	for (let i = 0; i < bestResult.communities.length; i++) {	3✔
162	for (const nodeId of bestResult.communities[i]) {	22✔
163	communityMap.set(nodeId, i);	43✔
164	}	43✔
165	}	22✔
166
167	// Store results on nodes
168	for (const nodeId of nodes) {	3✔
169	const communityId = communityMap.get(nodeId) ?? 0;	43!
170	this.addNodeResult(nodeId, "communityId", communityId);	43✔
171	}	43✔
172
173	// Store graph-level results
174	this.addGraphResult("modularity", bestResult.modularity);	3✔
175	this.addGraphResult("communityCount", bestResult.communities.length);	3✔
176	}	3✔
177	}	19✔
178
179	// Auto-register this algorithm when the module is imported
180	Algorithm.register(GirvanNewmanAlgorithm);	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