Re: [jgrapht-users] Potential bug in BreadthFirstIterator?

[H.N. de R. <hnr...@gr...>]

On Sun, Feb 24, 2013 at 04:16:43PM -0800, Jack Gibson wrote:

Hi Jack,

> To illustrate the issue I create a graph that looks as follows (F is the root):
> 
> F -> A -> B -> C -> D -> E
> 
> Now when I traverse with BreadthFirstIterator I get following representation. Note that the result is not sorted correctly as the root is A and not F!!
> 
> Vertex A
>    Edge A -> B
> Vertex B
>    Edge B -> C
> Vertex C
>    Edge C -> D
> Vertex D
>    Edge D -> E
> Vertex E
> Vertex F
>    Edge F -> A

This is not an error. If you don't specify the start vertex, the
BreadthFirstIterator starts at an arbitrary vertex. Once it has visited all
vertices reachable from there, it will pick an arbitrary unvisited vertex
and start from there.

So your code could also have traversed as:
D->E->F; B->C; A

If you have sources in your graph and want to do a BFS from them, you'll
have to find them yourself and start BFS from there. Note that in this case
the iterator will not restart itself once it has visited all vertices
reachable from the provided start vertex.

Regards,
   Ernst

-- 
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org