pgrouting no result // topology problem

Question

First of all, I am new to map making, and I am mostly relying on tutorials to learn. As part of a project, I am making an airway map using QGIS and I do it by uploading the points with lat/long thru a csv file, and then connect them thru Points2One plugin. After that, I used pgrouting to create topology and calculate shortest path with dijkstra. However, when input the start and end points for calculation, the pgr_dijkstra won't return anything unless I used the "source" and "target" points. Below is the route network:

If I use point 5 & 6, it will yield result since in the table, there are the source and target. but if I use 29 and 23, it won't give result.

Is pgr_djikstra supposed to work like that? Anything that I am doing wrong?

Answer 1

EDIT 3:
After a long discussion in the comments I reviewed my answer, taking the sample data and it´s upload into PostgreSQL from within QGIS into account. I deleted my EDIT 2 as it became useless.

The problem is that you initially run pgr_dijkstra on multilinestrings. Next to the topology (that you created), the basic geometric structure for any pgRouting function to run the way it should is to have a properly noded network, consisting of simple linestrings instead, defined by two nodes (-> source, target).

pgRouting has the built in pgr_nodeNetwork function to do just that for you (albeit with possible drawbacks, see EDIT 1). In order to get expected results:

• run data import: in the GUI, check the box 'Create single-part geometries instead of multi-part' to create the table yourtablename.
  Note: at this point you can also project your data into a CRS suitable for your region of interest, to have all further calculations and their outputs in meter instead of (decimal) degrees. This will affect the tolerance settings I used below.
• run pgr_nodeNetwork: create a noded network from your initial set of linestrings (Note: the function does not keep any attributes, it will add an old_id column instead to refer to your initial data!). Since your data is in EPSG:4326, use a low tolerance in degrees to treat nearby vertices as equal:
  SELECT pgr_nodeNetwork('<yourtablename>', 0.00001, 'id', 'geom');
• run pgr_createTopology: create the topology reference with the noded network table created above (usually called yourtablename_noded):
  SELECT pgr_createTopology('<yourtablename_noded>', 0.00001, 'geom');
• run pgr_dijkstra: calculate shortest path between nodes on the same noded network table yourtablename_noded.
  Note: you have to refer to the created vertice table yourtablename_noded_vertices_pgr for the start and end points of your desired route (e.g. visualize that table in QGIS and pick the source/target vertice ids to route from/to)!
  JOIN those with the yourtablename_noded table and the original table to get your route with combined columns:

SELECT route.*,
       original.*
FROM pgr_dijkstra(
        'SELECT id,
                old_id,
                source,
                target,
                ST_Length(geom) AS cost
         FROM <yourtablename_noded>',
         29, 96,
         FALSE
) AS route
JOIN <yourtablename_noded> AS edges
  ON route.edge = edges.id
JOIN <yourtablename> AS original
  ON original.id = edges.old_id;

EDIT 1:

As @dkastl pointed out, pgr_nodeNetwork does try to split the given network at every intersection found, which might be undesirable for many cases, e.g. where two lines visually intersect but thematically should be treated as not intersecting (consider bridges in road networks [thanks to @dkastl]).

The more general rule here should be to make sure the network you want to route on consists of simple linestrings with nodes only at desired intersections, and pgr_nodeNetwork being a tool to achieve that efficiently if no intersection restrictions occur.

Answer 2

I was having problems with pgr_nodenetwork, so I looked at the known issues. It seems that pgr_nodenetwork has not been working properly see here. To overcome these issues, I manually noded my network before running

drop table if exists in_edges_int;
create table in_edges_int as
select * from (
select a.id, b.id as int_id, (st_dump(st_intersection(a.geom,b.geom))).geom from in_edges a, in_edges b where a.id != b.id and st_intersects(a.geom,b.geom)) foo
where st_geometrytype(geom) = 'ST_LineString';

drop table if exists in_edges_split;

create table in_edges_split as
select a.id, (st_dump(st_split(st_segmentize(a.geom,1),st_union(b.geom)))).geom as geom 
from in_edges a, in_edges_int b where b.id = a.id and st_intersects(a.geom,b.geom) group by a.id;

insert into in_edges_split (id, geom) 
select id, geom from in_edges where not st_intersects(geom,(select st_union(geom) from in_edges_int));

You'll need to re-join any attributes you need after this as all your left with is id and geom columns (or you can add the columns you need into the queries above).