0

I want to find the maximum number of nodes which can be reached from each node in a graph using igraph in R.

For example, I have the following graph:

IGRAPH fb9255f DN-- 4 3 -- + attr: name (v/c), X (e/l) + edges from fb9255f (vertex names): 1 1->2 2->3 2->4

Resulting graph

For node 1, for example, I would like to obtain the list of all the possible nodes reachable (not only using one hop) from it.

In this case, for node 1 it will be: [2,3,4]

I have read the igraph documentation, but I do not see any function that can help.

Any help will be appreciated. Thanks

Carlos

Carlos Borrego Iglesias
  • 1
  • 1

1 Answers1

1

You can compute this using the subcomponent function.

Since you do not provide any data, I will illustrate with an arbitrary example. 

## Example graph
library(igraph)
set.seed(123)
g = erdos.renyi.game(15, 0.15, directed = TRUE)
plot(g)

A directed graph

subcomponent gives you all of nodes that are reachable. Here, I am assuming that you are using directed graphs and you mean reachable by going forward along the directed edges. You can change this by altering the mode argument to subcomponent.

sort(subcomponent(g, 2, mode="out"))
+ 7/15 vertices:
[1]  2  5 10 12 13 14 15

If you just want the number of nodes that can be reached, just take the length

length(subcomponent(g, 2, mode="out"))
[1] 7
G5W
  • 36,531
  • 10
  • 47
  • 80
  • @ G5W: Is it possible to add a "degree" argument here? e.g. how many nodes can you reach from "2" having degree 0,1,2,3? – stats_noob Mar 01 '23 at 07:33
  • 1
    @stats_noob It would be easy to compute that with an extra line or so of code. Please ask this as a new question and refer to this one as context. If you direct me to your new question, I will answer there. – G5W Mar 01 '23 at 14:11
  • @ G5W: Thank you for your reply! I have created this new question here: https://stackoverflow.com/questions/75608018/r-all-nodes-of-degree-n-that-can-be-reached-from-some-node – stats_noob Mar 01 '23 at 19:15