20390753610

Committed 20 Dec 2025 06:53AM UTC coverage: 82.423% (-1.2%) from 83.666%

Build # 20390753610

Build Type

push

github

Committed by

apowers313

Commit Message

Merge branch 'master' of https://github.com/graphty-org/graphty-element

Run Details

5162 of 6088 branches covered (84.79%)

Branch coverage included in aggregate %.

24775 of 30233 relevant lines covered (81.95%)

6480.4 hits per line

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

89.36

/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",
    });

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

graphty-org / graphty-element / 20390753610

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