BreadthFirstSearchAlgorithm order of events?

Topics: algorithm, bug
Jan 16, 2008 at 4:59 AM
I'm not an expert in graph theory, but I am trying to use QuickGraph for my needs.

In the Visit(TVertex S) function
there is code
                    if (vColor == GraphColor.White)
                    {
                        OnTreeEdge(e);
                        VertexColors[v] = GraphColor.Gray;
                        OnDiscoverVertex(v);
                        this.vertexQueue.Push(v);
                    }

but I am wondering if it shouldn't be
                    if (vColor == GraphColor.White)
                    {
                        VertexColors[v] = GraphColor.Gray;
                        OnDiscoverVertex(v);
                        this.vertexQueue.Push(v);
                        OnTreeEdge(e);
                    }

I ask because I am using a VertexDistanceRecorderObserver while running the BFS

            BreadthFirstSearchAlgorithm<string, Edge<string>> bfs =
                new BreadthFirstSearchAlgorithm<string, Edge<string>>(_graph);
            VertexPredecessorRecorderObserver<string, Edge<string>> bObserver =
                new VertexPredecessorRecorderObserver<string, Edge<string>>();
 
            Dictionary<string, int> vertexDistance = new Dictionary<string, int>(_graph.VertexCount);
 
            VertexDistanceRecorderObserver<string, Edge<string>> dObserver =
                new VertexDistanceRecorderObserver<string, Edge<string>>(vertexDistance);
 
            bObserver.Attach(bfs);
            dObserver.Attach(bfs);
 
            string rootNode = "test"
            bfs.Compute(rootNode);
 
            foreach (string node in bObserver.VertexPredecessors.Keys)
            {
                Console.WriteLine("Distance From {0} to {1}: {2}", rootNode, node, dObserver.Distances[node]);
            }
 
            bObserver.Detach(bfs);
            dObserver.Detach(bfs);

and I was getting all the distances between the vertices as 0 which is wrong.

In the VertexDistanceRecorderObserver class, I found:
        private void DiscoverVertex(Object sender, VertexEventArgs<Vertex> args)
        {
            this.distances[args.Vertex] = 0;
        }
 
        private void TreeEdge(Object sender, EdgeEventArgs<Vertex,Edge> args)
        {
            this.distances[args.Edge.Target] = 
                this.distances[args.Edge.Source] + 1;
        }

And the distances were being set properly in the TreeEdge but were being almost immediately overwritten by the execution of DiscoverVertex delegate.

When I changed the order of the events being fired, my function worked as expected.

Can you confirm that what I am doing is correct or explain to me why I am wrong?

Thank you so much. I really love the library and it is making my job much easier. Thanks for sharing it.
-Chris
Coordinator
Jan 31, 2008 at 5:05 AM
The issue in the distance recorder observer, I should not use the vertex events for this observer. I've checked in a fix.