I’m trying to understand how to use
LightGraphs.jl . They both return the same graph so I don’t know how to extract the actual order in which the nodes were visited.
g = double_binary_tree(4)
bfs = bfs_tree(g, 1)
dfs = dfs_tree(g, 1)
bfs == dfs
Can somebody show me an example of how to use these two functions?
These functions seemingly only return the final BFS/DFS trees but not the order in which nodes were visited. Since your input graph is already a tree, you get the same output for
dfs. For e.g., random graphs
g = SimpleGraph(20,100) the functions will return different
I do not know if
LightGraphs.jl has something built-in to output the traversal order. But you could copy/paste the functions from the source code and adapt them (e.g., with print functions).
Thanks for the answer. @GunnarFarneback came up with this solution in Slack:
It looks like you can get a dfs traversal order with
For bfs I don’t see anything in the sources but from the output of
bfs_tree it should be very easy to construct it. Maybe something like:
function bfs_traversal(g, s)
b = bfs_tree(g, s)
x = [s]
i = 1
while i <= length(x)
append!(x, neighbors(b, x[i]))
i += 1
Yes, and it works great! I was just looking if I could get rid of that dependency given that I’m using
LightGraphs.jl for other stuff.
Yeah, currently I’m using
PostOrderDFS function. I was just wondering if I could get the same functionality from
LightGraphs.jl to get rid of
Oh sorry that I suggested something that you are already doing. Anyways lets see if someone from the LightGraphs community can be of more use.
I see that you also poster in slack #graph channel. Have you tried the #help-desk channel also?
Initially, my issue was that I didn’t understand how to use
dfs_tree() functions. But the problem turned out to be that I didn’t understand what they are meant for. The conclusion is that
LightGraphs.jl doesn’t provide DFS and BFS traversal functionality (in the form of iterators) like
AbstractTrees.jl does. I’m happy with that response. @GunnarFarneback found a small hack of how to get these traversal orders using
LightGraphs.jl (posted above). Another approach is to copy/paste
dfs_tree and adapt them to my needs, as suggested by @mike_k.
Thanks for the
AbstractTrees.jl recommendation though. For now, I will keep this dependency in my code.