CODEWITHSUNDEEP
rparent-childigraph
Jonas Schnidrig
Jonas Schnidrig

Reputation: 149

R find all paths from all children to all parents

Working in energy systems, I'm trying to identify all routes from the parents to the children, represented in the graph below using R.
I already found the pretty useful library igraph, but am not able to achieve my target.
I'm a newbie to graph theory, therefore please be generous with me when using the wrong terminology.

I'm seeking results such as
1 -> 2 -> 3
1 -> 2 -> 4
5 -> 4
4 -> 6 -> 4

Where I can identify the parents: 1,5,4 and the "last children" 3,4

library(igraph)
df <- data.frame(c(1,2,2,5,6,4),c(2,3,4,4,4,6))
df_graph <- graph_from_data_frame(df)
plot(df_graph)

Graph from chunk above

Upvotes: 1

Views: 391

Answers (2)

clp
clp

Reputation: 1528

Instead of talking about fathers, children and ends, use

  • sources, vertices without incoming edges.
  • sinks, vertices without outgoing edges.
  • and detect and remove loops manually.

Try this.

library(igraph)
g <- graph(c(1,2, 2,3, 2,4, 5,4, 6,4), directed=TRUE)
stopifnot(length(feedback_arc_set(g)) == 0)
sinks   <- V(g)[degree(g, mode = 'out')==0]
sources <- V(g)[degree(g, mode = 'in') ==0]
res <- c()
for (i in seq_along(sources) ){
  res <- append(res, all_simple_paths(g, sources[i], sinks, mode="out"))
}
res

Upvotes: 0

Szabolcs
Szabolcs

Reputation: 25703

You can use all_simple_paths to find all paths from a vertex to a set of other vertices. For example, the following finds all paths from 1 to 3 or 4.

> all_simple_paths(df_graph, "1", c("3", "4"))
[[1]]
+ 3/6 vertices, named, from 11c31e4:
[1] 1 2 4

[[2]]
+ 3/6 vertices, named, from 11c31e4:
[1] 1 2 3

Note that since the graph was created from a dataframe, the vertices have string names that do not coincide with their index:

> V(df_graph)$name
[1] "1" "2" "5" "6" "4" "3"

This is why it was necessary to quote vertex names. If we were to pass in 3 instead of "3", it would be interpreted as the 3rd vertex, which is vertex "5". To avoid this inconvenience, you could use graph_from_edgelist(as.matrix(df)), which interprets the input as vertex IDs instead of vertex names.

Upvotes: 1

Related Questions