All Paths in Directed Tree Graph from Root to Leaves in Igraph R

All paths in directed tree graph from root to leaves in igraph R

Based on Gabor's comment:

all_simple_paths(g, from = root, to = leaves)

yields:

[[1]]
+ 3/5 vertices, named:
[1] A B C

[[2]]
+ 3/5 vertices, named:
[1] A B D

[[3]]
+ 3/5 vertices, named:
[1] A B E

[[4]]
+ 2/5 vertices, named:
[1] A C

How to get all leaf nodes from a directed subtree using igraph in R?

You can define a function f with distances() and degree like below

f <- function(g, r) {
  names(V(g))[is.finite(distances(g, r, mode = "out")) & degree(g) == 1]
}

which gives

> f(g, "B")
[1] "K" "L" "M" "N" "O"

Determine source vertices and find all paths to a target vertex

This question is highly related to All paths in directed tree graph from root to leaves in igraph R
. The basic methods are the same, but here paths are determined from several source vertices.

Calculate degree of vertices for incoming edges (mode == "in"). To identify source vertices, check if degree equals zero. Use the resulting logical vector to index vertices (V(g)[...]).

from <- V(g)[degree(g, v = V(g), mode = "in") == 0]
from
# + 2/10 vertices, named, from 6cff414:
# [1] k x

Loop over source vertices to find all simple paths from each source to "c":

lapply(from, function(v) all_simple_paths(g, from = v, to = "c")) 

# $k
# $k[[1]]
# + 5/10 vertices, named, from 6cff414:
# [1] k z d e c
# 
# $k[[2]]
# + 5/10 vertices, named, from 6cff414:
# [1] k z a b c
# 
# 
# $x
# $x[[1]]
# + 5/10 vertices, named, from 6cff414:
# [1] x z d e c
# 
# $x[[2]]
# + 5/10 vertices, named, from 6cff414:
# [1] x z a b c

---

OP has not provided any rule to distinguish between the two alternative paths for each source vertex.

igraph: tree graph where terminal (not root) nodes are at same level?

When counting the level from bottom to top, the solution becomes:

require(igraph)

tree2  <- make_tree(10, 3) + make_tree(10, 2)
tree3  <- set_edge_attr(tree2, name="weight", value=-1) # longest path = shortest negative
dist   <- (-distances(tree3, v=(V(tree3)), mode="out")) # matrix of VxV distances of shortest paths
layers <- apply(dist, 1, max)                           # max per row
layers <- max(layers) - layers                          # shift down

plot(tree3, layout=layout_with_sugiyama(tree3, layers=layers))

If the dist matrix does not fit in memory then a dfs() search must be done, calculating the layers.

R: How to traverse from root node to each leaf node in an iGraph data object and get the path?

How about

root <- "chamber"
leafnodes <- sapply(V(df.g), function(x) length(neighbors(df.g,x))==0 )
paths <- get.all.shortest.paths(df.g, V(df.g)[root], leafnodes)$res
sapply(paths, function(vs) paste(V(df.g)[vs]$name, collapse="->"))

This lists all the leaf nodes you can get to

# [1] "chamber->leak"            "chamber->process"         "chamber->found"          
# [4] "chamber->check->power"    "chamber->issue->customer" "chamber->check->customer"
# [7] "chamber->issue->wafer"    "chamber->issue->replaced"

Finding root vertices in largeish dataset in igraph on R

For any node, n, you can find the number of edges into the node using
neighbors(g, n, mode="in"). A node is an initial vertex if it does not have any edges coming into it. So you can just test all of the nodes for how many edges enter the node and select those for which the answer is zero.

Here is a simple example graph:

library(igraph)
set.seed(2017)
g = erdos.renyi.game(12, 20, type="gnm", directed=TRUE)
plot(g)

Now we can find the root nodes.

which(sapply(sapply(V(g), 
    function(x) neighbors(g,x, mode="in")), length) == 0)
[1] 1 2

This says that nodes 1 and 2 are sources.

Since you say that you are a beginner, let me explain this just a little.

function(x) neighbors(g,x, mode="in") is a function that takes a node as an argument and uses neighbors to return a list of nodes y that have a link from y to x (the parents of x).

sapply(V(g), function(x) neighbors(g,x, mode="in")) applies that function to all of the nodes in the graph, and so gives a list of the parents for every node. We are interested in the nodes that have no parents so we want the nodes for which the length of this list is zero. Thus, we apply length to the list of parents and check which lengths are zero.

R: get nodes from root to leaves of a tree model?

As MrFlick noted, you should provide a reproducible example.

This might get you started on how to find the path of a BinaryTree object of the party package:

library(data.tree)
library(party)

airq <- subset(airquality, !is.na(Ozone))
airct <- ctree(Ozone ~ ., data = airq, 
               controls = ctree_control(maxsurrogate = 3))

CreateNodeFromParty <- function(splitNode) {
  node <- Node$new(splitNode$nodeID,
                   weights = splitNode$weights,
                   criterion = splitNode$criterion,
                   psplit = splitNode$psplit)
  if (!splitNode$terminal) {
    node$AddChildNode( CreateNodeFromParty(splitNode$left) )
    node$AddChildNode( CreateNodeFromParty(splitNode$right) )
  }
  return (node)
}

tree <- CreateNodeFromParty(airct@tree)

tree

This will give you the data.tree structure:

      levelName
1 1            
2  ¦--2        
3  ¦   ¦--3    
4  ¦   °--4    
5  ¦       ¦--5
6  ¦       °--6
7  °--7        
8      ¦--8    
9      °--9  

To find a specific node, do:

tree$FindNode(6)$path

Which will give you:

[1] "1" "2" "4" "6"

---

Related Topics