| /* ----------------------------------------------------------------------- *//** |
| * |
| * 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",out,out_summary,out_path, |
| vertex_alt,edge_alt,out_alt,out_alot_summary, |
| edge_gr,out_gr,out_gr_summary,out_gr_path, |
| edge_gr2, out_gr2, out_gr2_summary, |
| "edge_Q", "out_Q", "out_Q_summary", "out_Q_path"; |
| |
| CREATE TABLE vertex( |
| id INTEGER |
| ); |
| |
| CREATE TABLE "EDGE"( |
| src INTEGER, |
| dest INTEGER, |
| weight DOUBLE PRECISION |
| ); |
| |
| INSERT INTO vertex VALUES |
| (0), |
| (1), |
| (2), |
| (3), |
| (4), |
| (5), |
| (6), |
| (7) |
| ; |
| INSERT INTO "EDGE" VALUES |
| (0, 1, 1), |
| (0, 2, 1), |
| (0, 4, 10), |
| (1, 2, 2), |
| (1, 3, 10), |
| (2, 3, 1), |
| (2, 5, 1), |
| (2, 6, 3), |
| (3, 0, 1), |
| (4, 0, -2), |
| (5, 6, 1), |
| (6, 7, 1) |
| ; |
| |
| SELECT graph_sssp('vertex',NULL,'"EDGE"',NULL,0,'out'); |
| |
| SELECT * FROM out; |
| |
| SELECT assert(weight = 3, 'Wrong output in graph (SSSP)') |
| FROM out WHERE id = 6; |
| SELECT assert(parent = 5, 'Wrong parent in graph (SSSP)') |
| FROM out WHERE id = 6; |
| |
| SELECT graph_sssp_get_path('out',6,'out_path'); |
| |
| CREATE TABLE vertex_alt AS SELECT id AS v_id |
| FROM vertex; |
| CREATE TABLE edge_alt AS SELECT src AS e_src, dest, weight AS e_weight |
| FROM "EDGE"; |
| |
| SELECT graph_sssp('vertex_alt','v_id','edge_alt','src=e_src, weight=e_weight' |
| ,1,'out_alt'); |
| |
| SELECT * FROM out_alt; |
| |
| SELECT assert(e_weight = 4, 'Wrong output in graph (SSSP)') |
| FROM out_alt WHERE v_id = 6; |
| SELECT assert(parent = 5, 'Wrong parent in graph (SSSP)') |
| FROM out_alt WHERE v_id = 6; |
| |
| CREATE TABLE edge_gr AS |
| ( SELECT *, 0 AS grp FROM "EDGE" |
| UNION |
| SELECT *, 1 AS grp FROM "EDGE" WHERE src < 6 AND dest < 6 |
| UNION |
| SELECT *, 2 AS grp FROM "EDGE" WHERE src < 6 AND dest < 6 |
| ); |
| |
| INSERT INTO edge_gr VALUES |
| (7,NULL,NULL,1), |
| (4,0,-20,2); |
| |
| SELECT graph_sssp('vertex',NULL,'edge_gr',NULL,0,'out_gr','grp'); |
| |
| SELECT assert(weight = 3, 'Wrong output in graph (SSSP)') |
| FROM out_gr WHERE id = 6 AND grp = 0; |
| SELECT assert(parent = 5, 'Wrong parent in graph (SSSP)') |
| FROM out_gr WHERE id = 6 AND grp = 0; |
| |
| SELECT assert(weight = 2, 'Wrong output in graph (SSSP)') |
| FROM out_gr WHERE id = 5 AND grp = 1; |
| SELECT assert(parent = 2, 'Wrong parent in graph (SSSP)') |
| FROM out_gr WHERE id = 5 AND grp = 1; |
| |
| SELECT assert(weight = 'Infinity', 'Wrong output in graph (SSSP)') |
| FROM out_gr WHERE id = 7 AND grp = 1; |
| |
| SELECT graph_sssp_get_path('out_gr',5,'out_gr_path'); |
| |
| CREATE TABLE edge_gr2 AS |
| ( SELECT *, 0 AS grp1, 0 AS grp2 FROM "EDGE" |
| UNION |
| SELECT *, 1 AS grp1, 0 AS grp2 FROM "EDGE" WHERE src < 6 AND dest < 6 |
| UNION |
| SELECT *, 1 AS grp1, 1 AS grp2 FROM "EDGE" WHERE src < 6 AND dest < 6 |
| ); |
| |
| SELECT graph_sssp('vertex',NULL,'edge_gr2',NULL,0,'out_gr2','grp1,grp2'); |
| |
| SELECT assert(weight = 3, 'Wrong output in graph (SSSP)') |
| FROM out_gr2 WHERE id = 6 AND grp1 = 0 AND grp2 = 0; |
| SELECT assert(parent = 5, 'Wrong parent in graph (SSSP)') |
| FROM out_gr2 WHERE id = 6 AND grp1 = 0 AND grp2 = 0; |
| |
| CREATE TABLE "edge_Q" AS SELECT src, dest AS "dest_Q", weight FROM "EDGE"; |
| |
| SELECT graph_sssp('vertex','','"edge_Q"','dest="dest_Q"',0,'"out_Q"',''); |
| |
| SELECT * FROM "out_Q"; |
| SELECT * FROM "out_Q_summary"; |
| SELECT graph_sssp_get_path('"out_Q"',5,'"out_Q_path"'); |
| |
| SELECT * FROM "out_Q_path"; |
| |
| -- 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_sssp('vertex','src','edge_gr',NULL,0,'out','grp'); |
| SELECT * FROM out; |
| |
| DROP TABLE IF EXISTS out, out_summary; |
| ALTER TABLE vertex RENAME COLUMN src TO dest; |
| |
| SELECT graph_sssp('vertex','dest','edge_gr',NULL,0,'out','grp'); |
| SELECT * FROM out; |
| |
| ALTER TABLE vertex RENAME COLUMN dest TO id; |
| |
| -- Test for bigint columns |
| |
| CREATE TABLE v2 AS SELECT (id+992147483647)::bigint as id FROM vertex; |
| CREATE TABLE e2 AS SELECT (src+992147483647)::bigint as src, (dest+992147483647)::bigint as dest, weight FROM "EDGE"; |
| |
| DROP TABLE IF EXISTS pg_temp.out2, pg_temp.out2_summary, pg_temp.out2_path; |
| SELECT graph_sssp('v2',NULL,'e2',NULL,992147483647,'pg_temp.out2'); |
| SELECT count(*) from pg_temp.out2; |
| SELECT graph_sssp_get_path('pg_temp.out2',992147483652,'pg_temp.out2_path'); |
| |
| -- Test for infinite paths |
| DROP TABLE IF EXISTS out, out_summary, out_path; |
| DELETE FROM "EDGE" WHERE dest = 7; |
| |
| SELECT graph_sssp('vertex',NULL,'"EDGE"',NULL,0,'out'); |
| |
| SELECT assert(count(*) = 0, 'Null parent in the out table') FROM |
| (SELECT * FROM out WHERE parent IS NULL)q1; |
| |
| SELECT graph_sssp_get_path('out',5,'out_path'); |
| |
| -- Test for multiple column identifiers |
| -- The datasets have the columns doubled so that the same tests can be run on the output tables |
| |
| DROP TABLE IF EXISTS vertex_mult_sssp, edge_mult_sssp, edge_mult_sssp_gr2 CASCADE; |
| CREATE TABLE vertex_mult_sssp( |
| id1 INTEGER, |
| id2 INTEGER |
| ); |
| CREATE TABLE edge_mult_sssp( |
| src1 INTEGER, |
| dest1 INTEGER, |
| weight INTEGER, |
| src2 INTEGER, |
| dest2 INTEGER |
| ); |
| INSERT INTO vertex_mult_sssp VALUES |
| (0, 0), |
| (1, 1), |
| (2, 2), |
| (3, 3), |
| (4, 4), |
| (5, 5), |
| (6, 6); |
| INSERT INTO edge_mult_sssp VALUES |
| (0, 1, 1, 0, 1), |
| (0, 2, 1, 0, 2), |
| (0, 4, 10, 0, 4), |
| (1, 2, 2, 1, 2), |
| (1, 3, 10, 1, 3), |
| (2, 3, 1, 2, 3), |
| (2, 5, 1, 2, 5), |
| (2, 6, 3, 2, 6), |
| (3, 0, 1, 3, 0), |
| (4, 0, -2, 4, 0), |
| (5, 6, 1, 5, 6), |
| (6, 7, 1, 6, 7); |
| |
| CREATE TABLE edge_mult_sssp_gr2 AS |
| ( SELECT *, 0 AS grp1, 0 AS grp2 FROM edge_mult_sssp |
| UNION |
| SELECT *, 1 AS grp1, 0 AS grp2 FROM edge_mult_sssp WHERE src1 < 6 AND dest1 < 6 |
| UNION |
| SELECT *, 1 AS grp1, 1 AS grp2 FROM edge_mult_sssp WHERE src1 < 6 AND dest1 < 6 |
| ); |
| |
| DROP TABLE IF EXISTS sssp_mult_col_out; |
| DROP TABLE IF EXISTS sssp_mult_col_out_summary; |
| DROP TABLE IF EXISTS sssp_mult_col_out_path; |
| SELECT graph_sssp( |
| 'vertex_mult_sssp', -- Vertex table |
| '[id1,id2]', -- Vertex id column |
| 'edge_mult_sssp', -- edge_mult_sssp table |
| 'src=[src1,src2], dest=[dest1,dest2]', -- edge_mult_sssp args |
| ARRAY[0,0], |
| 'sssp_mult_col_out'); |
| |
| SELECT assert(weight = 3, 'Wrong output in graph (SSSP)') |
| FROM sssp_mult_col_out WHERE id = ARRAY[6,6]::BIGINT[]; |
| SELECT assert(parent = ARRAY[5,5]::BIGINT[], 'Wrong parent in graph (SSSP)') |
| FROM sssp_mult_col_out WHERE id = ARRAY[6,6]::BIGINT[]; |
| |
| SELECT graph_sssp_get_path('sssp_mult_col_out',ARRAY[6,6],'sssp_mult_col_out_path'); |
| |
| DROP TABLE IF EXISTS sssp_mult_col_out; |
| DROP TABLE IF EXISTS sssp_mult_col_out_summary; |
| SELECT graph_sssp( |
| 'vertex_mult_sssp', -- Vertex table |
| '[id1,id2]', -- Vertex id column |
| 'edge_mult_sssp_gr2', -- edge_mult_sssp table |
| 'src=[src1,src2], dest=[dest1,dest2]', -- edge_mult_sssp args |
| ARRAY[0,0], |
| 'sssp_mult_col_out', -- Output table of SSSP |
| 'grp1,grp2'); |
| |
| SELECT assert(weight = 3, 'Wrong output in graph (SSSP)') |
| FROM sssp_mult_col_out WHERE id = ARRAY[6,6]::BIGINT[] AND grp1 = 0 AND grp2 = 0; |
| SELECT assert(parent = ARRAY[5,5]::BIGINT[], 'Wrong parent in graph (SSSP)') |
| FROM sssp_mult_col_out WHERE id = ARRAY[6,6]::BIGINT[] AND grp1 = 0 AND grp2 = 0; |
| |
| -- Test where |shortest path| = |V| |
| DROP TABLE IF EXISTS out, out_summary; |
| CREATE TABLE v(id INT); |
| INSERT INTO v VALUES |
| (ascii('s')), |
| (ascii('t')), |
| (ascii('y')), |
| (ascii('x')), |
| (ascii('z')); |
| |
| CREATE TABLE e(src INT, dest INT, weight float8); |
| INSERT INTO e VALUES |
| (ascii('t'), ascii('x'), 5), |
| (ascii('t'), ascii('y'), 8), |
| (ascii('t'), ascii('z'), -4), |
| (ascii('x'), ascii('t'), -2), |
| (ascii('y'), ascii('x'), -3), |
| (ascii('y'), ascii('z'), 9), |
| (ascii('z'), ascii('x'), 7), |
| (ascii('z'), ascii('s'), 2), |
| (ascii('s'), ascii('t'), 6), |
| (ascii('s'), ascii('y'), 7); |
| |
| CREATE TABLE e_grp(src INT, dest INT, weight float8, grp INT); |
| INSERT INTO e_grp VALUES |
| (ascii('t'), ascii('x'), 5, 1), |
| (ascii('t'), ascii('y'), 8, 1), |
| (ascii('t'), ascii('z'), -4, 1), |
| (ascii('x'), ascii('t'), -2, 1), |
| (ascii('y'), ascii('x'), -3, 1), |
| (ascii('y'), ascii('z'), 9, 1), |
| (ascii('z'), ascii('x'), 7, 1), |
| (ascii('z'), ascii('s'), 2, 1), |
| (ascii('s'), ascii('t'), 6, 1), |
| (ascii('s'), ascii('y'), 7, 1), |
| (ascii('t'), ascii('x'), 5, 2), |
| (ascii('t'), ascii('y'), 8, 2), |
| (ascii('t'), ascii('z'), -4, 2), |
| (ascii('x'), ascii('t'), -2, 2), |
| (ascii('y'), ascii('x'), -3, 2), |
| (ascii('y'), ascii('z'), 9, 2), |
| (ascii('z'), ascii('x'), 7, 2), |
| (ascii('z'), ascii('s'), 2, 2), |
| (ascii('s'), ascii('t'), 6, 2), |
| (ascii('s'), ascii('y'), 7, 2); |
| |
| DROP TABLE IF EXISTS out, out_summary; |
| SELECT graph_sssp('v', |
| 'id', |
| 'e', |
| 'src=src,dest=dest,weight=weight', |
| ascii('s'), |
| 'out'); |
| |
| SELECT * FROM out_summary; |
| |
| DROP TABLE IF EXISTS out, out_summary; |
| SELECT graph_sssp('v', |
| 'id', |
| 'e_grp', |
| 'src=src,dest=dest,weight=weight', |
| ascii('s'), |
| 'out', |
| 'grp'); |
| |
| SELECT * FROM out_summary; |
| |
| -- Test negative cycle |
| DROP TABLE IF EXISTS vertex,"EDGE" CASCADE; |
| |
| CREATE TABLE vertex( |
| id INTEGER |
| ); |
| |
| CREATE TABLE "EDGE"( |
| src INTEGER, |
| dest INTEGER, |
| weight DOUBLE PRECISION |
| ); |
| |
| INSERT INTO vertex VALUES |
| (0), |
| (1), |
| (2), |
| (3), |
| (4), |
| (5), |
| (6), |
| (7) |
| ; |
| INSERT INTO "EDGE" VALUES |
| (0, 1, 1), |
| (0, 2, 1), |
| (0, 4, 10), |
| (1, 2, 2), |
| (1, 3, 10), |
| (2, 3, 1), |
| (2, 5, 1), |
| (2, 6, 3), |
| (3, 0, -999), |
| (4, 0, -2), |
| (5, 6, 1), |
| (6, 7, 1) |
| ; |
| |
| DROP TABLE IF EXISTS out, out_summary; |
| SELECT assert(trap_error($TRAP$SELECT graph_sssp('vertex',NULL,'"EDGE"',NULL,0,'out'); |
| $TRAP$) = 1, |
| 'Graph with negative cycle should error out.'); |