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

94.61

/src/algorithms/DFSAlgorithm.ts

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

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

/**
 * Zod-based options schema for DFS algorithm
 */
export const dfsOptionsSchema = defineOptions({
    source: {
        schema: z.union([z.string(), z.number()]).nullable().default(null),
        meta: {
            label: "Source Node",
            description: "Starting node for DFS 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,
        },
    },
    recursive: {
        schema: z.boolean().default(false),
        meta: {
            label: "Recursive",
            description: "Use recursive implementation instead of iterative (may cause stack overflow on large graphs)",
            advanced: true,
        },
    },
    preOrder: {
        schema: z.boolean().default(true),
        meta: {
            label: "Pre-Order",
            description: "Visit nodes before their children (pre-order) vs after (post-order)",
            advanced: true,
        },
    },
});

/**
 * Options for DFS algorithm
 */
export interface DFSOptions 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;
    /** Use recursive implementation vs iterative */
    recursive: boolean;
    /** Use pre-order traversal (visit before children) vs post-order */
    preOrder: boolean;
}

/**
 * Depth-First Search (DFS) algorithm for graph traversal
 *
 * Performs a depth-first traversal from a source node, computing discovery time,
 * finish time, and predecessor relationships for each reachable node.
 */
export class DFSAlgorithm extends Algorithm<DFSOptions> {
    static namespace = "graphty";
    static type = "dfs";

    static zodOptionsSchema: ZodOptionsSchema = dfsOptionsSchema;

    /**
     * Options schema for DFS algorithm
     */
    static optionsSchema: OptionsSchema = {
        source: {
            type: "nodeId",
            default: null,
            label: "Source Node",
            description: "Starting node for DFS 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,
        },
        recursive: {
            type: "boolean",
            default: false,
            label: "Recursive",
            description: "Use recursive implementation instead of iterative (may cause stack overflow on large graphs)",
            advanced: true,
        },
        preOrder: {
            type: "boolean",
            default: true,
            label: "Pre-Order",
            description: "Visit nodes before their children (pre-order) vs after (post-order)",
            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.dfs.discoveryTimePct"],
                        output: "style.texture.color",
                        expr: "{ return StyleHelpers.color.sequential.inferno(arguments[0] ?? 0) }",
                    },
                },
                metadata: {
                    name: "DFS - Discovery Time Colors",
                    description: "Colors nodes by DFS discovery time (inferno gradient: black to yellow)",
                },
            },
        ],
        description: "Visualizes depth-first traversal discovery order from source node",
        category: "hierarchy",
    });

    /**
     * Configure the algorithm with source node
     * @param options - Configuration options
     * @param options.source - The source node to start DFS 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 DFS algorithm on the graph
     *
     * Computes discovery time, finish time, and predecessor information for all reachable nodes.
     */
    async run(): Promise<void> {
        const g = this.graph;
        const dm = g.getDataManager();
        const nodes = Array.from(dm.nodes.keys());

        if (nodes.length === 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, recursive, preOrder} = this._schemaOptions;

        // Check if source exists
        if (!dm.nodes.has(source)) {
            return;
        }

        // Convert to @graphty/algorithms format (undirected for traversal)
        const graphData = toAlgorithmGraph(g);

        // Run DFS algorithm - returns {visited: Set, order: NodeId[], tree?: Map}
        const result = depthFirstSearch(graphData, source, {
            targetNode: targetNode ?? undefined,
            recursive,
            preOrder,
        });

        // Build discovery time map from order array (index = discovery time)
        const discoveryTimeMap = new Map<number | string, number>();
        for (let i = 0; i < result.order.length; i++) {
            discoveryTimeMap.set(result.order[i], i);
        }

        // Max discovery time for normalization
        const maxTime = result.order.length > 0 ? result.order.length - 1 : 0;

        // Store results on nodes
        for (const nodeId of nodes) {
            const discoveryTime = discoveryTimeMap.get(nodeId);
            const isVisited = result.visited.has(nodeId);

            this.addNodeResult(nodeId, "visited", isVisited);

            if (discoveryTime !== undefined) {
                this.addNodeResult(nodeId, "discoveryTime", discoveryTime);
                // Normalize discovery time to percentage
                const discoveryTimePct = maxTime > 0 ? discoveryTime / maxTime : 0;
                this.addNodeResult(nodeId, "discoveryTimePct", discoveryTimePct);
            }
        }

        // Store graph-level results
        this.addGraphResult("maxTime", maxTime);
        this.addGraphResult("visitedCount", result.visited.size);
    }
}

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

1	import {depthFirstSearch} 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 {Algorithm} from "./Algorithm";	15 ✔
6	import {type OptionsSchema} from "./types/OptionSchema";
7	import {toAlgorithmGraph} from "./utils/graphConverter";	15 ✔
8
9	/**
10	* Zod-based options schema for DFS algorithm
11	*/
12	export const dfsOptionsSchema = defineOptions({	15 ✔
13	source: {	15 ✔
14	schema: z.union([z.string(), z.number()]).nullable().default(null),	15 ✔
15	meta: {	15 ✔
16	label: "Source Node",	15 ✔
17	description: "Starting node for DFS traversal (uses first node if not set)",	15 ✔
18	},	15 ✔
19	},	15 ✔
20	targetNode: {	15 ✔
21	schema: z.union([z.string(), z.number()]).nullable().default(null),	15 ✔
22	meta: {	15 ✔
23	label: "Target Node",	15 ✔
24	description: "Target node for early termination (optional - searches all nodes if not set)",	15 ✔
25	advanced: true,	15 ✔
26	},	15 ✔
27	},	15 ✔
28	recursive: {	15 ✔
29	schema: z.boolean().default(false),	15 ✔
30	meta: {	15 ✔
31	label: "Recursive",	15 ✔
32	description: "Use recursive implementation instead of iterative (may cause stack overflow on large graphs)",	15 ✔
33	advanced: true,	15 ✔
34	},	15 ✔
35	},	15 ✔
36	preOrder: {	15 ✔
37	schema: z.boolean().default(true),	15 ✔
38	meta: {	15 ✔
39	label: "Pre-Order",	15 ✔
40	description: "Visit nodes before their children (pre-order) vs after (post-order)",	15 ✔
41	advanced: true,	15 ✔
42	},	15 ✔
43	},	15 ✔
44	});	15 ✔
45
46	/**
47	* Options for DFS algorithm
48	*/
49	export interface DFSOptions extends Record<string, unknown> {
50	/** Starting node for traversal (defaults to first node if not provided) */
51	source: number \| string \| null;
52	/** Target node for early termination (optional) */
53	targetNode: number \| string \| null;
54	/** Use recursive implementation vs iterative */
55	recursive: boolean;
56	/** Use pre-order traversal (visit before children) vs post-order */
57	preOrder: boolean;
58	}
59
60	/**
61	* Depth-First Search (DFS) algorithm for graph traversal
62	*
63	* Performs a depth-first traversal from a source node, computing discovery time,
64	* finish time, and predecessor relationships for each reachable node.
65	*/
66	export class DFSAlgorithm extends Algorithm<DFSOptions> {	15 ✔
67	static namespace = "graphty";	19 ✔
68	static type = "dfs";	19 ✔
69
70	static zodOptionsSchema: ZodOptionsSchema = dfsOptionsSchema;	19 ✔
71
72	/**
73	* Options schema for DFS algorithm
74	*/
75	static optionsSchema: OptionsSchema = {	19 ✔
76	source: {	19 ✔
77	type: "nodeId",	19 ✔
78	default: null,	19 ✔
79	label: "Source Node",	19 ✔
80	description: "Starting node for DFS traversal (uses first node if not set)",	19 ✔
81	required: false,	19 ✔
82	},	19 ✔
83	targetNode: {	19 ✔
84	type: "nodeId",	19 ✔
85	default: null,	19 ✔
86	label: "Target Node",	19 ✔
87	description: "Target node for early termination (optional - searches all nodes if not set)",	19 ✔
88	required: false,	19 ✔
89	advanced: true,	19 ✔
90	},	19 ✔
91	recursive: {	19 ✔
92	type: "boolean",	19 ✔
93	default: false,	19 ✔
94	label: "Recursive",	19 ✔
95	description: "Use recursive implementation instead of iterative (may cause stack overflow on large graphs)",	19 ✔
96	advanced: true,	19 ✔
97	},	19 ✔
98	preOrder: {	19 ✔
99	type: "boolean",	19 ✔
100	default: true,	19 ✔
101	label: "Pre-Order",	19 ✔
102	description: "Visit nodes before their children (pre-order) vs after (post-order)",	19 ✔
103	advanced: true,	19 ✔
104	},	19 ✔
105	};	19 ✔
106
107	/**
108	* Legacy options set via configure() for backward compatibility
109	*/
110	private legacyOptions: {source: number \| string} \| null = null;	19 ✔
111
112	static suggestedStyles = (): SuggestedStylesConfig => ({	120 ✔
113	layers: [	10 ✔
114	{	10 ✔
115	node: {	10 ✔
116	selector: "",	10 ✔
117	style: {enabled: true},	10 ✔
118	calculatedStyle: {	10 ✔
119	inputs: ["algorithmResults.graphty.dfs.discoveryTimePct"],	10 ✔
120	output: "style.texture.color",	10 ✔
121	expr: "{ return StyleHelpers.color.sequential.inferno(arguments[0] ?? 0) }",	10 ✔
122	},	10 ✔
123	},	10 ✔
124	metadata: {	10 ✔
125	name: "DFS - Discovery Time Colors",	10 ✔
126	description: "Colors nodes by DFS discovery time (inferno gradient: black to yellow)",	10 ✔
127	},	10 ✔
128	},	10 ✔
129	],	10 ✔
130	description: "Visualizes depth-first traversal discovery order from source node",	10 ✔
131	category: "hierarchy",	10 ✔
132	});	10 ✔
133
134	/**
135	* Configure the algorithm with source node
136	* @param options - Configuration options
137	* @param options.source - The source node to start DFS from
138	* @returns This algorithm instance for chaining
139	* @deprecated Use constructor options instead. This method is kept for backward compatibility.
140	*/
141	configure(options: {source: number \| string}): this {	19 ✔
142	this.legacyOptions = options;	10 ✔
143	return this;	10 ✔
144	}	10 ✔
145
146	/**
147	* Executes the DFS algorithm on the graph
148	*
149	* Computes discovery time, finish time, and predecessor information for all reachable nodes.
150	*/
151	async run(): Promise<void> {	19 ✔
152	const g = this.graph;	15 ✔
153	const dm = g.getDataManager();	15 ✔
154	const nodes = Array.from(dm.nodes.keys());	15 ✔
155
156	if (nodes.length === 0) {	15 !
157	return;	1 ✔
158	}	1 ✔
159
160	// Get source from legacy options, schema options, or use first node as default
161	// Legacy configure() takes precedence for backward compatibility
162	const source = this.legacyOptions?.source ?? this._schemaOptions.source ?? nodes[0];	15 !
163	const {targetNode, recursive, preOrder} = this._schemaOptions;	15 ✔
164
165	// Check if source exists
166	if (!dm.nodes.has(source)) {	15 !
167	return;	×
168	}	✔
169
170	// Convert to @graphty/algorithms format (undirected for traversal)
171	const graphData = toAlgorithmGraph(g);	14 ✔
172
173	// Run DFS algorithm - returns {visited: Set, order: NodeId[], tree?: Map}
174	const result = depthFirstSearch(graphData, source, {	14 ✔
175	targetNode: targetNode ?? undefined,	14 ✔
176	recursive,	15 ✔
177	preOrder,	15 ✔
178	});	15 ✔
179
180	// Build discovery time map from order array (index = discovery time)
181	const discoveryTimeMap = new Map<number \| string, number>();	15 ✔
182	for (let i = 0; i < result.order.length; i++) {	15 ✔
183	discoveryTimeMap.set(result.order[i], i);	723 ✔
184	}	723 ✔
185
186	// Max discovery time for normalization
187	const maxTime = result.order.length > 0 ? result.order.length - 1 : 0;	15 !
188
189	// Store results on nodes
190	for (const nodeId of nodes) {	15 ✔
191	const discoveryTime = discoveryTimeMap.get(nodeId);	742 ✔
192	const isVisited = result.visited.has(nodeId);	742 ✔
193
194	this.addNodeResult(nodeId, "visited", isVisited);	742 ✔
195
196	if (discoveryTime !== undefined) {	742 ✔
197	this.addNodeResult(nodeId, "discoveryTime", discoveryTime);	723 ✔
198	// Normalize discovery time to percentage
199	const discoveryTimePct = maxTime > 0 ? discoveryTime / maxTime : 0;	723 !
200	this.addNodeResult(nodeId, "discoveryTimePct", discoveryTimePct);	723 ✔
201	}	723 ✔
202	}	742 ✔
203
204	// Store graph-level results
205	this.addGraphResult("maxTime", maxTime);	14 ✔
206	this.addGraphResult("visitedCount", result.visited.size);	14 ✔
207	}	15 ✔
208	}	19 ✔
209
210	// Auto-register this algorithm when the module is imported
211	Algorithm.register(DFSAlgorithm);	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