Traversal primitives as query building blocks

Note: Company names, engineers, incidents, numbers, and scaling scenarios in this article are hypothetical — even when they resemble real ones. See the full disclaimer.

"Find everyone within three handshakes of Sundar Pichai." "What is the shortest money trail from this flagged account to a known mule?" These are not single hops; they are patterns of hops, and those patterns have names, textbook implementations, and well-understood costs. Before learning Cypher or Gremlin, learn the primitives that Cypher and Gremlin compile into.

The thesis: seven primitives, infinite queries

There are roughly seven traversal primitives that account for almost every graph query in production. They are not a recent invention — Tarjan and Hopcroft were publishing O(V+E) algorithms for most of them in the early 1970s, decades before "graph database" was a product category. What graph databases did was take these textbook algorithms and run them efficiently against on-disk adjacency lists. The algorithms themselves remain unchanged.

Primitive 1: BFS, the workhorse

Breadth-first search is the primitive a graph engineer reaches for first. The shape: explore everything 1 hop from the source, then everything 2 hops away, then 3, and so on. The data structures are unforgivingly simple — a FIFO queue holding the frontier (nodes discovered but not yet expanded), a visited set holding everything seen so far, and an optional level/distance map. Why a FIFO queue: pop-from-front + push-to-back guarantees that nodes are dequeued in the order they were discovered. Combined with the fact that all edges have unit weight, that ordering is the shortest-path ordering. Switch to a LIFO stack and you get DFS; switch to a min-heap keyed by distance and you get Dijkstra. The data structure is the algorithm.

from collections import deque

def bfs(graph, source):
    """graph: dict[node] -> list[neighbour]. Returns dict[node] -> distance."""
    visited = {source: 0}
    queue = deque([source])
    while queue:
        node = queue.popleft()           # dequeue the frontier
        for neighbour in graph[node]:    # one pointer-chase per neighbour
            if neighbour not in visited:
                visited[neighbour] = visited[node] + 1
                queue.append(neighbour)
    return visited

That is the entire algorithm. Twelve lines, including the docstring. It runs in O(V+E) because every node is enqueued at most once and every edge is examined at most twice (once from each endpoint, in an undirected graph). Memory is O(V) for the visited set and the queue. Now layer on a bound — "stop after k hops" — and you have the most common production graph query in existence:

def bfs_bounded(graph, source, max_depth):
    visited = {source: 0}
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if visited[node] >= max_depth:
            continue                     # do not expand past the bound
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited[neighbour] = visited[node] + 1
                queue.append(neighbour)
    return visited

This is what powers "find everyone within 3 handshakes", "show me all accounts within 4 hops of a flagged transaction", and "expand the topic graph two levels around quantum-entanglement". The Cypher equivalent is MATCH (s)-[*1..3]-(x). The Gremlin equivalent is g.V(s).repeat(both()).times(3). Both compile to a bounded BFS exactly like the snippet above.

A subtle but important point: the cost of one BFS hop in a native graph engine (Neo4j, Memgraph) is roughly 1 µs of pointer-chase, not 100 µs of B-tree probe. So a 3-hop BFS over a graph where the average node has 30 neighbours touches about 30³ = 27,000 nodes and runs in roughly 27 ms — interactively fast. The same query on a Postgres-backed graph schema would take 2.7 seconds. This is why graph databases exist as a separate category: BFS is the most common graph operation, and BFS over native adjacency is two orders of magnitude faster than BFS over a relational schema.

Primitive 2: DFS, the path-finder

Switch the queue to a stack and BFS becomes DFS. The Python literally differs by one character — popleft() becomes pop():

def dfs(graph, source):
    visited = {source}
    stack = [source]
    while stack:
        node = stack.pop()              # LIFO — most recently discovered first
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                stack.append(neighbour)
    return visited

Same O(V+E). Different exploration order. DFS plunges down one branch as far as it can go, then backtracks. That is the right shape for problems where you care about paths rather than distances: "is there a path from A to B?", "find me any cycle", "compute a topological sort", "find all strongly connected components" (Tarjans 1972 algorithm — one DFS, three pointers per node, magic). DFS is also the natural fit for recursive descent, which is why most textbook implementations are recursive — though in production you almost always want the iterative stack version because Pythons recursion limit hits at depth 1000 and many real graphs are deeper than that.

When to choose DFS over BFS: cycle detection, topological sort, finding any path (not necessarily shortest), depth-limited tree-like traversals, and any recursive structure where the "go deep then come back" pattern is the natural one. When to choose BFS: shortest distance, level-bounded queries, anything where "how far?" is the question.

Primitive 3: Dijkstra, the weighted generalisation

BFS works because every edge has weight 1, so the FIFO order is the order of increasing distance. The moment edges have weights — distance in kilometres, money flow in rupees, latency in milliseconds, similarity score from 0 to 1 — that property breaks. BFS no longer finds the shortest weighted path. The fix: replace the FIFO queue with a min-priority heap keyed by accumulated distance. Pop the closest unsettled node, relax its outgoing edges (update distances if you found a shorter route), repeat.

import heapq

def dijkstra(graph, source):
    """graph: dict[node] -> list[(neighbour, weight)]."""
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:               # stale heap entry, skip
            continue
        for neighbour, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbour, float('inf')):
                dist[neighbour] = new_dist
                heapq.heappush(heap, (new_dist, neighbour))
    return dist

Cost: O((V+E) log V), dominated by the heap operations. Why log V on the heap: every edge can trigger one heap push, and every push and pop costs O(log V) because that is the depth of a binary heap holding up to V entries. The heap can contain stale entries (we lazy-update rather than decrease-key, since Pythons heapq does not support decrease-key), which is why the if d > dist[node]: continue` check exists — a node can be popped multiple times, but only the first pop counts.

The strict requirement: edge weights must be non-negative. With negative weights, Dijkstra is wrong (use Bellman-Ford in O(VE), or Johnsons algorithm for all-pairs). Almost every real-world weight is non-negative — distance, time, money, latency, count — so Dijkstra wins in practice. Variants worth knowing: A* (Dijkstra plus a heuristic, used by every routing engine on the planet), bidirectional Dijkstra (search from both endpoints, meet in the middle, halves the explored area), and contraction hierarchies (preprocess the graph for O(log V)` queries — what real navigation systems use).

Primitive 4: Floyd-Warshall, the all-pairs hammer

Sometimes you need every pairwise distance. Network analysis, small-world coefficient calculations, the diameter of a friendship cluster, transitive closure of a reachability graph. Run Dijkstra V times and you pay O(V × E log V). There is a simpler alternative: Floyd-Warshall, a triple for loop that fills in a V × V distance matrix.

def floyd_warshall(nodes, edges):
    INF = float('inf')
    dist = {(u, v): INF for u in nodes for v in nodes}
    for u in nodes:
        dist[(u, u)] = 0
    for u, v, w in edges:
        dist[(u, v)] = w
    for k in nodes:                      # try every node as intermediate
        for i in nodes:
            for j in nodes:
                if dist[(i, k)] + dist[(k, j)] < dist[(i, j)]:
                    dist[(i, j)] = dist[(i, k)] + dist[(k, j)]
    return dist

The cost is O(V³). That sounds awful, but the constant factor is tiny — three nested loops with one comparison and one assignment in the inner body. For V = 500 the inner loop body runs 125 million times, which Python does in a couple of seconds and a tight C implementation does in 50 milliseconds. So Floyd-Warshall is the right call up to a few hundred nodes; above that, run Dijkstra V times in parallel.

Primitive 5: PageRank and the centrality family

The questions BFS, DFS, and Dijkstra answer are all path questions — how do I get from A to B. A separate family asks importance questions — who matters in this graph. The canonical answer is PageRank, the algorithm that built Querion: each page`s rank is a weighted sum of the ranks of pages linking to it, divided by their out-degree, plus a damping term. Iterate until convergence:

def pagerank(graph, damping=0.85, iterations=50):
    N = len(graph)
    rank = {node: 1.0 / N for node in graph}
    for _ in range(iterations):
        new_rank = {node: (1 - damping) / N for node in graph}
        for node in graph:
            out_degree = len(graph[node]) or 1
            share = damping * rank[node] / out_degree
            for neighbour in graph[node]:
                new_rank[neighbour] += share
        rank = new_rank
    return rank

Same shape applies to betweenness centrality (how often does a node lie on shortest paths between other pairs), eigenvector centrality (a node is important if its neighbours are important — PageRank without the damping), and Katz centrality (PageRank with attenuation by path length). All of them are "iterate a local rule until the global structure stabilises" and all of them are bread-and-butter for fraud detection ("which accounts have suspiciously high betweenness in the money-flow graph?"), recommendation systems ("personalised PageRank rooted at the user"), and influence analysis on social graphs.

Primitive 6: Connected components

The simplest of all. Pick any unvisited node, run a BFS or DFS, label every node you reach with the same component ID. Pick the next unvisited node, increment the ID, repeat. Linear time, O(V+E). Used everywhere — clustering, dead-code analysis (a "garbage" object in a heap dump is one not in the same component as a GC root), connectivity sanity checks, partitioning a graph for parallel processing. The Union-Find variant is even faster for incremental updates: as edges arrive, union the endpoints, near-constant amortised time per operation.

Primitive 7: Pattern matching

The hardest primitive — and the one Cyphers MATCH clause is built around. Given a small "pattern" graph (e.g. "a person who knows a person who works at a company") and a large data graph, find all occurrences of the pattern. This is *subgraph isomorphism*, and in the general case it is NP-complete. Practical implementations cheat: they pick the most selective node in the pattern (lowest cardinality), look it up in an index, then expand outward via constrained BFS, pruning candidates that fail the patterns structural or property constraints. This is what Neo4js [query planner](https://neo4j.com/docs/cypher-manual/current/planning-and-tuning/) does, what TigerGraphs GSQL does, and what Apache TinkerPop`s pattern-matching steps do under the hood.

Composing primitives: the real-world skill

Here is the punchline: most real graph queries are compositions of two or three primitives plus set operations. Three examples:

• "Friends of friends who like the same products": BFS-2-hops on the social graph from user u, BFS-1-hop on the purchase graph from u, intersect the two result sets on product nodes. Three primitive calls, one set intersection.
• "Recommend articles like this one": Personalised PageRank rooted at the article you are reading, take the top 10 by rank. One primitive call.
• "Find suspicious accounts": Connected components on the transaction graph, filter to clusters where average transaction amount exceeds threshold X, then PageRank within each suspect cluster to find the central nodes. Two primitive calls plus filter.

The skill of writing fast graph queries is recognising which primitive each part of your problem is asking for, then ordering the primitives so the most selective one runs first. If your filter is "users who paid more than ₹1 lakh in a single transaction" and you have an index on transaction amount, run the filter first and BFS outward from the small candidate set — do not run BFS from every user and then filter.

A fraud detection example

import math, heapq
def cheapest_trail(graph, source, target):
    dist = {source: 0.0}
    heap = [(0.0, source, [source])]
    while heap:
        d, node, path = heapq.heappop(heap)
        if node == target:
            return path, d
        if d > dist[node]:
            continue
        for nbr, amount in graph[node]:    # edges with rupee amounts
            cost = d + (-math.log(amount))
            if cost < dist.get(nbr, float('inf')):
                dist[nbr] = cost
                heapq.heappush(heap, (cost, nbr, path + [nbr]))
    return None

Cost cheat-sheet

Internalise the following costs and you will pick the right primitive instinctively.

Common confusions

• "BFS and DFS are interchangeable — just pick whichever, the answer is the same." Only their vertex set is the same; the order in which they discover nodes is different, and many problems depend on that order. BFS guarantees that the first time you see a node, you have arrived along a shortest path (in unweighted edge count). DFS guarantees no such thing — its first-visit order is a depth-priority. So if you swap BFS for DFS in a "find the closest mutual friend" query, the answer is wrong; it will return some mutual friend along a deep branch, not the nearest one. The interchange only works for "is v reachable from s?", which is the only question that ignores order.

• "Dijkstra also works with negative weights, you just have to be careful." No. Dijkstra is provably incorrect on graphs with negative edges. The proof: Dijkstra settles a node the first time it pops out of the heap, but a later relaxation along a negative edge can shorten that node's distance, which Dijkstra has already locked in. Use Bellman-Ford in O(VE) for graphs with negative edges, and Bellman-Ford will additionally detect negative cycles (which make "shortest path" undefined). Real money-flow graphs almost never have negative weights — −log(amount) is bounded below for amount ≤ 1 but you typically clamp very tiny transfers — so the question rarely arises in payments fraud, but it is a constant trap in optimisation problems.

• "PageRank gives you the most-connected node." No — it gives you the node with the most important incoming links, recursively defined. A node with a thousand random followers can rank lower than a node with three followers who are themselves highly ranked. That is exactly what the algorithm is for: separating "high in-degree" from "high influence". On a fraud graph, high-in-degree might just mean a popular merchant; high PageRank from suspicious sources is what you actually want.

• "Floyd-Warshall is obsolete because Dijkstra is faster." Per-pair, yes. For all-pairs on a small dense graph (say V = 300, E = 30,000), Floyd-Warshall's V³ = 27 million inner-loop iterations beat V × Dijkstra = 300 × E log V ≈ 300 × 30,000 × 9 = 81 million heap operations, and the constant factors favour Floyd-Warshall by another order of magnitude. The triple-loop's three array accesses and one compare per iteration vectorise beautifully on modern CPUs; Dijkstra's heap does not. Below V ≈ 500, Floyd-Warshall wins.

• "Cypher's MATCH (a)-[*]-(b) is just BFS." Only if you bound the depth. Unbounded variable-length paths in Cypher are path enumeration, not BFS — every distinct path between the endpoints is materialised, and the count can be exponential in the graph diameter. Always write MATCH (a)-[*1..k]-(b) with a finite k. Neo4j's planner will refuse to run unbounded variable-length matches on large graphs precisely because of this trap.

• "Pattern matching is just a fancy join — Postgres can do it." It can, in the same way you can do BFS with recursive WITH CTEs. But subgraph isomorphism is NP-complete; the cost depends on the order in which you bind the pattern's nodes to data nodes, and a bad order is exponentially worse than a good one. Cypher's planner spends real CPU on this — it estimates cardinality at every pattern node and starts from the most selective one. A SQL JOIN chain has no equivalent — the join order is fixed at compile time and cannot react to per-pattern selectivity. You can implement subgraph isomorphism in SQL; you will not implement it efficiently.

Going deeper

The seven primitives are the trunk; each has a branch of variations and refinements that production systems actually use. This section walks the three most important ones — A on top of Dijkstra, Tarjan's strongly-connected-components on top of DFS, and personalised PageRank on top of PageRank — and ends with the connection to labelled property graphs, where every primitive picks up an extra parameter: the edge label.*

A* — Dijkstra plus a heuristic, for road networks

Dijkstra explores radially in all directions from the source until it reaches the target. If you know roughly where the target is — say, you are routing a truck from Coimbatore to Chennai and you have the GPS coordinates of both — you can bias the exploration toward the target and skip vast areas that obviously cannot contain a shorter path. That bias is the A algorithm*: replace the heap key from g(v) (cost-so-far) to g(v) + h(v) (cost-so-far plus a heuristic estimate of remaining cost). Why A* is still correct: as long as the heuristic h never overestimates the true remaining cost (it is "admissible"), the first time A* pops the target out of the heap, it has found the optimal path. The straight-line Euclidean distance to the goal is admissible for road graphs because no real road is shorter than a straight line. Every modern routing engine — Google Maps, OpenStreetMap's OSRM, India's own MapmyIndia — runs some descendant of A* under the hood, usually combined with contraction hierarchies that preprocess the graph so each query is O(log V) instead of O(E log V).

Tarjan's SCC — one DFS, three pointers, one stack

Strongly connected components (SCCs) are clusters where every node can reach every other node by following directed edges. The naive algorithm runs DFS from every node and intersects the reachability sets — O(V × (V+E)). Tarjan's 1972 algorithm computes all SCCs in one DFS, O(V+E), by maintaining for each node v two pointers: index[v] (the order in which v was discovered) and lowlink[v] (the smallest index reachable from v in the DFS tree). When the DFS finishes a node v with index[v] == lowlink[v], that node is the root of an SCC, and everything pushed onto an auxiliary stack since v was first discovered is the SCC's vertex set. The whole algorithm is forty lines of Python. SCCs matter in deadlock detection ("a deadlock is an SCC of size ≥ 2 in the wait-for graph"), in static analysis ("the strongly-connected components of the call graph are the recursive cliques"), and in fraud — circular money flow is an SCC. Most graph databases ship Tarjan as a built-in: Neo4j's GDS exposes it as gds.scc.stream.

Personalised PageRank — recommendations rooted at one node

Plain PageRank gives a global ranking — Querion's "most important pages on the web". Personalised PageRank gives a ranking from one specific node's perspective: instead of teleporting uniformly to a random node when the random walker gets bored, teleport back to the seed node s. The result is a probability distribution that scores every node by how relevant it is to s. Pinscope uses this to power "more like this" recommendations; Chirpline uses it for the "Who to follow" panel; the GraphSAGE family of graph neural nets uses an approximate variant during training. The algorithm is two-line modification to PageRank's iteration: replace (1 − damping) / N with (1 − damping) if node == s else 0. The cost is the same O(k × (V+E)); the result is dramatically more useful when the question is "what is most similar to the article Asha is reading right now" rather than "which articles are globally popular".

Property-graph variants — each primitive picks up a label parameter

In a property graph (Cypher, Gremlin, GQL), edges carry labels like :FOLLOWS, :LIKES, :TRANSFERRED, :PURCHASED. Every primitive in this chapter has a label-parameterised version. BFS becomes BFS over edges where label ∈ {L₁, L₂}. Dijkstra becomes Dijkstra weighted by amount, restricted to edges of label :TRANSFERRED. Pattern matching becomes the entire substance of the Cypher MATCH clause. The cost stays the same — adding a label filter is a constant-time check at each edge — but the answers change drastically: BFS-3-hops over :FOLLOWS returns "third-degree friends", while BFS-3-hops over :FOLLOWS or :LIKES mixes the social and interest graphs and returns something closer to "people whose taste resembles yours". This is why graph engines beat relational schemas not on raw traversal cost but on expressivity: the same primitive run with a different label set is a different query, with no schema change required.

The cost model in practice

A back-of-envelope worth memorising for Indian-scale workloads. UPI in early 2026 processes ~14 billion transactions per month — about 5,400 per second average, with peaks of around 50,000 tps during festival evenings. Storing a year's worth of UPI transactions as a graph (one node per account, one edge per transaction) is roughly 2 billion edges. A BFS-3-hops query at average degree 30 visits 27,000 edges and finishes in around 30 ms on a single Neo4j instance with the index-free adjacency layout. A Dijkstra over the full graph touches all 2 billion edges and takes minutes — which is why fraud teams at companies like NPCI, PaisaBridge, and DigiPaisa pre-compute connected components nightly, restrict Dijkstra to the suspect component, and only run global pattern matching as a periodic batch. The lesson: which primitive you choose is half the engineering; how much of the graph you let the primitive see is the other half.

Where this is going

You now have the vocabulary. A query like Cyphers MATCH (u:User {id:42})-[:FOLLOWS*1..2]-(f)-[:LIKES]->(p:Product)<-[:LIKES]-(u) RETURN p is no longer mysterious — it is bounded BFS to depth 2 from user 42, then a 1-hop expansion along the LIKES edge, then a set intersection with user 42s own LIKES set. Three primitives, one set operation. The next chapter takes the Cypher and Gremlin query languages apart line by line and shows exactly how each clause compiles down to the primitives in this chapter, executed against the index-free adjacency layout of the previous one. After that, the rest of part 20 covers transactions on graphs, distributed graph storage with TigerGraph and JanusGraph, and the property-graph extensions (GQL, the new ISO standard) that are landing in 2026.

References

1. Tarjan, R. Data Structures and Network Algorithms. SIAM, 1983. The canonical text on graph algorithms and their analysis.
2. Robinson, I., Webber, J., Eifrem, E. Graph Databases (2nd edition), O`Reilly, 2015. Chapter 4 covers traversal patterns and Cypher decomposition in detail.
3. Neo4j. Traversal Framework Reference — the procedural API for custom BFS/DFS over the native store.
4. Apache TinkerPop. Gremlin Traversal Steps — the reference for graph traversal as a fluent DSL.
5. Boost. Boost Graph Library — the C++ implementation reference for every primitive in this chapter.
6. Page, L., Brin, S. The PageRank Citation Ranking, Stanford technical report, 1999. The original derivation.