1 : import { Edge } from '../core/Edge.js';
2 : 
3 : /**
4 : * Implementation of Depth-first Search.
5 : *
6 : * @author {@link https://github.com/Mugen87|Mugen87}
7 : */
8 : class DFS {
9 : 
10 : 	/**
11 : 	* Constructs a DFS algorithm object.
12 : 	*
13 : 	* @param {Graph} graph - The graph.
14 : 	* @param {Number} source - The node index of the source node.
15 : 	* @param {Number} target - The node index of the target node.
16 : 	*/
17 : 	constructor( graph = null, source = - 1, target = - 1 ) {
18 : 
19 : 		/**
20 : 		* The graph.
21 : 		* @type {?Graph}
22 : 		* @default null
23 : 		*/
24 : 		this.graph = graph;
25 : 
26 : 		/**
27 : 		* The node index of the source node.
28 : 		* @type {Number}
29 : 		* @default - 1
30 : 		*/
31 : 		this.source = source;
32 : 
33 : 		/**
34 : 		* The node index of the target node.
35 : 		* @type {Number}
36 : 		* @default - 1
37 : 		*/
38 : 		this.target = target;
39 : 
40 : 		/**
41 : 		* Whether the search was successful or not.
42 : 		* @type {Boolean}
43 : 		* @default false
44 : 		*/
45 : 		this.found = false;
46 : 
47 : 		this._route = new Map(); // this holds the route taken to the target
48 : 		this._visited = new Set(); // holds the visited nodes
49 : 
50 : 		this._spanningTree = new Set(); // for debugging purposes
51 : 
52 : 	}
53 : 
54 : 	/**
55 : 	* Executes the graph search. If the search was successful, {@link DFS#found}
56 : 	* is set to true.
57 : 	*
58 : 	* @return {DFS} A reference to this DFS object.
59 : 	*/
60 : 	search() {
61 : 
62 : 		// create a stack(LIFO) of edges, done via an array
63 : 
64 : 		const stack = new Array();
65 : 		const outgoingEdges = new Array();
66 : 
67 : 		// create a dummy edge and put on the stack to begin the search
68 : 
69 : 		const startEdge = new Edge( this.source, this.source );
70 : 
71 : 		stack.push( startEdge );
72 : 
73 : 		// while there are edges in the stack keep searching
74 : 
75 : 		while ( stack.length > 0 ) {
76 : 
77 : 			// grab the next edge and remove it from the stack
78 : 
79 : 			const nextEdge = stack.pop();
80 : 
81 : 			// make a note of the parent of the node this edge points to
82 : 
83 : 			this._route.set( nextEdge.to, nextEdge.from );
84 : 
85 : 			// and mark it visited
86 : 
87 : 			this._visited.add( nextEdge.to );
88 : 
89 : 			// expand spanning tree
90 : 
91 : 			if ( nextEdge !== startEdge ) {
92 : 
93 : 				this._spanningTree.add( nextEdge );
94 : 
95 : 			}
96 : 
97 : 			// if the target has been found the method can return success
98 : 
99 : 			if ( nextEdge.to === this.target ) {
100 : 
101 : 				this.found = true;
102 : 
103 : 				return this;
104 : 
105 : 			}
106 : 
107 : 			// determine outgoing edges
108 : 
109 : 			this.graph.getEdgesOfNode( nextEdge.to, outgoingEdges );
110 : 
111 : 			// push the edges leading from the node this edge points to onto the
112 : 			// stack (provided the edge does not point to a previously visited node)
113 : 
114 : 			for ( let i = 0, l = outgoingEdges.length; i < l; i ++ ) {
115 : 
116 : 				const edge = outgoingEdges[ i ];
117 : 
118 : 				if ( this._visited.has( edge.to ) === false ) {
119 : 
120 : 					stack.push( edge );
121 : 
122 : 				}
123 : 
124 : 			}
125 : 
126 : 		}
127 : 
128 : 		this.found = false;
129 : 
130 : 		return this;
131 : 
132 : 	}
133 : 
134 : 	/**
135 : 	* Returns the shortest path from the source to the target node as an array of node indices.
136 : 	*
137 : 	* @return {Array<Number>} The shortest path.
138 : 	*/
139 : 	getPath() {
140 : 
141 : 		// array of node indices that comprise the shortest path from the source to the target
142 : 
143 : 		const path = new Array();
144 : 
145 : 		// just return an empty path if no path to target found or if no target has been specified
146 : 
147 : 		if ( this.found === false || this.target === - 1 ) return path;
148 : 
149 : 		// start with the target of the path
150 : 
151 : 		let currentNode = this.target;
152 : 
153 : 		path.push( currentNode );
154 : 
155 : 		// while the current node is not the source node keep processing
156 : 
157 : 		while ( currentNode !== this.source ) {
158 : 
159 : 			// determine the parent of the current node
160 : 
161 : 			currentNode = this._route.get( currentNode );
162 : 
163 : 			// push the new current node at the beginning of the array
164 : 
165 : 			path.unshift( currentNode );
166 : 
167 : 		}
168 : 
169 : 		return path;
170 : 
171 : 	}
172 : 
173 : 	/**
174 : 	* Returns the search tree of the algorithm as an array of edges.
175 : 	*
176 : 	* @return {Array<Edge>} The search tree.
177 : 	*/
178 : 	getSearchTree() {
179 : 
180 : 		return [ ...this._spanningTree ];
181 : 
182 : 	}
183 : 
184 : 	/**
185 : 	* Clears the internal state of the object. A new search is now possible.
186 : 	*
187 : 	* @return {DFS} A reference to this DFS object.
188 : 	*/
189 : 	clear() {
190 : 
191 : 		this.found = false;
192 : 
193 : 		this._route.clear();
194 : 		this._visited.clear();
195 : 		this._spanningTree.clear();
196 : 
197 : 		return this;
198 : 
199 : 	}
200 : 
201 : }
202 : 
203 : export { DFS };