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 :slightly_smiling_face:

Nice! I was just thinking there must be graph :package:s out there that do this. Will take a look, cheers :hugs:

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 :joy_cat:.

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. :thinking:

1 Like

:woman_facepalming: 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.