search method

BFS search()

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

Implementation

BFS search() {
	// create a queue(FIFO) of edges, done via an array
	final queue = [];
	final outgoingEdges = <Edge>[];

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

	queue.add( startEdge );

	// mark the source node as visited
	_visited.add( source );

	// while there are edges in the queue keep searching
	while ( queue.isNotEmpty ) {
		// grab the first edge and remove it from the queue
		final nextEdge = queue.removeAt(0);

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

		// 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
		// queue (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 ) {
				queue.add( edge );

				// the node is marked as visited here, BEFORE it is examined,
				// because it ensures a maximum of N edges are ever placed in the queue rather than E edges.
				// (N = number of nodes, E = number of edges)
				_visited.add( edge.to );
			}
		}
	}

	found = false;
	return this;
}