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

Coverage Stats

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.31

/src/algorithms/BFSAlgorithm.ts

import {breadthFirstSearch} from "@graphty/algorithms";
import {z} from "zod/v4";

import {defineOptions, type OptionsSchema as ZodOptionsSchema, type SuggestedStylesConfig} from "../config";
import type {Graph} from "../Graph";
import {Algorithm} from "./Algorithm";
import {type OptionsSchema} from "./types/OptionSchema";
import {toAlgorithmGraph} from "./utils/graphConverter";

/**
 * Zod-based options schema for BFS algorithm
 */
export const bfsOptionsSchema = defineOptions({
    source: {
        schema: z.union([z.string(), z.number()]).nullable().default(null),
        meta: {
            label: "Source Node",
            description: "Starting node for BFS traversal (uses first node if not set)",
        },
    },
    targetNode: {
        schema: z.union([z.string(), z.number()]).nullable().default(null),
        meta: {
            label: "Target Node",
            description: "Target node for early termination (optional - searches all nodes if not set)",
            advanced: true,
        },
    },
});

/**
 * Options for BFS algorithm
 */
export interface BFSOptions extends Record<string, unknown> {
    /** Starting node for traversal (defaults to first node if not provided) */
    source: number | string | null;
    /** Target node for early termination (optional) */
    targetNode: number | string | null;
}

/**
 * Breadth-First Search (BFS) algorithm for graph traversal
 *
 * Performs a breadth-first traversal from a source node, computing level information
 * and predecessor relationships for each reachable node.
 */
export class BFSAlgorithm extends Algorithm<BFSOptions> {
    static namespace = "graphty";
    static type = "bfs";

    static zodOptionsSchema: ZodOptionsSchema = bfsOptionsSchema;

    /**
     * Options schema for BFS algorithm
     */
    static optionsSchema: OptionsSchema = {
        source: {
            type: "nodeId",
            default: null,
            label: "Source Node",
            description: "Starting node for BFS traversal (uses first node if not set)",
            required: false,
        },
        targetNode: {
            type: "nodeId",
            default: null,
            label: "Target Node",
            description: "Target node for early termination (optional - searches all nodes if not set)",
            required: false,
            advanced: true,
        },
    };

    /**
     * Legacy options set via configure() for backward compatibility
     */
    private legacyOptions: {source: number | string} | null = null;

    static suggestedStyles = (): SuggestedStylesConfig => ({
        layers: [
            {
                node: {
                    selector: "",
                    style: {enabled: true},
                    calculatedStyle: {
                        inputs: ["algorithmResults.graphty.bfs.levelPct"],
                        output: "style.texture.color",
                        expr: "{ return StyleHelpers.color.sequential.viridis(arguments[0] ?? 0) }",
                    },
                },
                metadata: {
                    name: "BFS - Level Colors",
                    description: "Colors nodes by BFS level from source (viridis gradient)",
                },
            },
        ],
        description: "Visualizes breadth-first traversal levels from source node",
        category: "hierarchy",
    });

    /**
     * Configure the algorithm with source node
     * @param options - Configuration options
     * @param options.source - The source node to start BFS from
     * @returns This algorithm instance for chaining
     * @deprecated Use constructor options instead. This method is kept for backward compatibility.
     */
    configure(options: {source: number | string}): this {
        this.legacyOptions = options;
        return this;
    }

    /**
     * Executes the BFS algorithm on the graph
     *
     * Computes BFS level, predecessor, and distance information for all reachable 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;
        }

        // Get source from legacy options, schema options, or use first node as default
        // Legacy configure() takes precedence for backward compatibility
        const source = this.legacyOptions?.source ?? this._schemaOptions.source ?? nodes[0];
        const targetNode = this._schemaOptions.targetNode ?? undefined;

        // Convert to @graphty/algorithms format
        // Using directed=false so the converter adds reverse edges for undirected traversal
        const graphData = toAlgorithmGraph(g as unknown as Graph, {directed: false});

        // Check if source exists
        if (!graphData.hasNode(source)) {
            // Source not in graph - nothing to do
            return;
        }

        // Track levels and visit order manually since breadthFirstSearch doesn't return them directly
        const levels = new Map<string | number, number>();
        const visitOrders = new Map<string | number, number>();
        let visitOrder = 0;
        let maxLevel = 0;
        let foundTarget = false;

        // Use visitCallback to track levels
        breadthFirstSearch(graphData, source, {
            targetNode,
            visitCallback: (node, level) => {
                levels.set(node, level);
                visitOrders.set(node, visitOrder);
                visitOrder++;
                if (level > maxLevel) {
                    maxLevel = level;
                }

                if (targetNode !== undefined && node === targetNode) {
                    foundTarget = true;
                }
            },
        });

        // Store results on nodes
        for (const nodeId of nodes) {
            const level = levels.get(nodeId);
            const order = visitOrders.get(nodeId);

            if (level !== undefined) {
                this.addNodeResult(nodeId, "level", level);
                // Normalize level to percentage
                const levelPct = maxLevel > 0 ? level / maxLevel : 0;
                this.addNodeResult(nodeId, "levelPct", levelPct);
            }

            if (order !== undefined) {
                this.addNodeResult(nodeId, "visitOrder", order);
            }
        }

        // Store graph-level results
        this.addGraphResult("maxLevel", maxLevel);
        this.addGraphResult("visitedCount", levels.size);
        if (targetNode !== undefined) {
            this.addGraphResult("targetFound", foundTarget);
        }
    }
}

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

1	import {breadthFirstSearch} 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 type {Graph} from "../Graph";
6	import {Algorithm} from "./Algorithm";	15 ✔
7	import {type OptionsSchema} from "./types/OptionSchema";
8	import {toAlgorithmGraph} from "./utils/graphConverter";	15 ✔
9
10	/**
11	* Zod-based options schema for BFS algorithm
12	*/
13	export const bfsOptionsSchema = defineOptions({	15 ✔
14	source: {	15 ✔
15	schema: z.union([z.string(), z.number()]).nullable().default(null),	15 ✔
16	meta: {	15 ✔
17	label: "Source Node",	15 ✔
18	description: "Starting node for BFS traversal (uses first node if not set)",	15 ✔
19	},	15 ✔
20	},	15 ✔
21	targetNode: {	15 ✔
22	schema: z.union([z.string(), z.number()]).nullable().default(null),	15 ✔
23	meta: {	15 ✔
24	label: "Target Node",	15 ✔
25	description: "Target node for early termination (optional - searches all nodes if not set)",	15 ✔
26	advanced: true,	15 ✔
27	},	15 ✔
28	},	15 ✔
29	});	15 ✔
30
31	/**
32	* Options for BFS algorithm
33	*/
34	export interface BFSOptions extends Record<string, unknown> {
35	/** Starting node for traversal (defaults to first node if not provided) */
36	source: number \| string \| null;
37	/** Target node for early termination (optional) */
38	targetNode: number \| string \| null;
39	}
40
41	/**
42	* Breadth-First Search (BFS) algorithm for graph traversal
43	*
44	* Performs a breadth-first traversal from a source node, computing level information
45	* and predecessor relationships for each reachable node.
46	*/
47	export class BFSAlgorithm extends Algorithm<BFSOptions> {	15 ✔
48	static namespace = "graphty";	17 ✔
49	static type = "bfs";	17 ✔
50
51	static zodOptionsSchema: ZodOptionsSchema = bfsOptionsSchema;	17 ✔
52
53	/**
54	* Options schema for BFS algorithm
55	*/
56	static optionsSchema: OptionsSchema = {	17 ✔
57	source: {	17 ✔
58	type: "nodeId",	17 ✔
59	default: null,	17 ✔
60	label: "Source Node",	17 ✔
61	description: "Starting node for BFS traversal (uses first node if not set)",	17 ✔
62	required: false,	17 ✔
63	},	17 ✔
64	targetNode: {	17 ✔
65	type: "nodeId",	17 ✔
66	default: null,	17 ✔
67	label: "Target Node",	17 ✔
68	description: "Target node for early termination (optional - searches all nodes if not set)",	17 ✔
69	required: false,	17 ✔
70	advanced: true,	17 ✔
71	},	17 ✔
72	};	17 ✔
73
74	/**
75	* Legacy options set via configure() for backward compatibility
76	*/
77	private legacyOptions: {source: number \| string} \| null = null;	17 ✔
78
79	static suggestedStyles = (): SuggestedStylesConfig => ({	120 ✔
80	layers: [	10 ✔
81	{	10 ✔
82	node: {	10 ✔
83	selector: "",	10 ✔
84	style: {enabled: true},	10 ✔
85	calculatedStyle: {	10 ✔
86	inputs: ["algorithmResults.graphty.bfs.levelPct"],	10 ✔
87	output: "style.texture.color",	10 ✔
88	expr: "{ return StyleHelpers.color.sequential.viridis(arguments[0] ?? 0) }",	10 ✔
89	},	10 ✔
90	},	10 ✔
91	metadata: {	10 ✔
92	name: "BFS - Level Colors",	10 ✔
93	description: "Colors nodes by BFS level from source (viridis gradient)",	10 ✔
94	},	10 ✔
95	},	10 ✔
96	],	10 ✔
97	description: "Visualizes breadth-first traversal levels from source node",	10 ✔
98	category: "hierarchy",	10 ✔
99	});	10 ✔
100
101	/**
102	* Configure the algorithm with source node
103	* @param options - Configuration options
104	* @param options.source - The source node to start BFS from
105	* @returns This algorithm instance for chaining
106	* @deprecated Use constructor options instead. This method is kept for backward compatibility.
107	*/
108	configure(options: {source: number \| string}): this {	19 ✔
109	this.legacyOptions = options;	8 ✔
110	return this;	8 ✔
111	}	8 ✔
112
113	/**
114	* Executes the BFS algorithm on the graph
115	*
116	* Computes BFS level, predecessor, and distance information for all reachable nodes.
117	*/
118	async run(): Promise<void> {	19 ✔
119	const g = this.graph;	13 ✔
120	const dm = g.getDataManager();	13 ✔
121	const nodes = Array.from(dm.nodes.keys());	13 ✔
122	const n = nodes.length;	13 ✔
123
124	if (n === 0) {	13 !
125	return;	1 ✔
126	}	1 ✔
127
128	// Get source from legacy options, schema options, or use first node as default
129	// Legacy configure() takes precedence for backward compatibility
130	const source = this.legacyOptions?.source ?? this._schemaOptions.source ?? nodes[0];	13 !
131	const targetNode = this._schemaOptions.targetNode ?? undefined;	13 ✔
132
133	// Convert to @graphty/algorithms format
134	// Using directed=false so the converter adds reverse edges for undirected traversal
135	const graphData = toAlgorithmGraph(g as unknown as Graph, {directed: false});	13 ✔
136
137	// Check if source exists
138	if (!graphData.hasNode(source)) {	13 !
139	// Source not in graph - nothing to do
140	return;	×
141	}	✔
142
143	// Track levels and visit order manually since breadthFirstSearch doesn't return them directly
144	const levels = new Map<string \| number, number>();	12 ✔
145	const visitOrders = new Map<string \| number, number>();	12 ✔
146	let visitOrder = 0;	12 ✔
147	let maxLevel = 0;	12 ✔
148	let foundTarget = false;	12 ✔
149
150	// Use visitCallback to track levels
151	breadthFirstSearch(graphData, source, {	12 ✔
152	targetNode,	12 ✔
153	visitCallback: (node, level) => {	12 ✔
154	levels.set(node, level);	569 ✔
155	visitOrders.set(node, visitOrder);	569 ✔
156	visitOrder++;	569 ✔
157	if (level > maxLevel) {	569 ✔
158	maxLevel = level;	31 ✔
159	}	31 ✔
160
161	if (targetNode !== undefined && node === targetNode) {	569 !
162	foundTarget = true;	×
163	}	×
164	},	569 ✔
165	});	12 ✔
166
167	// Store results on nodes
168	for (const nodeId of nodes) {	13 ✔
169	const level = levels.get(nodeId);	588 ✔
170	const order = visitOrders.get(nodeId);	588 ✔
171
172	if (level !== undefined) {	588 ✔
173	this.addNodeResult(nodeId, "level", level);	569 ✔
174	// Normalize level to percentage
175	const levelPct = maxLevel > 0 ? level / maxLevel : 0;	569 !
176	this.addNodeResult(nodeId, "levelPct", levelPct);	569 ✔
177	}	569 ✔
178
179	if (order !== undefined) {	588 ✔
180	this.addNodeResult(nodeId, "visitOrder", order);	569 ✔
181	}	569 ✔
182	}	588 ✔
183
184	// Store graph-level results
185	this.addGraphResult("maxLevel", maxLevel);	12 ✔
186	this.addGraphResult("visitedCount", levels.size);	12 ✔
187	if (targetNode !== undefined) {	13 !
188	this.addGraphResult("targetFound", foundTarget);	×
189	}	×
190	}	13 ✔
191	}	19 ✔
192
193	// Auto-register this algorithm when the module is imported
194	Algorithm.register(BFSAlgorithm);	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