convert a shapefile into graph with nodes and edges

Question

Is there a way to convert a shapefile into graph with nodes and edges(except networkx). I'm using qgis and I want to convert a road vector layer into a graph, so that I can use it to apply shortest path algorithms (astar). Please help me to find a solution.

Answer 1

Hopefully this is not too much off-topic, but here comes how you can do it with Spatialite. The theory of routing is the same for all the routing tools and if there is a way to do he same with QGIS the procedure will be very similar. I believe that my recipe can be used as is till populating the node_from and node_to columns.

Before starting take care that your shapefile is noded correctly so that end points and start points of lines match exactly. The idea is to add node_from and node_to colums to the shapefile and populate them with unique node IDs. Node IDs are taken from a temporary table that collects all the unique start and end points from the lines of the shapefile. Once the node_from and node_to columns have been filled the routable graph can be created with the Spatialite tool "virtual network" which can be used from command line or from Spatialite-gui.

I happened to find a SQL script that I have been using myself. I edited it a bit and I hope I did not introduce too many errors. For running the script save in on disk as "create_nodes.sql", run if from spatialite-gui or open a spatialite command window and execute with

spatialite> .read create_nodes.sql cp1252

-- Comments can be written 
-- by using this syntax
select datetime('now')||' begin';
CREATE TABLE nodes AS
SELECT ST_StartPoint(geometry) AS node_geometry
FROM lines
UNION
SELECT ST_EndPoint(geometry) AS node_geometry
FROM lines;
-- UNION takes care that from identical points
-- only one will be written into the node table
select datetime('now')||' nodes created';
alter table lines add column node_from;
alter table lines add column node_to;
select datetime('now')||' node_from and node_to columns added';
select RecoverGeometryColumn('nodes','node_geometry',4326,'POINT');
select datetime('now')|| ' geometryfield registered';
-- we told that column node_geometry contains points,
-- with SRID EPSG:4326
select CreateSpatialIndex('nodes','node_geometry');
select datetime('now')||' spatial index created';
-- spatial index is created and message printed on the screen
update lines set node_from =
(select rowid from "nodes"
where "nodes"."node_geometry"=StartPoint(lines.geometry) and
"nodes"."rowid" in
(select rowid from spatialindex where f_table_name='nodes'
and search_frame=StartPoint(lines.geometry)));
select datetime('now')||' node_from has been filled';
-- We wrote unique IDs of start points into the lines table
-- and we used spatial index for making it fast
update lines set node_to =
(select rowid from "nodes"
where "nodes"."node_geometry"=EndPoint(lines.geometry) and
"nodes"."rowid" in
(select rowid from spatialindex where f_table_name='nodes'
and search_frame=EndPoint(lines.geometry)));
select datetime('now')||' node_to has been filled';
-- Same thing that was done for start points but for end points this time
create table rings as
select * from lines
where node_from=node_to;
select datetime('now')||' ring ways copied';
-- We copied ways which have same node as start and end points
-- to a new table because Spatialite routing cannot handle them
-- and now we delete them
delete from lines where node_from=node_to;
select datetime('now')||' ring ways deleted';
select datetime('now')||' everything ready for building a graph';

I would recommend to use the spatialite_network utility for creating the graph because it gives good error messages if something fails. However, graph can also be created with GUI

A document about Spatialite routing is here http://www.gaia-gis.it/gaia-sins/Using-Routing.pdf.

Answer 2

The networkx library for python has two very nifty functions, read_shp() and write_shp(), which read an arbitrary lines shape file and then write two shapefiles, one of edges and one of nodes. Any line attributes are retained in the edges output file.

One thing that would be nice would be if I could figure out how to append the node ID information to the link objects...

Answer 3

I encountered the same problem, the same no-perfect-solution. So I wrote this https://github.com/caesar0301/python-s2g

Answer 4

Can't you just use the road graph plugin? As far as I'm aware, you can just use shapefiles for it.

Demo: Youtube Link