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

97.47

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

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
     *
     * @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());

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