Multi-source Breadth First Search

[BrendanMartin]

I've been digging around BreadthFirstSearchAlgorithm and other algorithms to see what's possible, but I'm getting stuck trying to figure out if it's possible to initialize BFS with multiple roots, or if I need to implement my own solutions.

I thought it would work something like this:

        var q = new QuikGraph.Collections.Queue<int>();
        var colors = new Dictionary<int, GraphColor>();
        foreach (var root in _roots)
        {
            q.Enqueue(root);
            colors[root] = GraphColor.Gray;
        }

        _dfs = new BreadthFirstSearchAlgorithm<int, Edge>(_graph, q, colors);

But calling _dfs.Compute() still starts at one root.

Any help is appreciated.

EDIT: I did make a workaround, which uses a single root node with edges to the first node layer I want to start from. Then just run BFS from the single root node.

[KeRNeLith]

Hello @BrendanMartin, The BFS algorithm is the only one that is providing a queue in its constructor. You can push vertices into it before calling the Compute in order to control which vertex will be treated first. But note also that the behavior of the Compute is that it looks at graph roots and loop over those roots vertices to enqueue them. Here is the code of the BFS:

if (TryGetRootVertex(out TVertex rootVertex))
{
    AssertRootInGraph(rootVertex);

    // Enqueue select root only
    EnqueueRoot(rootVertex);
}
else
{
    // Enqueue roots
    foreach (TVertex root in VisitedGraph.Roots())
        EnqueueRoot(root);
}

The point here is that you can use the method Compute() which will end looping over your vertices push at construction and then all graph roots, or using the Compute(rootVertex) which will run with all vertices push at construction plus the root vertex.

Looking at this, I'm wondering if in the case the queue is not empty at construction then we only take the queue into account and not graph roots. I'm not sure. What's your feeling about this?

[KeRNeLith]

@BrendanMartin I'm closing the support request for now, feel free to reopen/open a new one if needed ;-)

[Looooong]

if (TryGetRootVertex(out TVertex rootVertex))
{
    AssertRootInGraph(rootVertex);

    // Enqueue select root only
    EnqueueRoot(rootVertex);
}
else
{
    // Enqueue roots
    foreach (TVertex root in VisitedGraph.Roots())
        EnqueueRoot(root);
}

I think this code need to be revised. In my case, I want the algorithm to only process the specified vertex queue and not the VisitedGraph.Roots()

if (TryGetRootVertex(out TVertex rootVertex))
{
    AssertRootInGraph(rootVertex);

    // Enqueue select root only
    EnqueueRoot(rootVertex);
}
else if (_vertexQueue.Count == 0) // <- Change to this
{
    // Enqueue roots
    foreach (TVertex root in VisitedGraph.Roots())
        EnqueueRoot(root);
}