0

In R, I need to get the number of layers below each node in a tree. If my data are:

from,to
A,Z
B,Z
C,A
D,A
E,A
F,D
G,D
H,G
I,C

The results should be:

A 3
B 0
C 1
D 2
E 0
F 0
G 1
H 0
I 0
Z 4

I've been trying to figure something out with data.tree but I can't seem to figure it out, and not sure what other packages would be helpful here. Any help would be much appreciated.

Aaron K.
  • 23
  • 1
  • 4
  • Can you describe the logic for going from input to output? I don't understand how you get "A 3, B 0" etc. – Phil Jan 07 '18 at 02:58
  • If you draw out the tree, it's the max number of levels below each node. B, E, F, H, I all have 0 other nodes pointing to them. For A, it has 3 children, and the path from A->D->G->H is the longest so it gets 3. The others would be A->E; A->C->I; and A->D->F. – Aaron K. Jan 07 '18 at 03:01
  • It appears that when you say from A to Z you interpret that as A in one step below Z. Is that correct? – G5W Jan 07 '18 at 03:03
  • Yes, that's correct. – Aaron K. Jan 07 '18 at 03:05
  • It might be something along that line, but that only counts the number of nodes pointed to a specific node and not the number of levels below each one. – Aaron K. Jan 07 '18 at 03:18

2 Answers2

2

With data.tree:

EdgeList <- read.table(text="from to
A Z
B Z 
C A
D A
E A
F D
G D
H G
I C",
header=TRUE)

library(data.tree)
dt <- FromDataFrameNetwork(EdgeList)

Either in tree format:

print(dt, lvls = function(node) node$height - 1)

This will print like this:

   levelName            lvls
1  Z                    4
2   ¦--A                3
3   ¦   ¦--C            1
4   ¦   ¦   °--I        0
5   ¦   ¦--D            2
6   ¦   ¦   ¦--F        0
7   ¦   ¦   °--G        1
8   ¦   ¦       °--H    0
9   ¦   °--E            0
10  °--B                0

Or in the format you requested

dt$Get("height") - 1

If you need it sorted in the original order, you can add a sorting variable to EdgeList.

Christoph Glur
  • 1,224
  • 6
  • 10
  • I like your answer, Could you you give me solution for this link https://stackoverflow.com/questions/52039222/how-to-implement-hierarchical-multilevel-datatable-in-javascript?noredirect=1#comment91031196_52039222 – Varun Sharma Aug 29 '18 at 04:17
1

You can get this using the igraph package. You can convert your edgelist to a graph and then compute the distances between nodes. You just want the maximum distance. 

## Your data
EdgeList = as.matrix(read.table(text="from to
A Z
B Z 
C A
D A
E A
F D
G D
H G
I C",
header=TRUE))

## convert to an igraph graph
library(igraph)
g = graph_from_edgelist(EdgeList)

## Make a function to compute the height of a node
height = function(v) {
    D = distances(g, to=v, mode="out")
    max(D[D != Inf])
}

## Apply it to all nodes
sapply(V(g), height)
A Z B C D E F G H I 
3 4 0 1 2 0 0 1 0 0

If you really want these in alphabetical order, you can order them with 

H = sapply(V(g), height)
H[order(names(H))]
G5W
  • 36,531
  • 10
  • 47
  • 80