neo4j/community — pull request #565 by tinwelint (2012-05-28 09:15:01+00:00)
Title: Additions and changes to the core traversal framework.

Here's a summary of the changes

:Bidirectional traversals:
The traversal framework has been about providing a starting point and a description of
how to traverse the graph from that starting point as well as criterias to know
what to look for and consider a match. In many scenarios both the start point and end
point of the returned traversal paths are known and will benefit greatly from traversing
from the two points and see where they meet in the middle. The benefit comes from that
less relationships needs to be traversed to find the paths. A first version of this ability
is now built in and such a traversal can be described with a BidirectionalTraversalDescription.

:AllPaths/AllSimplePaths are now bidirectional:
As a result of implementing bidirectional traversals in the framework the common "all paths"
and "all simple paths" algorithms now uses that bidirectional feature to reduce the number of
relationships needed to traverse to find the correct answer, and thus reducing time spent looking
for them.

:Multiple start nodes:
A traversal can be given multiple starting points, as opposed to just a single starting point.
This also applies to bidirectional traversal where multiple start points as well as multiple
end points can be given.

:PathExpander (RelationshipExpander for Paths):
RelationshipExpander is good for implementing intelligent traversers which change behavior
depending on where it is at the moment. The problem with RelationshipExpander is that it accepts
a Node as argument and hence lacks the full Path information provided by the traversal.
Therefore a PathExpander is added which accepts a Path as argument and can additionally get
and modify traversal branch state for even more intelligent traversals.

:TraversalBranch state:
Each path that a traverser follows (which of course can branch off into new branches recursively)
can get associated with a state which follows that particular branch as it expands further.
A PathExpander can see this state and also change it for children branches. It's there to further
allow for more intelligent PathExpander implementations.

:Metadata about the traversal:
Ever wondered how many relationships your traverser visited during the traversal?
Traverser#metadata() provides useful information, currently only number of traversed relationships
and number of returned paths.

:Path got more useful methods:
Paths are sometimes used for making decisions where to go next in a traversal (in for example
a PathExpander). Path#reverseNodes() and Path#reverseRelationshis() was added because it's more
often the case that it's the last part of a path that is interesting when making decisions.
A reverse nodes/relationships call returns an iterable for each node/relationship, starting
from the end of the path. It also allows for a cheaper implementation than Path#nodes() or
Path#relationships().

:Sort result from traversal:
A utility sort() method was added to TraversalDescription for getting the returned paths sorted
(given a Comparator). It will gather all result paths, sort them and return them sorted.

:Traversals produce less garbage and holds less memory:
Some memory and garbage considerations have been addressed so that each traversal takes less
memory and is a little lighter on the garbage generation.