How to flatten a hierarchical data structure given parent child relationships in R

Here is a function with while loop:

fun <- function(s){
  i <- 1
  while(i<=length(s)){
    if(any(s[[i]] %in% names(s)))
    {
      nms <- s[[i]]
      s[[i]] <- stack(s[nms])
      s[nms] <- NULL
    }
    else
      s[[i]] <- data.frame(values = NA, ind = s[[i]])
    i <- i+1
  }
  s
}

dplyr::bind_rows(fun(unstack(df)), .id = 'Level.01')[c(2:3,1)]
 values       ind Level.01
1  Apple     Fruit     Food
2 Banana     Fruit     Food
3   Pear     Fruit     Food
4 Carrot Vegetable     Food
5 Celery Vegetable     Food
6   <NA>      Bike Not Food
7   <NA>       Car Not Food

You could generalize this if you had more levels

I would think about it like a graph problem. There are 2 changes to make to the original data to fit this approach: switch the order of columns to show the hierarchical direction (parent to child), and add a top-level node (I'm calling it "Items") that links to the major groups (food & not food). You could probably do that second part programmatically but it seems like more of a pain than it's worth.

library(dplyr)

df <- tibble::tribble(
  ~Child,     ~Parent,
  "Fruit",      "Food",
  "Vegetable",      "Food",
  "Apple",     "Fruit",
  "Banana",     "Fruit",
  "Pear",     "Fruit",
  "Carrot", "Vegetable",
  "Celery", "Vegetable",
  "Bike",  "Not Food",
  "Car",  "Not Food"
) %>%
  select(Parent, Child) %>%
  add_row(Parent = "Items", Child = c("Food", "Not Food"))

The first method is with data.tree, which is designed to work with this type of data. It creates a tree representation, which you can then convert back to a data frame with one of a few shapes.

library(data.tree)

g1 <- FromDataFrameNetwork(df)
g1
#>             levelName
#> 1  Items             
#> 2   ¦--Food          
#> 3   ¦   ¦--Fruit     
#> 4   ¦   ¦   ¦--Apple 
#> 5   ¦   ¦   ¦--Banana
#> 6   ¦   ¦   °--Pear  
#> 7   ¦   °--Vegetable 
#> 8   ¦       ¦--Carrot
#> 9   ¦       °--Celery
#> 10  °--Not Food      
#> 11      ¦--Bike      
#> 12      °--Car
ToDataFrameTypeCol(g1)
#>   level_1  level_2   level_3 level_4
#> 1   Items     Food     Fruit   Apple
#> 2   Items     Food     Fruit  Banana
#> 3   Items     Food     Fruit    Pear
#> 4   Items     Food Vegetable  Carrot
#> 5   Items     Food Vegetable  Celery
#> 6   Items Not Food      Bike    <NA>
#> 7   Items Not Food       Car    <NA>

The second method is more convoluted and probably only makes sense if there are other graph operations you need to do. Make a graph with igraph, then get all the paths in the graph starting from the top node Items. That gives you a list of vertex objects; for each of those, extract IDs. One example of those is below.

library(igraph)
g2 <- graph_from_data_frame(df)
all_simple_paths(g2, from = "Items") %>%
  purrr::map(as_ids) %>%
  `[[`(4)
#> [1] "Items"  "Food"   "Fruit"  "Banana"

Create data frames from all those vectors, bind, and reshape to get one column per level.

all_simple_paths(g2, from = "Items") %>%
  purrr::map(as_ids) %>%
  purrr::map_dfr(tibble::enframe, .id = "row") %>%
  tidyr::pivot_wider(id_cols = row, names_prefix = "level_")
#> # A tibble: 11 × 5
#>    row   level_1 level_2  level_3   level_4
#>    <chr> <chr>   <chr>    <chr>     <chr>  
#>  1 1     Items   Food     <NA>      <NA>   
#>  2 2     Items   Food     Fruit     <NA>   
#>  3 3     Items   Food     Fruit     Apple  
#>  4 4     Items   Food     Fruit     Banana 
#>  5 5     Items   Food     Fruit     Pear   
#>  6 6     Items   Food     Vegetable <NA>   
#>  7 7     Items   Food     Vegetable Carrot 
#>  8 8     Items   Food     Vegetable Celery 
#>  9 9     Items   Not Food <NA>      <NA>   
#> 10 10    Items   Not Food Bike      <NA>   
#> 11 11    Items   Not Food Car       <NA>

In either case, drop the level 1 column if you don't actually want it.

In this special case you could get your desired result by doing some joining and binding:

library(dplyr)

df2 <- df %>% 
  inner_join(df, 
             by = c("Parent" = "Child"),
             suffix = c("", "_top")) 

df %>% 
  anti_join(df2) %>%
  select(Parent_top = Parent, Parent = Child) %>% 
  bind_rows(df2) %>%
  group_by(Parent_top, Parent) %>% 
  filter(!is.na(Child) | n() == 1) %>% 
  select(Level_01 = Parent_top, Level_02 = Parent, Level_03 = Child)

But I don't think that way is very stable for larger/other datasets. Perhaps just using a loop over this dataset gives you a better answer.