# Understanding LightGraph's depth-first search

Hello everyone,

I want to use the depth-first search functionality offered by LightGraphs.jl. However, I don’t seem to understand the results given by the `dfs_parents` function.

I wrote a simple example

``````using LightGraphs, GraphPlot
g = double_binary_tree(3)
gplothtml(g, nodelabel=vertices(g))
``````

``````julia> p = dfs_parents(g, 6)
14-element Array{Int64,1}:
3
1
6
2
2
6
3
1
8
8
9
9
10
10
``````

I don’t understand this output or how to use it. I was actually expecting each node of the graph `g` to be visited once. Can somebody help me understand this result?

1 Like

This function is deprecated in favor of `LightGraphs.Traversals.parents`, but these are the parents of each vertex.

So the parent of vertex 1 on your graph is `p[1]` which is 3. The parent of vertex seven is `p[7]` which is 3. These are the parents relative to your starting vertex 6, of course. They would be different with a different second argument.

What I’m trying to do is to traverse the tree starting from the leaves and ending at a given node, e.g. 1 in the graph above. I found that this is called postorder in the context of directed trees. I was hoping that LightGraph’s depth-first search could help me accomplish this, but I haven’t figured out how. Do you know if there is a way to achieve this?

I managed to do this using the AbstractTrees.jl package using the `PostOrderDFS` function. This is the output i get:

``````julia> print_tree(root)
1
├─ 2
│  ├─ 4
│  └─ 5
├─ 3
│  ├─ 6
│  └─ 7
└─ 8
├─ 9
│  ├─ 11
│  └─ 12
└─ 10
├─ 13
└─ 14

julia> sched =  [node.id for node in PostOrderDFS(root)]
14-element Array{Int64,1}:
4
5
2
6
7
3
11
12
9
13
14
10
8
1
``````

Would this be possible to do with LightGraphs.jl?

1 Like