20390753610

Committed 20 Dec 2025 06:53AM UTC coverage: 82.423% (-1.2%) from 83.666%

Build # 20390753610

Build Type

push

github

Committed by

apowers313

Commit Message

Merge branch 'master' of https://github.com/graphty-org/graphty-element

Coverage Stats

5162 of 6088 branches covered (84.79%)

Branch coverage included in aggregate %.

24775 of 30233 relevant lines covered (81.95%)

6480.4 hits per line

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

93.2

/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;
}

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
     *
     * @deprecated Use constructor options instead. This method is kept for backward compatibility.
     */
    configure(options: {source: number | string}): this {
        this.legacyOptions = options;
        return this;
    }

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

graphty-org / graphty-element / 20390753610

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