Traversing a graph

This page describes how to traverse a graph using the Traversal Framework.

The Matrix example

This example of a traversed graph uses some of the characters featured in the film trilogy "The Matrix". The source code can be found in NewMatrix.java.

Figure 1. Matrix node space view

The following is an example of how to define the TraversalDescription to find all the friends and friends of friends of a person X, and how to return the results excluding the person X:

private Traverser getFriends( Transaction transaction, final Node person )
{
    TraversalDescription td = transaction.traversalDescription()
            .breadthFirst()
            .relationships( RelTypes.KNOWS, Direction.OUTGOING )
            .evaluator( Evaluators.excludeStartPosition() );
    return td.traverse( person );
}

Perform the actual traversal and print the names of all found friends:

int numberOfFriends = 0;
String output = neoNode.getProperty( "name" ) + "'s friends:\n";
Traverser friendsTraverser = getFriends( tx, neoNode );
for ( Path friendPath : friendsTraverser )
{
    output += "At depth " + friendPath.length() + " => "
              + friendPath.endNode()
                      .getProperty( "name" ) + "\n";
    numberOfFriends++;
}
output += "Number of friends found: " + numberOfFriends + "\n";

The traversal returns the following output:

Thomas Anderson's friends:
At depth 1 => Morpheus
At depth 1 => Trinity
At depth 2 => Cypher
At depth 3 => Agent Smith
Number of friends found: 4

Solving the Matrix

To find the mastermind behind "The Matrix", follow all outgoing relationships that have the type KNOWS or CODED_BY. The final node connected to the relationship CODED_BY will be the Matrix’s coder.

private Traverser findHackers( Transaction transaction, final Node startNode )
{
    TraversalDescription td = transaction.traversalDescription()
        .breadthFirst()
        .relationships( RelTypes.CODED_BY, Direction.OUTGOING )
        .relationships( RelTypes.KNOWS, Direction.OUTGOING )
        .evaluator(Evaluators.includeWhereLastRelationshipTypeIs( RelTypes.CODED_BY ) );
    return td.traverse( startNode );
}

Here is how to print out the result and find all hackers:

String output = "Hackers:\n";
int numberOfHackers = 0;
Traverser traverser = findHackers( tx, getNeoNode( tx ) );
for ( Path hackerPath : traverser )
{
    output += "At depth " + hackerPath.length() + " => " + hackerPath.endNode().getProperty( "name" ) + "\n";
    numberOfHackers++;
}
output += "Number of hackers found: " + numberOfHackers + "\n";

Now you know who coded the Matrix:

Hackers:
At depth 4 => The Architect
Number of hackers found: 1

Walking an ordered path

The following example shows how to use a custom Evaluator to find paths that adhere to a predefined order. The source code can be found in OrderedPath.java.

First, you create the example graph that will be traversed over:

Node A = tx.createNode();
Node B = tx.createNode();
Node C = tx.createNode();
Node D = tx.createNode();

A.createRelationshipTo( C, REL2 );
C.createRelationshipTo( D, REL3 );
A.createRelationshipTo( B, REL1 );
B.createRelationshipTo( C, REL2 );

When setting up the traversal of the graph, store the order of the relationships (REL1 → REL2 → REL3) in an ArrayList. Upon traversal, the Evaluator can check against it to ensure that the only paths included and returned have the predefined order of relationships:

final ArrayList<RelationshipType> orderedPathContext = new ArrayList<>();
orderedPathContext.add( REL1 );
orderedPathContext.add( REL2 );
orderedPathContext.add( REL3 );
TraversalDescription td = tx.traversalDescription()
    .evaluator( new Evaluator()
    {
        @Override
        public Evaluation evaluate( final Path path )
        {
            if ( path.length() == 0 )
            {
                return Evaluation.EXCLUDE_AND_CONTINUE;
            }
            RelationshipType expectedType = orderedPathContext.get( path.length() - 1 );
            boolean isExpectedType = path.lastRelationship()
                    .isType( expectedType );
            boolean included = path.length() == orderedPathContext.size() && isExpectedType;
            boolean continued = path.length() < orderedPathContext.size() && isExpectedType;
            return Evaluation.of( included, continued );
        }
    } )
    .uniqueness( Uniqueness.NODE_PATH ); (1)

Note that the uniqueness is set to Uniqueness.NODE_PATH. This makes it possible to revisit the same node during the traversal, but not the same path.

Then, you can perform the traversal and print all ordered paths found:

Traverser traverser = td.traverse( tx.getNodeById( A.getId() ) );
PathPrinter pathPrinter = new PathPrinter( "name" );
for ( Path path : traverser )
{
    output += Paths.pathToString( path, pathPrinter );
}

This returns the following output:

(A)--[REL1]-->(B)--[REL2]-->(C)--[REL3]-->(D)

In this case, a customized class is used to format the path output.

static class PathPrinter implements Paths.PathDescriptor<Path>
{
    private final String nodePropertyKey;

    public PathPrinter( String nodePropertyKey )
    {
        this.nodePropertyKey = nodePropertyKey;
    }

    @Override
    public String nodeRepresentation( Path path, Node node )
    {
        return "(" + node.getProperty( nodePropertyKey, "" ) + ")";
    }

    @Override
    public String relationshipRepresentation( Path path, Node from, Relationship relationship )
    {
        String prefix = "--", suffix = "--";
        if ( from.equals( relationship.getEndNode() ) )
        {
            prefix = "<--";
        }
        else
        {
            suffix = "-->";
        }
        return prefix + "[" + relationship.getType().name() + "]" + suffix;
    }
}

Uniqueness of Paths in traversals

The following example demonstrates the use of node uniqueness. It lists all pets descended from other pets that are owned by Principal1:

Descendants example graph

uniqueness of paths in traversals graph

To return all descendants of Pet0 which are owned by Principal1 (i.e. Pet1 and Pet3), the uniqueness of the traversal needs to be set to NODE_PATH rather than the default NODE_GLOBAL. This way, nodes can be traversed more than once, and paths that have different nodes with some in common (like the start and the end nodes) can be returned.

Node dataTarget = data.get().get( "Principal1" );
String output = "";
int count = 0;
try ( Transaction transaction = graphdb().beginTx() )
{
    start = transaction.getNodeById( start.getId() );
    final Node target = transaction.getNodeById( dataTarget.getId() );
    TraversalDescription td = transaction.traversalDescription()
            .uniqueness( Uniqueness.NODE_PATH )
            .evaluator( new Evaluator()
    {
        @Override
        public Evaluation evaluate( Path path )
        {
            boolean endNodeIsTarget = path.endNode().equals( target );
            return Evaluation.of( endNodeIsTarget, !endNodeIsTarget );
        }
    } );

    Traverser results = td.traverse( start );
}

This will return the following paths:

(2)-[descendant,2]->(0)<-[owns,5]-(1)
(2)-[descendant,0]->(5)<-[owns,3]-(1)

You can also see how this differs from using NODE_GLOBAL uniqueness. Note that the TraversalDescription object is immutable, so a new instance is required.

TraversalDescription nodeGlobalTd = tx.traversalDescription().uniqueness( Uniqueness.NODE_PATH ).evaluator( new Evaluator()
{
    @Override
    public Evaluation evaluate( Path path )
    {
        boolean endNodeIsTarget = path.endNode().equals( target );
        return Evaluation.of( endNodeIsTarget, !endNodeIsTarget );
    }
} ).uniqueness( Uniqueness.NODE_GLOBAL );
Traverser results = nodeGlobalTd.traverse( start );

Now only one path is returned because the node Principal1 can only be traversed once:

(2)-[descendant,2]->(0)<-[owns,5]-(1)