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

89.92

/src/algorithms/FloydWarshallAlgorithm.ts

import {floydWarshall} from "@graphty/algorithms";

import type {SuggestedStylesConfig} from "../config";
import type {Graph} from "../Graph";
import {Algorithm} from "./Algorithm";
import {toAlgorithmGraph} from "./utils/graphConverter";

/**
 *
 */
export class FloydWarshallAlgorithm extends Algorithm {
    static namespace = "graphty";
    static type = "floyd-warshall";

    static suggestedStyles = (): SuggestedStylesConfig => ({
        layers: [
            {
                node: {
                    selector: "",
                    style: {enabled: true},
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.floyd-warshall.eccentricityPct"],
                        output: "style.texture.color",
                        expr: "{ return StyleHelpers.color.sequential.viridis(arguments[0] ?? 0) }",
                    },
                },
                metadata: {
                    name: "Floyd-Warshall - Eccentricity Heatmap",
                    description: "Colors nodes by eccentricity (purple=central, yellow=peripheral)",
                },
            },
        ],
        description: "Visualizes all-pairs shortest path distances via eccentricity heatmap",
        category: "path",
    });

    /**
     * Executes the Floyd-Warshall algorithm on the graph
     *
     * Computes shortest path distances between all pairs of nodes.
     */
    async run(): Promise<void> {
        const g = this.graph;
        const dm = g.getDataManager();
        const nodes = Array.from(dm.nodes.keys());
        const n = nodes.length;

        if (n === 0) {
            return;
        }

        // Convert to @graphty/algorithms format
        const graphData = toAlgorithmGraph(g as unknown as Graph, {directed: false});

        // Run Floyd-Warshall algorithm
        const result = floydWarshall(graphData);

        // Store graph-level results
        this.addGraphResult("hasNegativeCycle", result.hasNegativeCycle);
        this.addGraphResult("nodeCount", n);

        // Compute eccentricity for each node
        // Eccentricity = max distance from node to any other node
        const eccentricities = new Map<string | number, number>();

        for (const nodeId of nodes) {
            const nodeDistances = result.distances.get(nodeId);
            if (!nodeDistances) {
                eccentricities.set(nodeId, Infinity);
                continue;
            }

            let maxDist = 0;
            for (const dist of nodeDistances.values()) {
                if (isFinite(dist) && dist > maxDist) {
                    maxDist = dist;
                }
            }
            eccentricities.set(nodeId, maxDist);
        }

        // Compute diameter (max eccentricity) and radius (min eccentricity)
        let diameter = 0;
        let radius = Infinity;

        for (const ecc of eccentricities.values()) {
            if (isFinite(ecc)) {
                if (ecc > diameter) {
                    diameter = ecc;
                }

                if (ecc < radius) {
                    radius = ecc;
                }
            }
        }

        // If no valid eccentricities, reset to 0
        if (radius === Infinity) {
            radius = 0;
        }

        this.addGraphResult("diameter", diameter);
        this.addGraphResult("radius", radius);

        // Store eccentricity results on nodes
        for (const nodeId of nodes) {
            const eccentricity = eccentricities.get(nodeId) ?? Infinity;
            this.addNodeResult(nodeId, "eccentricity", eccentricity);

            // Normalize eccentricity to percentage
            const eccentricityPct =
                diameter > 0 && isFinite(eccentricity) ? eccentricity / diameter : 0;
            this.addNodeResult(nodeId, "eccentricityPct", eccentricityPct);

            // Mark central nodes (eccentricity = radius)
            const isCentral = isFinite(eccentricity) && eccentricity === radius;
            this.addNodeResult(nodeId, "isCentral", isCentral);

            // Mark peripheral nodes (eccentricity = diameter)
            const isPeripheral = isFinite(eccentricity) && eccentricity === diameter;
            this.addNodeResult(nodeId, "isPeripheral", isPeripheral);
        }
    }
}

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

1	import {floydWarshall} from "@graphty/algorithms";	15✔
2
3	import type {SuggestedStylesConfig} from "../config";
4	import type {Graph} from "../Graph";
5	import {Algorithm} from "./Algorithm";	15✔
6	import {toAlgorithmGraph} from "./utils/graphConverter";	15✔
7
8	/**
9	*
10	*/
11	export class FloydWarshallAlgorithm extends Algorithm {	15✔
12	static namespace = "graphty";	17✔
13	static type = "floyd-warshall";	118✔
14
15	static suggestedStyles = (): SuggestedStylesConfig => ({	118✔
16	layers: [	6✔
17	{	6✔
18	node: {	6✔
19	selector: "",	6✔
20	style: {enabled: true},	6✔
21	calculatedStyle: {	6✔
22	inputs: ["algorithmResults.graphty.floyd-warshall.eccentricityPct"],	6✔
23	output: "style.texture.color",	6✔
24	expr: "{ return StyleHelpers.color.sequential.viridis(arguments[0] ?? 0) }",	6✔
25	},	6✔
26	},	6✔
27	metadata: {	6✔
28	name: "Floyd-Warshall - Eccentricity Heatmap",	6✔
29	description: "Colors nodes by eccentricity (purple=central, yellow=peripheral)",	6✔
30	},	6✔
31	},	6✔
32	],	6✔
33	description: "Visualizes all-pairs shortest path distances via eccentricity heatmap",	6✔
34	category: "path",	6✔
35	});	6✔
36
37	/**
38	* Executes the Floyd-Warshall algorithm on the graph
39	*
40	* Computes shortest path distances between all pairs of nodes.
41	*/
42	async run(): Promise<void> {	17✔
43	const g = this.graph;	8✔
44	const dm = g.getDataManager();	8✔
45	const nodes = Array.from(dm.nodes.keys());	8✔
46	const n = nodes.length;	8✔
47
48	if (n === 0) {	8✔
49	return;	1✔
50	}	1✔
51
52	// Convert to @graphty/algorithms format
53	const graphData = toAlgorithmGraph(g as unknown as Graph, {directed: false});	7✔
54
55	// Run Floyd-Warshall algorithm
56	const result = floydWarshall(graphData);	7✔
57
58	// Store graph-level results
59	this.addGraphResult("hasNegativeCycle", result.hasNegativeCycle);	7✔
60	this.addGraphResult("nodeCount", n);	7✔
61
62	// Compute eccentricity for each node
63	// Eccentricity = max distance from node to any other node
64	const eccentricities = new Map<string \| number, number>();	7✔
65
66	for (const nodeId of nodes) {	8✔
67	const nodeDistances = result.distances.get(nodeId);	60✔
68	if (!nodeDistances) {	60!
69	eccentricities.set(nodeId, Infinity);	×
70	continue;	×
71	}	×
72
73	let maxDist = 0;	60✔
74	for (const dist of nodeDistances.values()) {	60✔
75	if (isFinite(dist) && dist > maxDist) {	880✔
76	maxDist = dist;	110✔
77	}	110✔
78	}	880✔
79	eccentricities.set(nodeId, maxDist);	60✔
80	}	60✔
81
82	// Compute diameter (max eccentricity) and radius (min eccentricity)
83	let diameter = 0;	7✔
84	let radius = Infinity;	7✔
85
86	for (const ecc of eccentricities.values()) {	8✔
87	if (isFinite(ecc)) {	60✔
88	if (ecc > diameter) {	60✔
89	diameter = ecc;	9✔
90	}	9✔
91
92	if (ecc < radius) {	60✔
93	radius = ecc;	21✔
94	}	21✔
95	}	60✔
96	}	60✔
97
98	// If no valid eccentricities, reset to 0
99	if (radius === Infinity) {	8!
100	radius = 0;	×
101	}	✔
102
103	this.addGraphResult("diameter", diameter);	7✔
104	this.addGraphResult("radius", radius);	7✔
105
106	// Store eccentricity results on nodes
107	for (const nodeId of nodes) {	8✔
108	const eccentricity = eccentricities.get(nodeId) ?? Infinity;	60!
109	this.addNodeResult(nodeId, "eccentricity", eccentricity);	60✔
110
111	// Normalize eccentricity to percentage
112	const eccentricityPct =	60✔
113	diameter > 0 && isFinite(eccentricity) ? eccentricity / diameter : 0;	60!
114	this.addNodeResult(nodeId, "eccentricityPct", eccentricityPct);	60✔
115
116	// Mark central nodes (eccentricity = radius)
117	const isCentral = isFinite(eccentricity) && eccentricity === radius;	60✔
118	this.addNodeResult(nodeId, "isCentral", isCentral);	60✔
119
120	// Mark peripheral nodes (eccentricity = diameter)
121	const isPeripheral = isFinite(eccentricity) && eccentricity === diameter;	60✔
122	this.addNodeResult(nodeId, "isPeripheral", isPeripheral);	60✔
123	}	60✔
124	}	8✔
125	}	17✔
126
127	// Auto-register this algorithm when the module is imported
128	Algorithm.register(FloydWarshallAlgorithm);	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