Finding path in a directed graph


#1

Hi all, I have a question regarding the possibility to do BFS (breadth first search) in graql over a “directed” graph. Lets say I have a family tree with “directed” edges (created roles in the relationship parent -> child). I want to be able to find the path between two persons P1 and P2 only if the P1 is the ancestor of the P2 (has a clear sequence of parent->child relationships in that order). I need to return all nodes on the found path in Java.

The example with path and subgraphs given at http://dev.grakn.ai/docs/distributed-analytics/compute-shortest-path finds a path between Jacob and Barbara which is not suitable as they are at the same level of the tree and therefore Jacob is not ancestor of Barbara.

(asked this in grakn-community slack, was suggested to post it here)


#2

Hi Vladimir,

You’re right about the behaviour of compute path. It doesn’t take into account the direction of the relationships. Having said that, there is a way to achieve your goal using inference and retrieving the explanation object on the inferred result.

Given the following definitions:

define

person sub entity,
  plays parent,
  plays child;

parentship sub relationship,
  relates parent,
  relates child,
  plays ancestor,
  plays decedent;

ancestorship sub relationship,
  relates ancestor,
  relates decedent; 

transitive-ancestorship sub rule,
  when {
    (parent: $a, child: $p) isa parentship;
    (parent: $p, child: $c) isa parentship; 
  } then {
    (ancestor: $a, decedent: $c) isa ancestorship;
  };

Using client Java, you can query:

match 
  $p1 id <id of P1>; 
  $p2 id <id of P2>; 
  $anc (ancestor: $p1, decedent: $p2); 
get $anc;

and then retrieve the explanation object contained within the retrieved answer to get the path that explains the inferred concept ($anc).