CODEWITHSUNDEEP
rtreedepth
Anita
Anita

Reputation: 789

R: depth minimum spanning tree

In question R: tree with overlapping strings I've asked to make a tree that looks like: 

V621   --> V62123  --> V6212355
    --> V621335 --> V62133526
    --> V6216 --> V62162
    --> V621213452
    --> V62126324

It works with the minimum spanning tree from the package igraph, But now I want to determine the depth of each element of that tree. How coudl I do this?

Upvotes: 2

Views: 715

Answers (1)

MrFlick
MrFlick

Reputation: 206401

If we borrow all the relevant code from the previous answer...

df <- read.table(text='verkoop          V621  
verkoopcode      V62123  
verkoopcodenaam  V6212355  
verkoopdatum     V621335  
verkoopdatumchar V62133526  
verkooppr        V6216  
verkoopprijs     V62162  
verkoopsafdeling V621213452  
verkoopsartikel  V62126324')
# use igraph package
require(igraph)
# create adjacency matrix 
adj <- nchar(sapply(df$V1, gsub, x=df$V1, replacement=''))
adj[!sapply(df$V1, grepl, x=df$V1)] <- 0
# name adjecency matrix 
colnames(adj) <- df$V2
# original graph
gr <- graph.adjacency(adj, mode='directed', weighted=TRUE)
layout(matrix(1:2, ncol=2))
plot(gr)
# minimum spanning tree 
mst <- minimum.spanning.tree(gr)

You can get the depth with

shortest.paths(mst, to="V621", weights=rep(1, ecount(mst)))
#            V621
# V621          0
# V62123        1
# V6212355      2
# V621335       1
# V62133526     2
# V6216         1
# V62162        2
# V621213452    1
# V62126324     1

Note that we have to adjust the weights because by default graph.adjacency used the values in adj as weights for the edges and really we only want to count each edge as one. You could have also done

gr <- graph.adjacency(adj>0, mode='directed', weighted=TRUE)
mst <- minimum.spanning.tree(gr)
shortest.paths(mst, to="V621")

to set all the default weights to 1.

This assumes you know taht "V621" is the root node. If you didn't know which was the root node, you could find it with

dx <-degree(mst, mode="out")
root <- names(dx)[dx==0]
shortest.paths(mst, to=root, weights=rep(1, ecount(mst)))

Upvotes: 3

Related Questions