Prev |  | Next

## 9.2. Traversal Framework Java API

The traversal framework consists of a few main interfaces in addition to `Node` and `Relationship`: `TraversalDescription`, `Evaluator`, `Traverser` and `Uniqueness` are the main ones. The `Path` interface also has a special purpose in traversals, since it is used to represent a position in the graph when evaluating that position. Furthermore the `RelationshipExpander` and `Expander` interfaces are central to traversals, but users of the API rarely need to implement them. There are also a set of interfaces for advanced use, when explicit control over the traversal order is required: `BranchSelector`, `BranchOrderingPolicy` and `TraversalBranch`.

### 9.2.1. TraversalDescription

The `TraversalDescription` is the main interface used for defining and initializing traversals. It is not meant to be implemented by users of the traversal framework, but rather to be provided by the implementation of the traversal framework as a way for the user to describe traversals. `TraversalDescription` instances are immutable and its methods returns a new `TraversalDescription` that is modified compared to the object the method was invoked on with the arguments of the method.

#### Relationships

Adds a relationship type to the list of relationship types to traverse. By default that list is empty and it means that it will traverse all relationships, irregardless of type. If one or more relationships are added to this list only the added types will be traversed. There are two methods, one including direction and another one excluding direction, where the latter traverses relationships in both directions.

### 9.2.2. Evaluator

`Evaluator`s are used for deciding, at each position (represented as a `Path`): should the traversal continue, and/or should the node be included in the result. Given a `Path`, it asks for one of four actions for that branch of the traversal:

- `Evaluation.INCLUDE_AND_CONTINUE`: Include this node in the result and continue the traversal
- `Evaluation.INCLUDE_AND_PRUNE`: Include this node in the result, but don’t continue the traversal
- `Evaluation.EXCLUDE_AND_CONTINUE`: Exclude this node from the result, but continue the traversal
- `Evaluation.EXCLUDE_AND_PRUNE`: Exclude this node from the result and don’t continue the traversal

More than one evaluator can be added. Note that evaluators will be called for all positions the traverser encounters, even for the start node.

### 9.2.3. Traverser

The `Traverser` object is the result of invoking `traverse()` of a TraversalDescription object. It represents a traversal positioned in the graph, and a specification of the format of the result. The actual traversal is performed lazily each time the `next()`-method of the iterator of the `Traverser` is invoked.

### 9.2.4. Uniqueness

Sets the rules for how positions can be revisited during a traversal as stated in `Uniqueness`. Default if not set is `NODE_GLOBAL`.

A Uniqueness can be supplied to the TraversalDescription to dictate under what circumstances a traversal may revisit the same position in the graph. The various uniqueness levels that can be used in Neo4j are:

- `NONE` - any position in the graph may be revisited.
- `NODE_GLOBAL` uniqueness - no node in the entire graph may be visited more than once. This could potentially consume a lot of memory since it requires keeping an in-memory data structure remembering all the visited nodes.
- `RELATIONSHIP_GLOBAL` uniqueness - no relationship in the entire graph may be visited more than once. For the same reasons as NODE_GLOBAL uniqueness, this could use up a lot of memory. But since graphs typically have a larger number of relationships than nodes, the memory overhead of this uniqueness level could grow even quicker.
- `NODE_PATH` uniqueness - a node may not occur previously in the path reaching up to it.
- `RELATIONSHIP_PATH` uniqueness - a relationship may not occur previously in the path reaching up to it.
- `NODE_RECENT` uniqueness - Similar to NODE_GLOBAL uniqueness in that there is a global collection of visited nodes each position is checked against. This uniqueness level does however have a cap on how much memory it may consume in the form of a collection that only contains the most recently visited nodes. The size of this collection can be specified by providing a number as the second argument to the TraversalDescription.uniqueness()-method along with the uniqueness level.
- `RELATIONSHIP_RECENT` uniqueness - works like NODE_RECENT uniqueness, but with relationships instead of nodes.

#### Depth First / Breadth First

These are convenience methods for setting preorder depth-first/ breadth-first `BranchSelector`|`ordering` policies. The same result can be achieved by calling the `order` method with ordering policies from the `Traversal` `factory`, or to write your own `BranchSelector`/`BranchOrderingPolicy` and pass in.

### 9.2.5. Order - How to move through branches?

A more generic version of depthFirst/breadthFirst methods in that it allows an arbitrary `BranchOrderingPolicy` to be injected into the description.

### 9.2.6. BranchSelector

A BranchSelector is used for selecting which branch of the traversal to attempt next. This is used for implementing traversal orderings. The traversal framework provides a few basic ordering implementations:

- `Traversal.preorderDepthFirst()` - Traversing depth first, visiting each node before visiting its child nodes.
- `Traversal.postorderDepthFirst()` - Traversing depth first, visiting each node after visiting its child nodes.
- `Traversal.preorderBreadthFirst()` - Traversing breadth first, visiting each node before visiting its child nodes.
- `Traversal.postorderBreadthFirst()` - Traversing breadth first, visiting each node after visiting its child nodes.

| Note
Please note that breadth first traversals have a higher memory overhead than depth first traversals.

BranchSelectors carries state and hence needs to be uniquely instantiated for each traversal. Therefore it is supplied to the TraversalDescription through a BranchOrderingPolicy interface, which is a factory of BranchSelector instances.

A user of the Traversal framework rarely needs to implement his own BranchSelector or BranchOrderingPolicy, it is provided to let graph algorithm implementors provide their own traversal orders. The Neo4j Graph Algorithms package contains for example a BestFirst order BranchSelector/BranchOrderingPolicy that is used in BestFirst search algorithms such as A* and Dijkstra.

#### BranchOrderingPolicy

A factory for creating BranchSelectors to decide in what order branches are returned (where a branch’s position is represented as a `Path` from the start node to the current node). Common policies are `depth-first` and `breadth-first` and that’s why there are convenience methods for those. For example, calling `TraversalDescription#depthFirst()` is equivalent to:

    description.order( Traversal.preorderDepthFirst() );

#### TraversalBranch

An object used by the BranchSelector to get more branches from a certain branch. In essence these are a composite of a Path and a RelationshipExpander that can be used to get new `TraversalBranch`es from the current one.

### 9.2.7. Path

A `Path` is a general interface that is part of the Neo4j API. In the traversal API of Neo4j the use of Paths are twofold. Traversers can return their results in the form of the Paths of the visited positions in the graph that are marked for being returned. Path objects are also used in the evaluation of positions in the graph, for determining if the traversal should continue from a certain point or not, and whether a certain position should be included in the result set or not.

### 9.2.8. RelationshipExpander

The traversal framework use RelationshipExpanders to discover the relationships that should be followed from a particular node to further branches in the traversal.

### 9.2.9. Expander

A more generic version of relationships where a `RelationshipExpander` is injected, defining all relationships to be traversed for any given node. By default (and when using relationships) a default expander is used, where any particular order of relationships isn’t guaranteed. There’s another implementation which guarantees that relationships are traversed in order of relationship type, where types are iterated in the order they were added.

The `Expander` interface is an extension of the `RelationshipExpander` interface that makes it possible to build customized versions of an `Expander`. The implementation of `TraversalDescription` uses this to provide methods for defining which relationship types to traverse, this is the usual way a user of the API would define a `RelationshipExpander` - by building it internally in the `TraversalDescription`.

All the RelationshipExpanders provided by the Neo4j traversal framework also implement the Expander interface. For a user of the traversal API it is easier to implement the RelationshipExpander interface, since it only contains one method - the method for doing getting the relationships from a node, the methods that the Expander interface adds are just for building new Expanders.

### 9.2.10. How to use the Traversal framework

In contrary to Node#traverse a traversal description is built (using a fluent interface) and such a description can spawn traversers.

Figure 9.1. Hello World Graph

With the definition of the `RelationshipTypes` as

    private static enum Rels implements RelationshipType
    {
        LIKES, KNOWS
    }

The graph can be traversed with

    for ( Path position : Traversal.description()
            .depthFirst()
            .relationships( Rels.KNOWS )
            .relationships( Rels.LIKES, Direction.INCOMING )
            .prune( Traversal.pruneAfterDepth( 5 ) )
            .traverse( joe ) )
    {
      System.out.println( "Path from start node to current position is " + position );
    }

Since `TraversalDescription`s are immutable it is also useful to create template descriptions which holds common settings shared by different traversals, for example:

    final TraversalDescription FRIENDS_TRAVERSAL = Traversal.description()
            .relationships( Rels.KNOWS )
            .depthFirst()
            .uniqueness( Uniqueness.RELATIONSHIP_GLOBAL );

    // Don't go further than depth 3
    for ( Path position : FRIENDS_TRAVERSAL
              .prune( Traversal.pruneAfterDepth( 3 ) )
              .traverse( joe ) ) {}
    // Don't go further than depth 4
    for ( Path position : FRIENDS_TRAVERSAL
              .prune( Traversal.pruneAfterDepth( 4 ) )
              .traverse( joe ) ) {}

If you’re not interested in the `Path`s, but f.ex. the `Node`s you can transform the traverser into an iterable of nodes or relationships:

    for ( Node position : FRIENDS_TRAVERSAL.traverse( joe ).nodes() ) {}

The full source for this example is available at

TraversalTest.java

Copyright © 2011 Neo Technology

Prev | Up | Next
| Home |