R: Merging Parts of a Graph Together

Question

I am working with the R programming language.

I have the following "Tree" that depicts the results of a coin flipping game (start at 5 points, and 0.5 prob of +1 and 0.5 prob of -1 at each turn):

outcomes <- c(-1, 1)  

combinations <- expand.grid(rep(list(outcomes), 10))
colnames(combinations) <- paste("Turn", 1:10)

library(data.tree)

generate_tree <- function(node, depth, total) {
    if (depth == 0) {
        node$Set(total = total)
        return(node)
    } else {
        for (outcome in outcomes) {
            child <- node$AddChild(name = as.character(total + outcome), total = total + outcome)
            generate_tree(child, depth - 1, total + outcome)
        }
        return(node)
    }
}

root <- Node$new("Start", total = 5)

root <- generate_tree(root, 4, 5)

print(root, "total")

plot(root, "total")

My Question: Is it possible to reformat (i.e. merge) this graph such that at each turn, all "nodes" with the same "value" are collapsed into a single node? This would mean that at each turn, a given "value" could only appear once.

After reading the following references (How to collapse branches in a phylogenetic tree by the label in their nodes or leaves?, Plotting a tree - collapsing a vector of nodes) tried to do this with the following code:

collapse_nodes <- function(node) {
    if (node$isRoot) {
        return(node)
    } else {
        parent <- node$parent
        siblings <- parent$children
        same_value_siblings <- siblings[sapply(siblings, function(x) x$total == node$total)]
        if (length(same_value_siblings) > 1) {
            node$parent <- NULL
            parent$RemoveChild(node$name)
        }
        return(node)
    }
}
root <- Traverse(root, collapse_nodes, mode = "post-order")

print(root, "total")
plot(root, "total")

Unfortunately, I got the following error:

Error in Traverse(root, collapse_nodes, mode = "post-order") : 
  unused argument (mode = "post-order")

Can someone please suggest how to resolve this problem? Thanks!

Note: In the end, all nodes of the same color will merged into a single node - this is what I am trying to achieve:

Answer 1

I guess you can use igraph like below

library(igraph)

outcomes <- c(-1, 1)
start <- 5
depth <- 7

lvls <- paste0("L", seq(depth + 1), "_")
ps <- apply(
  expand.grid(rep(list(outcomes), depth)),
  1,
  \(x) path(paste0(lvls, c(start, start + cumsum(x)))),
  simplify = FALSE
)

vs <- unique(unlist(ps))
g <- make_empty_graph(n = length(vs)) %>%
  set_vertex_attr("name", value = vs) %>%
  Reduce(`+`, ps, init = .) %>%
  simplify() %>%
  set_vertex_attr("val", value = sub(".*_", "", names(V(.))))


lo <- layout_as_tree(g)
lo[, 1] <- ave(lo[, 1], lo[, 2], FUN = \(x) {
  l <- length(x)
  if (l == 1) 0 else seq(-l, l, length.out = l)
})

g %>%
  plot(
    layout = lo,
    vertex.label = V(.)$val,
    vertex.color = as.factor(V(.)$val)
  )

and the tree looks like this (the values are specified by colors)