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)?