arangodb - Way to count number of hops between two nodes and to identify lowest nodes in a hierarchy graph

Question

I am relatively new to arangodb hence the below questions might be super easy to answer but I wasn't able to dig out the solution from the documentation yet.

What I have:

1. Problem: I have modelled a parent child hierarchy of items (nodes) that are linked by edges (isChildOf). The depth is unbalanced for the individual branches and can reach from say 1 over 1.1 to 1.1.1 and 1.1.1.1. Each hierarchy has a root node. Now I want to find out for a given child, e.g. one that is 1.1.1.1 how many edges away it is from the root node 1. So instead of setting the number of edges as a query filter parameter, I want to do the contrary and count the number of "hops" from e.g. 1 to 1.1.1.1 or from 1.1.1.1 to 1.1.1.1.5.2. How could I achieve this in AQL?

2. Problem: I am still looking for a way on how to retrieve the lowest nodes of a previously defined hierarchy (nodes which are not a parent of a child node). E.g. if the hierarchy ends at 1.1.1.1 and 1.1.1.2.1 how can I retrieve all these lowest nodes in a AQL single query?

question from:https://stackoverflow.com/questions/65617822/way-to-count-number-of-hops-between-two-nodes-and-to-identify-lowest-nodes-in-a

Answer 1

There are a couple of ways to achieve this, depending on what you want to return (or how the queries are nested), but either way, either SHORTEST_PATH or K_SHORTEST_PATHS will be your friend. Here is an example:

FOR v,e IN INBOUND SHORTEST_PATH start_node to root_node
    GRAPH 'named_graph'
    RETURN e

Referencing the SHORTEST_PATH docs, we can start to break this down.

1. We are finding a path (the shortest path by the number of hops or "weight") from a "start" node to an "end" node.
2. Using INBOUND or OUTBOUND will depend on how your graph/data-model is built.
3. The v,e variables represent "vertices" and "edges" (v and e, respectively) found along the path.

This query pattern can then be used to calculate the number of vertices or edges, like so:

FOR start_node in child_collection
    FOR root_node IN root_collection
        LET edges = (
            FOR v,e IN INBOUND SHORTEST_PATH start_node to root_node
                GRAPH 'named_graph'
                RETURN e._id
        )
        RETURN {
            root: root_node._id,
            child: start_node._id,
            pathLen: LENGTH(paths)
        }

This may be a bit basic (there are likely ways to optimize this), but it shows how you can use a variable to hold a sub-query, using those results to calculate a path length.

Alternately, you can use K_SHORTEST_PATHS to do this calculation for you. For instance, the previous query could be reduced to this:

FOR p IN INBOUND K_SHORTEST_PATHS start_node to root_node
    GRAPH 'named_graph'
    OPTIONS { weightAttribute: 'weight' }
    LIMIT 1
    RETURN p

Which finds the first shortest path between two points. Here, we use LIMIT 1 to make sure we only return one path. The result will be something like:

[
  {
    edges: [ ... ],
    vertices: [ ... ],
    weight: <number>
  }
]

Or you can customize the return to better meet your needs. Do not return data you don't need or won't use.