search method

DFS search()

Executes the graph search. If the search was successful, {@link DFS#found} is set to true.

Implementation

DFS search() {
	// create a stack(LIFO) of edges, done via an array
	final stack = [];
	final outgoingEdges = <Edge>[];

	// create a dummy edge and put on the stack to begin the search
	final startEdge = Edge( source, source );

	stack.add( startEdge );

	// while there are edges in the stack keep searching
	while ( stack.isNotEmpty ) {
		// grab the next edge and remove it from the stack
		final nextEdge = stack.removeLast();

		// make a note of the parent of the node this edge points to
		_route[nextEdge.to] = nextEdge.from;

		// and mark it visited
		_visited.add( nextEdge.to );

		// expand spanning tree
		if ( nextEdge != startEdge ) {
			_spanningTree.add( nextEdge );
		}

		// if the target has been found the method can return success
		if ( nextEdge.to == target ) {
			found = true;
			return this;
		}

		// determine outgoing edges
		graph?.getEdgesOfNode( nextEdge.to, outgoingEdges );

		// push the edges leading from the node this edge points to onto the
		// stack (provided the edge does not point to a previously visited node)
		for ( int i = 0, l = outgoingEdges.length; i < l; i ++ ) {
			final edge = outgoingEdges[ i ];

			if ( _visited.contains( edge.to ) == false ) {
				stack.add( edge );
			}
		}
	}

	found = false;

	return this;
}