Get correct ordering of vertices within some weighted distance of start vertex

GSQL
1

I have a directed graph where each edge has a weighted distance attribute. Given a starting vertex and a maximum weighted distance, I would like to return all vertices that are within the maximum weighted distance of the start vertex, no matter how many hops out they are. I would also like each vertex within this set to update with the correct minimum weighted distance at each hop.

Example: Say I have start vertex A and maximum weighted distance 10.

  1. A → B with weighted distance 5 should return B, 5
  2. A → B → C with weighted distance 5 + 2 = 7 should return C, 7
  3. A → D has weighted distance 8, but A → B → D has weighted distance 5 + 1 = 6. This should return D, 6

Currently I have a query that satisfies cases 1 and 2 when limited to 2 hops, however, it does not satisfy case 3 – I am getting back D, 8. How can I get D, 6?

Here is the query (note that I have used placeholder vertex/edge types in this graph since all my vertices and edges are currently of the same type):

CREATE QUERY SingleSeedResults(VERTEX<vtype> f, INT max_distance) 
FOR GRAPH OldData 
RETURNS (SET<VERTEX<vtype>>)
SYNTAX v2 { 
  SumAccum<DOUBLE> @path_length;
  MinAccum<DOUBLE> @min_distance;
  SetAccum<VERTEX<vtype>> @@resultSet;
  
  # Initialize
  start = {f};
  init = SELECT s
           FROM start:s
           ACCUM 
              s.@path_length = 0,
              s.@min_distance = 0;
  marginalResult = {f};
  Result = {f};
  
  # Loop 
  WHILE(marginalResult.size()>0) LIMIT 2 DO
    marginalResult = SELECT tgt 
             FROM marginalResult:s-(etype>:e)-vtype:tgt 
             WHERE 
                s.@min_distance + e.distance < max_distance
                AND tgt != f           
             ACCUM 
                tgt.@path_length = s.@path_length + e.distance,
                @@resultSet += tgt
             POST-ACCUM 
                tgt.@min_distance += tgt.@path_length,
                tgt.@path_length = tgt.@min_distance;
    # trying to update with new minimum distance 
    newResult = Result MINUS (Result INTERSECT marginalResult);
    Result = newResult UNION marginalResult;
  END;
  
  # Output
  Result = SELECT s 
           FROM Result:s
           WHERE 
             s != f 
             AND s.@min_distance < max_distance
           ORDER BY s.@min_distance;
  PRINT Result[Result.@min_distance];
  RETURN @@resultSet;
  #RETURN Result;
}
2

This looks like a classic case of shortest path, which would utilize Dijkstra’s algorithm with a small modification for max distance. Can you take a look at this example and adapt it to your use case?

Scroll down to the code example

4 Likes
3

Oh, I hadn’t seen this example before! I was trying to adapt a different example I found that didn’t include edge weights. I’ll take a look at this tonight, thanks!

1 Like
4

By the way, in case it helps anyone else, I got this working for graphs where it’s more feasible to use a max distance than to recalculate for every single vertex.

CREATE QUERY SingleSeedResults(VERTEX<vtype> f, INT max_distance)
RETURNS (SET<VERTEX<vtype>>)
SYNTAX v2 {
  SetAccum<DOUBLE> @path_length;
  MinAccum<DOUBLE> @min_distance;
  MinAccum<INT> @min_hops;
  SetAccum<VERTEX<vtype>> @@resultSet;

  # Initialize
  start = {f};
  seed_init = SELECT s
              FROM start:s
              ACCUM
                s.@path_length += 0,
                s.@min_distance = 0,
                s.@min_hops = 0;
  t_init = SELECT t
           FROM vtype:s-(etype>:e)-vtype:t
           WHERE s != f
           ACCUM
             s.@min_distance = 1000;
  marginalResult = {f};
  Result = {f};

  # Loop
  WHILE(marginalResult.size()>0) DO
    marginalResult = SELECT tgt
             FROM marginalResult:s-(etype>:e)-vtype:tgt
             WHERE
                max(s.@path_length) + e.distance < max_distance
                AND s.@min_distance + e.distance < tgt.@min_distance
                AND tgt != f
             ACCUM
                tgt.@path_length += s.@min_distance + e.distance,
                tgt.@path_length += max(s.@path_length) + e.distance,
                tgt.@min_hops += s.@min_hops + 1,
                @@resultSet += tgt
             POST-ACCUM
                tgt.@min_distance += min(tgt.@path_length);
    newResult = Result MINUS (Result INTERSECT marginalResult);
    Result = newResult UNION marginalResult;
  END;

  # Output
  Result = SELECT s
           FROM Result:s
           WHERE
             s != f
             AND s.@min_distance < max_distance
           ORDER BY s.@min_hops, s.@min_distance;
  PRINT Result[Result.@min_hops, Result.@min_distance];
  RETURN @@resultSet;
}
4 Likes
5

Thank you for sharing @ellimere! :pray:

2 Likes