Neo4j - Adding logic to graph traversal

Question

My question in short - is whether I can modify the traversal logic used by Neo4j - how to have a control over which edges are traversed and which aren't, during the reachbility computation.

Full description:

I am considering migrating from our current DB to neo4j, and I am wondering if neo4j is a good fit for the following task:

We have large graphs with about 10M simple nodes - their attribute is only a single id.
We also have 3 kinds of edges - "standard", "opening" and "closing". The "opening" and "closing" ones also have a "color" attribute, so they are matched. Each "opening" edge has exactly one matching "closing" edge". For example, there is one opening edge colored as "3", so there's also one closing edge colored the same.

We need to solve a reachability between two nodes where the rules of traversal are fairly simple: You can go through standard edges as you want, you can go through opening edges as you want, while maintaining the order of visited "opening" edges in a stack BUT (that's the tricky part) when you come to a junction that has several "closing" edges, you MUST go through the closing edge which matches the last "open" edge encountered, and then pop out that "open" edge from the stack.

For example:

a -[STANDARD]->B-[Open color:3]->C-[Standard]->D-[Close color:3]->E
and also
D-[Close color:4]->F

note that D has two "closing" edges, with different colors. By the rules defined above, E is reachable by A as the color stack has [3] on its top.
F, however, is not reachable by A.

Can neo4j be configured for such graph traversal logic? Thanks!!

Look at the neo4j traversal framework in the docs: docs.neo4j.org/chunked/milestone/tutorial-traversal.html It has options for callbacks on which relationships to follow and also allows you to order those, with a traversal-state object you can keep your local stack of opening / closing relationships. — Michael Hunger

Mattias Finné Mattias Finné · Accepted Answer · 2013-01-09T13:41:09

This is possible by implementing your own PathExpander and passing to the TraversalDescription. As Michael Hunger pointed out: BranchState can be used to optimize your expander so that you don't have to check the full path each expansion, but instead some kind of boiled down (immutable mind you) state that each traversal branch carries. The expander can pass on a modified state to each next step.

Unfortunately the neo4j manual lacks good examples of using branch state. This sounds like an awesome usage though!

Neo4j - Adding logic to graph traversal

1 Answers