Find all shortest paths using TraversalDescription

Question

I need to find all all shortest paths between two nodes using TraversalDescription.

(I cannot use Cypher procedure allShortestPaths() because I need to add some specific evaluator later: Neo4J: shortest paths with specific relation types sequence constrain )

Node startNode = ...;
Node endNode = ...;
TraversalDescription td = graphDb.traversalDescription()
    .breadthFirst()
    .evaluator(Evaluators.endNodeIs(Evaluation.INCLUDE_AND_PRUNE,
                                    Evaluation.EXCLUDE_AND_CONTINUE,
                                    endNode));

for (Path path : td.traverse(startNode)) {
    // only 1 path found
}

I get only 1 path.

But if I run the Cypher query:

MATCH (startNode{...})
MATCH (endNode{...})
MATCH path = allShortestPaths((startNode)-[*]-(endNode))
RETURN path;

There are more then one paths found for the same startNode and endNode.

How to set up the TraversalDescription to find all (shortest) paths?

Answer 1

Some suggestions:

1. Take a look at how shortestpath and allshortestpths are actually implemented. You may be able to modify a copy of the code to do what you want. TraversaDescription is not used at all.

2. There is also an "experimental" BidirectionalTraversalDescription that seems to be closer to the design of the shortestpath and allshortestpths implementations. You might be able to use that instead.

Answer 2

the root of your problem is "prune". You stop traversing when you find a first path with endPoint. So try this:

TraversalDescription td = graphDb.traversalDescription()
    .breadthFirst()
    .evaluator(Evaluators.endNodeIs(Evaluation.INCLUDE_AND_CONTINUE,
                                    Evaluation.EXCLUDE_AND_CONTINUE,
                                    endNode));

Answer 3

My TraversalDescription cannot be used to find more than 1 path because of default Uniqueness.NODE_GLOBAL: once discovered, the end node will never be visited again.

So, the 1-st step is to do:

td = td.uniqueness(Uniqueness.NODE_PATH);

But now we don't have a stop condition and traversal returns not only shortest paths.

2-nd step is to add path evaluator that brings a stop condition:

class EndNodeAndNotDeeperEvaluator implements Evaluator
{
    int depth = Integer.MAX_VALUE;
    Node endNode;

    public EndNodeAndNotDeeperEvaluator(Node node) {
        endNode = node;
    }

    @Override
    public Evaluation evaluate(Path path) {
        if (path.length() > depth)
            return Evaluation.EXCLUDE_AND_PRUNE;

        if (path.endNode().equals(endNode)) {
            depth = path.length();
            return Evaluation.INCLUDE_AND_PRUNE;
        }

        return Evaluation.EXCLUDE_AND_CONTINUE;
    }
}

td = td.evaluator(new EndNodeAndNotDeeperEvaluator(endNode));

Now it works! ...for short paths (length < 10)
But for more long paths it does not give any result, but gives OutOfMemoryException.

This is because a lot of obviously not shortest paths are being investigated.

3-rd step: We need to make sure that each intermediate node is not encountered at the previous levels:

public class EndNodeAndNotDeeperEvaluator implements Evaluator
{
    private Node endNode;
    private Map<Long,Integer> nodeDepths = new HashMap(100000);

    public EndNodeAndNotDeeperEvaluator(Node node) {
        endNode = node;
    }

    @Override
    public Evaluation evaluate(Path path) {
        Node pEndNode = path.endNode();

        Integer nodeDepth = nodeDepths.get(pEndNode.getId());
        if (nodeDepth == null) {
            nodeDepths.put(pEndNode.getId(), path.length());
        }
        else if (path.length() > nodeDepth) {
            return Evaluation.EXCLUDE_AND_PRUNE;
        }

        if (pEndNode.equals(endNode)) {
            //System.err.println(" map.size="+nodeDepths.size());
            return Evaluation.INCLUDE_AND_PRUNE;
        }

        return Evaluation.EXCLUDE_AND_CONTINUE;
    }
}

And now it works for all shortest paths that I have.
But not very quickly... For longest paths (length=81) it takes about 6700ms...
While the usual traversal with Uniqueness.NODE_GLOBAL takes 550ms (finds only first path);
And the built in GraphAlgoFactory.shortestPath(...).findAllPaths(...) takes 90ms!