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