Dgraph query to fetch all possible paths between two node types with depth limit

Users GraphQL
, , ,
1

I’m working with a Dgraph dataset where nodes have different types and are connected by a RELATED_TO edge with facets.

Here’s a simplified version of the dataset:

_:node_11 <dgraph.type> "Node_Type1" .
_:node_11 <name> "abc1" .
_:node_12 <dgraph.type> "Node_Type1" .
_:node_12 <name> "abc2" .
_:node_13 <dgraph.type> "Node_Type1" .
_:node_13 <name> "abc3" .

_:node_21 <dgraph.type> "Node_Type2" .
_:node_21 <name> "xyz1" .
_:node_22 <dgraph.type> "Node_Type2" .
_:node_22 <name> "xyz2" .
_:node_23 <dgraph.type> "Node_Type2" .
_:node_23 <name> "xyz3" .

_:node_31 <dgraph.type> "Node_Type3" .
_:node_31 <name> "asdf1" .
_:node_32 <dgraph.type> "Node_Type3" .
_:node_32 <name> "asdf2" .
_:node_33 <dgraph.type> "Node_Type3" .
_:node_33 <name> "asdf3" .

# Relationships
_:node_11 <RELATED_TO> _:node_21 (rel_type="CONNECTED") .
_:node_21 <RELATED_TO> _:node_31 (rel_type="CONNECTED") .

_:node_12 <RELATED_TO> _:node_23 (rel_type="CONNECTED") .
_:node_23 <RELATED_TO> _:node_42 (rel_type="CONNECTED") .

_:node_11 <RELATED_TO> _:node_43 (rel_type="CONNECTED") .
_:node_43 <RELATED_TO> _:node_31 (rel_type="CONNECTED") .

_:node_13 <RELATED_TO> _:node_23 (rel_type="CONNECTED") .
_:node_23 <RELATED_TO> _:node_43 (rel_type="CONNECTED") .

What I want to achieve:

  • Fetch all paths between nodes of type Node_Type1 and Node_Type2

  • Limit search to depth = 2

  • Include all possible paths, not just the shortest one

Example Expected Output:

From the above dataset, I would expect something like:

  • node_11 -> node_21 -> node_31

  • node_11 -> node_43 -> node_31

What I tried:

I tried using the shortest query in Dgraph:

{
  path as shortest(from: 0x146f52e7, to: 0x14801bbe, depth: 2) {
    RELATED_TO
  }

  path(func: uid(path)) {
    uid
    expand(_all_)
  }
}

But this only gives me the shortest path between two nodes, not all possible paths of a given depth.

Question:

How can I query Dgraph to get all paths between two node types (Node_Type1 → Node_Type2) with a depth of 2, instead of just the shortest path?

1 Like
2

Check out the numpaths param to shortest: shortest - Dgraph

3

The numpaths The parameter will only return the number of paths you specify, but I want to retrieve all available paths. For example, if I set the depth to 3 and there is one node connected at the third level, I might have 2 paths at depth 2 and 1 path at depth 3. In this scenario, I expect the output to include all 3 paths, not just the 2 shortest ones.

4

Finally had a chance to dig around in DQL with this. The shortest func is doing what it does, returning the shortest path. Here’s an example DQL that lists all the depth 2 paths between the types. It’s not ideal because it’s fixed to three hops, but hopefully it might give you a starting point from which you can work:

{
  var(func: type(Node_Type1)) {
    s as uid
    RELATED_TO @facets(eq(rel_type, "CONNECTED")) {
      m as uid
      RELATED_TO @facets(eq(rel_type, "CONNECTED")) {
        t as uid
      }
    }
  }

  paths(func: uid(s)) @normalize {
    from_uid: uid
    from_name: name

    RELATED_TO @facets(eq(rel_type, "CONNECTED")) @filter(uid(m)) {
      mid_uid: uid
      mid_name: name

      RELATED_TO @facets(eq(rel_type, "CONNECTED")) @filter(uid(t)) {
        to_uid: uid
        to_name: name
      }
    }
  }
}