Understanding LightGraph's depth-first search

Specific Domains Graphs
1

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

image
image503×520 14 KB

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
2

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.

3

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