I am trying to port code from python NetworkX to R igraph. In NetworkX there is a function with the name has_path that finds if two vertices have a path. I want to find in an efficient way all the vertices of a graph that don't have an edge between them but they have a path.
Does igraph has "has_path" function?
Viewed 51
2 Answers
I think you can use the code below to check if there is a path from vertex V1 to V2 (the graph can be directed or undirected)
c(!is.infinite(distances(g, V1, V2, mode = "out")))
If you need to check this repeatedly in an undirected graph, simply break it into connected components and check if both vertices are within the same component. This will be very efficient, as the components need to be found only once.
See the components function. It gives you a membership vector. You need to check if the position corresponding to the two vertices has the same value (same component index).
If the graph is directed, the simplest solution is the one posted by @ThomasIsCoding. This is perfectly fine for a one-time check. Speeding up repeated checks is more trouble and warrants its own question.
Related