 identify transitive root of trees by pairwise relations

Say I have two columns with pair-wise cover relations of tree nodes. How would I tidy my way to a mutate that identified the transitive root?

Here I've hard-coded the root:

``````library(tidyverse)

tribble(
~node, ~cover,
"a", "b",
"c", "b",
"b", "d",
"e", "f",
"f", "g"
) %>% mutate(
root = c(rep("d", 3), "g", "g")
)
#> # A tibble: 5 x 3
#>   node  cover root
#>   <chr> <chr> <chr>
#> 1 a     b     d
#> 2 c     b     d
#> 3 b     d     d
#> 4 e     f     g
#> 5 f     g     g
``````

Created on 2019-04-29 by the reprex package (v0.2.0).

That is, a < b, c < b, b < d, so, a,b,c < d, and e < f, f < g, so e,f < g.

Hey @pandagrrl! I think I mentioned DiagrammeR to you a while ago as a way to do networks and Gantt chartey sorts of visualisations, but I completely forgot that it also has a bunch of functionality built-in around actually working with graphs. For example, you can specify a graph in a tidy way like your specification:

http://rich-iannone.github.io/DiagrammeR/graph_creation.html

And then you can do a bunch of selections or traversals:

http://rich-iannone.github.io/DiagrammeR/selections.html

http://rich-iannone.github.io/DiagrammeR/traversals.html

I know that that's not a direct answer, but I think that if you take a broader look at what DiagrammeR has off-the-shelf, you might find it really useful Nice! I was just thinking there must be graph s out there that do this. Will take a look, cheers 1 Like

Did a deep dive of DiagrammeR and igraph, but still haven't found a solution.

Reassuring to find I'm not the only algebraist cross-over into rstats, though .

1 Like

Perhaps I should make this a directed graph problem. After all, separate trees are just disjoint connected graphs. Then I hopefully there'd be functions for calculating the distances between vertices. Then I could get the level of multiple roots. 1 Like I need a Hasse diagram! Now to see what format I need my data in.

Could you do something like:

``````library(tidyverse)

g <- tribble(
~node, ~cover,
"a", "b",
"c", "b",
"b", "d",
"e", "f",
"f", "g"
)

# identify roots and compute graph distances
roots <- setdiff(g\$cover, g\$node)
distances <- igraph::distances(igraph::graph_from_data_frame(g)) %>%
as_tibble()

# generate look-up table of roots
LUT <- data.frame(node = names(distances),
root = distances %>%
select(roots) %>%
apply(1, which.min) %>%
roots[.])

# join roots
left_join(g, LUT, by = "node")
``````
2 Likes

This topic was automatically closed 21 days after the last reply. New replies are no longer allowed.

If you have a query related to it or one of the replies, start a new topic and refer back with a link.