Get paths between all set of vertices supplied

GSQL
1

Hi there, I’m trying to write a query to get all the paths between a set of vertices being supplied as a parameter.

So for example, I could supply User vertices of A, B, C, D.

I wish to find the shortest path from A to B, A to C, A to D, B to C and so on… I’m not too concerned about what type of edges I can use, and I also hope to not get ‘repeated’ paths, i.e if I found a path from A to D, I don’t have to get a path from D to A as it would just be the same but in reverse.

So far, this is the code I came up with, I’ve tried using FOR loops as well but couldn’t seem to get the syntax right. Any advice would be greatly appreciated. If you’ve done a similar query as well, it would also greatly help if you could share a code snippet! Thanks in advance!

CREATE QUERY all_paths_from_set (SET<String> start) FOR GRAPH name {
  MinAccum<INT> @min_dis;
  OrAccum @or_visited;
  ListAccum<VERTEX> @path_list;
  SetAccum<EDGE> @@edge_set;

  ResultSet = {};
  ListAccum<VERTEX> @@start_list;
  allUsers = {User.*};
  cm = SELECT au FROM allUsers:au WHERE au.name IN start ACCUM @@start_list += au;
  FOREACH i IN @@start_list DO
    // This does not run as there is an error with making a set in the next statement
    Source = {i};
    Res = SELECT t FROM Source:s -((<_|_>)*)- cm:t
      ACCUM t.@path_list = s.@path_list + [t];
    ResultSet = ResultSet UNION Res;
  END;
  PRINT ResultSet;
2

Hello!

I’m thinking you could maybe use All-Pairs Shortest Path and modifying it slightly to run the unweighted shortest path.

Let me know if this helps!

1 Like
3

Hi there, thank you for the response. I went and modified my code referencing some of the docs, and wish to accumulate nodes I have visited along my traversal. I’m doing something like this:

sourceSet = SELECT t FROM sourceSet:s -(:e)- :t 
      WHERE t.@visited == false
      ACCUM CASE WHEN t IN @@end_vertices THEN 
        t.@visited = true, @@shortest_path += (s.@path_list + [t]), @@edge_list += e
      ELSE
        t.@visited = true, t.@path_list = s.@path_list + [t], @@edge_list += e
      END;

where end_vertices specify a set of vertices I wish to traverse to from a set of sources.
However, I seem to get an error of ‘no type can be inferred for t in @@end_vertices’ in the line CASE WHEN t IN @@end_vertices. I understand that that’s because my alias t can be a vertex of any type, but how could I solve this problem? I basically just want to check if the vertex ‘t’ I’m currently traversing is in my end_vertices set.

4

Hey, @silver! Could you provide me with a bit more information? Is @@end_vertices all vertices of the same type? And if so, I believe you could specify a type for the end vertex (the same type if the vertices in your set) in your SELECT statement?