Handling parallels after getting a path (pgr_ksp focus) - pgRouting/pgrouting GitHub Wiki
The drawing
Data
drop table if exists parallel;
CREATE TABLE parallel (
id serial,
source integer,
target integer,
cost double precision,
reverse_cost double precision,
x1 double precision,
y1 double precision,
x2 double precision,
y2 double precision,
the_geom geometry
);
INSERT INTO parallel (x1,y1,x2,y2)
VALUES (1,0,1,1),(1,1,1,3),(1,1,1,3),(1,1,1,3),(1,3,1,4),(1,1,-1,1),(-1,1,-1,3),(-1,3,1,3);
UPDATE parallel SET the_geom = ST_makeline(ST_point(x1,y1),ST_point(x2,y2));
UPDATE parallel SET the_geom = ST_makeline(ARRAY[ST_point(1,1),ST_point(0,2),ST_point(1,3)]) WHERE id = 3;
UPDATE parallel SET the_geom = ST_makeline(ARRAY[ST_point(1,1),ST_point(2,1),ST_point(2,3),ST_point(1,3)])
WHERE id = 4;
UPDATE parallel SET cost = ST_length(the_geom), reverse_cost = ST_length(the_geom);
SELECT pgr_createTopology('parallel',0.001);
pgr_ksp results
We ignore the costs because we want all the parallels
select seq, id1 as route, id2 as node, id3 as edge into routes
from pgr_ksp('select id, source, target, cost, reverse_cost from parallel',
1, 4, 3);
select * from routes;
seq | route | node | edge
-----+-------+------+------
0 | 0 | 1 | 1
1 | 0 | 2 | 2
2 | 0 | 3 | 5
3 | 0 | 4 | -1
4 | 1 | 1 | 1
5 | 1 | 2 | 6
6 | 1 | 5 | 7
7 | 1 | 6 | 8
8 | 1 | 3 | 5
9 | 1 | 4 | -1
(10 rows)
But we want the parallels.. lets see the parallels. We need an aggregate function:
CREATE AGGREGATE array_accum (anyelement)
(
sfunc = array_append,
stype = anyarray,
initcond = '{}'
);
Now lets generate a table.
select distinct seq,route,source,target, array_accum(id) as edges into paths
from (select seq, route, source, target
from parallel, routes where id = edge) as r
join parallel using (source, target)
group by seq,route,source,target order by seq;
ksp_test=# select * from paths;
seq | route | source | target | edges
-----+-------+--------+--------+---------
0 | 0 | 1 | 2 | {1}
1 | 0 | 2 | 3 | {2,3,4}
2 | 0 | 3 | 4 | {5}
4 | 1 | 1 | 2 | {1}
5 | 1 | 2 | 5 | {6}
6 | 1 | 5 | 6 | {7}
7 | 1 | 6 | 3 | {8}
8 | 1 | 3 | 4 | {5}
Functions
To generate a table with all the combinations for parallel routes: We need some aggregate functions:
create or replace function multiply( integer, integer )
returns integer as
$$
select $1 * $2;
$$
language sql stable;
create aggregate prod(integer)
(
sfunc = multiply,
stype = integer,
initcond = 1
);
And a function that "expands" the table
CREATE OR REPLACE function expand_parallel_edge_paths(tab text)
returns TABLE (
seq INTEGER,
route INTEGER,
source INTEGER, target INTEGER, -- this ones are not really needed
edge INTEGER ) AS
$body$
DECLARE
nroutes INTEGER;
newroutes INTEGER;
rec record;
seq2 INTEGER := 1;
rnum INTEGER := 0;
BEGIN -- get the number of distinct routes
execute 'select count(DISTINCT route) from ' || tab INTO nroutes;
FOR i IN 0..nroutes-1
LOOP
-- compute the number of new routes this route will expand into
-- this is the product of the lengths of the edges array for each route
execute 'select prod(array_length(edges, 1))-1 from '
|| quote_ident(tab) || ' where route=' || i INTO newroutes;
-- now we generate the number of new routes for this route
-- by repeatedly listing the route and swapping out the parallel edges
FOR j IN 0..newroutes
LOOP
-- query the specific route
FOR rec IN execute 'select * from ' || quote_ident(tab) ||' where route=' || i
|| ' order by seq'
LOOP
seq := seq2;
route := rnum;
source := rec.source;
target := rec.target;
-- using module arithmetic iterate through the various edge choices
edge := rec.edges[(j % (array_length(rec.edges, 1)))+1];
-- return a new record
RETURN next;
seq2 := seq2 + 1; -- increment the record count
END LOOP;
seq := seq2;
route := rnum;
source := rec.target;
target := -1;
edge := -1;
RETURN next; -- Insert the ending record of the route
seq2 := seq2 + 1;
rnum := rnum + 1; -- increment the route count
END LOOP;
END LOOP;
END;
$body$
language plpgsql volatile strict cost 100 rows 100;
Test it
select * from expand_parallel_edge_paths( 'paths' );
seq | route | source | target | edge
-----+-------+--------+--------+------
1 | 0 | 1 | 2 | 1
2 | 0 | 2 | 3 | 2
3 | 0 | 3 | 4 | 5
4 | 0 | 4 | -1 | -1
5 | 1 | 1 | 2 | 1
6 | 1 | 2 | 3 | 3
7 | 1 | 3 | 4 | 5
8 | 1 | 4 | -1 | -1
9 | 2 | 1 | 2 | 1
10 | 2 | 2 | 3 | 4
11 | 2 | 3 | 4 | 5
12 | 2 | 4 | -1 | -1
13 | 3 | 1 | 2 | 1
14 | 3 | 2 | 5 | 6
15 | 3 | 5 | 6 | 7
16 | 3 | 6 | 3 | 8
17 | 3 | 3 | 4 | 5
18 | 3 | 4 | -1 | -1
(18 rows)