16448606452

Committed 22 Jul 2025 03:21PM UTC coverage: 90.516% (-1.6%) from 92.089%

Build # 16448606452

Build Type

push

github

Committed by

apowers313

Commit Message

feat: add priority 3 algorithms and tests

Run Details

1763 of 2062 branches covered (85.5%)

Branch coverage included in aggregate %.

1613 of 1802 new or added lines in 9 files covered. (89.51%)

8 existing lines in 1 file now uncovered.

6168 of 6700 relevant lines covered (92.06%)

2627.44 hits per line

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

85.26

/src/algorithms/centrality/betweenness.ts

import type {Graph} from "../../core/graph.js";
import type {NodeId} from "../../types/index.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;
}

/**
 * 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
    for (const source of nodes) {
        const stack: NodeId[] = [];
        const predecessors = new Map<NodeId, NodeId[]>();
        const sigma = new Map<NodeId, number>(); // Number of shortest paths
        const distance = new Map<NodeId, number>();
        const delta = new Map<NodeId, number>();

        // Initialize
        for (const nodeId of nodes) {
            predecessors.set(nodeId, []);
            sigma.set(nodeId, 0);
            distance.set(nodeId, -1);
            delta.set(nodeId, 0);
        }

        sigma.set(source, 1);
        distance.set(source, 0);

        const queue: NodeId[] = [source];

        // BFS to find shortest paths
        while (queue.length > 0) {
            const current = queue.shift();
            if (!current) {
                break;
            }

            stack.push(current);

            for (const neighbor of Array.from(graph.neighbors(current))) {
                const currentDistance = distance.get(current);
                let neighborDistance = distance.get(neighbor);

                if (currentDistance === undefined || neighborDistance === undefined) {
                    continue;
                }

                // First time we reach this neighbor
                if (neighborDistance < 0) {
                    queue.push(neighbor);
                    distance.set(neighbor, currentDistance + 1);
                    neighborDistance = currentDistance + 1; // Update local variable
                }

                // Shortest path to neighbor via current
                if (neighborDistance === currentDistance + 1) {
                    const neighborSigma = sigma.get(neighbor) ?? 0;
                    const currentSigma = sigma.get(current) ?? 0;
                    sigma.set(neighbor, neighborSigma + currentSigma);

                    const preds = predecessors.get(neighbor);
                    if (preds) {
                        preds.push(current);
                    }
                }
            }
        }

        // Accumulation - back-propagation of dependencies
        while (stack.length > 0) {
            const w = stack.pop();
            if (!w) {
                break;
            }

            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 = predecessors.get(w)?.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;
            }
        }
    }

    // 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 currentValue = centrality[key];
            if (currentValue !== undefined) {
                centrality[key] = currentValue / 2;
            }
        }
    }

    // Normalization
    if (options.normalized) {
        const n = nodes.length;
        let normalizationFactor: number;

        if (graph.isDirected) {
            normalizationFactor = (n - 1) * (n - 2);
        } else {
            normalizationFactor = ((n - 1) * (n - 2)) / 2;
        }

        if (normalizationFactor > 0) {
            for (const nodeId of nodes) {
                const key = String(nodeId);
                const currentValue = centrality[key];
                if (currentValue !== undefined) {
                    centrality[key] = currentValue / normalizationFactor;
                }
            }
        }
    }

    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 stack: NodeId[] = [];
        const predecessors = new Map<NodeId, NodeId[]>();
        const sigma = new Map<NodeId, number>();
        const distance = new Map<NodeId, number>();
        const delta = new Map<NodeId, number>();

        // Initialize
        for (const nodeId of nodes) {
            predecessors.set(nodeId, []);
            sigma.set(nodeId, 0);
            distance.set(nodeId, -1);
            delta.set(nodeId, 0);
        }

        sigma.set(source, 1);
        distance.set(source, 0);

        const queue: NodeId[] = [source];

        // BFS to find shortest paths
        while (queue.length > 0) {
            const current = queue.shift();
            if (!current) {
                break;
            }

            stack.push(current);

            for (const neighbor of Array.from(graph.neighbors(current))) {
                const currentDistance = distance.get(current);
                let neighborDistance = distance.get(neighbor);

                if (currentDistance === undefined || neighborDistance === undefined) {
                    continue;
                }

                if (neighborDistance < 0) {
                    queue.push(neighbor);
                    distance.set(neighbor, currentDistance + 1);
                    neighborDistance = currentDistance + 1; // Update local variable
                }

                if (neighborDistance === currentDistance + 1) {
                    const neighborSigma = sigma.get(neighbor) ?? 0;
                    const currentSigma = sigma.get(current) ?? 0;
                    sigma.set(neighbor, neighborSigma + currentSigma);

                    const preds = predecessors.get(neighbor);
                    if (preds) {
                        preds.push(current);
                    }
                }
            }
        }

        // Accumulation for edges
        while (stack.length > 0) {
            const w = stack.pop();
            if (!w) {
                break;
            }

            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 = predecessors.get(w)?.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);
                }
            }
        }
    }

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

graphty-org / algorithms / 16448606452

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