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

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