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.
- A → B with weighted distance 5 should return B, 5
- A → B → C with weighted distance 5 + 2 = 7 should return C, 7
- 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;
}