How can I turn a vector layer into a graph G = (V, E)?

Question

I have a number of rail networks, in the form of shapefiles of the "line" type. I want to turn them into a more abstract graph format, i.e. the kind with vertices and edges, not chart-type graphs. Moreover I want these data to be usable outside my GIS programs, in Python. Basically what I want is to extract something along the lines of the TSPLIB format, except with only vertices and edges. For my immediate purposes, I don't even need weights or anything. Just the topology.

Is there any relatively pain-free way to do this in QGIS or GRASS? I haven't quite lucked out yet.

Answer 1

NetworkX ( A python module for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks ) has a read_shp() function which generates a graphs from shapefiles. You might want to check it out. Here's a short tutorial.

No TPSLIB export as far as I know but does support writing the graphs into formats like GML, GraphML, Pickle, adjacency lists, and GEXF to name a few. The full list of output formats can be found here. I hope this helps. Good luck.

Answer 2

To turn your lines into edges, and give them an id, you may want to use assign_vertex_id inside PostGIS in case your lines are in PostgreSQL/PostGIS. Using that, you will get a unique id for your rail network lines. To get the vertices i.e. start and end point of the lines you can simply add two extra columns for them and run a simple update to fill values in those columns.

I hope that helped! Merry xmas! ;)