How to use `bfs_tree` and `dfs_tree` from `LightGraphs.jl`

Specific Domains Graphs
1

I’m trying to understand how to use bfs_tree and dfs_tree from 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.

using LightGraphs

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?

2

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 bfs and dfs. For e.g., random graphs g = SimpleGraph(20,100) the functions will return different bfs and dfs.

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).

1 Like
3

Thanks for the answer. @GunnarFarneback came up with this solution in Slack:

It looks like you can get a dfs traversal order with

topological_sort_by_dfs(dfs_tree(g,1))

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
    end
    return x
end
4

Have you tried https://github.com/JuliaCollections/AbstractTrees.jl ?

5

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.

6

You mean AbstractTrees.jl?

7

Yeah, currently I’m using AbstractTrees.jl’s PostOrderDFS function. I was just wondering if I could get the same functionality from LightGraphs.jl to get rid of AbstractTrees.jl.

8

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?

9

Initially, my issue was that I didn’t understand how to use bfs_tree() and 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 bfs_tree and 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.

2 Likes