Traversals in depth - Neo4j in Action - page 198

8.4. Bidirectional traversals
Inall the traversals you'vetried sofar,youwalked the graphfromthe single selected start-
ing node until you found the solution, or until you walked the entire graph. You haven't
had multiple starting points from which to start traversing the graph. This was a limitation
of the Neo4j Traversal API until Neo4j version 1.8, which introduced the concept of bid-
irectional traversals.
Let's consider a typical social network graph with thousands of users, similar to the graph
in figure 8.5 . Users who know each other are connected via a KNOWS relationship. One of
the typical traversal queries in such a graph would be “Are the selected two users (user 1
and user 2) in the same network?” (In other words, are the selected users connected, and, if
so, how?)
You can solve this problem by using the standard Traversal API: starting from user 1, fol-
low the KNOWS relationships; for each node you visit, check if that node is user 2. If it
is, you found the connection; if it isn't, you continue further, until you exhaust the entire
graph. This is a perfectly valid solution, but if the graph is very large and densely connec-
ted, finding the solution can be quite time-consuming.
What if you could start the traversal from user 1 in the direction of user 2, and at the same
time start another traversal from user 2 in the opposite direction? When the two traversals
meet (called the collision point ), you'll have found the connection, and you can determine
the full path between the users. This is exactly what bidirectional traversal allows you to
do. Figure 8.6 illustrates bidirectional traversal in action.