2  Theory

The data structures and algorithms behind graphfast

Almost everything graphfast does reduces to one question: which things are transitively connected? That question is answered by a disjoint-set (Union–Find) structure, so it is worth understanding it well — the rest of the package is engineering around it.

2.1 Connected components

A graph is a set of nodes joined by edges. A connected component is a maximal set of nodes such that there is a path between any two of them. Computing components is the canonical “group the related things” operation:

  • In a social graph, components are isolated friend circles.
  • In record linkage, a component is one real-world entity assembled from many rows that share phone numbers, emails, etc.
  • In infrastructure, a component is a sub-network that can still reach itself after some links are removed.

2.1.1 Union–Find (disjoint sets)

Union–Find maintains a forest where each tree is one component. Every node has a parent; following parents leads to a root that names the component. Two operations:

  • find(x) — return the root of x’s tree.
  • union(x, y) — merge the trees containing x and y.

Building components is then trivial: start with every node as its own root, then union the endpoints of every edge. Afterwards, two nodes are in the same component if they share a root.

edges: 1-2, 2-3, 5-6

  1        becomes      2
  |                    / \
  2          ->       1   3        (one tree = {1,2,3})
  |
  3                    6
                       |
  5 - 6                5            (another tree = {5,6})

2.1.2 Two optimisations that make it fast

A naive forest can degrade to a linked list (O(n) per find). Two classic tricks keep it almost flat:

  1. Union by rank — when merging, hang the shorter tree under the taller one, so trees stay shallow. graphfast tracks a rank per root for this.

  2. Path compression / halving — while walking up to the root, point nodes closer to the root so future walks are shorter. graphfast uses path halving (parent[x] = parent[parent[x]]) inside an iterative find:

    int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];  // halve the path
        x = parent[x];
    }
    return x;
}

    Iterative (rather than recursive) matters at scale: a recursive find on a graph with a long chain can overflow the C call stack on hundreds of millions of nodes. Path halving gives the same asymptotics as full compression while touching each node at most once per call.

2.1.3 Complexity

With both optimisations, a sequence of m operations over n elements runs in

\[ O\!\big(m \cdot \alpha(n)\big) \]

where \(\alpha\) is the inverse Ackermann function. \(\alpha(n) \le 4\) for any \(n\) that fits in this universe, so component construction is effectively linear in the number of edges. Memory is \(O(n)\): two integer arrays (parent, rank) of length n_nodes.

2.1.4 Relabelling roots

Roots are arbitrary integers in [0, n_nodes). To return tidy, consecutive component ids 1..k, graphfast makes a single pass assigning each new root the next id. Because roots live in a known bounded range, this uses a flat vector<int> of size n_nodes (an O(n) lookup) rather than a hash map or a balanced tree (std::map, O(n log n) plus per-node allocations). This is the kind of constant-factor decision that dominates wall-clock time once you are in the tens-of-millions regime.

2.2 Shortest paths

For unweighted graphs the shortest path (in hops) between two nodes is found by breadth-first search (BFS). From the source, explore all neighbours at distance 1, then distance 2, and so on; the first time you reach the target you have the shortest distance. BFS is O(n + m) per query.

graphfast is optimised for many queries against one graph:

  • The adjacency list is built once, with each node’s neighbour vector pre-reserved to its exact degree (counted in a first pass), avoiding repeated reallocations.
  • A single distance buffer is reused across all queries. Instead of re-zeroing an n_nodes-length array per query (which alone is O(n_nodes) per query and dominates when queries are short), nodes carry a visited “version” stamp; bumping the version invalidates the previous query’s marks in O(1).
  • An optional max_distance lets BFS terminate early once the frontier exceeds the depth you care about.

Unreachable pairs return -1. The algorithm stores no full distance matrix, so memory stays at O(n + m).

TipComponents first, paths second

If you only need to know whether two nodes are connected (not how far apart), use are_connected() — it builds Union–Find once and answers each query in near-constant time, far cheaper than a BFS per pair.

2.3 Graph statistics

graph_statistics() computes degree per node in a single O(m) pass over the edges, then derives min/mean/max degree and density. Density for an undirected simple graph is

\[ \text{density} = \frac{m}{\binom{n}{2}} = \frac{2m}{n(n-1)}. \]

No adjacency matrix is materialised, so this is safe on graphs where an \(n \times n\) matrix would be impossible.

2.4 Entity resolution as a graph problem

“Group all records that share a phone number, or an email, or any value across these columns” is a connected-components problem in disguise. Two equivalent reductions are used:

2.4.1 1. Value-keyed Union–Find (group_id())

Treat each row as a node. For every column value, collect the rows that carry it; union those rows together. Rows end up in the same component exactly when a chain of shared values links them. Incomparable values ("", "NA", "Unknown", …) are skipped so they never glue unrelated rows. This runs in \(O(N \cdot \alpha(N))\) over the N total cell values and is the default engine, with a specialised numeric-only fast path.

2.4.2 2. Bipartite edge reduction (set_group_id())

Build a bipartite graph with two kinds of node — row ids and values — and an edge for every (row, value) pair. The connected components of this graph are the entity groups. This phrasing lets the same component machinery (edge_components()) and data.table::melt() do the work, which can be the faster route when columns are very wide.

Both are the same idea: shared value ⇒ edge ⇒ same component.

2.5 Why node-ID remapping matters

The core C++ routines index a parent array directly by node id, so they want a dense id space 1..n_nodes. If your ids are sparse or huge (e.g. account numbers up to \(10^{12}\)), allocating an array up to the maximum id is wasteful or impossible.

  • find_connected_components() assumes a reasonably dense space and warns/stops if the implied allocation is large.
  • find_connected_components_safe() and add_component_column() remap the observed ids to 1..(unique nodes) first, using fastmatch::fmatch(). fmatch builds a hash once and reuses it, so mapping millions of ids is fast and light — far better than coercing every id as.character() and doing named-vector lookups.
  • find_connected_components_large() extends this to ids beyond the 32-bit integer range by keeping them as doubles until after remapping.

2.6 Why C++ / Rcpp

The hot loops — one pass per edge for union, one pass per node for relabelling, BFS frontier expansion — are tight integer work. In interpreted R each iteration carries per-element overhead; in compiled C++ they are a few machine instructions over contiguous memory. Rcpp lets the package keep R’s ergonomic interface (matrices, data.table, named lists) while the inner loops run at native speed, and .registration = TRUE exposes the compiled routines safely.

2.7 Design principles, summarised

  • One idea, done well. Union–Find + BFS cover components, connectivity, grouping, and distance.
  • No heavyweight graph object. Consume edge lists; return plain vectors.
  • Keep the R glue cheap. data.table for I/O by reference, fastmatch for id mapping, minimal copying.
  • Mind the constant factors. Flat arrays over maps, iterative over recursive, reuse buffers, reserve capacity. At 100M edges, constants are the runtime.