cancel
Showing results for 
Search instead for 
Did you mean: 

Join the community at Nodes 2022, our free virtual event on November 16 - 17.

Traversing a graph in neo4j

ramikaraki747
Node Link

Hey there,

Hope this year be the best for all of you,
While I was learning this online training course (Overview of Neo4j 4.x) I learned that there are 3 different types of traversing a graph (walk, trail and path)

how to achieve this in cypher , apoc or GDSL .

I mean what procedures like (shortestPath) can we use to find a path?
or a path in general, not the shortest one only?

Thanks

4 REPLIES 4

Hello,

Although Cypher uses the term "path", these actually adhere to the "trail" technical definition: nodes can be revisited, but no relationship can be repeated per Cypher "path". This is also referred to as relationship isomorphism.

More info on that here:

As for shortestPath(), when using shortestPath() in a MATCH, this should return actual "paths" that also adhere to the technical definition. By default no repeat of a node or relationship can happen per path, because a repeat would mean that there is a shorter path not taken. shortestPath() uses a breadth-first exploration, so a shortest path will be found naturally before any longer path with repeats can be found. The caveat here is that when using shortestPath(), the start and end nodes MUST be known and found first before the expansion. This is the difference between "find me the shortest path from this starting node to the first node of this other type" (which it does NOT do, and if you need to do this then you need to use a different approach), vs "for every combination of this starting node and every node of this other type, find me the shortest path for each of those resulting pairs" (which is how shortestPath() behaves).

When using the traversal API or APOC path expander procedures, you have additional options for how to handle uniqueness during expansion. Here are the types that can be used:

The notable ones here are RELATIONSHIP_PATH (this is identical to Cypher's default relationship isomorphism during expansion), NODE_PATH (nodes must be unique per path, so this fits the technical definition of a "trail"), and NODE_GLOBAL (a node can only be visited once across all paths generated from the expansion...this means that once a path is found to a given node, no other alternate path to that node will be considered. This is good for reachability queries).

GDS has its own pathfinding algos that can be useful depending on what you need:

Hi @andrew.bowman , thanks a lot for this amazing explanation answer it was very helpful
so no way to find a path using walk traverse I mean (repeated node, repeated relationship)?

I was facing an issue with finding path but using shortestPath, allsimplepath, Dijkstra.... all of them was returning nodes not needed in the path because of this (the node can ve revisited but no relationship will be repeated) actually I fixed that by excluding the nodes after finding the path.

For a walk, with the traversal API and APOC path expanders (excluding subgraphNodes(), subgraphAll(), and spanningTree(), which all use NODE_GLOBAL uniqueness) you can use the NONE uniqueness to remove restrictions on uniqueness.

perfect, thanks @andrew.bowman appreciated