Re: [jgrapht-users] Potential bug in BreadthFirstIterator?
Brought to you by:
barak_naveh,
perfecthash
|
From: H.N. de R. <hnr...@gr...> - 2013-02-25 08:48:25
|
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 |