Skip to content

Instantly share code, notes, and snippets.

@ImreSamu

ImreSamu/walking_tree_sql_final.log

Created July 28, 2023 00:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ImreSamu/cdd9afed6106366296622b10c0d44be2 to your computer and use it in GitHub Desktop.
Save ImreSamu/cdd9afed6106366296622b10c0d44be2 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
walking_tree_sql_final.log
-----
-----
-- original code: http://web.archive.org/web/20111006010109/http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html
----
----
DROP TABLE IF EXISTS network;
DROP TABLE
Time: 5.564 ms
BEGIN;
BEGIN
Time: 0.123 ms
CREATE TABLE network ( segment geometry, id integer primary key);
CREATE TABLE
Time: 1.564 ms
INSERT INTO network VALUES ('LINESTRING( 1 1, 0 0)', 1);
INSERT 0 1
Time: 11.178 ms
INSERT INTO network VALUES ('LINESTRING( 2 1, 1 1)', 2);
INSERT 0 1
Time: 0.238 ms
INSERT INTO network VALUES ('LINESTRING( 1 2, 1 1)', 3);
INSERT 0 1
Time: 0.218 ms
INSERT INTO network VALUES ('LINESTRING( 3 1, 2 1)', 4);
INSERT 0 1
Time: 0.171 ms
INSERT INTO network VALUES ('LINESTRING( 3 2, 2 1)', 5);
INSERT 0 1
Time: 0.165 ms
INSERT INTO network VALUES ('LINESTRING( 2 3, 1 2)', 6);
INSERT 0 1
Time: 0.124 ms
INSERT INTO network VALUES ('LINESTRING( 1 3, 1 2)', 7);
INSERT 0 1
Time: 0.118 ms
INSERT INTO network VALUES ('LINESTRING( 4 2, 3 2)', 8);
INSERT 0 1
Time: 0.148 ms
INSERT INTO network VALUES ('LINESTRING( 3 4, 2 3)', 9);
INSERT 0 1
Time: 0.130 ms
INSERT INTO network VALUES ('LINESTRING( 2 4, 2 3)', 10);
INSERT 0 1
Time: 0.133 ms
INSERT INTO network VALUES ('LINESTRING( 1 4, 1 3)', 11);
INSERT 0 1
Time: 0.129 ms
INSERT INTO network VALUES ('LINESTRING( 4 3, 4 2)', 12);
INSERT 0 1
Time: 0.125 ms
INSERT INTO network VALUES ('LINESTRING( 4 4, 3 4)', 13);
INSERT 0 1
Time: 0.116 ms
-- add some extra edges to make it interesting
INSERT INTO network VALUES ('LINESTRING( 1 1, 1 0)', 14);
INSERT 0 1
Time: 0.140 ms
INSERT INTO network VALUES ('LINESTRING( 1 1, 0 1)', 15);
INSERT 0 1
Time: 0.125 ms
INSERT INTO network VALUES ('LINESTRING( 1 0, 0 0)', 16);
INSERT 0 1
Time: 0.159 ms
INSERT INTO network VALUES ('LINESTRING( 0 1, 0 0)', 17);
INSERT 0 1
Time: 0.130 ms
INSERT INTO network VALUES ('LINESTRING( 0 0, -1 -1)', 18);
INSERT 0 1
Time: 0.128 ms
INSERT INTO network VALUES ('LINESTRING(-1 -1, -2 -2)', 19);
INSERT 0 1
Time: 0.130 ms
INSERT INTO network VALUES ('LINESTRING( 1 0, 5 0)', 20);
INSERT 0 1
Time: 0.122 ms
ALTER TABLE network ADD COLUMN "source" integer;
ALTER TABLE
Time: 0.221 ms
ALTER TABLE network ADD COLUMN "target" integer;
ALTER TABLE
Time: 0.143 ms
ALTER TABLE network ADD COLUMN cost float;
ALTER TABLE
Time: 0.146 ms
UPDATE network SET cost = ST_Length(segment);
UPDATE 20
Time: 0.324 ms
CREATE INDEX network_gix ON network USING GIST (segment);
CREATE INDEX
Time: 0.639 ms
COMMIT;
COMMIT
Time: 1.490 ms
VACUUM FULL ANALYZE network;
VACUUM
Time: 209.545 ms
-- enable pgrouting : https://pgrouting.org/
CREATE EXTENSION IF NOT EXISTS PGROUTING ;
psql:code/walking_tree_sql_final.sql:44: NOTICE: extension "pgrouting" already exists, skipping
CREATE EXTENSION
Time: 0.442 ms
-- Builds a network topology based on the geometry information.
-- https://docs.pgrouting.org/latest/en/pgr_createTopology.html
SELECT pgr_createTopology('network', 0.000001, 'segment', 'id');
psql:code/walking_tree_sql_final.sql:47: NOTICE: PROCESSING:
psql:code/walking_tree_sql_final.sql:47: NOTICE: pgr_createTopology('network', 1e-06, 'segment', 'id', 'source', 'target', rows_where := 'true', clean := f)
psql:code/walking_tree_sql_final.sql:47: NOTICE: Performing checks, please wait .....
psql:code/walking_tree_sql_final.sql:47: NOTICE: Creating Topology, Please wait...
psql:code/walking_tree_sql_final.sql:47: NOTICE: -------------> TOPOLOGY CREATED FOR 20 edges
psql:code/walking_tree_sql_final.sql:47: NOTICE: Rows with NULL geometry or NULL id: 0
psql:code/walking_tree_sql_final.sql:47: NOTICE: Vertices table for table public.network is: public.network_vertices_pgr
psql:code/walking_tree_sql_final.sql:47: NOTICE: ----------------------------------------------
+--------------------+
| pgr_createtopology |
+--------------------+
| OK |
+--------------------+
(1 row)
Time: 70.875 ms
-- Vertices table for table public.network is: public.network_vertices_pgr
-- analyze the network table
SELECT pgr_analyzeGraph('network', 0.000001, the_geom := 'segment', id := 'id');
psql:code/walking_tree_sql_final.sql:51: NOTICE: PROCESSING:
psql:code/walking_tree_sql_final.sql:51: NOTICE: pgr_analyzeGraph('network',1e-06,'segment','id','source','target','true')
psql:code/walking_tree_sql_final.sql:51: NOTICE: Performing checks, please wait ...
psql:code/walking_tree_sql_final.sql:51: NOTICE: Analyzing for dead ends. Please wait...
psql:code/walking_tree_sql_final.sql:51: NOTICE: Analyzing for gaps. Please wait...
psql:code/walking_tree_sql_final.sql:51: NOTICE: Analyzing for isolated edges. Please wait...
psql:code/walking_tree_sql_final.sql:51: NOTICE: Analyzing for ring geometries. Please wait...
psql:code/walking_tree_sql_final.sql:51: NOTICE: Analyzing for intersections. Please wait...
psql:code/walking_tree_sql_final.sql:51: NOTICE: ANALYSIS RESULTS FOR SELECTED EDGES:
psql:code/walking_tree_sql_final.sql:51: NOTICE: Isolated segments: 0
psql:code/walking_tree_sql_final.sql:51: NOTICE: Dead ends: 7
psql:code/walking_tree_sql_final.sql:51: NOTICE: Potential gaps found near dead ends: 0
psql:code/walking_tree_sql_final.sql:51: NOTICE: Intersections detected: 0
psql:code/walking_tree_sql_final.sql:51: NOTICE: Ring geometries: 0
+------------------+
| pgr_analyzegraph |
+------------------+
| OK |
+------------------+
(1 row)
Time: 36.972 ms
-- the new network table
\d+ network
Table "public.network"
+---------+------------------+-----------+----------+---------+---------+-------------+--------------+-------------+
| Column | Type | Collation | Nullable | Default | Storage | Compression | Stats target | Description |
+---------+------------------+-----------+----------+---------+---------+-------------+--------------+-------------+
| segment | geometry | | | | main | | | |
| id | integer | | not null | | plain | | | |
| source | integer | | | | plain | | | |
| target | integer | | | | plain | | | |
| cost | double precision | | | | plain | | | |
+---------+------------------+-----------+----------+---------+---------+-------------+--------------+-------------+
Indexes:
"network_pkey" PRIMARY KEY, btree (id)
"network_gix" gist (segment)
"network_source_idx" btree (source)
"network_target_idx" btree (target)
Access method: heap
select * from network;
+------------------------------------------------------------------------------------+----+--------+--------+--------------------+
| segment | id | source | target | cost |
+------------------------------------------------------------------------------------+----+--------+--------+--------------------+
| 010200000002000000000000000000F03F000000000000F03F00000000000000000000000000000000 | 1 | 1 | 2 | 1.4142135623730951 |
| 0102000000020000000000000000000040000000000000F03F000000000000F03F000000000000F03F | 2 | 3 | 1 | 1 |
| 010200000002000000000000000000F03F0000000000000040000000000000F03F000000000000F03F | 3 | 4 | 1 | 1 |
| 0102000000020000000000000000000840000000000000F03F0000000000000040000000000000F03F | 4 | 5 | 3 | 1 |
| 010200000002000000000000000000084000000000000000400000000000000040000000000000F03F | 5 | 6 | 3 | 1.4142135623730951 |
| 01020000000200000000000000000000400000000000000840000000000000F03F0000000000000040 | 6 | 7 | 4 | 1.4142135623730951 |
| 010200000002000000000000000000F03F0000000000000840000000000000F03F0000000000000040 | 7 | 8 | 4 | 1 |
| 0102000000020000000000000000001040000000000000004000000000000008400000000000000040 | 8 | 9 | 6 | 1 |
| 0102000000020000000000000000000840000000000000104000000000000000400000000000000840 | 9 | 10 | 7 | 1.4142135623730951 |
| 0102000000020000000000000000000040000000000000104000000000000000400000000000000840 | 10 | 11 | 7 | 1 |
| 010200000002000000000000000000F03F0000000000001040000000000000F03F0000000000000840 | 11 | 12 | 8 | 1 |
| 0102000000020000000000000000001040000000000000084000000000000010400000000000000040 | 12 | 13 | 9 | 1 |
| 0102000000020000000000000000001040000000000000104000000000000008400000000000001040 | 13 | 14 | 10 | 1 |
| 010200000002000000000000000000F03F000000000000F03F000000000000F03F0000000000000000 | 14 | 1 | 15 | 1 |
| 010200000002000000000000000000F03F000000000000F03F0000000000000000000000000000F03F | 15 | 1 | 16 | 1 |
| 010200000002000000000000000000F03F000000000000000000000000000000000000000000000000 | 16 | 15 | 2 | 1 |
| 0102000000020000000000000000000000000000000000F03F00000000000000000000000000000000 | 17 | 16 | 2 | 1 |
| 01020000000200000000000000000000000000000000000000000000000000F0BF000000000000F0BF | 18 | 2 | 17 | 1.4142135623730951 |
| 010200000002000000000000000000F0BF000000000000F0BF00000000000000C000000000000000C0 | 19 | 17 | 18 | 1.4142135623730951 |
| 010200000002000000000000000000F03F000000000000000000000000000014400000000000000000 | 20 | 15 | 19 | 4 |
+------------------------------------------------------------------------------------+----+--------+--------+--------------------+
(20 rows)
Time: 0.308 ms
-- the new vertices table
\d+ network_vertices_pgr
Table "public.network_vertices_pgr"
+----------+-----------------+-----------+----------+--------------------------------------------------+---------+-------------+--------------+-------------+
| Column | Type | Collation | Nullable | Default | Storage | Compression | Stats target | Description |
+----------+-----------------+-----------+----------+--------------------------------------------------+---------+-------------+--------------+-------------+
| id | bigint | | not null | nextval('network_vertices_pgr_id_seq'::regclass) | plain | | | |
| cnt | integer | | | | plain | | | |
| chk | integer | | | | plain | | | |
| ein | integer | | | | plain | | | |
| eout | integer | | | | plain | | | |
| the_geom | geometry(Point) | | | | main | | | |
+----------+-----------------+-----------+----------+--------------------------------------------------+---------+-------------+--------------+-------------+
Indexes:
"network_vertices_pgr_pkey" PRIMARY KEY, btree (id)
"network_vertices_pgr_the_geom_idx" gist (the_geom)
Access method: heap
select * from network_vertices_pgr;
+----+-----+-----+-----+------+--------------------------------------------+
| id | cnt | chk | ein | eout | the_geom |
+----+-----+-----+-----+------+--------------------------------------------+
| 1 | 5 | 0 | | | 0101000000000000000000F03F000000000000F03F |
| 2 | 4 | 0 | | | 010100000000000000000000000000000000000000 |
| 3 | 3 | 0 | | | 01010000000000000000000040000000000000F03F |
| 4 | 3 | 0 | | | 0101000000000000000000F03F0000000000000040 |
| 5 | 1 | 0 | | | 01010000000000000000000840000000000000F03F |
| 6 | 2 | 0 | | | 010100000000000000000008400000000000000040 |
| 7 | 3 | 0 | | | 010100000000000000000000400000000000000840 |
| 8 | 2 | 0 | | | 0101000000000000000000F03F0000000000000840 |
| 9 | 2 | 0 | | | 010100000000000000000010400000000000000040 |
| 10 | 2 | 0 | | | 010100000000000000000008400000000000001040 |
| 11 | 1 | 0 | | | 010100000000000000000000400000000000001040 |
| 12 | 1 | 0 | | | 0101000000000000000000F03F0000000000001040 |
| 13 | 1 | 0 | | | 010100000000000000000010400000000000000840 |
| 14 | 1 | 0 | | | 010100000000000000000010400000000000001040 |
| 15 | 3 | 0 | | | 0101000000000000000000F03F0000000000000000 |
| 16 | 2 | 0 | | | 01010000000000000000000000000000000000F03F |
| 17 | 2 | 0 | | | 0101000000000000000000F0BF000000000000F0BF |
| 18 | 1 | 0 | | | 010100000000000000000000C000000000000000C0 |
| 19 | 1 | 0 | | | 010100000000000000000014400000000000000000 |
+----+-----+-----+-----+------+--------------------------------------------+
(19 rows)
Time: 0.266 ms
-----------------------------------
-- This code essentially finds all paths in the network
-- that start from the edge with id = 6 and end at a node that has no outgoing edges (end node).
-- It avoids cycles by not including an edge in a path if it is already in the path.
-- This code uses a recursive common table expression (CTE) to perform the path search.
-- The recursion is done by joining the paths generated
-- so far with the edges in the network based on the end node of the path
-- and the start node of the edge.
-----------------------------------
--
-- Start a recursive CTE (Common Table Expression)
WITH RECURSIVE paths(path, last_node) AS (
-- Initial selection for the recursive CTE ------
-- The initial path is an array with a single element, the start node's id
-- The last_node is the end node of the edge with the start node's id
SELECT ARRAY[id] AS path, target AS last_node
FROM network
WHERE id = 6 -- Select the edge with id = 6 as the start edge
UNION ALL -- Union to append following results to the initial selection
-- Recursive part of the CTE -------
-- Build the path by appending the current edge id to the existing path,
-- and update the last node to the end node of the current edge
SELECT p.path || ARRAY[e.id], e.target
FROM network e
INNER JOIN paths p ON e.source = p.last_node -- Join with the previous paths based on the last_node
WHERE NOT e.id = any( p.path ) -- Prevent cycles: Do not select an edge if its id is already in the path
)
-- Finally, select the paths
SELECT path
FROM paths
WHERE NOT EXISTS (
-- For each path, check if there exists an edge in the network starting from the path's last node
-- If such an edge exists, the path is not selected, because the path has not reached the end
SELECT 1
FROM network e
WHERE e.source = paths.last_node
);
+-------------------+
| path |
+-------------------+
| {6,3,14,20} |
| {6,3,1,18,19} |
| {6,3,14,16,18,19} |
| {6,3,15,17,18,19} |
+-------------------+
(4 rows)
Time: 0.666 ms
----------------------------------
---------------------------------------------------------
-- (pgrouting) pgr_KSP - K Shortest Path solution;
-- This script first creates a "ksp" table
-- to fetch the K shortest paths from a specific source to all other targets
-- in the network that are not sources.
-- From the "ksp": It then extracts each path, organizes the sequence of edges and nodes,
-- and presents the result in a structured way.
------------------------------------------------
-- Creating a 'ksp' table (K Shortest Paths)
drop table if exists ksp;
DROP TABLE
Time: 3.465 ms
create table ksp as
-- Selects the edge_id and source from the network table where id = 6,
-- and selects all targets from the network that are not sources
SELECT
tsource.edge_id as edge_id -- This is the id of the selected edge
, tsource.source as source -- This is the source node of the selected edge
, tx.target as target -- These are the target nodes which are not sources
, (pgr_KSP ( -- This is a pgRouting function to get the K shortest paths from source to target.
-- https://docs.pgrouting.org/latest/en/pgr_KSP.html
'SELECT id, source, target, cost FROM network' -- This is the SQL to generate the network graph
,tsource.source -- This is the source node of the selected edge
,tx.target -- These are the target nodes which are not sources
,999999999 -- This is the maximum number of paths to return
,directed:=true -- This is a pgRouting function to indicate that the graph is directed
)).*
FROM
(
-- This subquery selects the edge with id = 6 as the source edge
select id as edge_id, source from network where id = 6 ) as tsource
,(
-- This subquery selects all targets that are not sources
SELECT target
FROM network
EXCEPT
SELECT source
FROM network
) tx
;
SELECT 25
Time: 5.708 ms
-- examine ksp
select * from ksp;
+---------+--------+--------+-----+---------+----------+------+------+--------------------+--------------------+
| edge_id | source | target | seq | path_id | path_seq | node | edge | cost | agg_cost |
+---------+--------+--------+-----+---------+----------+------+------+--------------------+--------------------+
| 6 | 7 | 19 | 1 | 1 | 1 | 7 | 6 | 1.4142135623730951 | 0 |
| 6 | 7 | 19 | 2 | 1 | 2 | 4 | 3 | 1 | 1.4142135623730951 |
| 6 | 7 | 19 | 3 | 1 | 3 | 1 | 14 | 1 | 2.414213562373095 |
| 6 | 7 | 19 | 4 | 1 | 4 | 15 | 20 | 4 | 3.414213562373095 |
| 6 | 7 | 19 | 5 | 1 | 5 | 19 | -1 | 0 | 7.414213562373095 |
| 6 | 7 | 18 | 1 | 1 | 1 | 7 | 6 | 1.4142135623730951 | 0 |
| 6 | 7 | 18 | 2 | 1 | 2 | 4 | 3 | 1 | 1.4142135623730951 |
| 6 | 7 | 18 | 3 | 1 | 3 | 1 | 1 | 1.4142135623730951 | 2.414213562373095 |
| 6 | 7 | 18 | 4 | 1 | 4 | 2 | 18 | 1.4142135623730951 | 3.82842712474619 |
| 6 | 7 | 18 | 5 | 1 | 5 | 17 | 19 | 1.4142135623730951 | 5.242640687119285 |
| 6 | 7 | 18 | 6 | 1 | 6 | 18 | -1 | 0 | 6.65685424949238 |
| 6 | 7 | 18 | 7 | 2 | 1 | 7 | 6 | 1.4142135623730951 | 0 |
| 6 | 7 | 18 | 8 | 2 | 2 | 4 | 3 | 1 | 1.4142135623730951 |
| 6 | 7 | 18 | 9 | 2 | 3 | 1 | 14 | 1 | 2.414213562373095 |
| 6 | 7 | 18 | 10 | 2 | 4 | 15 | 16 | 1 | 3.414213562373095 |
| 6 | 7 | 18 | 11 | 2 | 5 | 2 | 18 | 1.4142135623730951 | 4.414213562373095 |
| 6 | 7 | 18 | 12 | 2 | 6 | 17 | 19 | 1.4142135623730951 | 5.82842712474619 |
| 6 | 7 | 18 | 13 | 2 | 7 | 18 | -1 | 0 | 7.242640687119285 |
| 6 | 7 | 18 | 14 | 3 | 1 | 7 | 6 | 1.4142135623730951 | 0 |
| 6 | 7 | 18 | 15 | 3 | 2 | 4 | 3 | 1 | 1.4142135623730951 |
| 6 | 7 | 18 | 16 | 3 | 3 | 1 | 15 | 1 | 2.414213562373095 |
| 6 | 7 | 18 | 17 | 3 | 4 | 16 | 17 | 1 | 3.414213562373095 |
| 6 | 7 | 18 | 18 | 3 | 5 | 2 | 18 | 1.4142135623730951 | 4.414213562373095 |
| 6 | 7 | 18 | 19 | 3 | 6 | 17 | 19 | 1.4142135623730951 | 5.82842712474619 |
| 6 | 7 | 18 | 20 | 3 | 7 | 18 | -1 | 0 | 7.242640687119285 |
+---------+--------+--------+-----+---------+----------+------+------+--------------------+--------------------+
(25 rows)
Time: 0.387 ms
-- Now the final edges and nodes :
select edge_id -- Selects edge_id
,source -- Selects source
,target -- Selects target
,path_id -- Selects path_id
-- Aggregates all edges from 'ksp' in the order of their sequence, excluding edge = -1
,array_agg(edge order by path_seq ) FILTER (Where edge != -1 ) as edges
-- Aggregates all nodes from 'ksp' in the order of their sequence
,array_agg(node order by path_seq ) as nodes
from ksp
group by edge_id,source,target, path_id
order by edge_id,source,target, path_id
;
+---------+--------+--------+---------+-------------------+--------------------+
| edge_id | source | target | path_id | edges | nodes |
+---------+--------+--------+---------+-------------------+--------------------+
| 6 | 7 | 18 | 1 | {6,3,1,18,19} | {7,4,1,2,17,18} |
| 6 | 7 | 18 | 2 | {6,3,14,16,18,19} | {7,4,1,15,2,17,18} |
| 6 | 7 | 18 | 3 | {6,3,15,17,18,19} | {7,4,1,16,2,17,18} |
| 6 | 7 | 19 | 1 | {6,3,14,20} | {7,4,1,15,19} |
+---------+--------+--------+---------+-------------------+--------------------+
(4 rows)
Time: 0.480 ms
Raw
walking_tree_sql_final.sql
-----
-----
-- original code: http://web.archive.org/web/20111006010109/http://blog.cleverelephant.ca/2010/07/network-walking-in-postgis.html
----
----
DROP TABLE IF EXISTS network;
BEGIN;
CREATE TABLE network ( segment geometry, id integer primary key);
INSERT INTO network VALUES ('LINESTRING( 1 1, 0 0)', 1);
INSERT INTO network VALUES ('LINESTRING( 2 1, 1 1)', 2);
INSERT INTO network VALUES ('LINESTRING( 1 2, 1 1)', 3);
INSERT INTO network VALUES ('LINESTRING( 3 1, 2 1)', 4);
INSERT INTO network VALUES ('LINESTRING( 3 2, 2 1)', 5);
INSERT INTO network VALUES ('LINESTRING( 2 3, 1 2)', 6);
INSERT INTO network VALUES ('LINESTRING( 1 3, 1 2)', 7);
INSERT INTO network VALUES ('LINESTRING( 4 2, 3 2)', 8);
INSERT INTO network VALUES ('LINESTRING( 3 4, 2 3)', 9);
INSERT INTO network VALUES ('LINESTRING( 2 4, 2 3)', 10);
INSERT INTO network VALUES ('LINESTRING( 1 4, 1 3)', 11);
INSERT INTO network VALUES ('LINESTRING( 4 3, 4 2)', 12);
INSERT INTO network VALUES ('LINESTRING( 4 4, 3 4)', 13);
-- add some extra edges to make it interesting
INSERT INTO network VALUES ('LINESTRING( 1 1, 1 0)', 14);
INSERT INTO network VALUES ('LINESTRING( 1 1, 0 1)', 15);
INSERT INTO network VALUES ('LINESTRING( 1 0, 0 0)', 16);
INSERT INTO network VALUES ('LINESTRING( 0 1, 0 0)', 17);
INSERT INTO network VALUES ('LINESTRING( 0 0, -1 -1)', 18);
INSERT INTO network VALUES ('LINESTRING(-1 -1, -2 -2)', 19);
INSERT INTO network VALUES ('LINESTRING( 1 0, 5 0)', 20);
ALTER TABLE network ADD COLUMN "source" integer;
ALTER TABLE network ADD COLUMN "target" integer;
ALTER TABLE network ADD COLUMN cost float;
UPDATE network SET cost = ST_Length(segment);
CREATE INDEX network_gix ON network USING GIST (segment);
COMMIT;
VACUUM FULL ANALYZE network;
-- enable pgrouting : https://pgrouting.org/
CREATE EXTENSION IF NOT EXISTS PGROUTING ;
-- Builds a network topology based on the geometry information.
-- https://docs.pgrouting.org/latest/en/pgr_createTopology.html
SELECT pgr_createTopology('network', 0.000001, 'segment', 'id');
-- Vertices table for table public.network is: public.network_vertices_pgr
-- analyze the network table
SELECT pgr_analyzeGraph('network', 0.000001, the_geom := 'segment', id := 'id');
-- the new network table
\d+ network
select * from network;
-- the new vertices table
\d+ network_vertices_pgr
select * from network_vertices_pgr;
-----------------------------------
-- This code essentially finds all paths in the network
-- that start from the edge with id = 6 and end at a node that has no outgoing edges (end node).
-- It avoids cycles by not including an edge in a path if it is already in the path.
-- This code uses a recursive common table expression (CTE) to perform the path search.
-- The recursion is done by joining the paths generated
-- so far with the edges in the network based on the end node of the path
-- and the start node of the edge.
-----------------------------------
--
-- Start a recursive CTE (Common Table Expression)
WITH RECURSIVE paths(path, last_node) AS (
-- Initial selection for the recursive CTE ------
-- The initial path is an array with a single element, the start node's id
-- The last_node is the end node of the edge with the start node's id
SELECT ARRAY[id] AS path, target AS last_node
FROM network
WHERE id = 6 -- Select the edge with id = 6 as the start edge
UNION ALL -- Union to append following results to the initial selection
-- Recursive part of the CTE -------
-- Build the path by appending the current edge id to the existing path,
-- and update the last node to the end node of the current edge
SELECT p.path || ARRAY[e.id], e.target
FROM network e
INNER JOIN paths p ON e.source = p.last_node -- Join with the previous paths based on the last_node
WHERE NOT e.id = any( p.path ) -- Prevent cycles: Do not select an edge if its id is already in the path
)
-- Finally, select the paths
SELECT path
FROM paths
WHERE NOT EXISTS (
-- For each path, check if there exists an edge in the network starting from the path's last node
-- If such an edge exists, the path is not selected, because the path has not reached the end
SELECT 1
FROM network e
WHERE e.source = paths.last_node
);
----------------------------------
---------------------------------------------------------
-- (pgrouting) pgr_KSP - K Shortest Path solution;
-- This script first creates a "ksp" table
-- to fetch the K shortest paths from a specific source to all other targets
-- in the network that are not sources.
-- From the "ksp": It then extracts each path, organizes the sequence of edges and nodes,
-- and presents the result in a structured way.
------------------------------------------------
-- Creating a 'ksp' table (K Shortest Paths)
drop table if exists ksp;
create table ksp as
-- Selects the edge_id and source from the network table where id = 6,
-- and selects all targets from the network that are not sources
SELECT
tsource.edge_id as edge_id -- This is the id of the selected edge
, tsource.source as source -- This is the source node of the selected edge
, tx.target as target -- These are the target nodes which are not sources
, (pgr_KSP ( -- This is a pgRouting function to get the K shortest paths from source to target.
-- https://docs.pgrouting.org/latest/en/pgr_KSP.html
'SELECT id, source, target, cost FROM network' -- This is the SQL to generate the network graph
,tsource.source -- This is the source node of the selected edge
,tx.target -- These are the target nodes which are not sources
,999999999 -- This is the maximum number of paths to return
,directed:=true -- This is a pgRouting function to indicate that the graph is directed
)).*
FROM
(
-- This subquery selects the edge with id = 6 as the source edge
select id as edge_id, source from network where id = 6 ) as tsource
,(
-- This subquery selects all targets that are not sources
SELECT target
FROM network
EXCEPT
SELECT source
FROM network
) tx
;
-- examine ksp
select * from ksp;
-- Now the final edges and nodes :
select edge_id -- Selects edge_id
,source -- Selects source
,target -- Selects target
,path_id -- Selects path_id
-- Aggregates all edges from 'ksp' in the order of their sequence, excluding edge = -1
,array_agg(edge order by path_seq ) FILTER (Where edge != -1 ) as edges
-- Aggregates all nodes from 'ksp' in the order of their sequence
,array_agg(node order by path_seq ) as nodes
from ksp
group by edge_id,source,target, path_id
order by edge_id,source,target, path_id
;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment