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

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;
}
``````

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

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

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

Thank you for sharing @ellimere!

2 Likes