On Fri, Aug 24, 2012 at 9:11 PM, Francis P. Boscoe
<fpb01 at health.state.ny.us> wrote:
Hi, I've been poking around igraph and spatgraphs but have not been able to find a sufficiently simple example to make sense of. Suppose I have three points A, B, and C. The path from A to B is 3 units, from B to C is 4 units, and from A to C is 8 units. Could someone provide a simple coding example showing that A-B-C represents the shortest path?
using igraph, it couldn't be much simpler:
#1 make a graph, giving a two-column matrix of FROM and TO node names:
> ABC = graph.edgelist(cbind(c("A","B","A"),c("B","C","C")))
#2 attach distances as weights:
> E(ABC)$weight = c(3,4,8)
#3 see what we got:
> ABC
Vertices: 3
Edges: 3
Directed: TRUE
Edges:
[0] 'A' -> 'B'
[1] 'B' -> 'C'
[2] 'A' -> 'C'
Note this is a Directed graph. There's no way back from B to A!
#4 shortest path from A to C:
get.shortest.paths(ABC,from="A",to="C")
[[1]] [1] 0 1 2 And since there might be more than one shortest path, the return is a list. Here it has one element, and the numbers are the indices of the nodes. Starting from zero[1]. This is computer science, after all. To get the nodes, index the V (vertices) function: > V(ABC)[get.shortest.paths(ABC,from="A",to="C")[[1]]] Vertex sequence: [1] "A" "B" "C" #5 just to check, lets set the distances to all 1 and see if the algorithm figures out the direct route is quicker: > E(ABC)$weight = c(1,1,1) > V(ABC)[get.shortest.paths(ABC,from="A",to="C")[[1]]] Vertex sequence: [1] "A" "C" Happy graphing! Barry [1] I think the zero indexing might be changing soon, or has changed... Recent igraphs might be different, but indexing the V function should still work.