0

Currently, I am working on a project that involves NYC Taxi data, in which I am given where a person is picked up and dropped off in a network.

I am working with an ESRI shapefile, which I can load into R as an igraph object with the shp2graph package; I need to utilize Dijkstra's algorithm (or a similar shortest-path algorithm) to find the single shortest path between two given vertices. I thought that the get.shortest.paths() method of the igraph package would be my solution, but to my surprise, this calculates all shortest paths from a vertex to all others in a network.

To me, this seems like overkill, because I need only one single path between two specified nodes. I did some poking around online and in the igraph documentation, but all I can find are methods surrounding calculating many shortest paths from a given vertex to all others.

Due to how computationally expensive it would be to calculate every single shortest path from a vertex, and then just select one from the behemoth of a list, I'm looking for a way to utilize Dijkstra's algorithm between two specified vertices in a graph. Is there a way to do this in the igraph package, or if not, is there a good way to do this with a different package in R?

EDIT: In the end, I am hoping to look for a function that will take in the graph object and the ID of two vertices I wish to find the shortest path between, then return a list of paths/edges (or IDs) along that shortest path. This would help me to inspect each individual street along the shortest path between the two vertices.

EDIT: As an example of how I am currently using the function: path <- get.shortest.paths(NYCgraph, from=32, mode="out"). Something I would hope to find is path <- shortestPathFunction(NYCgraph, from=32, to=37) to arbitrary calculate a shortest path between vertex ID 32 and vertex ID 37 (two random street intersections in the network).

NelsonGon
  • 13,015
  • 7
  • 27
  • 57
Anthony Niemiec
  • 37
  • 3
  • 4
    When asking for help, you should include a simple [reproducible example](https://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example) with sample input and desired output that can be used to test and verify possible solutions. What parameters did you pass to `get.shortest.paths()` exactly? There is both a `from=` and `to=` parameter. – MrFlick Feb 12 '18 at 22:16
  • My mistake; I was asking for a general solution to how to pass two vertex ID's into a method that would return a list of routes between them (I'll update my post to ask this). In the shortest.paths() documentation, I see the get.shortest.paths() has a usage of: "get.shortest.paths(graph, from, mode = "all")." It is possible to append a "to=" parameter to this function? – Anthony Niemiec Feb 12 '18 at 22:22
  • Use `get.shortest.paths(NYCgraph, from=32, to=37)`. If that doesn't exist, what version if `igraph` are you using? The "current" name of the function is `shortest_paths()`. – MrFlick Feb 12 '18 at 22:37
  • You're exactly right - that's what I needed! As a side note, I realized that along the way to getting the igraph object, I had called a function wrong: for those who are curious, during the process of reading in an ESRI shapefile, you encounter a function nel2igraph; I had simply passed the wrong parameters to this, and my resulting NYCgraph object wasn't compatible with get.shortest.paths(). Thanks! – Anthony Niemiec Feb 13 '18 at 05:57
  • Don't edit your question to include an "answer." Just answer your own question as you've already done. This properly closes it out and let's the community vote on whether or not they agree. – MrFlick Feb 13 '18 at 15:02

1 Answers1

2

I found my issue, which occurred before I called get.shortest.paths(). For those who are curious on how to read in an ESRI shapefile, and find a single shortest path between two points (which was my dilemma):

myShapefile <- readOGR(dsn=".", layer="MyShapefileName") # i.e. "MyShapefileName.shp"
shpData <- readshpnw(myShapefile, ELComputed=TRUE)
igraphShpObject <- nel2igraph(shpData[[2]], shpData[[3]], weight=shpData[[4]])
testPath <- get.shortest.paths(igraphShpObject, from=42, to=52) # arbitrary nodes
testPath[1] # print the node IDs to the console

Furthermore, if one was interested in getting the ID of the edge connecting two nodes (perhaps from nodes in the testPath):

get.edge.ids(igraphShpObject, c(42,45) # arbitrary nodes 42 and 45

This indexing is the same as the indexing in shpData; for example, if you want to get the length of edge ID x, as found in get.edge.ids(), you may type shpData[[4]][x].

I hope these tidbits may be helpful to somebody in the future encountering the same problems! This method utilizes the shp2graph, rgdal, and igraph packages in R.

MrFlick
  • 195,160
  • 17
  • 277
  • 295
Anthony Niemiec
  • 37
  • 3