Traversals in depth - Neo4j in Action - page 179

Take node 4 in figure 8.1 , as an example. If you start to traverse the graph from root node
1 using depth-first ordering, the traversal will need to walk almost the entire graph before
node 4 is found, because it's visited next to last. If you do the same using breadth-first or-
dering, node 4 will be visited fourth from the start, with half as many nodes visited on its
path.Astraversalspeedisdirectlyproportionatetothenumberofhops(ornodesvisitedon
the path), you could find the result in half the time if you used breadth-first ordering rather
than depth-first ordering.

If you're looking for node 5, the depth-first algorithm would yield the result in three hops,
and the breadth-first algorithm would need five.

The larger the graph gets, the bigger the impact of traversal ordering on traversal perform-
ance. To illustrate, create a graph where each node has exactly three descendants. Create a
starting node and connect it with three child nodes. Then take each of the three child nodes
and add three descendants to each of them. Then continue like that up to depth level 12.
The resulting graph will have 797,161 nodes and 797,160 relationships.

Now run a traversal to find a particular node at a specific depth level. As a measure of per-
formance, we'll use the number of nodes visited until the solution is found.

Note

The number of hops and nodes visited is directly related to the time needed to perform the
traversal. Usingactual times tomeasure performance wouldmaketheresultsdependent on
available hardware resources as well as the state of the caches, which we're trying to avoid
in this simple experiment. Neo4j can visit between tens of thousands and millions of nodes
per second, depending on the hardware, caches, and traversal complexity.

Table 8.1 illustrates the results of the experiment.

Table 8.1. The performance of a traversal depending on the location of node searched for and the traversal
algorithm used

Depth level Node location Depth-first Breadth-first

3 First on left side 3 13

3 Last on right side 767,637 39