CODEWITHSUNDEEP
rigraph
gbt
gbt

Reputation: 809

Is R IGraph computing undirected shortest path in directed network?

there is something that i'm missing about IGraph shortest paths computation.

suppose I generate a network (find somewhere in stackoverflow) and perform simple computations:

library(igraph);
relations <- data.frame(from=c("Bob", "Cecil", "Cecil", "David", "David", "Esmeralda"), to=c("Alice", "Bob", "Alice", "Alice", "Bob", "Alice"));
g = simplify(graph_from_data_frame(d=relations, directed=T), remove.multiple = F, remove.loops = T);
#plotting the network in order to appreciate the directions of the edges
plot(g,edge.arrow.size=0.5);
#V(g)[5] is "Alice" which apparently should not be able to reach any node
print(all_shortest_paths(g,from=V(g)[5],to=V(g),mode="all")$res);

as you can see, the shortest paths found are:

> print(all_shortest_paths(g,from=V(g)[5],to=V(g),mode="all")$res);
[[1]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice Bob  

[[2]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice Cecil

[[3]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice David

[[4]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice     Esmeralda

[[5]]
+ 1/5 vertex, named, from 823c15d:
[1] Alice

what I'm expecting is that no shortest paths should be returned since Alice, in a directed graph, has no edges that are going out from itself. Is this due to the fact that, when I compute the shortest paths, I'm using the option:

mode="all"

and this, somehow, works even for directed graphs?

Of course, if I change the graph construction and set:

directed=F

i.e.

library(igraph);
relations <- data.frame(from=c("Bob", "Cecil", "Cecil", "David", "David", "Esmeralda"), to=c("Alice", "Bob", "Alice", "Alice", "Bob", "Alice"));

g = simplify(graph_from_data_frame(d=relations, directed=F), remove.multiple = F, remove.loops = T);

#plottin the network in order to appreciate the directions of the edges
plot(g,edge.arrow.size=0.5);

#V(g)[5] is "Alice" which apparently should not be able to reach any node
print(all_shortest_paths(g,from=V(g)[5],to=V(g),mode="all")$res);

the same results are returned.

What is going on? Am I just too tired to get this straight?

Upvotes: 3

Views: 415

Answers (1)

G5W
G5W

Reputation: 37661

That is just what mode="all" means - use all edges regardless of direction.

I will use a simpler graph to make it easy to see what is going on. 

rel2 <- data.frame(from=c("Bob", "Bob", "David"), 
        to=c("Alice", "Carol", "Carol"))
g = simplify(graph_from_data_frame(d=rel2, directed=T))
LO = layout_as_bipartite(g, types=c(F,F,T,T))
plot(g, layout=LO)

Simple directional graph

Now with your shortest path statement

print(all_shortest_paths(g,from=V(g)[3],to=V(g),mode="all")$res)
[[1]]
+ 2/4 vertices, named:
[1] Alice Bob  
[[2]]
+ 4/4 vertices, named:
[1] Alice Bob   Carol David
[[3]]
+ 1/4 vertex, named:
[1] Alice
[[4]]
+ 3/4 vertices, named:
[1] Alice Bob   Carol

We get all paths connecting Alice to another node, even though the edges go in opposite directions.

I think that what you want is:

print(all_shortest_paths(g,from=V(g)[3],to=V(g),mode="out")$res)
[[1]]
+ 1/4 vertex, named:

Which gives only the zero-length path from Alice to itself.

Just for completeness, 

print(all_shortest_paths(g,from=V(g)[3],to=V(g),mode="in")$res)
[[1]]
+ 2/4 vertices, named:
[1] Alice Bob  

[[2]]
+ 1/4 vertex, named:
[1] Alice

This follows paths using only incoming edges, so we get the path "from" Alice "to" Bob using the edge into Alice, but we get nothing else because there are no edges into Bob.

Upvotes: 1

Related Questions