[GIS] 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.