CODEWITHSUNDEEP
javaneo4j
lishaak
lishaak

Reputation: 488

Directed paths in Neo4j

I am facing a seemingly simple issue. I want to traverse the nodes of a Neo4j graph, using the traversal Java API. I want to include only paths where all relationships have the same direction, though. If I do something like

db.traversalDescription().relationships(<type>, Direction.BOTH)

paths like 

[a]-[:TYPE]->[b]<-[:TYPE]-[c]

are included as well which I don't want. I only want paths like

[a]-[:TYPE]->[b]-[:TYPE]->[c]
[a]<-[:TYPE]-[b]<-[:TYPE]-[c]

Can anybody help? It seems like the solution should be quite simple.

Upvotes: 3

Views: 755

Answers (2)

Stefan Armbruster
Stefan Armbruster

Reputation: 39905

Detailing Wes' idea a little bit. In your custom PathEvaluator you need to set branch state to remember the direction of the first relationship. All subsequent visits check if the last relationship matches the direction. In pseudo code:

class SameDirectionPathEvaluator implements PathEvaluator<Direction> {

   public Evaluation evaluate(Path path, BranchState<Direction> state) {
      if (path.length()==0) {
         return Evaluation.EXCLUDE_AND_CONTINUE;
      } else if (path.length()==1) {
         state.setState(getDirectionOfLastRelationship(path));
         return Evaluation.INCLUDE_AND_CONTINUE;
      } else {
         if (state.getState().equals(getDirectionOfLastRelationship(path)) {
            return Evaluation.INCLUDE_AND_CONTINUE;
         } else {
            return Evaluation.EXCLUDE_AND_PRUNE;
         }
      }
   }

   private Direction getDirectionOfLastRelationship(Path path) {
      assert path.length() > 0;
      Direction direction = Direction.INCOMING
      if (path.endNode().equals(path.lastRelationship().getEndNode()) {
        direction = Direction.OUTGOING;
      }
      return direction;
   }

}

Please note I did not compile or test the code above - it's just for sketching the idea.

UPDATE

It seems there is a more efficient way to do this. Since traversals use expanders before evaluators are invoked it makes more sense to implement this behaviour in an expander:

     class ConstantDirectionExpander implements PathExpander<STATE>() {
        @Override
        public Iterable<Relationship> expand(Path path, BranchState<STATE> state) {
            if (path.length()==0) {
                return path.endNode().getRelationships(types);
            } else {
                Direction direction = getDirectionOfLastRelationship(path);
                return path.endNode().getRelationships(direction, types);
            }
        }

        @Override
        public PathExpander<STATE> reverse() {
            return this;
        }

        private Direction getDirectionOfLastRelationship(Path path) {
            assert path.length() > 0;
            Direction direction = Direction.INCOMING;
            if (path.endNode().equals(path.lastRelationship().getEndNode())) {
                direction = Direction.OUTGOING;
            }
            return direction;
        }
    }

In your traversal you need use a InitialBranchSate:

TraversersDescription td = graphDatabaseService.traversalDescriptioin().
  .expand(new ConstantDirectionExpander(reltype))
  .traverse(startNode)

Upvotes: 4

Eve Freeman
Eve Freeman

Reputation: 33145

The way I can think of is you'd implement a PathEvaluator, which scans the path and checks that the nodes are pointing all the same direction. Then you can add it to your TraversalDescription with .evaluator().

There may be a fancier way, though.. you're right, this does seem like it should be built-in.

Upvotes: 3

Related Questions