| /* ----------------------------------------------------------------------- *//** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * |
| *//* ----------------------------------------------------------------------- */ |
| |
| |
| DROP TABLE IF EXISTS vertex,"EDGE",edge_grp; |
| |
| CREATE TABLE vertex( |
| id INTEGER |
| ); |
| INSERT INTO vertex VALUES |
| (0), |
| (1), |
| (2), |
| (3), |
| (4), |
| (5), |
| (6), |
| (7), |
| (8), |
| (9), |
| (10), |
| (11) |
| ; |
| |
| CREATE TABLE "EDGE"( |
| "SRC" INTEGER, |
| dest INTEGER, |
| weight DOUBLE PRECISION |
| ); |
| INSERT INTO "EDGE" VALUES |
| (0, 5, 1), |
| (1, 0, 1), |
| (1, 3, 1), |
| (2, 6, 1), |
| (3, 4, 1), |
| (3, 5, 1), |
| (4, 2, 1), |
| (8, 9, 1), |
| (9, 10, 1), |
| (9, 11, 1), |
| (10, 8, 1) |
| ; |
| |
| CREATE TABLE edge_grp( |
| g1 INTEGER, |
| g2 TEXT, |
| "SRC" INTEGER, |
| dest INTEGER, |
| weight DOUBLE PRECISION |
| ); |
| INSERT INTO edge_grp VALUES |
| (100, 'a', 0, 5, 1), |
| (100, 'a', 1, 0, 1), |
| (100, 'a', 1, 3, 1), |
| (100, 'a', 2, 6, 1), |
| (100, 'a', 3, 4, 1), |
| (100, 'a', 3, 5, 1), |
| (100, 'a', 4, 2, 1), |
| (100, 'a', 8, 9, 1), |
| (100, 'a', 9, 10, 1), |
| (100, 'a', 9, 11, 1), |
| (100, 'a', 10, 8, 1), |
| (100, 'b', 0, 5, 1), |
| (100, 'b', 1, 0, 1), |
| (100, 'b', 1, 3, 1), |
| (100, 'b', 2, 6, 1), |
| (100, 'b', 3, 4, 1), |
| (100, 'b', 3, 5, 1), |
| (100, 'b', 4, 2, 1), |
| (100, 'b', 8, 9, 1), |
| (100, 'b', 9, 10, 1), |
| (100, 'b', 9, 11, 1), |
| (100, 'b', 10, 8, 1), |
| (202, 'c', 8, 9, 1), |
| (202, 'c', 9, 10, 1), |
| (202, 'c', 9, 11, 1), |
| (202, 'c', 10, 8, 1), |
| (NULL, 'b', 8, 9, 1), |
| (NULL, 'b', 9, 10, 1), |
| (NULL, 'b', 9, 11, 1), |
| (NULL, 'b', 10, 8, 1); |
| |
| --------------------- |
| -- Undirected Graph |
| --------------------- |
| -- Results to check against - uncomment if needed |
| -- -- source_vertex = 3 |
| -- DROP TABLE IF EXISTS out_actual; |
| -- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT); |
| -- INSERT INTO out_actual VALUES |
| -- (3,3,0,NULL), |
| -- (3,1,1,3), |
| -- (3,4,1,3), |
| -- (3,5,1,3), |
| -- (3,0,2,1), |
| -- (3,2,2,4), |
| -- (3,6,3,2) |
| -- ; |
| -- -- source_vertex = 7 |
| -- DROP TABLE IF EXISTS out_actual; |
| -- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT); |
| -- |
| -- -- source_vertex = 8 |
| -- DROP TABLE IF EXISTS out_actual; |
| -- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT); |
| -- INSERT INTO out_actual VALUES |
| -- (8,8,0,NULL), |
| -- (8,9,1,8), |
| -- (8,10,1,8), |
| -- (8,11,2,9) |
| -- ; |
| |
| -- Undirected graph |
| -- source_vertex = 3 |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',3,'out_frombfs'); |
| |
| SELECT assert( |
| (array_agg(id ORDER BY id) = ARRAY[1,4,5]::INT[]) |
| AND |
| (array_agg(parent ORDER BY id) = ARRAY[3,3,3]::INT[]), |
| 'Wrong output in graph (BFS)') |
| FROM out_frombfs WHERE dist = 1 GROUP BY dist; |
| |
| SELECT assert(max(dist) = 3, 'Wrong output in graph (BFS)') |
| FROM out_frombfs; |
| |
| -- source_vertex = 7 |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',7,'out_frombfs'); |
| |
| SELECT assert(COUNT(*) = 0, 'Wrong output in graph (BFS)') FROM out_frombfs; |
| |
| -- source_vertex = 8 |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',8,'out_frombfs',NULL,FALSE,NULL); |
| |
| SELECT assert(parent = 8, 'Wrong output in graph (BFS)') |
| FROM out_frombfs WHERE dist = 2 AND id = 10; |
| |
| ------------------- |
| -- Directed graph |
| ------------------- |
| -- Results to check against - uncomment if needed |
| |
| -- -- source_vertex = 3 |
| -- DROP TABLE IF EXISTS out_actual; |
| -- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT); |
| -- INSERT INTO out_actual VALUES |
| -- (3,3,0,NULL), |
| -- (3,4,1,3), |
| -- (3,5,1,3), |
| -- (3,2,2,4), |
| -- (3,6,3,2) |
| -- ; |
| -- -- source_vertex = 7 |
| -- DROP TABLE IF EXISTS out_actual; |
| -- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT); |
| -- -- source_vertex = 8 |
| -- DROP TABLE IF EXISTS out_actual; |
| -- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT); |
| -- (8, 8, 0, NULL), |
| -- (8, 9, 1, 8), |
| -- (8, 10, 2, 9), |
| -- (8, 11, 2, 9) |
| -- ; |
| |
| -- source_vertex = 3 |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex','id','"EDGE"','src="SRC",dest',3,'out_frombfs',NULL,TRUE,NULL); |
| |
| SELECT assert( |
| (array_agg(id ORDER BY id) = ARRAY[4,5]::INT[]) |
| AND |
| (array_agg(parent ORDER BY id) = ARRAY[3,3]::INT[]), |
| 'Wrong output in graph (BFS)') |
| FROM out_frombfs WHERE dist = 1 GROUP BY dist; |
| SELECT assert(COUNT(*) = 5, 'Wrong output in graph (BFS)') FROM out_frombfs; |
| |
| -- source_vertex = 7 |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex','id','"EDGE"','src="SRC",dest',7,'out_frombfs',NULL,TRUE,NULL); |
| |
| SELECT assert(COUNT(*) = 0, 'Wrong output in graph (BFS)') FROM out_frombfs; |
| |
| -- source_vertex = 8 |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',8,'out_frombfs',NULL,TRUE); |
| |
| SELECT assert(COUNT(*) = 2, 'Wrong output in graph (BFS)') |
| FROM out_frombfs WHERE dist = 2; |
| |
| ----------------------- |
| -- max_distance check |
| ----------------------- |
| -- source_vertex = 3 |
| -- Undirected graph |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex','id','"EDGE"','src="SRC",dest',3,'out_frombfs',2,FALSE); |
| |
| SELECT assert(MAX(dist) = 2 AND COUNT(*) = 6, |
| 'Wrong output in graph (BFS)') FROM out_frombfs; |
| |
| -- Directed graph |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',3,'out_frombfs',2,TRUE); |
| |
| SELECT assert(MAX(dist) = 2 AND COUNT(*) = 4, |
| 'Wrong output in graph (BFS)') FROM out_frombfs; |
| |
| --------------------- |
| -- Grouping columns |
| --------------------- |
| -- -- source_vertex = 3 |
| -- -- Undirected graph |
| -- DROP TABLE IF EXISTS out_actual; |
| -- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT); |
| -- INSERT INTO out_actual VALUES |
| -- (3,100,'a',3,0,NULL), |
| -- (3,100,'a',1,1,3), |
| -- (3,100,'a',4,1,3), |
| -- (3,100,'a',5,1,3), |
| -- (3,100,'a',0,2,1), |
| -- (3,100,'a',2,2,4), |
| -- (3,100,'a',6,3,2), |
| -- (3,100,'b',3,0,NULL), |
| -- (3,100,'b',1,1,3), |
| -- (3,100,'b',4,1,3), |
| -- (3,100,'b',5,1,3), |
| -- (3,100,'b',0,2,1), |
| -- (3,100,'b',2,2,4), |
| -- (3,100,'b',6,3,2) |
| -- ; |
| |
| DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary; |
| SELECT graph_bfs('vertex',NULL,'edge_grp','src="SRC"',3,'out_frombfs',NULL,NULL,'g1,g2'); |
| |
| SELECT assert( COUNT(*) = 14,'Wrong output in graph (BFS)') FROM out_frombfs; |
| SELECT assert(COUNT(*) = 7, |
| 'Wrong output in graph (BFS)') FROM out_frombfs WHERE g2 = 'a' |
| ; |
| SELECT assert( |
| array_agg(id ORDER BY id) = ARRAY[0,2]::INT[] |
| AND |
| array_agg(parent ORDER BY id) = ARRAY[1,4]::INT[], |
| 'Wrong output in graph (BFS)') |
| FROM out_frombfs WHERE dist = 2 AND g1 = 100 AND g2 = 'a' |
| ; |
| SELECT assert( |
| array_agg(id ORDER BY id) = ARRAY[0,2]::INT[] |
| AND |
| array_agg(parent ORDER BY id) = ARRAY[1,4]::INT[], |
| 'Wrong output in graph (BFS)') |
| FROM out_frombfs WHERE dist = 2 AND g1 = 100 AND g2 = 'b' |
| ; |
| SELECT assert(MIN(g1) = 100 AND MAX(g1) = 100, |
| 'Wrong output in graph (BFS)') FROM out_frombfs GROUP BY g1,g2 |
| ; |
| |
| -- Test for common column names in vertex and edge tables |
| DROP TABLE IF EXISTS out, out_summary; |
| ALTER TABLE vertex RENAME COLUMN id TO "SRC"; |
| |
| SELECT graph_bfs('vertex','"SRC"','edge_grp','src="SRC"',3,'out',NULL,NULL,'g1'); |
| SELECT * FROM out; |
| |
| DROP TABLE IF EXISTS out, out_summary; |
| ALTER TABLE vertex RENAME COLUMN "SRC" TO dest; |
| |
| SELECT graph_bfs('vertex','dest','edge_grp','src="SRC"',3,'out',NULL,NULL,'g1'); |
| SELECT * FROM out; |
| |
| ALTER TABLE vertex RENAME COLUMN dest TO id; |
| |
| -- Test for bigint columns |
| CREATE TABLE v2 AS SELECT id::bigint FROM vertex; |
| CREATE TABLE e2 AS SELECT "SRC"::bigint, dest::bigint, weight FROM "EDGE"; |
| |
| DROP TABLE IF EXISTS pg_temp.out2, pg_temp.out2_summary; |
| SELECT graph_bfs('v2',NULL,'e2','src="SRC"',3,'pg_temp.out2'); |
| SELECT count(*) from pg_temp.out2; |
| SELECT * from pg_temp.out2_summary; |
| |
| -- Test for infinite paths |
| DROP TABLE IF EXISTS out, out_summary, out_path; |
| DELETE FROM "EDGE" WHERE dest = 7; |
| |
| SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',3,'out'); |
| |
| SELECT assert(count(*) = 0, 'Null parent in the out table') |
| FROM (SELECT * FROM out WHERE parent IS NULL)q1; |
