# 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()
.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()
.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<>();
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

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)``