AQL - ArangoDB. Cycles. Recalculating paths after cycles. Add the last node from a cycle

32 Views Asked by At

Context

The graph is oriented, all connections have one specific type and traversal of the graph occurs in a certain direction of connections.

In the graph, there are possible cases:

  • cycles
  • loops (the node is connected to itself)
  • several paths between nodes

Example

1. A -> B -> C -> D -> E -> C -> F -> ...
              
2. A -> A -> A -> B -> C

3. A -> B -> C
   A -> D -> B -> C

Query

FOR node, relation, path IN 1..@depth OUTBOUND
    start relation
PRUNE relation != null AND relation.type != "Loads"
OPTIONS { "order" : "bfs", "uniqueVertices": "none", "uniqueEdges": "path" }
FILTER relation.type == "Loads"
RETURN {"node": node, "relation": relation }

This query returns a graph with "Loads" type relationships. Since loops and loops are possible in the graph(this loops can occur in the middle of the traversal), then uniqueVertices: none.

Problem

  1. If you use uniqueVertices: path, then the connection between the beginning of the cycle and the last node in it will not be returned from the graph.
A -> B -> C -> D -> E -> C -> F -> ...
return
A -> B
B -> C
C -> F
C -> D
D -> E

There isn't relation E -> A

There is same situation with

A -> A -> A -> B -> C
  1. I also noticed that arango returns a lot more connections, since, as I understood after the cycles, it recalculates the paths anew. This behavior greatly reduces the performance of the query.
A -> B -> C -> D -> E -> C -> F -> ...

After this type of path, all next paths after C will be recalculated.

I have one success try to resolve cases when we have a loop in the node.

PRUNE relation != null AND relation._from == relation._to

Question

  1. Is there a way to make the logic work like with PRUNE so that the initial entity in the loop returns?

  2. Is there a way to stop recalculating paths after cycles. Probably by right PRUNE condition.

  3. Is the recalculation of paths the specifics of the implementation of arango's work?

0

There are 0 best solutions below