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

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