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

Run Details

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