making sense of bfs and dfs-CodePudding

I'm trying to make sense of the outputs of bfs and dfs. I have a mst of some 3d point clouds which i am performing registration on, from which I want to derive a sequence of pairwise registrations along the edges. These pairwise registrations rely on previous registrations starting from a seed subsample.

As such I am trying to get an ordered list of edges from a seed edge (or vertex) so that pairwise comparisons can be properly propagated through the tree.

I have been trying to use bfs and dfs but can't make sense of the outputs to construct my ordered edge list.

library(igraph)

edges <- data.frame(
  from = c(2,14,8,17,11,16,14,12,14,13,14,16,13,19,15,23,21,21,22,23,20,22),
  to   = c(1,1,2,2,3,3,4,5,5,6,7,8,9,10,11,13,16,18,18,18,19,20),
 dist  = c(1.7479352,4.1400081,0.9064689,0.5735992,0.7550112,1.3880579,1.6968155,
          1.0064647,2.7119138,2.4033570,3.7260517,1.1921137,2.0857017,0.2903520,
          1.4191598,0.6111305,1.5752026,1.3102844,0.5070067,0.6522495,0.3172266,
          0.6373009
))
g <- graph.data.frame(edges, directed = F)
plot(g)

https://i.stack.imgur.com/I5xd0.png

I then choose the seed as the pair with the largest distance between them and run bfs or dfs

seedPair <- edges[which.max(edges[,3]),1:2]
> seedPair
  row col
2  14   1

For simplicity I just directly input vertex 14 as the root

path <- bfs(g, root = 14, father = T, rank = T)
> path
$root
[1] 14

$mode
[1] "out"

$order
  23/23 vertices, named, from 192f5fa:
 [1] 20 19 22 10 18 23 21 13 16 6  9  8  3  2  11 17 1  15 14 4  5  7  12

$rank
 2 14  8 17 11 16 12 13 19 15 23 21 22 20  1  3  4  5  6  7  9 10 18 
14 19 12 16 15  9 23  8  2 18  6  7  3  1 17 13 20 21 10 22 11  4  5 

$father
  23/23 vertices, named, from 192f5fa:
 [1] 2  14 8  17 11 16 12 13 19 15 23 21 22 20 1  3  4  5  6  7  9  10 18

path <- dfs(g, root = 14, order = T, order.out = T, father = T)
> path
$root
[1] 13

$mode
[1] "out"

$order
  23/23 vertices, named, from 192f5fa:
 [1] 20 19 10 22 18 23 13 6  9  21 16 8  2  17 1  14 4  5  12 7  3  11 15

$order.out
  23/23 vertices, named, from 192f5fa:
 [1] 10 19 6  9  13 23 17 4  12 5  7  14 1  2  8  15 11 3  16 21 18 22 20

$father
  23/23 vertices, named, from 192f5fa:
 [1] 2  14 8  17 11 16 12 13 19 15 23 21 22 20 1  3  4  5  6  7  9  10 18

$dist
NULL

$neimode
[1] "out"

Looking at the mst, neither of these outputs make sense to me if I'm starting at vertex 14. dfs is more intuitive to me and is easier to follow the edge sequence, but I also don't understand why its returning the root as 13, but then actually starting at node 20.

I would very appreciate any help understanding these outputs, or alternative approaches to getting an ordered edge sequence from a seed location. Thanks!

CodePudding user response：

When I run.

edges <- data.frame(
  from = c(2,14,8,17,11,16,14,12,14,13,14,16,13,19,15,23,21,21,22,23,20,22),
  to   = c(1,1,2,2,3,3,4,5,5,6,7,8,9,10,11,13,16,18,18,18,19,20),
 dist  = c(1.7479352,4.1400081,0.9064689,0.5735992,0.7550112,1.3880579,1.6968155,
          1.0064647,2.7119138,2.4033570,3.7260517,1.1921137,2.0857017,0.2903520,
          1.4191598,0.6111305,1.5752026,1.3102844,0.5070067,0.6522495,0.3172266,
          0.6373009
))
g <- graph.data.frame(edges, directed = F)
V(g)$name <- seq(vcount(g))   # ! Reset node n to "n".
>g

The resulting graph is.

IGRAPH 902edcd UN-- 23 22 -- 
  attr: name (v/c), dist (e/n)
  edges from 902edcd (vertex names):
 [1] 1 --15 2 --15 1 --3  1 --4  5 --16 6 --16 2 --17 7 --18 2 --18 8 --19 2 --20 3 --6  8 --21 9 --22 5 --10 8 --11
[17] 6 --12 12--23 13--23 11--23 9 --14 13--14

Running dfs().

path <- dfs(g, root = 14, order = TRUE, order.out = TRUE, father = TRUE)
>path

This gives.

$root
[1] 13

$mode
[1] "out"

$order
  23/23 vertices, named, from e6365e8:
 [1] 14 9  22 13 23 11 8  19 21 12 6  3  1  4  15 2  17 18 7  20 16 5  10

$order.out
  23/23 vertices, named, from e6365e8:
 [1] 22 9  19 21 8  11 4  17 7  18 20 2  15 1  3  10 5  16 6  12 23 13 14

$father
  23/23 vertices, named, from e6365e8:
 [1] 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23

$dist
NULL

$neimode
[1] "out"

Which is different then the output in the question, The reason being the statement V(g)$name <- seq(vcount(g)). Without this statement V(g)[14] is 20, due to the data frame logic.

The following code implements a simple dfs() search.

visit <- function(g, v){
  if (length(visited)>0L && !visited[v]) {
    cat("order: ", v, '\n')
    visited[v] <<- 1L
    for (w in V(g)[.nei(v)]) visit(g, w)
    cat("order.out: ", v, '\n')
    }
  }
 
# Call dfs()
  visited <- rep(0L, gorder(g))
  visit(g, 14)

According to the docs, $order.out is a numeric vector, the vertex ids, in the order of the completion of their subtree. $order shows the vertex ids at entry.

Try a simple graph, like make_ring(10), to check the logic.

Hope this helps.