20198813057

Committed 13 Dec 2025 10:31PM UTC coverage: 86.318% (-4.8%) from 91.088%

Build # 20198813057

Build Type

push

github

Committed by

apowers313

Commit Message

fix: algorithm exports

Run Details

2508 of 2962 branches covered (84.67%)

Branch coverage included in aggregate %.

9056 of 10435 relevant lines covered (86.78%)

693539.89 hits per line

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

89.27

/src/algorithms/centrality/betweenness.ts

import type {Graph} from "../../core/graph.js";
import type {NodeId} from "../../types/index.js";
import {bfsWithPathCounting} from "../traversal/bfs-variants.js";

/**
 * Betweenness centrality implementation using Brandes' algorithm
 *
 * Measures the extent to which a node lies on paths between other nodes.
 * Uses the fast O(VE) algorithm by Ulrik Brandes.
 */

/**
 * Betweenness centrality options
 */
export interface BetweennessCentralityOptions {
    /**
     * Whether to normalize the centrality values (default: false)
     */
    normalized?: boolean;
    /**
     * Whether to use endpoints in path counting (default: false)
     */
    endpoints?: boolean;
    /**
     * Whether to use optimized BFS implementation for large graphs
     */
    optimized?: boolean;
}

/**
 * Result of Brandes algorithm computation for a single source
 */
interface BrandesResult {
    stack: NodeId[];
    predecessors: Map<NodeId, NodeId[]>;
    sigma: Map<NodeId, number>;
    distance: Map<NodeId, number>;
}

/**
 * Run single-source shortest path computation using BFS
 */
function brandesSingleSource(graph: Graph, source: NodeId, optimized?: boolean): BrandesResult {
    const result = bfsWithPathCounting(graph, source, optimized !== undefined ? {optimized} : {});

    return {
        stack: result.stack,
        predecessors: result.predecessors,
        sigma: result.sigma,
        distance: result.distances,
    };
}

/**
 * Accumulate betweenness contributions from a single source
 */
function accumulateBetweenness(
    result: BrandesResult,
    source: NodeId,
    centrality: Record<string, number>,
    options: BetweennessCentralityOptions,
): void {
    const {stack, predecessors, sigma} = result;
    const delta = new Map<NodeId, number>();

    // Initialize delta
    for (const node of stack) {
        delta.set(node, 0);
    }

    // Accumulation - back-propagation of dependencies
    // Process nodes in reverse BFS order
    for (let i = stack.length - 1; i >= 0; i--) {
        const w = stack[i];
        if (!w) {
            continue;
        }

        const wPreds = predecessors.get(w) ?? [];
        const wSigma = sigma.get(w) ?? 0;
        const wDelta = delta.get(w) ?? 0;

        for (const v of wPreds) {
            const vSigma = sigma.get(v) ?? 0;
            const vDelta = delta.get(v) ?? 0;

            if (vSigma > 0 && wSigma > 0) {
                let contribution = (vSigma / wSigma) * (1 + wDelta);

                // Apply endpoints option: when false, exclude endpoint contributions
                if (!options.endpoints) {
                    // For standard betweenness, don't count paths that only involve endpoints
                    const isTargetEndpoint = wPreds.length === 0 && w !== source;
                    if (isTargetEndpoint) {
                        contribution = 0; // Exclude endpoint contributions
                    }
                }

                delta.set(v, vDelta + contribution);
            }
        }

        if (w !== source) {
            const currentCentrality = centrality[String(w)] ?? 0;
            centrality[String(w)] = currentCentrality + wDelta;
        }
    }
}

/**
 * Accumulate edge betweenness contributions from a single source
 */
function accumulateEdgeBetweenness(
    result: BrandesResult,
    source: NodeId,
    edgeCentrality: Map<string, number>,
    options: BetweennessCentralityOptions,
): void {
    const {stack, predecessors, sigma} = result;
    const delta = new Map<NodeId, number>();

    // Initialize delta
    for (const node of stack) {
        delta.set(node, 0);
    }

    // Accumulation for edges
    // Process nodes in reverse BFS order
    for (let i = stack.length - 1; i >= 0; i--) {
        const w = stack[i];
        if (!w) {
            continue;
        }

        const wPreds = predecessors.get(w) ?? [];
        const wSigma = sigma.get(w) ?? 0;
        const wDelta = delta.get(w) ?? 0;

        for (const v of wPreds) {
            const vSigma = sigma.get(v) ?? 0;

            if (vSigma > 0 && wSigma > 0) {
                let edgeContribution = (vSigma / wSigma) * (1 + wDelta);

                // Apply endpoints option for edge betweenness
                if (!options.endpoints) {
                    const isTargetEndpoint = wPreds.length === 0 && w !== source;
                    if (isTargetEndpoint) {
                        edgeContribution = 0; // Exclude endpoint contributions
                    }
                }

                // Update edge centrality
                const edgeKey = `${String(v)}-${String(w)}`;
                const currentEdgeCentrality = edgeCentrality.get(edgeKey) ?? 0;
                edgeCentrality.set(edgeKey, currentEdgeCentrality + edgeContribution);

                // Update node delta
                const vDelta = delta.get(v) ?? 0;
                delta.set(v, vDelta + edgeContribution);
            }
        }
    }
}

/**
 * Apply normalization to centrality values
 */
function normalizeCentrality(
    centrality: Record<string, number>,
    nodeCount: number,
    isDirected: boolean,
): void {
    const n = nodeCount;
    const normalizationFactor = isDirected ?
        (n - 1) * (n - 2) :
        ((n - 1) * (n - 2)) / 2;

    if (normalizationFactor > 0) {
        for (const key in centrality) {
            const value = centrality[key];
            if (value !== undefined) {
                centrality[key] = value / normalizationFactor;
            }
        }
    }
}

/**
 * Calculate betweenness centrality for all nodes using Brandes' algorithm
 */
export function betweennessCentrality(
    graph: Graph,
    options: BetweennessCentralityOptions = {},
): Record<string, number> {
    const nodes = Array.from(graph.nodes()).map((node) => node.id);
    const centrality: Record<string, number> = {};

    // Initialize centrality scores
    for (const nodeId of nodes) {
        centrality[String(nodeId)] = 0;
    }

    // Brandes' algorithm - run from each source
    for (const source of nodes) {
        const result = brandesSingleSource(graph, source, options.optimized);
        accumulateBetweenness(result, source, centrality, options);
    }

    // For undirected graphs, divide by 2 (each shortest path is counted twice)
    if (!graph.isDirected) {
        for (const nodeId of nodes) {
            const key = String(nodeId);
            const value = centrality[key];
            if (value !== undefined) {
                centrality[key] = value / 2;
            }
        }
    }

    // Normalization
    if (options.normalized) {
        normalizeCentrality(centrality, nodes.length, graph.isDirected);
    }

    return centrality;
}

/**
 * Calculate betweenness centrality for a specific node
 */
export function nodeBetweennessCentrality(
    graph: Graph,
    targetNode: NodeId,
    options: BetweennessCentralityOptions = {},
): number {
    if (!graph.hasNode(targetNode)) {
        throw new Error(`Node ${String(targetNode)} not found in graph`);
    }

    const allCentralities = betweennessCentrality(graph, options);
    return allCentralities[String(targetNode)] ?? 0;
}

/**
 * Calculate edge betweenness centrality
 */
export function edgeBetweennessCentrality(
    graph: Graph,
    options: BetweennessCentralityOptions = {},
): Map<string, number> {
    const nodes = Array.from(graph.nodes()).map((node) => node.id);
    const edgeCentrality = new Map<string, number>();

    // Initialize edge centrality scores
    for (const edge of Array.from(graph.edges())) {
        const edgeKey = `${String(edge.source)}-${String(edge.target)}`;
        edgeCentrality.set(edgeKey, 0);
    }

    // Modified Brandes' algorithm for edge betweenness
    for (const source of nodes) {
        const result = brandesSingleSource(graph, source, options.optimized);
        accumulateEdgeBetweenness(result, source, edgeCentrality, options);
    }

    // For undirected graphs, divide by 2 (each shortest path is counted twice)
    if (!graph.isDirected) {
        for (const [edgeKey, centrality] of Array.from(edgeCentrality)) {
            edgeCentrality.set(edgeKey, centrality / 2);
        }
    }

    // Normalization for edges
    if (options.normalized) {
        const n = nodes.length;
        const normalizationFactor = graph.isDirected ?
            (n - 1) * (n - 2) :
            ((n - 1) * (n - 2)) / 2;

        if (normalizationFactor > 0) {
            for (const [edgeKey, centrality] of Array.from(edgeCentrality)) {
                edgeCentrality.set(edgeKey, centrality / normalizationFactor);
            }
        }
    }

    return edgeCentrality;
}

1	import type {Graph} from "../../core/graph.js";
2	import type {NodeId} from "../../types/index.js";
3	import {bfsWithPathCounting} from "../traversal/bfs-variants.js";	1✔
4
5	/**
6	* Betweenness centrality implementation using Brandes' algorithm
7	*
8	* Measures the extent to which a node lies on paths between other nodes.
9	* Uses the fast O(VE) algorithm by Ulrik Brandes.
10	*/
11
12	/**
13	* Betweenness centrality options
14	*/
15	export interface BetweennessCentralityOptions {
16	/**
17	* Whether to normalize the centrality values (default: false)
18	*/
19	normalized?: boolean;
20	/**
21	* Whether to use endpoints in path counting (default: false)
22	*/
23	endpoints?: boolean;
24	/**
25	* Whether to use optimized BFS implementation for large graphs
26	*/
27	optimized?: boolean;
28	}
29
30	/**
31	* Result of Brandes algorithm computation for a single source
32	*/
33	interface BrandesResult {
34	stack: NodeId[];
35	predecessors: Map<NodeId, NodeId[]>;
36	sigma: Map<NodeId, number>;
37	distance: Map<NodeId, number>;
38	}
39
40	/**
41	* Run single-source shortest path computation using BFS
42	*/
43	function brandesSingleSource(graph: Graph, source: NodeId, optimized?: boolean): BrandesResult {	308✔
44	const result = bfsWithPathCounting(graph, source, optimized !== undefined ? {optimized} : {});	308!
45
46	return {	308✔
47	stack: result.stack,	308✔
48	predecessors: result.predecessors,	308✔
49	sigma: result.sigma,	308✔
50	distance: result.distances,	308✔
51	};	308✔
52	}	308✔
53
54	/**
55	* Accumulate betweenness contributions from a single source
56	*/
57	function accumulateBetweenness(	263✔
58	result: BrandesResult,	263✔
59	source: NodeId,	263✔
60	centrality: Record<string, number>,	263✔
61	options: BetweennessCentralityOptions,	263✔
62	): void {	263✔
63	const {stack, predecessors, sigma} = result;	263✔
64	const delta = new Map<NodeId, number>();	263✔
65
66	// Initialize delta
67	for (const node of stack) {	263✔
68	delta.set(node, 0);	10,536✔
69	}	10,536✔
70
71	// Accumulation - back-propagation of dependencies
72	// Process nodes in reverse BFS order
73	for (let i = stack.length - 1; i >= 0; i--) {	263✔
74	const w = stack[i];	10,536✔
75	if (!w) {	10,536!
76	continue;	×
77	}	×
78
79	const wPreds = predecessors.get(w) ?? [];	10,536✔
80	const wSigma = sigma.get(w) ?? 0;	10,536!
81	const wDelta = delta.get(w) ?? 0;	10,536!
82
83	for (const v of wPreds) {	10,536✔
84	const vSigma = sigma.get(v) ?? 0;	10,293!
85	const vDelta = delta.get(v) ?? 0;	10,293!
86
87	if (vSigma > 0 && wSigma > 0) {	10,293✔
88	let contribution = (vSigma / wSigma) * (1 + wDelta);	10,293✔
89
90	// Apply endpoints option: when false, exclude endpoint contributions
91	if (!options.endpoints) {	10,293✔
92	// For standard betweenness, don't count paths that only involve endpoints
93	const isTargetEndpoint = wPreds.length === 0 && w !== source;	10,257!
94	if (isTargetEndpoint) {	10,257!
95	contribution = 0; // Exclude endpoint contributions	×
96	}	×
97	}	10,257✔
98
99	delta.set(v, vDelta + contribution);	10,293✔
100	}	10,293✔
101	}	10,293✔
102
103	if (w !== source) {	10,536✔
104	const currentCentrality = centrality[String(w)] ?? 0;	10,273!
105	centrality[String(w)] = currentCentrality + wDelta;	10,273✔
106	}	10,273✔
107	}	10,536✔
108	}	263✔
109
110	/**
111	* Accumulate edge betweenness contributions from a single source
112	*/
113	function accumulateEdgeBetweenness(	45✔
114	result: BrandesResult,	45✔
115	source: NodeId,	45✔
116	edgeCentrality: Map<string, number>,	45✔
117	options: BetweennessCentralityOptions,	45✔
118	): void {	45✔
119	const {stack, predecessors, sigma} = result;	45✔
120	const delta = new Map<NodeId, number>();	45✔
121
122	// Initialize delta
123	for (const node of stack) {	45✔
124	delta.set(node, 0);	147✔
125	}	147✔
126
127	// Accumulation for edges
128	// Process nodes in reverse BFS order
129	for (let i = stack.length - 1; i >= 0; i--) {	45✔
130	const w = stack[i];	147✔
131	if (!w) {	147!
132	continue;	×
133	}	×
134
135	const wPreds = predecessors.get(w) ?? [];	147✔
136	const wSigma = sigma.get(w) ?? 0;	147!
137	const wDelta = delta.get(w) ?? 0;	147!
138
139	for (const v of wPreds) {	147✔
140	const vSigma = sigma.get(v) ?? 0;	106!
141
142	if (vSigma > 0 && wSigma > 0) {	106✔
143	let edgeContribution = (vSigma / wSigma) * (1 + wDelta);	106✔
144
145	// Apply endpoints option for edge betweenness
146	if (!options.endpoints) {	106✔
147	const isTargetEndpoint = wPreds.length === 0 && w !== source;	94!
148	if (isTargetEndpoint) {	94!
149	edgeContribution = 0; // Exclude endpoint contributions	×
150	}	×
151	}	94✔
152
153	// Update edge centrality
154	const edgeKey = `${String(v)}-${String(w)}`;	106✔
155	const currentEdgeCentrality = edgeCentrality.get(edgeKey) ?? 0;	106✔
156	edgeCentrality.set(edgeKey, currentEdgeCentrality + edgeContribution);	106✔
157
158	// Update node delta
159	const vDelta = delta.get(v) ?? 0;	106!
160	delta.set(v, vDelta + edgeContribution);	106✔
161	}	106✔
162	}	106✔
163	}	147✔
164	}	45✔
165
166	/**
167	* Apply normalization to centrality values
168	*/
169	function normalizeCentrality(	11✔
170	centrality: Record<string, number>,	11✔
171	nodeCount: number,	11✔
172	isDirected: boolean,	11✔
173	): void {	11✔
174	const n = nodeCount;	11✔
175	const normalizationFactor = isDirected ?	11✔
176	(n - 1) * (n - 2) :	2✔
177	((n - 1) * (n - 2)) / 2;	9✔
178
179	if (normalizationFactor > 0) {	11✔
180	for (const key in centrality) {	6✔
181	const value = centrality[key];	19✔
182	if (value !== undefined) {	19✔
183	centrality[key] = value / normalizationFactor;	19✔
184	}	19✔
185	}	19✔
186	}	6✔
187	}	11✔
188
189	/**
190	* Calculate betweenness centrality for all nodes using Brandes' algorithm
191	*/
192	export function betweennessCentrality(	1✔
193	graph: Graph,	51✔
194	options: BetweennessCentralityOptions = {},	51✔
195	): Record<string, number> {	51✔
196	const nodes = Array.from(graph.nodes()).map((node) => node.id);	51✔
197	const centrality: Record<string, number> = {};	51✔
198
199	// Initialize centrality scores
200	for (const nodeId of nodes) {	51✔
201	centrality[String(nodeId)] = 0;	263✔
202	}	263✔
203
204	// Brandes' algorithm - run from each source
205	for (const source of nodes) {	51✔
206	const result = brandesSingleSource(graph, source, options.optimized);	263✔
207	accumulateBetweenness(result, source, centrality, options);	263✔
208	}	263✔
209
210	// For undirected graphs, divide by 2 (each shortest path is counted twice)
211	if (!graph.isDirected) {	51✔
212	for (const nodeId of nodes) {	40✔
213	const key = String(nodeId);	225✔
214	const value = centrality[key];	225✔
215	if (value !== undefined) {	225✔
216	centrality[key] = value / 2;	225✔
217	}	225✔
218	}	225✔
219	}	40✔
220
221	// Normalization
222	if (options.normalized) {	51✔
223	normalizeCentrality(centrality, nodes.length, graph.isDirected);	11✔
224	}	11✔
225
226	return centrality;	51✔
227	}	51✔
228
229	/**
230	* Calculate betweenness centrality for a specific node
231	*/
232	export function nodeBetweennessCentrality(	1✔
233	graph: Graph,	5✔
234	targetNode: NodeId,	5✔
235	options: BetweennessCentralityOptions = {},	5✔
236	): number {	5✔
237	if (!graph.hasNode(targetNode)) {	5✔
238	throw new Error(`Node ${String(targetNode)} not found in graph`);	1✔
239	}	1✔
240
241	const allCentralities = betweennessCentrality(graph, options);	4✔
242	return allCentralities[String(targetNode)] ?? 0;	5!
243	}	5✔
244
245	/**
246	* Calculate edge betweenness centrality
247	*/
248	export function edgeBetweennessCentrality(	1✔
249	graph: Graph,	17✔
250	options: BetweennessCentralityOptions = {},	17✔
251	): Map<string, number> {	17✔
252	const nodes = Array.from(graph.nodes()).map((node) => node.id);	17✔
253	const edgeCentrality = new Map<string, number>();	17✔
254
255	// Initialize edge centrality scores
256	for (const edge of Array.from(graph.edges())) {	17✔
257	const edgeKey = `${String(edge.source)}-${String(edge.target)}`;	31✔
258	edgeCentrality.set(edgeKey, 0);	31✔
259	}	31✔
260
261	// Modified Brandes' algorithm for edge betweenness
262	for (const source of nodes) {	17✔
263	const result = brandesSingleSource(graph, source, options.optimized);	45✔
264	accumulateEdgeBetweenness(result, source, edgeCentrality, options);	45✔
265	}	45✔
266
267	// For undirected graphs, divide by 2 (each shortest path is counted twice)
268	if (!graph.isDirected) {	17✔
269	for (const [edgeKey, centrality] of Array.from(edgeCentrality)) {	12✔
270	edgeCentrality.set(edgeKey, centrality / 2);	52✔
271	}	52✔
272	}	12✔
273
274	// Normalization for edges
275	if (options.normalized) {	17✔
276	const n = nodes.length;	6✔
277	const normalizationFactor = graph.isDirected ?	6✔
278	(n - 1) * (n - 2) :	2✔
279	((n - 1) * (n - 2)) / 2;	4✔
280
281	if (normalizationFactor > 0) {	6✔
282	for (const [edgeKey, centrality] of Array.from(edgeCentrality)) {	1✔
283	edgeCentrality.set(edgeKey, centrality / normalizationFactor);	4✔
284	}	4✔
285	}	1✔
286	}	6✔
287
288	return edgeCentrality;	17✔
289	}	17✔

graphty-org / algorithms / 20198813057

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