Bug in BFS?

[apeano]

Hello,
it seems that the procedure never enters in the "allowTraversal" function. Thus, it loops forever in case of graphs with cycles.

I don't know very well PowerShell, however from a first insight it is weird that the $seen variable is initialized every time allowTraversal is called.

I used this patch:
$graph.getNeighbors($currentVertex).ForEach{ $nextVertex = $_ if (!$seen[$nextVertex.getKey()]) { "NOT SEEN: " + $nextVertex.getKey() $seen[$nextVertex.getKey()] = $true $vertexQueue.enqueue($nextVertex) } }

Cheers

[dfinke]

Probably. I didn't finish building this out.

[apeano]

Since you have helped me... I try to give back the favour...
This implementation works for me.
`
class GraphAlg {
[Object]breadthFirstSearch($graph, $startVertex) {
$graph.toString()
$startVertex.GetType()
$vertexQueue = New-Object Queue
$edgeQueue = New-Object Queue
# Do initial queue setup.
$vertexQueue.enqueue($startVertex)
$previousVertex = $null
$seen = @{}
$seen[$startVertex.getKey()] = $true

	# Traverse all vertices from the queue.
	while (!$vertexQueue.isEmpty()) {
		$currentVertex = $vertexQueue.dequeue()
					
		# Add all neighbors to the queue for future traversals.
		$graph.getNeighbors($currentVertex).ForEach{
			$nextVertex = $_
			if (!$seen[$nextVertex.getKey()]) {
				$seen[$nextVertex.getKey()] = $true
				$vertexQueue.enqueue($nextVertex)
				#this measures the depth of the node in the tree
				#$nextVertex.data = $currentVertex.data + 1
				$e = $currentVertex.findEdge($nextVertex)
				$edgeQueue.enqueue($e)
			}
		}
	}
	
	$edgeQueue.toString()
	return $edgeQueue
}

}
`

[dfinke]

Thank you! Would you like to try your hand at forking the code, adding this and doing a pull request (PR)?