BidirectionalGraph and BreadthFirstSearchAlgorithm

Topics: algorithm, bug
Jun 6, 2011 at 4:16 PM

When I'm running BreadthFirstSearchAlgorithm on BidirectionalGraph graph i have different results according to if i add 'back' edges. I need to find all 'reachable' verteices from a given. According to documentation of IUndirectedEdge I was constructing graph adding edges only when 'source' < 'target', but BFS where not founding paths to vertexes that are 'smaller' than root vertex. Here is code:

var edges = List<UndirectedEdge<int>>();

// filling edges

var graph = new BidirectionalGraph<int, UndirectedEdge<int>>(true);

graph.AddVerticesAndEdgeRange(edges);

var observer = new VertexDistanceRecorderObserver<int, UndirectedEdge<int>>(e => 1);
var algoritm = new BreadthFirstSearchAlgorithm<int, UndirectedEdge<int>>(clientGraph);
using (observer.Attach(algoritm))
{
  algoritm.Compute(clientID);
 }

Is it correct behaviour? If so, is there undirected implementation of IVertexListGraph in the library as BSF expects such graph?