Shortest Paths Between 2 Vertex Types

GSQL
#1

Hello I haven’t seen this question before but surely it’s been solved:

Can I have a GSQL code snippet to count the number of shortest paths (weight doesn’t matter) between two vertex types?

E.g.,

Start = {A.};
Targets = {B.};

shortest_paths_between(Start, Targets, edge_type = ANY)

#2

Hello @emackie . Disclaimer: I’m at the beginning of learning gsql.

Do you mean that you wish to find the number of shortest paths between all vertices of one type and all vertices of another type?

If you mean that you wish to find the number of shortest paths between two vertices, independent of their type, then the following query might help you:

USE GRAPH <YourGraph>
Set syntax_version = "v2"

CREATE QUERY num_shortest_paths(VERTEX source_v, VERTEX target_v, INT max_path_length = 100) 
{

ListAccum<VERTEX> @path_from_source; 
OrAccum @end_point;
OrAccum @visited;

SumAccum<INT> @@num_shortest_paths; 
ListAccum<ListAccum<VERTEX>> @@shortest_paths; 

INT length_shortest_path = 0; 

source = {source_v};
endVertex = {target_v};

source = SELECT n 
    FROM source:n 
    ACCUM
    n.@path_from_source += n, 
    n.@visited += True; 

endVertex = SELECT n 
    FROM endVertex:n
    ACCUM
    n.@end_point = True; 

WHILE @@num_shortest_paths == 0 and source.size() > 0 LIMIT max_path_length DO
    result = SELECT t
    FROM source:n -(:e)- :t
    WHERE t.@visited == False
    ACCUM
    t.@path_from_source = n.@path_from_source + [t]
    POST-ACCUM
    t.@visited += True, 
    IF t.@end_point == True THEN 
        @@num_shortest_paths += 1,
        @@shortest_paths += t.@path_from_source,
        length_shortest_path = t.@path_from_source.size()
    END; 
    source = result; 
END;

PRINT length_shortest_path, @@num_shortest_paths; 
}```
2 Likes