How to do graph traversal with rules


#1

Has anyone tried to do this? I have some Entity API code using loom to do a breadth first traversal that needs to port to client. I’ve seen the musicbrainz rules, but its not obvious to me how or if that strategy can generalize to a traversal. Order is not important—just that I can determine the set of reachable nodes.

Is this possible to do?


#2

Hey Dustin,

Way to break the new-forum-ice!

Presumably you could do this with a recursive rule (assuming your ‘links’ all use the same attribute), but depending on the size of your graph you may prefer an approach like the one Joshua Davey used here, which utilizes direct datoms access to implement the traversal algorithm.


#3

Incidentally, I just looked around our documentation and it seems that we don’t have a straightforward recursive rule example. I’ll look into adding one.

The Yet Analytics folks had an example of one (here) from their blog post about writing a checkers app in Clojure.


#4

Hi Marshall, My links don’t use the same attribute, using Loom i was able to define a successors function which dynamically decides, given an entity, which entities are reachable. The function inspects schema and has a whitelist of allowable attrs. Is this possible using rules? I could imagine pre-processing my inputs into some data structure that is more homogenous and rule friendly and composing the queries. I could also imagine needing database functions for this, though I don’t think Cloud has that capability yet.


#5

Right, if you don’t use the same attribute for your ‘edges’ then you’d have to do something more complex to get traversal logic into a rule. I can imagine a method that might use mutually recursive rules to do so, but that approach will likely get complicated once you end up with more than 2 or 3 link ‘types’.

You’re correct that the Client API doesn’t currently support db functions. We’re working on options there and will provide updates as soon as we have them.