Graph Diameter, in depth: eccentricity bounds, the double sweep, iFUB and BoundingDiameters measured, the SETH barrier and the traps on real graphs

Eccentricity, radius and the factor-of-two bound

Write d(u, v) for the shortest-path distance. The eccentricity of a vertex is ecc(v) = max over u of d(v, u), the distance to the vertex farthest from it. The diameter is the largest eccentricity, D = max ecc(v), and the radius is the smallest. Vertices achieving the radius form the center; vertices achieving the diameter form the periphery. On an unweighted graph a single breadth-first search from v yields ecc(v) in O(n + m) time, so the textbook algorithm runs n searches for O(nm) total. On a weighted graph each search becomes Dijkstra and the cost becomes O(n m log n).

One inequality drives everything that follows. For any vertex v in an undirected connected graph, ecc(v) <= D <= 2 ecc(v). The left half is the definition; the right half is the triangle inequality, because any two vertices x and y satisfy d(x, y) <= d(x, v) + d(v, y) <= 2 ecc(v). So one search already pins the diameter within a factor of two. The same argument applied to individual vertices gives per-vertex bounds: after a search from v, every vertex w has ecc(w) >= d(v, w) (v itself is that far away) and ecc(w) >= ecc(v) - d(v, w), and ecc(w) <= ecc(v) + d(v, w). Each search therefore tightens a lower and an upper bound on every vertex's eccentricity at once.

Two traps come first. On a disconnected graph the diameter is infinite, and libraries either raise an error or silently report the largest finite value. On a directed graph d(u, v) and d(v, u) differ and the bound ecc(v) - d(v, w) fails.

Why there is no fast exact algorithm

Why not just find a clever exact algorithm? Because there is good evidence none exists. Roditty and Vassilevska Williams (STOC 2013) showed that, assuming the Strong Exponential Time Hypothesis, no algorithm running in O(n^2-ε) time can approximate the diameter of sparse graphs better than a factor of 3/2. The same paper gives an estimate D' with floor(2D/3) <= D' <= D in about O(m √n) expected time. For exact answers on sparse graphs, n searches is essentially the worst case you must accept.

The practical algorithms below keep that O(nm) worst case. They win because on real graphs a few well-chosen searches give lower and upper bounds that meet; when they do not, cost climbs back toward the baseline.

The double sweep and the 4-sweep

The double sweep searches from any vertex r, jumps to the farthest vertex a, searches again and reports ecc(a). On a tree that is exactly the diameter; on a general graph it is only a lower bound.

from collections import deque

def bfs(adj, s):
    """Unweighted distances from s; -1 marks unreachable vertices."""
    dist = [-1] * len(adj); dist[s] = 0; q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] < 0:
                dist[v] = dist[u] + 1; q.append(v)
    return dist

def double_sweep(adj, r):
    """Lower bound on the diameter: BFS from r, then from the farthest vertex a."""
    d = bfs(adj, r); a = max(range(len(adj)), key=d.__getitem__)
    da = bfs(adj, a); b = max(range(len(adj)), key=da.__getitem__)
    return da[b], a, b            # ecc(a) <= D, with a and b a candidate pair

How good is the bound? On the Barabasi-Albert graph with 5,000 vertices and 9,996 edges, whose true diameter is 9, the double sweep from 100 random start vertices returned 9 only 13 times; it returned 8 in 73 runs and 7 in 14. On the 50 by 100 grid it found the exact value 148 immediately, because the farthest vertex from anywhere is a corner and the opposite corner is the answer. A refinement, the 4-sweep of Crescenzi and colleagues, runs a double sweep, moves to the midpoint of the path it found, and runs a second double sweep from there. On the BA graph it reached 9 in eight searches. The midpoint is also a good guess at a central vertex, which matters for the next algorithm.

iFUB: searching from the centre outwards in

iFUB (iterative Fringe Upper Bound; Crescenzi, Grossi, Habib, Lanzi and Marino, Theoretical Computer Science 2013) turns one well-placed search into an exact answer. Search from a vertex u and group vertices by distance into fringes F₁, ..., F_e. Take any pair x, y where both lie at distance at most i - 1 from u: then d(x, y) <= 2(i - 1). So if some vertex in the outer fringes already has eccentricity larger than 2(i - 1), no pair of inner vertices can beat it, and the search can stop. iFUB walks inward one fringe at a time, computing the eccentricity of every vertex in the fringe, until the best eccentricity seen exceeds twice the remaining radius.

def ifub(adj, u):
    """Exact diameter of a connected undirected graph, searching from u outwards in."""
    du = bfs(adj, u); i = max(du)
    levels = {}
    for v, x in enumerate(du):
        levels.setdefault(x, []).append(v)       # fringe F_i: vertices at distance i
    lb, ub = i, 2 * i
    while ub > lb:
        bi = max(max(bfs(adj, z)) for z in levels[i])
        if max(lb, bi) > 2 * (i - 1):            # nobody closer can beat it
            return max(lb, bi)
        lb, ub, i = max(lb, bi), 2 * (i - 1), i - 1
    return lb

The cost is the number of vertices in the fringes it had to process, so it is excellent when the outer fringes are tiny and poor when they are wide. Started from the 4-sweep midpoint, it needed 5 searches on the BA graph with attached paths (the far tips of the paths are the only distant vertices), 147 on the plain BA graph, and 1,226 on the grid, where every fringe is a long diagonal and the stopping rule fires late. Starting from the highest-degree vertex instead gave 5, 129 and 2,378: the hub is a fine centre for a scale-free graph and a poor one for a grid.

BoundingDiameters: pruning by eccentricity bounds

BoundingDiameters (Takes and Kosters, CIKM 2011) keeps the per-vertex bounds from the definitions section for every vertex and uses them two ways. The global lower bound is the largest eccentricity computed so far; the global upper bound is the largest per-vertex upper bound still in play. A vertex is dropped from the candidate set once its eccentricity is known exactly, or once its upper bound cannot exceed the current lower bound and its lower bound is already at least half the upper bound, so it can neither raise D_lo nor be needed to lower D_hi. The next search alternates between the candidate with the largest upper bound (likely peripheral, raises D_lo) and the one with the smallest lower bound (likely central, lowers D_hi), breaking ties by degree.

import math

def bounding_diameters(adj):
    """Takes and Kosters (CIKM 2011): exact diameter from eccentricity bounds."""
    n = len(adj); lo = [0] * n; hi = [math.inf] * n
    W = set(range(n)); d_lo, d_hi = 0, math.inf; pick_high = True
    while W and d_lo < d_hi:
        if pick_high: v = max(W, key=lambda x: (hi[x], len(adj[x])))
        else:         v = min(W, key=lambda x: (lo[x], -len(adj[x])))
        pick_high = not pick_high
        d = bfs(adj, v); e = max(d)
        d_lo, d_hi = max(d_lo, e), min(d_hi, 2 * e)
        for w in W:
            lo[w] = max(lo[w], d[w], e - d[w])
            hi[w] = min(hi[w], e + d[w])
        W.discard(v)
        if W:
            d_hi = min(d_hi, max(d_lo, max(hi[w] for w in W)))
        W = {w for w in W
             if lo[w] != hi[w] and not (hi[w] <= d_lo and lo[w] >= d_hi / 2)}
    return d_lo

On the grid this needed only 9 searches: alternating peripheral and central picks settled almost every vertex's bounds quickly. On the plain BA graph it needed 68, on the BA graph with paths 3. NetworkX ships this method as the usebounds option of its diameter function, citing the same paper.

Worked example: three graphs, three behaviours

The three graphs side by side, counting searches (each is one BFS). The naive baseline ran one search per vertex and took between 24 and 38 seconds per graph in pure Python on the test machine; the bounded methods finish in well under a second when they need a few dozen searches.

The lesson is that neither exact method dominates. iFUB is simple, needs only one distance array at a time, and is very fast when a graph has a dense core with a few long tendrils, which is what many real networks look like. BoundingDiameters keeps two integers per vertex and an O(n) scan per step, and it is robust on lattice-like graphs (road networks, meshes) where iFUB's fringes are wide. Both are exact, so you can run one with a budget and fall back to the other.

Weighted, directed, disconnected and huge graphs

Weighted graphs. All of the bounds above rely only on the triangle inequality, so they carry over to non-negative edge weights unchanged; replace BFS with Dijkstra and the fringes of iFUB with distance-sorted vertices. Each search now costs O(m log n), so pruning matters even more.

Directed graphs. Eccentricity splits into forward and backward versions, and the bound ecc(v) - d(v, w) no longer holds. The directed variant of iFUB (DiFUB, by the same group) alternates forward and backward searches. If the graph is not strongly connected the diameter is infinite, so most tools report the diameter of the largest strongly connected component; say which in your output.

Disconnected graphs. Compute components first, then the diameter of each, or of the giant component only. A bare max over a distance array that uses -1 or infinity for unreachable vertices gives a wrong answer in both directions.

Graphs too big for any exact method. Social-network studies report the effective diameter, the distance within which 90 percent of reachable pairs lie, estimated with probabilistic counters (HyperANF by Boldi, Rosa and Vigna) in a few passes over the edges. It is a distribution statistic, not the diameter, and it is far more stable: one long path changes D but barely moves the 90th percentile.

Failure modes

• Reporting a double sweep as the diameter. It is a lower bound; on the BA graph it was wrong 87 times in 100. Label it as such or run an exact method.
• Silent infinity. Unreachable vertices left at -1 make max() ignore them; left at infinity they make every vertex peripheral. Check connectivity first.
• Directed edges fed to undirected code. The pruning rules become unsound and the algorithm returns a confident wrong value, not an error.
• Unbounded runtime. Worst-case cost is still n searches. Put a search budget on any job that runs on user-supplied graphs and return [D_lo, D_hi] if it trips.

Trade-offs

For a dashboard number, a 4-sweep gives an interval in a handful of searches. For an exact value on a scale-free or core-periphery graph, iFUB is the shortest code and often the fastest. For lattices, road networks and unknown structure, BoundingDiameters is the safer default, at the cost of O(n) bound maintenance per step. For directed or disconnected inputs, define the quantity first; most bugs are definitional. For graphs too large to search dozens of times, report the effective diameter and do not call it the diameter.

What to do next

1. Write down whether your graph is directed, weighted and connected, and which quantity you want: exact D, D of the giant component, or effective diameter.
2. Implement the double sweep and the 4-sweep first; log D_lo and 2 ecc(start) as an interval on every run.
3. Add one exact method with a search budget. Start with BoundingDiameters if the graph is spatial and iFUB from the 4-sweep midpoint if it is scale-free.
4. Validate against the naive n-search answer on graphs of a few thousand vertices from your own data, as the table above did, and record the search counts.
5. In production, report D together with the number of searches used, so a structural change that makes the algorithm degrade shows up before it times out.
6. Read the tree diameter article for why the double sweep is exact on trees, the BFS article for direction-optimising search, BFS and DFS for traversal bugs, and multi-source BFS for sharing one frontier across many sources.