This is an automated email from the ASF dual-hosted git repository.
muhammadshoaib pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/age.git
The following commit(s) were added to refs/heads/master by this push:
new 5abb02f8 Add shortest_path / all_shortest_paths SRFs (#2430)
5abb02f8 is described below
commit 5abb02f8033db15d43a7dabce367155978294806
Author: John Gemignani <[email protected]>
AuthorDate: Sun Jun 21 14:35:36 2026 -0700
Add shortest_path / all_shortest_paths SRFs (#2430)
Add two C set-returning functions that compute unweighted (hop-count)
shortest paths over the cached global graph adjacency via BFS, callable
both at the SQL top level and inside a cypher() RETURN:
- age_shortest_path(...) -> the single shortest path (0 or 1 rows)
- age_all_shortest_paths(...) -> every shortest path, one per row
The signature follows the natural Cypher argument order
(graph, start, end, edge_types, direction, min_hops, max_hops), registered
in sql/agtype_typecast.sql (install) and age--1.7.0--y.y.y.sql (upgrade).
Unimplemented parameters fail loudly: multiple relationship types and a
non-zero min_hops raise ERRCODE_FEATURE_NOT_SUPPORTED. A single edge type
(string or one-element array) is honored, and a NULL endpoint yields no
rows per Cypher null semantics (wrong-typed endpoints / NULL graph still
error).
To call the SRFs inside a cypher() RETURN, transform_cypher_return now sets
query->hasTargetSRFs (it was the only results-producing clause that didn't,
so the planner never added a ProjectSet node), and transform_FuncCall
auto-prepends the graph name for snake_case shortest_path /
all_shortest_paths. camelCase names are reserved for the future native
grammar.
Robustness:
- BFS guards against non-existent endpoints (returns 0 rows instead of
crashing) and honors CHECK_FOR_INTERRUPTS.
- An unknown edge label now matches no edges instead of silently
traversing all of them (get_label_relation returns InvalidOid).
Adds the age_shortest_path regression test (directed/undirected, label
filtering, parallel edges, self-loops, max_hops, the not-supported stubs,
NULL and non-existent endpoint/graph guards).
38/38 installcheck pass.
Co-authored-by: Copilot <[email protected]>
modified: Makefile
modified: age--1.7.0--y.y.y.sql
modified: sql/agtype_typecast.sql
modified: src/backend/parser/cypher_clause.c
modified: src/backend/parser/cypher_expr.c
modified: src/backend/utils/adt/age_vle.c
new file: regress/expected/age_shortest_path.out
new file: regress/sql/age_shortest_path.sql
---
Makefile | 1 +
age--1.7.0--y.y.y.sql | 31 ++
regress/expected/age_shortest_path.out | 977 +++++++++++++++++++++++++++++++++
regress/sql/age_shortest_path.sql | 630 +++++++++++++++++++++
sql/agtype_typecast.sql | 31 ++
src/backend/parser/cypher_clause.c | 1 +
src/backend/parser/cypher_expr.c | 13 +-
src/backend/utils/adt/age_vle.c | 796 +++++++++++++++++++++++++++
8 files changed, 2475 insertions(+), 5 deletions(-)
diff --git a/Makefile b/Makefile
index b2d93ff4..41208ee0 100644
--- a/Makefile
+++ b/Makefile
@@ -201,6 +201,7 @@ REGRESS = scan \
cypher_delete \
cypher_with \
cypher_vle \
+ age_shortest_path \
cypher_union \
cypher_call \
cypher_merge \
diff --git a/age--1.7.0--y.y.y.sql b/age--1.7.0--y.y.y.sql
index ad2ce20f..b40cde09 100644
--- a/age--1.7.0--y.y.y.sql
+++ b/age--1.7.0--y.y.y.sql
@@ -549,6 +549,37 @@ CALLED ON NULL INPUT
PARALLEL UNSAFE
AS 'MODULE_PATHNAME';
+-- Unweighted (hop-count) shortest path between two vertices, computed over the
+-- cached global graph adjacency via BFS. Returns a single path (0 or 1 rows).
+-- Argument order mirrors the Cypher shortestPath() pattern
+-- (a)-[:type*min_hops..max_hops]->(b):
+-- (graph_name, start, end, edge_types, direction, min_hops, max_hops)
+CREATE FUNCTION ag_catalog.age_shortest_path(IN agtype, IN agtype, IN agtype,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL)
+ RETURNS SETOF agtype
+LANGUAGE C
+STABLE
+CALLED ON NULL INPUT
+PARALLEL UNSAFE
+AS 'MODULE_PATHNAME';
+
+-- All unweighted shortest paths between two vertices (one path per row).
+-- Same argument order as age_shortest_path.
+CREATE FUNCTION ag_catalog.age_all_shortest_paths(IN agtype, IN agtype, IN
agtype,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL)
+ RETURNS SETOF agtype
+LANGUAGE C
+STABLE
+CALLED ON NULL INPUT
+PARALLEL UNSAFE
+AS 'MODULE_PATHNAME';
+
--
-- Composite types for vertex and edge
--
diff --git a/regress/expected/age_shortest_path.out
b/regress/expected/age_shortest_path.out
new file mode 100644
index 00000000..7eb751d1
--- /dev/null
+++ b/regress/expected/age_shortest_path.out
@@ -0,0 +1,977 @@
+/*
+ * 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.
+ */
+LOAD 'age';
+SET search_path TO ag_catalog;
+--
+-- age_shortest_path / age_all_shortest_paths
+--
+SELECT * FROM create_graph('sp_graph');
+NOTICE: graph "sp_graph" has been created
+ create_graph
+--------------
+
+(1 row)
+
+-- Build a small deterministic graph:
+--
+-- A
+-- / \
+-- B C (A->B, A->C, B->D, C->D : two shortest A..D paths)
+-- \ /
+-- D
+-- |
+-- E (D->E : unique 3-hop path A..E)
+--
+-- Z (isolated, unreachable)
+--
+SELECT * FROM cypher('sp_graph', $$
+ CREATE (a:Person {name: 'A'}),
+ (b:Person {name: 'B'}),
+ (c:Person {name: 'C'}),
+ (d:Person {name: 'D'}),
+ (e:Person {name: 'E'}),
+ (z:Person {name: 'Z'}),
+ (a)-[:KNOWS]->(b),
+ (a)-[:KNOWS]->(c),
+ (b)-[:KNOWS]->(d),
+ (c)-[:KNOWS]->(d),
+ (d)-[:KNOWS]->(e)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- materialize the global graph context
+SELECT * FROM cypher('sp_graph', $$ MATCH (u) RETURN vertex_stats(u) ORDER BY
id(u) $$)
+ AS (result agtype);
+ result
+----------------------------------------------------------------------------------------------
+ {"id": 844424930131969, "label": "Person", "in_degree": 0, "out_degree": 2,
"self_loops": 0}
+ {"id": 844424930131970, "label": "Person", "in_degree": 1, "out_degree": 1,
"self_loops": 0}
+ {"id": 844424930131971, "label": "Person", "in_degree": 1, "out_degree": 1,
"self_loops": 0}
+ {"id": 844424930131972, "label": "Person", "in_degree": 2, "out_degree": 1,
"self_loops": 0}
+ {"id": 844424930131973, "label": "Person", "in_degree": 1, "out_degree": 0,
"self_loops": 0}
+ {"id": 844424930131974, "label": "Person", "in_degree": 0, "out_degree": 0,
"self_loops": 0}
+(6 rows)
+
+-- A -> D shortest path (length 2); expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype))
+);
+ path_count
+------------
+ 1
+(1 row)
+
+-- all shortest A -> D; expected: 2 paths (A-B-D and A-C-D), each length 2
+SELECT path
+FROM age_all_shortest_paths(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype))
+) AS path
+ORDER BY path;
+
path
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ [{"id": 844424930131969, "label": "Person", "properties": {"name":
"A"}}::vertex, {"id": 1125899906842625, "label": "KNOWS", "end_id":
844424930131970, "start_id": 844424930131969, "properties": {}}::edge, {"id":
844424930131970, "label": "Person", "properties": {"name": "B"}}::vertex,
{"id": 1125899906842627, "label": "KNOWS", "end_id": 844424930131972,
"start_id": 844424930131970, "properties": {}}::edge, {"id": 844424930131972,
"label": "Person", "properties": {"name": "D"}}::vertex]::path
+ [{"id": 844424930131969, "label": "Person", "properties": {"name":
"A"}}::vertex, {"id": 1125899906842626, "label": "KNOWS", "end_id":
844424930131971, "start_id": 844424930131969, "properties": {}}::edge, {"id":
844424930131971, "label": "Person", "properties": {"name": "C"}}::vertex,
{"id": 1125899906842628, "label": "KNOWS", "end_id": 844424930131972,
"start_id": 844424930131971, "properties": {}}::edge, {"id": 844424930131972,
"label": "Person", "properties": {"name": "D"}}::vertex]::path
+(2 rows)
+
+-- A -> E unique 3-hop path; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'E'}) RETURN id(n)
$$) AS (id agtype))
+);
+ path_count
+------------
+ 1
+(1 row)
+
+-- A -> E with max_hops = 2; expected: path_count = 0 (E is 3 hops away)
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'E'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, NULL, NULL, 2::agtype
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- zero-length path, start == end; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype))
+);
+ path_count
+------------
+ 1
+(1 row)
+
+-- unreachable vertex Z; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'Z'}) RETURN id(n)
$$) AS (id agtype))
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- direction 'in': D -> A traversing edges backwards; expected: path_count = 2
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, '"in"'::agtype
+);
+ path_count
+------------
+ 2
+(1 row)
+
+-- direction 'out': D -> A not reachable forwards; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, '"out"'::agtype
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- label filter 'KNOWS': A -> D still found; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ '"KNOWS"'::agtype
+);
+ path_count
+------------
+ 1
+(1 row)
+
+-- error: invalid direction string; expected: ERROR (must be 'out', 'in', or
'any')
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, '"sideways"'::agtype
+);
+ERROR: direction argument must be one of 'out', 'in', or 'any'
+-- error: start argument is neither a vertex nor an integer id; expected: ERROR
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ '"not_a_vertex"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype))
+);
+ERROR: start vertex argument must be a vertex or the integer id
+--
+-- Non-existent endpoint guards. These must NOT crash the backend and must
+-- return no rows (a path can only exist between vertices in the graph).
+-- Previously, start == end on a non-existent vertex id was matched at BFS
+-- depth 0 and path reconstruction dereferenced a missing vertex, crashing
+-- the server.
+--
+-- start == end on a non-existent integer id; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path('"sp_graph"'::agtype, 999999::agtype, 999999::agtype);
+ path_count
+------------
+ 0
+(1 row)
+
+-- existing start -> non-existent end; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ 999999::agtype
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- non-existent start -> existing end; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ 999999::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype))
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- all-shortest-paths with start == end non-existent; expected: 0 rows
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths('"sp_graph"'::agtype, 999999::agtype,
999999::agtype);
+ path_count
+------------
+ 0
+(1 row)
+
+-- cleanup
+SELECT * FROM drop_graph('sp_graph', true);
+NOTICE: drop cascades to 4 other objects
+DETAIL: drop cascades to table sp_graph._ag_label_vertex
+drop cascades to table sp_graph._ag_label_edge
+drop cascades to table sp_graph."Person"
+drop cascades to table sp_graph."KNOWS"
+NOTICE: graph "sp_graph" has been dropped
+ drop_graph
+------------
+
+(1 row)
+
+--
+-- Empty graph: a graph that exists but has no vertices must return no rows
+-- (and must not hang or crash) for any endpoint query.
+--
+SELECT * FROM create_graph('sp_empty');
+NOTICE: graph "sp_empty" has been created
+ create_graph
+--------------
+
+(1 row)
+
+SELECT count(*) AS path_count
+FROM age_shortest_path('"sp_empty"'::agtype, 0::agtype, 1::agtype);
+ path_count
+------------
+ 0
+(1 row)
+
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths('"sp_empty"'::agtype, 0::agtype, 0::agtype);
+ path_count
+------------
+ 0
+(1 row)
+
+SELECT * FROM drop_graph('sp_empty', true);
+NOTICE: drop cascades to 2 other objects
+DETAIL: drop cascades to table sp_empty._ag_label_vertex
+drop cascades to table sp_empty._ag_label_edge
+NOTICE: graph "sp_empty" has been dropped
+ drop_graph
+------------
+
+(1 row)
+
+--
+-- A large, programmatically generated graph (120 nodes) exercising long
+-- shortest paths (length up to 20), high-multiplicity all-shortest-paths,
+-- label filtering, and directed vs. undirected reachability.
+--
+-- Nodes: (:N {id: 0..119}). Structures built on top of them:
+--
+-- * Main chain 0 -> 1 -> ... -> 20 (unique 20-hop path)
+-- * Alternate chain 0 -> 50 -> 51 -> ... -> 68 -> 20
+-- (a second, disjoint 20-hop path 0..20)
+-- => all-shortest-paths 0..20 under KNOWS = 2 paths of length 20
+-- * 3x3 lattice on ids 70..78, id = 70 + 3*row + col, edges go right
+-- (id->id+1) and down (id->id+3). Monotone 70..78 paths:
+-- => all-shortest-paths 70..78 = C(4,2) = 6 paths of length 4
+-- * LIKES shortcut 0 -[:LIKES]-> 20 (1 hop; only visible when the edge
+-- label filter is NOT restricted to KNOWS)
+-- * Back-edge triangle 0 -> 96 -> 95 -> 0
+-- => directed 0->95 = 2 hops (0-96-95); undirected 0..95 = 1 hop
+-- * Many unused ids (e.g. 119) remain isolated / unreachable.
+--
+SELECT * FROM create_graph('sp_big');
+NOTICE: graph "sp_big" has been created
+ create_graph
+--------------
+
+(1 row)
+
+-- 120 vertices, ids 0..119
+SELECT * FROM cypher('sp_big', $$
+ UNWIND range(0, 119) AS i CREATE (:N {id: i})
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- main chain 0->1->...->20 (KNOWS)
+SELECT * FROM cypher('sp_big', $$
+ UNWIND range(0, 19) AS i
+ MATCH (a:N {id: i}), (b:N {id: i + 1})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- alternate, disjoint 20-hop path 0->50->51->...->68->20 (KNOWS)
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 0}), (b:N {id: 50}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+SELECT * FROM cypher('sp_big', $$
+ UNWIND range(50, 67) AS i
+ MATCH (a:N {id: i}), (b:N {id: i + 1})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 68}), (b:N {id: 20}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- 3x3 lattice on ids 70..78: right edges (id -> id+1)
+SELECT * FROM cypher('sp_big', $$
+ UNWIND [0, 1, 2] AS r
+ UNWIND [0, 1] AS c
+ MATCH (a:N {id: 70 + 3 * r + c}), (b:N {id: 70 + 3 * r + c + 1})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- 3x3 lattice: down edges (id -> id+3)
+SELECT * FROM cypher('sp_big', $$
+ UNWIND [0, 1] AS r
+ UNWIND [0, 1, 2] AS c
+ MATCH (a:N {id: 70 + 3 * r + c}), (b:N {id: 70 + 3 * (r + 1) + c})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- back-edge triangle 0 -> 96 -> 95 -> 0 (KNOWS)
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 0}), (b:N {id: 96}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 96}), (b:N {id: 95}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 95}), (b:N {id: 0}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- labelled shortcut 0 -[:LIKES]-> 20
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 0}), (b:N {id: 20}) CREATE (a)-[:LIKES]->(b)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- sanity: vertex count (also materializes the global context); expected:
count = 120
+SELECT * FROM cypher('sp_big', $$ MATCH (n) RETURN count(n) $$) AS (n agtype);
+ n
+-----
+ 120
+(1 row)
+
+-- all shortest 0 -> 20 under KNOWS (main chain + disjoint alternate);
+-- expected: 2 paths, each exactly 20 hops
+SELECT path
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype
+) AS path
+ORDER BY path;
+
[...]
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[...]
+ [{"id": 844424930131969, "label": "N", "properties": {"id": 0}}::vertex,
{"id": 1125899906842625, "label": "KNOWS", "end_id": 844424930131970,
"start_id": 844424930131969, "properties": {}}::edge, {"id": 844424930131970,
"label": "N", "properties": {"id": 1}}::vertex, {"id": 1125899906842626,
"label": "KNOWS", "end_id": 844424930131971, "start_id": 844424930131970,
"properties": {}}::edge, {"id": 844424930131971, "label": "N", "properties":
{"id": 2}}::vertex, {"id": 1125899906842627, " [...]
+ [{"id": 844424930131969, "label": "N", "properties": {"id": 0}}::vertex,
{"id": 1125899906842645, "label": "KNOWS", "end_id": 844424930132019,
"start_id": 844424930131969, "properties": {}}::edge, {"id": 844424930132019,
"label": "N", "properties": {"id": 50}}::vertex, {"id": 1125899906842646,
"label": "KNOWS", "end_id": 844424930132020, "start_id": 844424930132019,
"properties": {}}::edge, {"id": 844424930132020, "label": "N", "properties":
{"id": 51}}::vertex, {"id": 1125899906842647, [...]
+(2 rows)
+
+-- any label: the LIKES shortcut collapses 0 -> 20; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ NULL, '"out"'::agtype
+);
+ path_count
+------------
+ 1
+(1 row)
+
+-- all shortest 70 -> 78 across the 3x3 lattice; expected: path_count = 6
(C(4,2))
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype
+);
+ path_count
+------------
+ 6
+(1 row)
+
+-- the lattice paths listed; expected: 6 paths, each 4 hops
+SELECT path
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype
+) AS path
+ORDER BY path;
+
path
[...]
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[...]
+ [{"id": 844424930132039, "label": "N", "properties": {"id": 70}}::vertex,
{"id": 1125899906842665, "label": "KNOWS", "end_id": 844424930132040,
"start_id": 844424930132039, "properties": {}}::edge, {"id": 844424930132040,
"label": "N", "properties": {"id": 71}}::vertex, {"id": 1125899906842666,
"label": "KNOWS", "end_id": 844424930132041, "start_id": 844424930132040,
"properties": {}}::edge, {"id": 844424930132041, "label": "N", "properties":
{"id": 72}}::vertex, {"id": 1125899906842673 [...]
+ [{"id": 844424930132039, "label": "N", "properties": {"id": 70}}::vertex,
{"id": 1125899906842665, "label": "KNOWS", "end_id": 844424930132040,
"start_id": 844424930132039, "properties": {}}::edge, {"id": 844424930132040,
"label": "N", "properties": {"id": 71}}::vertex, {"id": 1125899906842672,
"label": "KNOWS", "end_id": 844424930132043, "start_id": 844424930132040,
"properties": {}}::edge, {"id": 844424930132043, "label": "N", "properties":
{"id": 74}}::vertex, {"id": 1125899906842668 [...]
+ [{"id": 844424930132039, "label": "N", "properties": {"id": 70}}::vertex,
{"id": 1125899906842665, "label": "KNOWS", "end_id": 844424930132040,
"start_id": 844424930132039, "properties": {}}::edge, {"id": 844424930132040,
"label": "N", "properties": {"id": 71}}::vertex, {"id": 1125899906842672,
"label": "KNOWS", "end_id": 844424930132043, "start_id": 844424930132040,
"properties": {}}::edge, {"id": 844424930132043, "label": "N", "properties":
{"id": 74}}::vertex, {"id": 1125899906842675 [...]
+ [{"id": 844424930132039, "label": "N", "properties": {"id": 70}}::vertex,
{"id": 1125899906842671, "label": "KNOWS", "end_id": 844424930132042,
"start_id": 844424930132039, "properties": {}}::edge, {"id": 844424930132042,
"label": "N", "properties": {"id": 73}}::vertex, {"id": 1125899906842667,
"label": "KNOWS", "end_id": 844424930132043, "start_id": 844424930132042,
"properties": {}}::edge, {"id": 844424930132043, "label": "N", "properties":
{"id": 74}}::vertex, {"id": 1125899906842668 [...]
+ [{"id": 844424930132039, "label": "N", "properties": {"id": 70}}::vertex,
{"id": 1125899906842671, "label": "KNOWS", "end_id": 844424930132042,
"start_id": 844424930132039, "properties": {}}::edge, {"id": 844424930132042,
"label": "N", "properties": {"id": 73}}::vertex, {"id": 1125899906842667,
"label": "KNOWS", "end_id": 844424930132043, "start_id": 844424930132042,
"properties": {}}::edge, {"id": 844424930132043, "label": "N", "properties":
{"id": 74}}::vertex, {"id": 1125899906842675 [...]
+ [{"id": 844424930132039, "label": "N", "properties": {"id": 70}}::vertex,
{"id": 1125899906842671, "label": "KNOWS", "end_id": 844424930132042,
"start_id": 844424930132039, "properties": {}}::edge, {"id": 844424930132042,
"label": "N", "properties": {"id": 73}}::vertex, {"id": 1125899906842674,
"label": "KNOWS", "end_id": 844424930132045, "start_id": 844424930132042,
"properties": {}}::edge, {"id": 844424930132045, "label": "N", "properties":
{"id": 76}}::vertex, {"id": 1125899906842669 [...]
+(6 rows)
+
+-- max_hops = 19, one short of the 20-hop route; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, NULL, 19::agtype
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- max_hops = 20 admits the full route; expected: path_count = 2
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, NULL, 20::agtype
+);
+ path_count
+------------
+ 2
+(1 row)
+
+-- DIRECTED out: 0 -> 95 must traverse 0->96->95; expected: 1 path (length 2)
+SELECT path
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 95}) RETURN id(n) $$)
AS (id agtype)),
+ NULL, '"out"'::agtype
+) AS path
+ORDER BY path;
+
path
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ [{"id": 844424930131969, "label": "N", "properties": {"id": 0}}::vertex,
{"id": 1125899906842677, "label": "KNOWS", "end_id": 844424930132065,
"start_id": 844424930131969, "properties": {}}::edge, {"id": 844424930132065,
"label": "N", "properties": {"id": 96}}::vertex, {"id": 1125899906842678,
"label": "KNOWS", "end_id": 844424930132064, "start_id": 844424930132065,
"properties": {}}::edge, {"id": 844424930132064, "label": "N", "properties":
{"id": 95}}::vertex]::path
+(1 row)
+
+-- UNDIRECTED: 0 .. 95 via the 95->0 back edge; expected: 1 path (length 1)
+SELECT path
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 95}) RETURN id(n) $$)
AS (id agtype))
+) AS path
+ORDER BY path;
+
path
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ [{"id": 844424930131969, "label": "N", "properties": {"id": 0}}::vertex,
{"id": 1125899906842679, "label": "KNOWS", "end_id": 844424930131969,
"start_id": 844424930132064, "properties": {}}::edge, {"id": 844424930132064,
"label": "N", "properties": {"id": 95}}::vertex]::path
+(1 row)
+
+-- DIRECTED out: 78 -> 70 against lattice flow; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype)),
+ NULL, '"out"'::agtype
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- UNDIRECTED: 78 .. 70 reverses the lattice; expected: path_count = 6
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype))
+);
+ path_count
+------------
+ 6
+(1 row)
+
+-- isolated id 119 unreachable from 0; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 119}) RETURN id(n) $$)
AS (id agtype))
+);
+ path_count
+------------
+ 0
+(1 row)
+
+-- zero-length path, start == end; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype))
+);
+ path_count
+------------
+ 1
+(1 row)
+
+-- cleanup
+SELECT * FROM drop_graph('sp_big', true);
+NOTICE: drop cascades to 5 other objects
+DETAIL: drop cascades to table sp_big._ag_label_vertex
+drop cascades to table sp_big._ag_label_edge
+drop cascades to table sp_big."N"
+drop cascades to table sp_big."KNOWS"
+drop cascades to table sp_big."LIKES"
+NOTICE: graph "sp_big" has been dropped
+ drop_graph
+------------
+
+(1 row)
+
+--
+-- Calling the age_* SRFs from inside cypher() (Tier 1).
+--
+-- Because the functions are prefixed with age_, the cypher() parser resolves
+-- the unqualified names 'shortest_path' and 'all_shortest_paths' to
+-- ag_catalog.age_shortest_path / ag_catalog.age_all_shortest_paths, and the
+-- graph name is auto-injected as the first argument (like vle/vertex_stats),
+-- so callers pass only the bound endpoints. A whole vertex implicitly casts to
+-- agtype, so the argument types resolve. The SRFs are set-returning and now
+-- work in a cypher RETURN projection (ProjectSet), returning one row per path.
+--
+SELECT * FROM create_graph('sp_cy');
+NOTICE: graph "sp_cy" has been created
+ create_graph
+--------------
+
+(1 row)
+
+SELECT * FROM cypher('sp_cy', $$
+ CREATE (a:N {name: 'A'}),
+ (b:N {name: 'B'}),
+ (c:N {name: 'C'}),
+ (a)-[:KNOWS]->(b),
+ (b)-[:KNOWS]->(c)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- materialize the global graph context
+SELECT * FROM cypher('sp_cy', $$ MATCH (u) RETURN vertex_stats(u) ORDER BY
id(u) $$)
+ AS (result agtype);
+ result
+-----------------------------------------------------------------------------------------
+ {"id": 844424930131969, "label": "N", "in_degree": 0, "out_degree": 1,
"self_loops": 0}
+ {"id": 844424930131970, "label": "N", "in_degree": 1, "out_degree": 1,
"self_loops": 0}
+ {"id": 844424930131971, "label": "N", "in_degree": 1, "out_degree": 0,
"self_loops": 0}
+(3 rows)
+
+-- shortest_path() inside a cypher RETURN; the graph name is auto-injected and
+-- the bound vertices are passed; expected: 1 path A..C (length 2)
+SELECT * FROM cypher('sp_cy', $$
+ MATCH (a:N {name:'A'}), (c:N {name:'C'})
+ RETURN shortest_path(a, c)
+$$) AS (path agtype);
+
path
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ [{"id": 844424930131969, "label": "N", "properties": {"name": "A"}}::vertex,
{"id": 1125899906842625, "label": "KNOWS", "end_id": 844424930131970,
"start_id": 844424930131969, "properties": {}}::edge, {"id": 844424930131970,
"label": "N", "properties": {"name": "B"}}::vertex, {"id": 1125899906842626,
"label": "KNOWS", "end_id": 844424930131971, "start_id": 844424930131970,
"properties": {}}::edge, {"id": 844424930131971, "label": "N", "properties":
{"name": "C"}}::vertex]::path
+(1 row)
+
+-- all_shortest_paths() inside a cypher RETURN; expected: 1 path A..C (length
2)
+SELECT * FROM cypher('sp_cy', $$
+ MATCH (a:N {name:'A'}), (c:N {name:'C'})
+ RETURN all_shortest_paths(a, c)
+$$) AS (path agtype);
+
path
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ [{"id": 844424930131969, "label": "N", "properties": {"name": "A"}}::vertex,
{"id": 1125899906842625, "label": "KNOWS", "end_id": 844424930131970,
"start_id": 844424930131969, "properties": {}}::edge, {"id": 844424930131970,
"label": "N", "properties": {"name": "B"}}::vertex, {"id": 1125899906842626,
"label": "KNOWS", "end_id": 844424930131971, "start_id": 844424930131970,
"properties": {}}::edge, {"id": 844424930131971, "label": "N", "properties":
{"name": "C"}}::vertex]::path
+(1 row)
+
+-- in-cypher with an explicit edge-label filter; expected: 1 path A..C (length
2)
+SELECT * FROM cypher('sp_cy', $$
+ MATCH (a:N {name:'A'}), (c:N {name:'C'})
+ RETURN shortest_path(a, c, 'KNOWS')
+$$) AS (path agtype);
+
path
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ [{"id": 844424930131969, "label": "N", "properties": {"name": "A"}}::vertex,
{"id": 1125899906842625, "label": "KNOWS", "end_id": 844424930131970,
"start_id": 844424930131969, "properties": {}}::edge, {"id": 844424930131970,
"label": "N", "properties": {"name": "B"}}::vertex, {"id": 1125899906842626,
"label": "KNOWS", "end_id": 844424930131971, "start_id": 844424930131970,
"properties": {}}::edge, {"id": 844424930131971, "label": "N", "properties":
{"name": "C"}}::vertex]::path
+(1 row)
+
+-- still supported: call the SRF at the top level; expected: 1 path A..C
(length 2)
+SELECT path
+FROM age_shortest_path(
+ '"sp_cy"'::agtype,
+ (SELECT id FROM cypher('sp_cy', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_cy', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype))
+) AS path
+ORDER BY path;
+
path
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ [{"id": 844424930131969, "label": "N", "properties": {"name": "A"}}::vertex,
{"id": 1125899906842625, "label": "KNOWS", "end_id": 844424930131970,
"start_id": 844424930131969, "properties": {}}::edge, {"id": 844424930131970,
"label": "N", "properties": {"name": "B"}}::vertex, {"id": 1125899906842626,
"label": "KNOWS", "end_id": 844424930131971, "start_id": 844424930131970,
"properties": {}}::edge, {"id": 844424930131971, "label": "N", "properties":
{"name": "C"}}::vertex]::path
+(1 row)
+
+-- cleanup
+SELECT * FROM drop_graph('sp_cy', true);
+NOTICE: drop cascades to 4 other objects
+DETAIL: drop cascades to table sp_cy._ag_label_vertex
+drop cascades to table sp_cy._ag_label_edge
+drop cascades to table sp_cy."N"
+drop cascades to table sp_cy."KNOWS"
+NOTICE: graph "sp_cy" has been dropped
+ drop_graph
+------------
+
+(1 row)
+
+--
+-- Edge cases: parallel/multi-edges, self-loops, unknown edge labels,
+-- max_hops boundaries (0 and negative), explicit 'any' direction, and
+-- NULL / unknown-graph argument errors.
+--
+SELECT * FROM create_graph('sp_edge');
+NOTICE: graph "sp_edge" has been created
+ create_graph
+--------------
+
+(1 row)
+
+-- A and B are connected by TWO parallel KNOWS edges plus one LIKES edge.
+-- B->C is a single KNOWS edge. S has a self-loop. These exercise the
+-- multi-predecessor (parallel edge) logic and the label filter.
+SELECT * FROM cypher('sp_edge', $$
+ CREATE (a:N {name: 'A'}),
+ (b:N {name: 'B'}),
+ (c:N {name: 'C'}),
+ (s:N {name: 'S'}),
+ (a)-[:KNOWS]->(b),
+ (a)-[:KNOWS]->(b),
+ (a)-[:LIKES]->(b),
+ (b)-[:KNOWS]->(c),
+ (s)-[:KNOWS]->(s)
+$$) AS (result agtype);
+ result
+--------
+(0 rows)
+
+-- materialize the global graph context
+SELECT * FROM cypher('sp_edge', $$ MATCH (u) RETURN vertex_stats(u) ORDER BY
id(u) $$)
+ AS (result agtype);
+ result
+-----------------------------------------------------------------------------------------
+ {"id": 844424930131969, "label": "N", "in_degree": 0, "out_degree": 3,
"self_loops": 0}
+ {"id": 844424930131970, "label": "N", "in_degree": 3, "out_degree": 1,
"self_loops": 0}
+ {"id": 844424930131971, "label": "N", "in_degree": 1, "out_degree": 0,
"self_loops": 0}
+ {"id": 844424930131972, "label": "N", "in_degree": 1, "out_degree": 1,
"self_loops": 1}
+(4 rows)
+
+-- parallel edges: two distinct KNOWS edges A->B are two distinct shortest
+-- paths; expected count 2
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype);
+ count
+-------
+ 2
+(1 row)
+
+-- no label filter: 2 KNOWS + 1 LIKES edge A->B are three distinct shortest
+-- paths; expected count 3
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, '"out"'::agtype);
+ count
+-------
+ 3
+(1 row)
+
+-- single shortest path A->B picks exactly one of the parallel edges; count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)));
+ count
+-------
+ 1
+(1 row)
+
+-- self-loop: a vertex with an edge to itself yields only the zero-length
+-- path for start == end (the self-loop is never used); count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)));
+ count
+-------
+ 1
+(1 row)
+
+-- all_shortest_paths with start == end (existing vertex): one zero-length
+-- path; count 1
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)));
+ count
+-------
+ 1
+(1 row)
+
+-- unknown relationship type matches no edges: A..C filtered by a label that
+-- does not exist must return no path (NOT silently fall back to all edges);
+-- count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"NOSUCHLABEL"'::agtype, '"out"'::agtype);
+ count
+-------
+ 0
+(1 row)
+
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"NOSUCHLABEL"'::agtype, '"out"'::agtype);
+ count
+-------
+ 0
+(1 row)
+
+-- the zero-length (start == end) path has no edges, so an unknown label
+-- still matches it; count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ '"NOSUCHLABEL"'::agtype, '"out"'::agtype);
+ count
+-------
+ 1
+(1 row)
+
+-- existing label that does not connect the endpoints: LIKES only exists on
+-- A->B, so A..C filtered by LIKES is unreachable; count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"LIKES"'::agtype, '"out"'::agtype);
+ count
+-------
+ 0
+(1 row)
+
+-- max_hops = 0 with start == end: the zero-length path is still returned;
+-- count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, NULL::agtype, NULL::agtype, '0'::agtype);
+ count
+-------
+ 1
+(1 row)
+
+-- max_hops = 0 with adjacent distinct endpoints: no path within zero hops;
+-- count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, NULL::agtype, NULL::agtype, '0'::agtype);
+ count
+-------
+ 0
+(1 row)
+
+-- negative max_hops is treated as unbounded: A..C (length 2) is found;
+-- count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, NULL::agtype, NULL::agtype, '-1'::agtype);
+ count
+-------
+ 1
+(1 row)
+
+-- explicit 'any' direction string (vs the default NULL == undirected);
+-- two parallel KNOWS edges A->B give two shortest paths; count 2
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"any"'::agtype);
+ count
+-------
+ 2
+(1 row)
+
+-- NULL start (or end) vertex yields no rows (Cypher null semantics: a null
+-- endpoint simply produces no match, it is not an error); count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ NULL::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)));
+ count
+-------
+ 0
+(1 row)
+
+-- NULL end vertex likewise yields no rows; count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype);
+ count
+-------
+ 0
+(1 row)
+
+-- all_shortest_paths with a NULL endpoint also yields no rows; count 0
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype);
+ count
+-------
+ 0
+(1 row)
+
+-- a single relationship type may be passed as a one-element array; expected:
+-- same as the bare-string form, A..C under KNOWS (length 2); count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '["KNOWS"]'::agtype, '"out"'::agtype);
+ count
+-------
+ 1
+(1 row)
+
+-- multiple relationship types are not yet supported; expected: ERROR
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '["KNOWS", "LIKES"]'::agtype, '"out"'::agtype);
+ERROR: age_shortest_path: multiple relationship types are not yet supported
+-- a non-zero minimum hop count is not yet supported; expected: ERROR
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, 2::agtype);
+ERROR: age_shortest_path: a minimum hop count is not yet supported
+-- a minimum hop count of 0 is the default and is accepted; A..C (length 2);
+-- count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, 0::agtype);
+ count
+-------
+ 1
+(1 row)
+
+-- a graph name that does not exist is an error
+SELECT count(*) FROM age_shortest_path('"no_such_graph"'::agtype, '1'::agtype,
'2'::agtype);
+ERROR: schema "no_such_graph" does not exist
+-- cleanup
+SELECT * FROM drop_graph('sp_edge', true);
+NOTICE: drop cascades to 5 other objects
+DETAIL: drop cascades to table sp_edge._ag_label_vertex
+drop cascades to table sp_edge._ag_label_edge
+drop cascades to table sp_edge."N"
+drop cascades to table sp_edge."KNOWS"
+drop cascades to table sp_edge."LIKES"
+NOTICE: graph "sp_edge" has been dropped
+ drop_graph
+------------
+
+(1 row)
+
diff --git a/regress/sql/age_shortest_path.sql
b/regress/sql/age_shortest_path.sql
new file mode 100644
index 00000000..82b4d66b
--- /dev/null
+++ b/regress/sql/age_shortest_path.sql
@@ -0,0 +1,630 @@
+/*
+ * 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.
+ */
+
+LOAD 'age';
+SET search_path TO ag_catalog;
+
+--
+-- age_shortest_path / age_all_shortest_paths
+--
+
+SELECT * FROM create_graph('sp_graph');
+
+-- Build a small deterministic graph:
+--
+-- A
+-- / \
+-- B C (A->B, A->C, B->D, C->D : two shortest A..D paths)
+-- \ /
+-- D
+-- |
+-- E (D->E : unique 3-hop path A..E)
+--
+-- Z (isolated, unreachable)
+--
+SELECT * FROM cypher('sp_graph', $$
+ CREATE (a:Person {name: 'A'}),
+ (b:Person {name: 'B'}),
+ (c:Person {name: 'C'}),
+ (d:Person {name: 'D'}),
+ (e:Person {name: 'E'}),
+ (z:Person {name: 'Z'}),
+ (a)-[:KNOWS]->(b),
+ (a)-[:KNOWS]->(c),
+ (b)-[:KNOWS]->(d),
+ (c)-[:KNOWS]->(d),
+ (d)-[:KNOWS]->(e)
+$$) AS (result agtype);
+
+-- materialize the global graph context
+SELECT * FROM cypher('sp_graph', $$ MATCH (u) RETURN vertex_stats(u) ORDER BY
id(u) $$)
+ AS (result agtype);
+
+-- A -> D shortest path (length 2); expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype))
+);
+
+-- all shortest A -> D; expected: 2 paths (A-B-D and A-C-D), each length 2
+SELECT path
+FROM age_all_shortest_paths(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype))
+) AS path
+ORDER BY path;
+
+-- A -> E unique 3-hop path; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'E'}) RETURN id(n)
$$) AS (id agtype))
+);
+
+-- A -> E with max_hops = 2; expected: path_count = 0 (E is 3 hops away)
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'E'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, NULL, NULL, 2::agtype
+);
+
+-- zero-length path, start == end; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype))
+);
+
+-- unreachable vertex Z; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'Z'}) RETURN id(n)
$$) AS (id agtype))
+);
+
+-- direction 'in': D -> A traversing edges backwards; expected: path_count = 2
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, '"in"'::agtype
+);
+
+-- direction 'out': D -> A not reachable forwards; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, '"out"'::agtype
+);
+
+-- label filter 'KNOWS': A -> D still found; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ '"KNOWS"'::agtype
+);
+
+-- error: invalid direction string; expected: ERROR (must be 'out', 'in', or
'any')
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype)),
+ NULL, '"sideways"'::agtype
+);
+
+-- error: start argument is neither a vertex nor an integer id; expected: ERROR
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ '"not_a_vertex"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'D'}) RETURN id(n)
$$) AS (id agtype))
+);
+
+--
+-- Non-existent endpoint guards. These must NOT crash the backend and must
+-- return no rows (a path can only exist between vertices in the graph).
+-- Previously, start == end on a non-existent vertex id was matched at BFS
+-- depth 0 and path reconstruction dereferenced a missing vertex, crashing
+-- the server.
+--
+
+-- start == end on a non-existent integer id; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path('"sp_graph"'::agtype, 999999::agtype, 999999::agtype);
+
+-- existing start -> non-existent end; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype)),
+ 999999::agtype
+);
+
+-- non-existent start -> existing end; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_graph"'::agtype,
+ 999999::agtype,
+ (SELECT id FROM cypher('sp_graph', $$ MATCH (n {name:'A'}) RETURN id(n)
$$) AS (id agtype))
+);
+
+-- all-shortest-paths with start == end non-existent; expected: 0 rows
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths('"sp_graph"'::agtype, 999999::agtype,
999999::agtype);
+
+-- cleanup
+SELECT * FROM drop_graph('sp_graph', true);
+
+
+--
+-- Empty graph: a graph that exists but has no vertices must return no rows
+-- (and must not hang or crash) for any endpoint query.
+--
+SELECT * FROM create_graph('sp_empty');
+SELECT count(*) AS path_count
+FROM age_shortest_path('"sp_empty"'::agtype, 0::agtype, 1::agtype);
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths('"sp_empty"'::agtype, 0::agtype, 0::agtype);
+SELECT * FROM drop_graph('sp_empty', true);
+
+
+
+--
+-- A large, programmatically generated graph (120 nodes) exercising long
+-- shortest paths (length up to 20), high-multiplicity all-shortest-paths,
+-- label filtering, and directed vs. undirected reachability.
+--
+-- Nodes: (:N {id: 0..119}). Structures built on top of them:
+--
+-- * Main chain 0 -> 1 -> ... -> 20 (unique 20-hop path)
+-- * Alternate chain 0 -> 50 -> 51 -> ... -> 68 -> 20
+-- (a second, disjoint 20-hop path 0..20)
+-- => all-shortest-paths 0..20 under KNOWS = 2 paths of length 20
+-- * 3x3 lattice on ids 70..78, id = 70 + 3*row + col, edges go right
+-- (id->id+1) and down (id->id+3). Monotone 70..78 paths:
+-- => all-shortest-paths 70..78 = C(4,2) = 6 paths of length 4
+-- * LIKES shortcut 0 -[:LIKES]-> 20 (1 hop; only visible when the edge
+-- label filter is NOT restricted to KNOWS)
+-- * Back-edge triangle 0 -> 96 -> 95 -> 0
+-- => directed 0->95 = 2 hops (0-96-95); undirected 0..95 = 1 hop
+-- * Many unused ids (e.g. 119) remain isolated / unreachable.
+--
+SELECT * FROM create_graph('sp_big');
+
+-- 120 vertices, ids 0..119
+SELECT * FROM cypher('sp_big', $$
+ UNWIND range(0, 119) AS i CREATE (:N {id: i})
+$$) AS (result agtype);
+
+-- main chain 0->1->...->20 (KNOWS)
+SELECT * FROM cypher('sp_big', $$
+ UNWIND range(0, 19) AS i
+ MATCH (a:N {id: i}), (b:N {id: i + 1})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+
+-- alternate, disjoint 20-hop path 0->50->51->...->68->20 (KNOWS)
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 0}), (b:N {id: 50}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+SELECT * FROM cypher('sp_big', $$
+ UNWIND range(50, 67) AS i
+ MATCH (a:N {id: i}), (b:N {id: i + 1})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 68}), (b:N {id: 20}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+
+-- 3x3 lattice on ids 70..78: right edges (id -> id+1)
+SELECT * FROM cypher('sp_big', $$
+ UNWIND [0, 1, 2] AS r
+ UNWIND [0, 1] AS c
+ MATCH (a:N {id: 70 + 3 * r + c}), (b:N {id: 70 + 3 * r + c + 1})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+
+-- 3x3 lattice: down edges (id -> id+3)
+SELECT * FROM cypher('sp_big', $$
+ UNWIND [0, 1] AS r
+ UNWIND [0, 1, 2] AS c
+ MATCH (a:N {id: 70 + 3 * r + c}), (b:N {id: 70 + 3 * (r + 1) + c})
+ CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+
+-- back-edge triangle 0 -> 96 -> 95 -> 0 (KNOWS)
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 0}), (b:N {id: 96}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 96}), (b:N {id: 95}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 95}), (b:N {id: 0}) CREATE (a)-[:KNOWS]->(b)
+$$) AS (result agtype);
+
+-- labelled shortcut 0 -[:LIKES]-> 20
+SELECT * FROM cypher('sp_big', $$
+ MATCH (a:N {id: 0}), (b:N {id: 20}) CREATE (a)-[:LIKES]->(b)
+$$) AS (result agtype);
+
+-- sanity: vertex count (also materializes the global context); expected:
count = 120
+SELECT * FROM cypher('sp_big', $$ MATCH (n) RETURN count(n) $$) AS (n agtype);
+
+-- all shortest 0 -> 20 under KNOWS (main chain + disjoint alternate);
+-- expected: 2 paths, each exactly 20 hops
+SELECT path
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype
+) AS path
+ORDER BY path;
+
+-- any label: the LIKES shortcut collapses 0 -> 20; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ NULL, '"out"'::agtype
+);
+
+-- all shortest 70 -> 78 across the 3x3 lattice; expected: path_count = 6
(C(4,2))
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype
+);
+
+-- the lattice paths listed; expected: 6 paths, each 4 hops
+SELECT path
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype
+) AS path
+ORDER BY path;
+
+-- max_hops = 19, one short of the 20-hop route; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, NULL, 19::agtype
+);
+
+-- max_hops = 20 admits the full route; expected: path_count = 2
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 20}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, NULL, 20::agtype
+);
+
+-- DIRECTED out: 0 -> 95 must traverse 0->96->95; expected: 1 path (length 2)
+SELECT path
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 95}) RETURN id(n) $$)
AS (id agtype)),
+ NULL, '"out"'::agtype
+) AS path
+ORDER BY path;
+
+-- UNDIRECTED: 0 .. 95 via the 95->0 back edge; expected: 1 path (length 1)
+SELECT path
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 95}) RETURN id(n) $$)
AS (id agtype))
+) AS path
+ORDER BY path;
+
+-- DIRECTED out: 78 -> 70 against lattice flow; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype)),
+ NULL, '"out"'::agtype
+);
+
+-- UNDIRECTED: 78 .. 70 reverses the lattice; expected: path_count = 6
+SELECT count(*) AS path_count
+FROM age_all_shortest_paths(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 78}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 70}) RETURN id(n) $$)
AS (id agtype))
+);
+
+-- isolated id 119 unreachable from 0; expected: path_count = 0
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 119}) RETURN id(n) $$)
AS (id agtype))
+);
+
+-- zero-length path, start == end; expected: path_count = 1
+SELECT count(*) AS path_count
+FROM age_shortest_path(
+ '"sp_big"'::agtype,
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_big', $$ MATCH (n:N {id: 0}) RETURN id(n) $$)
AS (id agtype))
+);
+
+-- cleanup
+SELECT * FROM drop_graph('sp_big', true);
+
+--
+-- Calling the age_* SRFs from inside cypher() (Tier 1).
+--
+-- Because the functions are prefixed with age_, the cypher() parser resolves
+-- the unqualified names 'shortest_path' and 'all_shortest_paths' to
+-- ag_catalog.age_shortest_path / ag_catalog.age_all_shortest_paths, and the
+-- graph name is auto-injected as the first argument (like vle/vertex_stats),
+-- so callers pass only the bound endpoints. A whole vertex implicitly casts to
+-- agtype, so the argument types resolve. The SRFs are set-returning and now
+-- work in a cypher RETURN projection (ProjectSet), returning one row per path.
+--
+SELECT * FROM create_graph('sp_cy');
+
+SELECT * FROM cypher('sp_cy', $$
+ CREATE (a:N {name: 'A'}),
+ (b:N {name: 'B'}),
+ (c:N {name: 'C'}),
+ (a)-[:KNOWS]->(b),
+ (b)-[:KNOWS]->(c)
+$$) AS (result agtype);
+
+-- materialize the global graph context
+SELECT * FROM cypher('sp_cy', $$ MATCH (u) RETURN vertex_stats(u) ORDER BY
id(u) $$)
+ AS (result agtype);
+
+-- shortest_path() inside a cypher RETURN; the graph name is auto-injected and
+-- the bound vertices are passed; expected: 1 path A..C (length 2)
+SELECT * FROM cypher('sp_cy', $$
+ MATCH (a:N {name:'A'}), (c:N {name:'C'})
+ RETURN shortest_path(a, c)
+$$) AS (path agtype);
+
+-- all_shortest_paths() inside a cypher RETURN; expected: 1 path A..C (length
2)
+SELECT * FROM cypher('sp_cy', $$
+ MATCH (a:N {name:'A'}), (c:N {name:'C'})
+ RETURN all_shortest_paths(a, c)
+$$) AS (path agtype);
+
+-- in-cypher with an explicit edge-label filter; expected: 1 path A..C (length
2)
+SELECT * FROM cypher('sp_cy', $$
+ MATCH (a:N {name:'A'}), (c:N {name:'C'})
+ RETURN shortest_path(a, c, 'KNOWS')
+$$) AS (path agtype);
+
+-- still supported: call the SRF at the top level; expected: 1 path A..C
(length 2)
+SELECT path
+FROM age_shortest_path(
+ '"sp_cy"'::agtype,
+ (SELECT id FROM cypher('sp_cy', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_cy', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype))
+) AS path
+ORDER BY path;
+
+-- cleanup
+SELECT * FROM drop_graph('sp_cy', true);
+
+--
+-- Edge cases: parallel/multi-edges, self-loops, unknown edge labels,
+-- max_hops boundaries (0 and negative), explicit 'any' direction, and
+-- NULL / unknown-graph argument errors.
+--
+SELECT * FROM create_graph('sp_edge');
+
+-- A and B are connected by TWO parallel KNOWS edges plus one LIKES edge.
+-- B->C is a single KNOWS edge. S has a self-loop. These exercise the
+-- multi-predecessor (parallel edge) logic and the label filter.
+SELECT * FROM cypher('sp_edge', $$
+ CREATE (a:N {name: 'A'}),
+ (b:N {name: 'B'}),
+ (c:N {name: 'C'}),
+ (s:N {name: 'S'}),
+ (a)-[:KNOWS]->(b),
+ (a)-[:KNOWS]->(b),
+ (a)-[:LIKES]->(b),
+ (b)-[:KNOWS]->(c),
+ (s)-[:KNOWS]->(s)
+$$) AS (result agtype);
+
+-- materialize the global graph context
+SELECT * FROM cypher('sp_edge', $$ MATCH (u) RETURN vertex_stats(u) ORDER BY
id(u) $$)
+ AS (result agtype);
+
+-- parallel edges: two distinct KNOWS edges A->B are two distinct shortest
+-- paths; expected count 2
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype);
+
+-- no label filter: 2 KNOWS + 1 LIKES edge A->B are three distinct shortest
+-- paths; expected count 3
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, '"out"'::agtype);
+
+-- single shortest path A->B picks exactly one of the parallel edges; count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)));
+
+-- self-loop: a vertex with an edge to itself yields only the zero-length
+-- path for start == end (the self-loop is never used); count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)));
+
+-- all_shortest_paths with start == end (existing vertex): one zero-length
+-- path; count 1
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)));
+
+-- unknown relationship type matches no edges: A..C filtered by a label that
+-- does not exist must return no path (NOT silently fall back to all edges);
+-- count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"NOSUCHLABEL"'::agtype, '"out"'::agtype);
+
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"NOSUCHLABEL"'::agtype, '"out"'::agtype);
+
+-- the zero-length (start == end) path has no edges, so an unknown label
+-- still matches it; count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'S'}) RETURN id(n) $$)
AS (id agtype)),
+ '"NOSUCHLABEL"'::agtype, '"out"'::agtype);
+
+-- existing label that does not connect the endpoints: LIKES only exists on
+-- A->B, so A..C filtered by LIKES is unreachable; count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"LIKES"'::agtype, '"out"'::agtype);
+
+-- max_hops = 0 with start == end: the zero-length path is still returned;
+-- count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, NULL::agtype, NULL::agtype, '0'::agtype);
+
+-- max_hops = 0 with adjacent distinct endpoints: no path within zero hops;
+-- count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, NULL::agtype, NULL::agtype, '0'::agtype);
+
+-- negative max_hops is treated as unbounded: A..C (length 2) is found;
+-- count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype, NULL::agtype, NULL::agtype, '-1'::agtype);
+
+-- explicit 'any' direction string (vs the default NULL == undirected);
+-- two parallel KNOWS edges A->B give two shortest paths; count 2
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"any"'::agtype);
+
+-- NULL start (or end) vertex yields no rows (Cypher null semantics: a null
+-- endpoint simply produces no match, it is not an error); count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ NULL::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'B'}) RETURN id(n) $$)
AS (id agtype)));
+
+-- NULL end vertex likewise yields no rows; count 0
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype);
+
+-- all_shortest_paths with a NULL endpoint also yields no rows; count 0
+SELECT count(*) FROM age_all_shortest_paths(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ NULL::agtype);
+
+-- a single relationship type may be passed as a one-element array; expected:
+-- same as the bare-string form, A..C under KNOWS (length 2); count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '["KNOWS"]'::agtype, '"out"'::agtype);
+
+-- multiple relationship types are not yet supported; expected: ERROR
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '["KNOWS", "LIKES"]'::agtype, '"out"'::agtype);
+
+-- a non-zero minimum hop count is not yet supported; expected: ERROR
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, 2::agtype);
+
+-- a minimum hop count of 0 is the default and is accepted; A..C (length 2);
+-- count 1
+SELECT count(*) FROM age_shortest_path(
+ '"sp_edge"'::agtype,
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'A'}) RETURN id(n) $$)
AS (id agtype)),
+ (SELECT id FROM cypher('sp_edge', $$ MATCH (n {name:'C'}) RETURN id(n) $$)
AS (id agtype)),
+ '"KNOWS"'::agtype, '"out"'::agtype, 0::agtype);
+
+-- a graph name that does not exist is an error
+SELECT count(*) FROM age_shortest_path('"no_such_graph"'::agtype, '1'::agtype,
'2'::agtype);
+
+-- cleanup
+SELECT * FROM drop_graph('sp_edge', true);
diff --git a/sql/agtype_typecast.sql b/sql/agtype_typecast.sql
index abca5e51..f12f215f 100644
--- a/sql/agtype_typecast.sql
+++ b/sql/agtype_typecast.sql
@@ -98,6 +98,37 @@ CALLED ON NULL INPUT
PARALLEL UNSAFE -- might be safe
AS 'MODULE_PATHNAME';
+-- Unweighted (hop-count) shortest path between two vertices, computed over the
+-- cached global graph adjacency via BFS. Returns a single path (0 or 1 rows).
+-- Argument order mirrors the Cypher shortestPath() pattern
+-- (a)-[:type*min_hops..max_hops]->(b):
+-- (graph_name, start, end, edge_types, direction, min_hops, max_hops)
+CREATE FUNCTION ag_catalog.age_shortest_path(IN agtype, IN agtype, IN agtype,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL)
+ RETURNS SETOF agtype
+LANGUAGE C
+STABLE
+CALLED ON NULL INPUT
+PARALLEL UNSAFE
+AS 'MODULE_PATHNAME';
+
+-- All unweighted shortest paths between two vertices (one path per row).
+-- Same argument order as age_shortest_path.
+CREATE FUNCTION ag_catalog.age_all_shortest_paths(IN agtype, IN agtype, IN
agtype,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL,
+ IN agtype DEFAULT NULL)
+ RETURNS SETOF agtype
+LANGUAGE C
+STABLE
+CALLED ON NULL INPUT
+PARALLEL UNSAFE
+AS 'MODULE_PATHNAME';
+
-- function to build an edge for a VLE match
CREATE FUNCTION ag_catalog.age_build_vle_match_edge(agtype, agtype)
RETURNS agtype
diff --git a/src/backend/parser/cypher_clause.c
b/src/backend/parser/cypher_clause.c
index dcd31b9d..5ac9dea6 100644
--- a/src/backend/parser/cypher_clause.c
+++ b/src/backend/parser/cypher_clause.c
@@ -2785,6 +2785,7 @@ static Query *transform_cypher_return(cypher_parsestate
*cpstate,
query->jointree = makeFromExpr(pstate->p_joinlist, NULL);
query->hasAggs = pstate->p_hasAggs;
query->hasSubLinks = pstate->p_hasSubLinks;
+ query->hasTargetSRFs = pstate->p_hasTargetSRFs;
assign_query_collations(pstate, query);
diff --git a/src/backend/parser/cypher_expr.c b/src/backend/parser/cypher_expr.c
index e62f2c6e..7e4f4460 100644
--- a/src/backend/parser/cypher_expr.c
+++ b/src/backend/parser/cypher_expr.c
@@ -2265,16 +2265,19 @@ static Node *transform_FuncCall(cypher_parsestate
*cpstate, FuncCall *fn)
fname = list_make2(makeString("ag_catalog"), makeString(ag_name));
/*
- * Currently 3 functions need the graph name passed in as the first
- * argument - in addition to the other arguments: startNode,
endNode,
- * and vle. So, check for those 3 functions here and that the arg
list
- * is not empty. Then prepend the graph name if necessary.
+ * Currently these functions need the graph name passed in as the
+ * first argument - in addition to the other arguments: startNode,
+ * endNode, vle, vertex_stats, shortest_path, and
all_shortest_paths.
+ * So, check for those functions here and that the arg list is not
+ * empty. Then prepend the graph name if necessary.
*/
if ((list_length(targs) != 0) &&
(strcasecmp("startNode", name) == 0 ||
strcasecmp("endNode", name) == 0 ||
strcasecmp("vle", name) == 0 ||
- strcasecmp("vertex_stats", name) == 0))
+ strcasecmp("vertex_stats", name) == 0 ||
+ strcasecmp("shortest_path", name) == 0 ||
+ strcasecmp("all_shortest_paths", name) == 0))
{
char *graph_name = cpstate->graph_name;
Datum d = string_to_agtype(graph_name);
diff --git a/src/backend/utils/adt/age_vle.c b/src/backend/utils/adt/age_vle.c
index 9e433b9e..804d9e17 100644
--- a/src/backend/utils/adt/age_vle.c
+++ b/src/backend/utils/adt/age_vle.c
@@ -65,6 +65,8 @@
#include "common/hashfn.h"
#include "funcapi.h"
+#include "miscadmin.h"
+#include "nodes/pg_list.h"
#include "utils/datum.h"
#include "utils/lsyscache.h"
@@ -1065,6 +1067,14 @@ static bool dfs_find_a_path_between(VLE_local_context
*vlelctx)
bool found = false;
uint32 edge_hashvalue;
+ /*
+ * Allow this traversal to be cancelled (e.g. by a user Ctrl-C or a
+ * statement_timeout). On a large or densely connected graph this DFS
+ * can run for a long time, so we must yield to interrupt processing
+ * on every iteration.
+ */
+ CHECK_FOR_INTERRUPTS();
+
/* get an edge, but leave it on the stack for now */
edge_id = gid_stack_peek(edge_stack);
/*
@@ -1200,6 +1210,14 @@ static bool dfs_find_a_path_from(VLE_local_context
*vlelctx)
bool found = false;
uint32 edge_hashvalue;
+ /*
+ * Allow this traversal to be cancelled (e.g. by a user Ctrl-C or a
+ * statement_timeout). On a large or densely connected graph this DFS
+ * can run for a long time, so we must yield to interrupt processing
+ * on every iteration.
+ */
+ CHECK_FOR_INTERRUPTS();
+
/* get an edge, but leave it on the stack for now */
edge_id = gid_stack_peek(edge_stack);
/*
@@ -2774,3 +2792,781 @@ Datum _ag_enforce_edge_uniqueness(PG_FUNCTION_ARGS)
hash_destroy(exists_hash);
PG_RETURN_BOOL(true);
}
+
+/*
+ * ---------------------------------------------------------------------------
+ * Shortest path / all shortest paths
+ * ---------------------------------------------------------------------------
+ *
+ * Plain (non-grammar) set-returning functions that compute the unweighted
+ * (hop-count) shortest path between two vertices, built directly on top of the
+ * cached global graph (GRAPH_global_context) and its flat-array adjacency
+ * (VertexEdgeArray). These do NOT go through the VLE grammar/transform path;
+ * they are user-callable helpers:
+ *
+ * ag_catalog.age_shortest_path(graph, start, end
+ * [, edge_types [, direction [, min_hops [, max_hops]]]])
+ * ag_catalog.age_all_shortest_paths(graph, start, end
+ * [, edge_types [, direction [, min_hops [, max_hops]]]])
+ *
+ * Both perform a breadth-first search from the start vertex. age_shortest_path
+ * returns a single path (0 or 1 rows); age_all_shortest_paths returns every
+ * path whose length equals the minimum hop count (one row per path), by
+ * recording a predecessor multiset during the BFS and enumerating the
+ * resulting shortest-path DAG.
+ *
+ * Because BFS depth strictly increases, every emitted path is simple (no
+ * repeated vertex and therefore no repeated edge), satisfying openCypher
+ * edge-isomorphism for these fixed-length results.
+ */
+
+/* Simple FIFO queue of graphids for the BFS frontier. */
+typedef struct sp_queue
+{
+ graphid *data;
+ int64 head;
+ int64 tail;
+ int64 cap;
+} sp_queue;
+
+/* One predecessor edge on a shortest path (all-shortest-paths mode). */
+typedef struct sp_pred
+{
+ graphid edge;
+ graphid parent_vertex;
+} sp_pred;
+
+/* Per-vertex BFS bookkeeping, keyed by vertex_id in the visited hashtable. */
+typedef struct sp_visit_entry
+{
+ graphid vertex_id; /* hash key — must be first */
+ int64 depth; /* BFS depth from the source vertex */
+ graphid parent_edge; /* single-path reconstruction */
+ graphid parent_vertex; /* single-path reconstruction */
+ List *preds; /* sp_pred * list for all-shortest-paths mode */
+} sp_visit_entry;
+
+/* Cross-call SRF state: the precomputed result paths streamed one per call. */
+typedef struct sp_srf_state
+{
+ Datum *paths;
+ int64 npaths;
+ int64 next;
+} sp_srf_state;
+
+static void sp_queue_init(sp_queue *q)
+{
+ q->cap = 1024;
+ q->head = 0;
+ q->tail = 0;
+ q->data = palloc(sizeof(graphid) * q->cap);
+}
+
+static void sp_queue_push(sp_queue *q, graphid v)
+{
+ if (q->tail == q->cap)
+ {
+ q->cap = q->cap * 2;
+ q->data = repalloc(q->data, sizeof(graphid) * q->cap);
+ }
+ q->data[q->tail] = v;
+ q->tail = q->tail + 1;
+}
+
+static bool sp_queue_is_empty(sp_queue *q)
+{
+ return q->head == q->tail;
+}
+
+static graphid sp_queue_pop(sp_queue *q)
+{
+ graphid v = q->data[q->head];
+
+ q->head = q->head + 1;
+ return v;
+}
+
+/* Resolve a vertex argument (a vertex agtype or an integer id) to a graphid.
*/
+static graphid sp_agtype_to_graphid(agtype *agt, const char *argname)
+{
+ agtype_value *agtv = NULL;
+
+ agtv = get_agtype_value("age_shortest_path", agt, AGTV_VERTEX, false);
+
+ if (agtv != NULL && agtv->type == AGTV_VERTEX)
+ {
+ agtv = GET_AGTYPE_VALUE_OBJECT_VALUE(agtv, "id");
+ }
+ else if (agtv == NULL || agtv->type != AGTV_INTEGER)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("%s argument must be a vertex or the integer id",
+ argname)));
+ }
+
+ return agtv->val.int_value;
+}
+
+/* Resolve the optional direction argument; NULL defaults to undirected. */
+static cypher_rel_dir sp_agtype_to_direction(agtype *agt)
+{
+ agtype_value *agtv = NULL;
+ char *s = NULL;
+ cypher_rel_dir dir = CYPHER_REL_DIR_NONE;
+
+ if (agt == NULL)
+ {
+ return CYPHER_REL_DIR_NONE;
+ }
+
+ agtv = get_agtype_value("age_shortest_path", agt, AGTV_STRING, true);
+ s = pnstrdup(agtv->val.string.val, agtv->val.string.len);
+
+ if (pg_strcasecmp(s, "out") == 0)
+ {
+ dir = CYPHER_REL_DIR_RIGHT;
+ }
+ else if (pg_strcasecmp(s, "in") == 0)
+ {
+ dir = CYPHER_REL_DIR_LEFT;
+ }
+ else if (pg_strcasecmp(s, "any") == 0)
+ {
+ dir = CYPHER_REL_DIR_NONE;
+ }
+ else
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("direction argument must be one of 'out', 'in', or
'any'")));
+ }
+
+ pfree_if_not_null(s);
+ return dir;
+}
+
+/*
+ * Wrap an interleaved [vertex, edge, vertex, ... , vertex] graphid array in a
+ * VLE_path_container and materialize it as an AGTV_PATH agtype Datum.
+ */
+static Datum sp_build_path_datum(Oid graph_oid, graphid *alt, int64 alt_len)
+{
+ VLE_path_container *vpc = NULL;
+ graphid *arr = NULL;
+ agtype_value *agtv_path = NULL;
+ agtype *agt = NULL;
+
+ vpc = create_VLE_path_container(alt_len);
+ vpc->graph_oid = graph_oid;
+
+ arr = GET_GRAPHID_ARRAY_FROM_CONTAINER(vpc);
+ memcpy(arr, alt, sizeof(graphid) * alt_len);
+
+ vpc->start_vid = alt[0];
+ vpc->end_vid = alt[alt_len - 1];
+
+ agtv_path = build_path(vpc);
+ agt = agtype_value_to_agtype(agtv_path);
+
+ return AGTYPE_P_GET_DATUM(agt);
+}
+
+/*
+ * Breadth-first search from source toward target over the flat-array
+ * adjacency. Returns the visited hashtable; sets *out_found and (if found)
+ * *out_target_depth (the shortest hop count). In all-shortest-paths mode
+ * (collect_all) every shortest-path predecessor is recorded per vertex.
+ */
+static HTAB *sp_run_bfs(GRAPH_global_context *ggctx, graphid source,
+ graphid target, bool filter_edges, Oid edge_label_oid,
+ cypher_rel_dir dir, int64 max_hops, bool collect_all,
+ int64 *out_target_depth, bool *out_found)
+{
+ HASHCTL ctl;
+ HTAB *visited = NULL;
+ sp_queue q;
+ sp_visit_entry *se = NULL;
+ bool found = false;
+ int64 target_depth = -1;
+ bool dir_out = (dir == CYPHER_REL_DIR_RIGHT || dir == CYPHER_REL_DIR_NONE);
+ bool dir_in = (dir == CYPHER_REL_DIR_LEFT || dir == CYPHER_REL_DIR_NONE);
+
+ /* visited hashtable: graphid -> sp_visit_entry */
+ MemSet(&ctl, 0, sizeof(ctl));
+ ctl.keysize = sizeof(int64);
+ ctl.entrysize = sizeof(sp_visit_entry);
+ ctl.hash = graphid_hash;
+ visited = hash_create("age shortest path visited", 1024, &ctl,
+ HASH_ELEM | HASH_FUNCTION);
+
+ /*
+ * A path can only exist between vertices that actually exist in the graph.
+ * If either endpoint is missing we are done: report "not found" and return
+ * the (empty) visited table. This guard is critical: without it a source
+ * that equals a non-existent target would be matched at depth 0 (see the
+ * "u == target" check below), and path reconstruction would then try to
+ * materialize a vertex that does not exist, dereferencing invalid memory
+ * and crashing the backend.
+ */
+ if (get_vertex_entry(ggctx, source) == NULL ||
+ get_vertex_entry(ggctx, target) == NULL)
+ {
+ *out_target_depth = -1;
+ *out_found = false;
+ return visited;
+ }
+
+ sp_queue_init(&q);
+
+ /* seed the frontier with the source vertex at depth 0 */
+ se = (sp_visit_entry *) hash_search(visited, &source, HASH_ENTER, NULL);
+ se->vertex_id = source;
+ se->depth = 0;
+ se->parent_edge = 0;
+ se->parent_vertex = source;
+ se->preds = NIL;
+ sp_queue_push(&q, source);
+
+ while (!sp_queue_is_empty(&q))
+ {
+ graphid u = sp_queue_pop(&q);
+ sp_visit_entry *ue = NULL;
+ vertex_entry *ve = NULL;
+ int64 du = 0;
+ int pass = 0;
+
+ /*
+ * Allow this search to be cancelled (e.g. by a user Ctrl-C or a
+ * statement_timeout). On a large graph the BFS frontier can grow very
+ * large, so we must yield to interrupt processing on every iteration.
+ */
+ CHECK_FOR_INTERRUPTS();
+
+ ue = (sp_visit_entry *) hash_search(visited, &u, HASH_FIND, NULL);
+ du = ue->depth;
+
+ /* target reached: record its (shortest) depth */
+ if (u == target)
+ {
+ found = true;
+ if (target_depth < 0)
+ {
+ target_depth = du;
+ }
+ /* single-path mode: the first discovery is sufficient */
+ if (!collect_all)
+ {
+ break;
+ }
+ }
+
+ /* never expand at or beyond the shortest target depth */
+ if (target_depth >= 0 && du >= target_depth)
+ {
+ continue;
+ }
+
+ /* respect the optional upper hop bound */
+ if (max_hops >= 0 && du >= max_hops)
+ {
+ continue;
+ }
+
+ ve = get_vertex_entry(ggctx, u);
+ if (ve == NULL)
+ {
+ continue;
+ }
+
+ /* pass 0 = outgoing edges, pass 1 = incoming edges */
+ for (pass = 0; pass < 2; pass++)
+ {
+ VertexEdgeArray *edges = NULL;
+ int32 i = 0;
+
+ if (pass == 0)
+ {
+ if (!dir_out)
+ {
+ continue;
+ }
+ edges = get_vertex_entry_edges_out_array(ve);
+ }
+ else
+ {
+ if (!dir_in)
+ {
+ continue;
+ }
+ edges = get_vertex_entry_edges_in_array(ve);
+ }
+
+ if (edges == NULL || edges->array == NULL)
+ {
+ continue;
+ }
+
+ for (i = 0; i < edges->size; i++)
+ {
+ graphid eid = edges->array[i];
+ edge_entry *ee = NULL;
+ graphid v = 0;
+ sp_visit_entry *vse = NULL;
+ bool was_present = false;
+
+ ee = get_edge_entry(ggctx, eid);
+ if (ee == NULL)
+ {
+ continue;
+ }
+
+ /*
+ * Optional edge label filter. When a label filter is active
+ * we keep only edges whose label table oid matches. Note that
+ * a label name which does not exist in this graph resolves to
+ * InvalidOid; because no real edge can have an InvalidOid
+ * label table, every edge is then skipped and only the
+ * zero-length (start == end) path can match -- matching the
+ * openCypher semantics that an unknown relationship type
+ * matches no relationships.
+ */
+ if (filter_edges &&
+ get_edge_entry_label_table_oid(ee) != edge_label_oid)
+ {
+ continue;
+ }
+
+ /* the neighbor depends on which side of the edge u is on */
+ if (pass == 0)
+ {
+ v = get_edge_entry_end_vertex_id(ee);
+ }
+ else
+ {
+ v = get_edge_entry_start_vertex_id(ee);
+ }
+
+ /* self loops never shorten a path to a different vertex */
+ if (v == u)
+ {
+ continue;
+ }
+
+ vse = (sp_visit_entry *) hash_search(visited, &v, HASH_ENTER,
+ &was_present);
+ if (!was_present)
+ {
+ vse->vertex_id = v;
+ vse->depth = du + 1;
+ vse->parent_edge = eid;
+ vse->parent_vertex = u;
+ vse->preds = NIL;
+
+ if (collect_all)
+ {
+ sp_pred *p = palloc(sizeof(sp_pred));
+
+ p->edge = eid;
+ p->parent_vertex = u;
+ vse->preds = lappend(vse->preds, p);
+ }
+
+ sp_queue_push(&q, v);
+ }
+ else if (collect_all && vse->depth == du + 1)
+ {
+ /* another equally-short predecessor of v */
+ sp_pred *p = palloc(sizeof(sp_pred));
+
+ p->edge = eid;
+ p->parent_vertex = u;
+ vse->preds = lappend(vse->preds, p);
+ }
+ }
+ }
+ }
+
+ *out_target_depth = target_depth;
+ *out_found = found;
+ return visited;
+}
+
+/*
+ * Recursively enumerate every shortest path by walking the predecessor DAG
+ * from target back to source. Each completed path is appended to *out as a
+ * freshly allocated interleaved graphid array of length alt_len.
+ */
+static void sp_enumerate(HTAB *visited, graphid source, graphid cur,
+ graphid *alt, int64 alt_len, int64 pos, List **out)
+{
+ sp_visit_entry *e = NULL;
+ ListCell *lc = NULL;
+
+ /*
+ * Enumerating every shortest path can be combinatorially expensive, so
+ * allow the user to cancel (Ctrl-C / statement_timeout) at each step.
+ */
+ CHECK_FOR_INTERRUPTS();
+
+ alt[pos] = cur;
+
+ if (cur == source)
+ {
+ /* a complete path only when we have consumed the whole array */
+ if (pos == 0)
+ {
+ graphid *copy = palloc(sizeof(graphid) * alt_len);
+
+ memcpy(copy, alt, sizeof(graphid) * alt_len);
+ *out = lappend(*out, copy);
+ }
+ return;
+ }
+
+ e = (sp_visit_entry *) hash_search(visited, &cur, HASH_FIND, NULL);
+ if (e == NULL)
+ {
+ return;
+ }
+
+ foreach(lc, e->preds)
+ {
+ sp_pred *p = (sp_pred *) lfirst(lc);
+
+ alt[pos - 1] = p->edge;
+ sp_enumerate(visited, source, p->parent_vertex, alt, alt_len, pos - 2,
+ out);
+ }
+}
+
+/*
+ * Resolve arguments, run the BFS, and materialize the result path(s) as an
+ * array of AGTV_PATH agtype Datums. Returns NULL with *out_count == 0 when no
+ * path exists. Caller must run in a context that survives the SRF.
+ */
+static Datum *sp_compute_paths(agtype *graph_name_agt, agtype *start_agt,
+ agtype *end_agt, agtype *label_agt,
+ agtype *dir_agt, agtype *minhops_agt,
+ agtype *maxhops_agt, bool collect_all,
+ int64 *out_count)
+{
+ agtype_value *agtv_temp = NULL;
+ char *graph_name = NULL;
+ Oid graph_oid = InvalidOid;
+ GRAPH_global_context *ggctx = NULL;
+ graphid source = 0;
+ graphid target = 0;
+ bool filter_edges = false;
+ Oid edge_label_oid = InvalidOid;
+ cypher_rel_dir dir = CYPHER_REL_DIR_NONE;
+ int64 max_hops = -1;
+ HTAB *visited = NULL;
+ int64 target_depth = -1;
+ bool found = false;
+ Datum *paths = NULL;
+
+ *out_count = 0;
+
+ /* the graph name is required */
+ if (graph_name_agt == NULL)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("age_shortest_path: graph name cannot be NULL")));
+ }
+
+ agtv_temp = get_agtype_value("age_shortest_path", graph_name_agt,
+ AGTV_STRING, true);
+ graph_name = pnstrdup(agtv_temp->val.string.val,
+ agtv_temp->val.string.len);
+ graph_oid = get_graph_oid(graph_name);
+
+ /*
+ * A NULL start or end vertex yields no rows, matching Cypher semantics
+ * where a null endpoint simply produces no match (it is not an error).
+ */
+ if (start_agt == NULL || end_agt == NULL)
+ {
+ return NULL;
+ }
+
+ source = sp_agtype_to_graphid(start_agt, "start vertex");
+ target = sp_agtype_to_graphid(end_agt, "end vertex");
+
+ /*
+ * Optional edge type filter. A single relationship type may be supplied
+ * either as a bare string or as a one-element array. Multiple relationship
+ * types (an array with more than one element) are not yet supported.
+ */
+ if (label_agt != NULL)
+ {
+ char *label_name = NULL;
+
+ if (AGT_ROOT_IS_ARRAY(label_agt) && !AGT_ROOT_IS_SCALAR(label_agt))
+ {
+ int nelems = AGT_ROOT_COUNT(label_agt);
+
+ if (nelems > 1)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("age_shortest_path: multiple relationship
types are not yet supported")));
+ }
+
+ if (nelems == 1)
+ {
+ agtv_temp = get_ith_agtype_value_from_container(
+ &label_agt->root, 0);
+ if (agtv_temp->type != AGTV_STRING)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("age_shortest_path: relationship type must
be a string")));
+ }
+ if (agtv_temp->val.string.len != 0)
+ {
+ label_name = pnstrdup(agtv_temp->val.string.val,
+ agtv_temp->val.string.len);
+ edge_label_oid = get_label_relation(label_name, graph_oid);
+ filter_edges = true;
+ }
+ }
+ }
+ else
+ {
+ agtv_temp = get_agtype_value("age_shortest_path", label_agt,
+ AGTV_STRING, true);
+ if (agtv_temp->val.string.len != 0)
+ {
+ label_name = pnstrdup(agtv_temp->val.string.val,
+ agtv_temp->val.string.len);
+ edge_label_oid = get_label_relation(label_name, graph_oid);
+ filter_edges = true;
+ }
+ }
+ }
+
+ /* optional direction (defaults to undirected) */
+ dir = sp_agtype_to_direction(dir_agt);
+
+ /*
+ * Optional minimum hop count. A genuine minimum-length constraint needs a
+ * different search than plain BFS, so for now only the default (NULL or 0)
+ * is accepted; any other value is rejected loudly.
+ */
+ if (minhops_agt != NULL)
+ {
+ int64 min_hops = 0;
+
+ agtv_temp = get_agtype_value("age_shortest_path", minhops_agt,
+ AGTV_INTEGER, true);
+ min_hops = agtv_temp->val.int_value;
+ if (min_hops != 0)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("age_shortest_path: a minimum hop count is not yet
supported")));
+ }
+ }
+
+ /* optional upper hop bound (NULL or negative means unbounded) */
+ if (maxhops_agt != NULL)
+ {
+ agtv_temp = get_agtype_value("age_shortest_path", maxhops_agt,
+ AGTV_INTEGER, true);
+ max_hops = agtv_temp->val.int_value;
+ if (max_hops < 0)
+ {
+ max_hops = -1;
+ }
+ }
+
+ /* build / fetch the global graph cache for this graph */
+ ggctx = manage_GRAPH_global_contexts(graph_name, graph_oid);
+ if (ggctx == NULL)
+ {
+ return NULL;
+ }
+
+ /* run the breadth-first search */
+ visited = sp_run_bfs(ggctx, source, target, filter_edges, edge_label_oid,
+ dir, max_hops, collect_all, &target_depth, &found);
+
+ if (!found)
+ {
+ hash_destroy(visited);
+ return NULL;
+ }
+
+ if (!collect_all)
+ {
+ /* reconstruct the single shortest path from the parent pointers */
+ int64 alt_len = (2 * target_depth) + 1;
+ graphid *alt = palloc(sizeof(graphid) * alt_len);
+ int64 pos = alt_len - 1;
+ graphid cur = target;
+
+ alt[pos] = cur;
+ pos = pos - 1;
+ while (cur != source)
+ {
+ sp_visit_entry *e = NULL;
+
+ e = (sp_visit_entry *) hash_search(visited, &cur, HASH_FIND, NULL);
+ alt[pos] = e->parent_edge;
+ pos = pos - 1;
+ alt[pos] = e->parent_vertex;
+ pos = pos - 1;
+ cur = e->parent_vertex;
+ }
+
+ paths = palloc(sizeof(Datum));
+ paths[0] = sp_build_path_datum(graph_oid, alt, alt_len);
+ *out_count = 1;
+ }
+ else
+ {
+ /* enumerate every equal-length shortest path */
+ int64 alt_len = (2 * target_depth) + 1;
+ graphid *alt = palloc(sizeof(graphid) * alt_len);
+ List *arrays = NIL;
+ ListCell *lc = NULL;
+ int64 n = 0;
+ int64 idx = 0;
+
+ sp_enumerate(visited, source, target, alt, alt_len, alt_len - 1,
+ &arrays);
+
+ n = list_length(arrays);
+ paths = palloc(sizeof(Datum) * (n > 0 ? n : 1));
+ foreach(lc, arrays)
+ {
+ graphid *a = (graphid *) lfirst(lc);
+
+ paths[idx] = sp_build_path_datum(graph_oid, a, alt_len);
+ idx = idx + 1;
+ }
+ *out_count = n;
+ }
+
+ hash_destroy(visited);
+ return paths;
+}
+
+/*
+ * Shared SRF driver for age_shortest_path / age_all_shortest_paths. The first
+ * call computes every result path up front and stores them; subsequent calls
+ * stream them one per row.
+ */
+static Datum sp_srf_impl(FunctionCallInfo fcinfo, bool collect_all)
+{
+ FuncCallContext *funcctx = NULL;
+ sp_srf_state *state = NULL;
+
+ if (SRF_IS_FIRSTCALL())
+ {
+ MemoryContext oldctx;
+ agtype *a_graph = NULL;
+ agtype *a_start = NULL;
+ agtype *a_end = NULL;
+ agtype *a_label = NULL;
+ agtype *a_dir = NULL;
+ agtype *a_min = NULL;
+ agtype *a_max = NULL;
+
+ funcctx = SRF_FIRSTCALL_INIT();
+ oldctx = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
+
+ /*
+ * Argument order mirrors the Cypher shortestPath() pattern
+ * (a)-[:type*min_hops..max_hops]->(b):
+ * 0 graph, 1 start, 2 end, 3 edge_types, 4 direction,
+ * 5 min_hops, 6 max_hops
+ */
+ a_graph = PG_ARGISNULL(0) ? NULL : AG_GET_ARG_AGTYPE_P(0);
+ a_start = PG_ARGISNULL(1) ? NULL : AG_GET_ARG_AGTYPE_P(1);
+ a_end = PG_ARGISNULL(2) ? NULL : AG_GET_ARG_AGTYPE_P(2);
+ a_label = PG_ARGISNULL(3) ? NULL : AG_GET_ARG_AGTYPE_P(3);
+ a_dir = PG_ARGISNULL(4) ? NULL : AG_GET_ARG_AGTYPE_P(4);
+ a_min = PG_ARGISNULL(5) ? NULL : AG_GET_ARG_AGTYPE_P(5);
+ a_max = PG_ARGISNULL(6) ? NULL : AG_GET_ARG_AGTYPE_P(6);
+
+ /* treat an explicit agtype null the same as a SQL NULL */
+ if (a_start != NULL && is_agtype_null(a_start))
+ {
+ a_start = NULL;
+ }
+ if (a_end != NULL && is_agtype_null(a_end))
+ {
+ a_end = NULL;
+ }
+ if (a_label != NULL && is_agtype_null(a_label))
+ {
+ a_label = NULL;
+ }
+ if (a_dir != NULL && is_agtype_null(a_dir))
+ {
+ a_dir = NULL;
+ }
+ if (a_min != NULL && is_agtype_null(a_min))
+ {
+ a_min = NULL;
+ }
+ if (a_max != NULL && is_agtype_null(a_max))
+ {
+ a_max = NULL;
+ }
+
+ state = palloc0(sizeof(sp_srf_state));
+ state->next = 0;
+ state->paths = sp_compute_paths(a_graph, a_start, a_end, a_label,
+ a_dir, a_min, a_max, collect_all,
+ &state->npaths);
+ funcctx->user_fctx = state;
+
+ MemoryContextSwitchTo(oldctx);
+ }
+
+ funcctx = SRF_PERCALL_SETUP();
+ state = (sp_srf_state *) funcctx->user_fctx;
+
+ if (state->next < state->npaths)
+ {
+ Datum d = state->paths[state->next];
+
+ state->next = state->next + 1;
+ SRF_RETURN_NEXT(funcctx, d);
+ }
+
+ SRF_RETURN_DONE(funcctx);
+}
+
+/*
+ * age_shortest_path(graph_name, start, end [, edge_types [, direction
+ * [, min_hops [, max_hops]]]]) -> SETOF agtype
+ *
+ * Returns the single unweighted shortest path (as an AGTV_PATH) between the
+ * start and end vertices, or no rows if unreachable.
+ */
+PG_FUNCTION_INFO_V1(age_shortest_path);
+
+Datum age_shortest_path(PG_FUNCTION_ARGS)
+{
+ return sp_srf_impl(fcinfo, false);
+}
+
+/*
+ * age_all_shortest_paths(graph_name, start, end [, edge_types [, direction
+ * [, min_hops [, max_hops]]]]) -> SETOF agtype
+ *
+ * Returns every unweighted shortest path (one AGTV_PATH per row) between the
+ * start and end vertices, i.e. all paths whose length equals the minimum hop
+ * count, or no rows if unreachable.
+ */
+PG_FUNCTION_INFO_V1(age_all_shortest_paths);
+
+Datum age_all_shortest_paths(PG_FUNCTION_ARGS)
+{
+ return sp_srf_impl(fcinfo, true);
+}
