Graphs and Graph Algorithms Questions

Direct answer

Running depth-first search (DFS) on a directed graph and recording, for every vertex $v$, a discovery time $d[v]$ (when DFS first reaches $v$) and a finish time $f[v]$ (when DFS has fully explored everything reachable from $v$ and returns), every edge $(u,v)$ falls into exactly one of four categories based on how those two intervals relate: tree, forward, back, or cross.

Structured elaboration

• Tree edge. $(u,v)$ is the edge DFS actually used to first discover $v$; $v$ becomes a child of $u$ in the DFS tree. Formally, $d[u] < d[v] < f[v] < f[u]$, and $v$'s discovery immediately follows $u$'s.
• Forward edge. $(u,v)$ points to a vertex $v$ that is a descendant of $u$ in the DFS tree, but was NOT the edge that first discovered $v$ (some other tree edge got there first, deeper in the recursion). Formally, the same interval containment as a tree edge, $d[u] < d[v] < f[v] < f[u]$, but $(u,v)$ is not the tree edge itself.
• Back edge. $(u,v)$ points to an ANCESTOR of $u$ in the DFS tree, that is, to a vertex still "in progress" (discovered but not yet finished) when $u$ is processed. Formally, $d[v] < d[u] < f[u] < f[v]$, the ancestor's interval contains the descendant's.
• Cross edge. $(u,v)$ points to a vertex $v$ that is neither an ancestor nor a descendant of $u$, typically in an already-finished, unrelated branch of the DFS tree. Formally, the two intervals are disjoint: $f[v] < d[u]$.

Relation to cycle detection. A directed graph contains a cycle if and only if DFS finds at least one back edge. This is because a back edge $(u,v)$ points at a vertex $v$ still on the current recursion path (an ancestor), so the tree-path from $v$ down to $u$, plus the edge $u \to v$, forms an explicit cycle. No back edge means no such "return to an in-progress ancestor" ever happens, which is exactly the absence of a directed cycle.

Relation to topological sorting. A directed acyclic graph (DAG, a directed graph with no cycles) has no back edges by the fact above. For every edge $(u,v)$ in a DAG, DFS's structure guarantees $f[u] > f[v]$ (this holds for tree, forward, and cross edges alike, and back edges cannot occur). So sorting vertices by DECREASING finish time produces an order where every edge points from an earlier vertex to a later one, exactly the definition of a valid topological order.

Worked example

Take the directed graph: $A \to B$, $A \to C$, $B \to C$, $C \to D$, $D \to B$. Running DFS from A, visiting neighbors in listed order:

Classification summary: $A\to B$ and $B\to C$ (the first time, via $A \to B \to C$) and $C \to D$ are TREE edges (they are the edges DFS actually used to first discover B, C, and D). $D \to B$ is a BACK edge (reveals the cycle $B \to C \to D \to B$). $A \to C$ is a FORWARD edge (C already reachable and discovered as A's descendant before this edge is examined). This graph has no cross edge at all; a genuine cross-edge example needs two sibling subtrees, for instance adding a vertex E with edges $A \to E$ and $E \to C$ after C is already finished would make $E \to C$ a cross edge (pointing into an already-finished, unrelated branch).

Trade-offs and pitfalls

• Common mistake: trying to classify an edge using only discovery time, without finish time. Discovery time alone cannot distinguish a forward edge from a cross edge in some graph shapes; the finish-time containment (or lack of it) is what actually distinguishes ancestor/descendant relationships from unrelated branches.
• Undirected graphs only have tree edges and back edges, no forward or cross edges. This is because in an undirected graph, an edge $(u,v)$ examined from $u$ toward an already-visited $v$ is the exact same edge as $(v,u)$ examined earlier from $v$'s own exploration, so what would be a "forward" edge from one direction is simply the same back edge already counted from the other direction; the four-way classification is specifically a directed-graph concept.
• The back-edge-implies-cycle result is exactly what a production cycle detector (for example, checking a dependency graph for circular dependencies) implements under the hood, usually via the lighter "white/gray/black" color-marking scheme rather than literal discovery/finish timestamps, gray is equivalent to "discovered but not yet finished," so a back edge is precisely an edge into a currently-gray node.

Direct answer

Seed a single breadth-first search (BFS) queue with all source nodes at distance 0 simultaneously, rather than running BFS once per source and taking the minimum. Because BFS explores in strict distance order, the first time any node is reached from ANY source is guaranteed to be its true minimum distance to the nearest source, so one pass over every vertex and edge suffices.

Structured elaboration

The key insight is that a standard single-source BFS's correctness argument, the first time a node is dequeued its distance is final, does not depend on there being only one source in the queue at the start. Seeding multiple sources at distance 0 just means the frontier expands outward from several points at once; distances still increase monotonically layer by layer, so a node discovered from source A at distance 3 and also reachable from source B at distance 5 will correctly end up recorded at distance 3, whichever source's expansion reaches it first, since BFS explores layer 3 (from either source) entirely before layer 4.

This avoids the alternative of running BFS once per source and taking an elementwise minimum, which costs $O(k \cdot (V+E))$ for $k$ sources instead of a single $O(V+E)$ pass.

Worked example

from collections import deque
from typing import List

def multi_source_bfs(n: int, edges: List[List[int]], sources: List[int]) -> List[int]:
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    dist = [-1] * n
    q = deque()
    for s in set(sources):
        if 0 <= s < n and dist[s] == -1:
            dist[s] = 0
            q.append(s)

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

if __name__ == "__main__":
    # n=8 undirected graph: a 6-cycle over nodes 0..5, plus a separate isolated pair 6-7
    n = 8
    edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[0,5],[6,7]]
    sources = [0, 4]

    dist = multi_source_bfs(n, edges, sources)
    print("dist:", dist)

    # verify against brute force: minimum over independent single-source BFS runs
    def bfs_from(src):
        d = [-1]*n
        adj = [[] for _ in range(n)]
        for u,v in edges:
            adj[u].append(v); adj[v].append(u)
        d[src]=0
        qq=deque([src])
        while qq:
            u=qq.popleft()
            for v in adj[u]:
                if d[v]==-1:
                    d[v]=d[u]+1
                    qq.append(v)
        return d
    d0, d4 = bfs_from(0), bfs_from(4)
    expected = [min(a,b) if a!=-1 and b!=-1 else (a if a!=-1 else b) for a,b in zip(d0,d4)]
    print("expected (min of independent single-source runs):", expected)
    print("matches:", dist == expected)
    print("unreachable nodes 6 and 7 both -1:", dist[6]==-1 and dist[7]==-1)

Output (actually executed with python3):

dist: [0, 1, 2, 1, 0, 1, -1, -1]
expected (min of independent single-source runs): [0, 1, 2, 1, 0, 1, -1, -1]
matches: True
unreachable nodes 6 and 7 both -1: True

Complexity

• Time: $O(V + E)$, each vertex is dequeued once and each edge is examined at most twice (once from each endpoint).
• Space: $O(V)$ for the adjacency list construction, the dist array, and the queue.

Edge cases

• No sources given: dist stays all -1, no error, since the for s in set(sources) loop simply does not run.
• A source index outside [0, n): silently ignored via the bounds check, rather than crashing on an out-of-range list access.
• Disconnected components not reachable from any source: correctly left at -1, handled naturally since BFS only expands from the seeded frontier.
• Duplicate sources: deduplicated via set(sources) so a repeated source does not enqueue the same starting node twice.

Trade-offs and pitfalls

• Common mistake: running BFS independently once per source and taking the minimum. This gives the same answer but costs $O(k \cdot (V+E))$ instead of $O(V+E)$, a real difference once $k$ (the number of sources) is large, for example this shape shows up as "distance to nearest fire station," "distance to nearest rotten orange," or "distance to nearest cache node."
• Common mistake: initializing all sources into the queue but forgetting to check dist[v] == -1 before overwriting on relaxation, which would let a later, longer path stomp an earlier, shorter one; the -1 sentinel check is what preserves BFS's "first time reached is shortest" guarantee.
• Extending this to a directed graph only requires building adj from directed edges (drop the reverse insert); the algorithm's correctness argument (layer-by-layer expansion) is unaffected by directedness.
• This does NOT generalize directly to weighted graphs with varying positive weights; that requires a priority queue and becomes multi-source Dijkstra, not multi-source BFS, since BFS's "distance equals number of edges" property depends on every edge costing exactly 1.

Direct answer

An implicit graph never materializes its full node or edge set up front: neighbors are computed on demand by calling produce_neighbors(state), and breadth-first search (BFS) still applies unmodified, since BFS only ever needs "give me the neighbors of this node right now," never the whole graph at once. This is exactly what a state-space search (a puzzle, a game position, an abstract configuration space) needs, since materializing every reachable state ahead of time is often impossible or wasteful.

Structured elaboration

Why BFS still guarantees shortest path here. BFS's core guarantee, the first time a state is discovered it is at its true minimum distance, depends only on exploring states in non-decreasing distance order, never on knowing the graph's shape in advance. Calling produce_neighbors lazily, one node at a time, preserves this exactly: each call happens precisely when that node is dequeued, in the same layer-by-layer order BFS always uses.

Pruning strategies. A visited set is the baseline prune (never re-expand a state already discovered), but implicit graphs often support domain-specific pruning too: reject a neighbor immediately if it violates an invariant (an illegal board position, a state outside a known-safe region) before it is ever added to the queue, saving both the memory to store it and the future work of expanding it. Pruning by domain invariant must never prune a state that could still be on SOME shortest path, or the "shortest" guarantee breaks; a prune based purely on redundancy (already visited) is always safe, a prune based on heuristic judgment is not automatically safe unless proven admissible.

Heuristics. If a heuristic estimate of remaining distance to the goal is available, switching from plain BFS to A* (using the heuristic to prioritize which state to expand next via a priority queue instead of a FIFO queue) can dramatically reduce the number of states visited, at the cost of losing BFS's simplicity and requiring the heuristic to be admissible (never overestimate the true remaining distance) to keep the shortest-path guarantee.

Bidirectional search. When both start and goal are known in advance (not always true in state-space search, but common), growing frontiers from both ends and stopping when they meet bounds the search to roughly the square root of the single-direction node count for a typical branching factor, the same principle as bidirectional BFS on any explicit graph.

Worked example

from collections import deque
from typing import Callable, Iterable, List, Optional, TypeVar

State = TypeVar("State")

def find_shortest_sequence(start: State, goal: State,
                            produce_neighbors: Callable[[State], Iterable[State]]) -> Optional[List[State]]:
    if start == goal:
        return [start]
    parent = {start: None}
    q = deque([start])
    while q:
        s = q.popleft()
        for nxt in produce_neighbors(s):
            if nxt in parent:
                continue
            parent[nxt] = s
            if nxt == goal:
                path = [nxt]
                cur = nxt
                while parent[cur] is not None:
                    cur = parent[cur]
                    path.append(cur)
                return list(reversed(path))
            q.append(nxt)
    return None

if __name__ == "__main__":
    # Abstract 12-state space: from state s, neighbors are s+1, s-1, s+5 (mod 12).
    # Deliberately not a literal grid or puzzle, to make the point that BFS
    # does not care what a "state" actually represents.
    N = 12
    def produce_neighbors(state):
        return [(state + 1) % N, (state - 1) % N, (state + 5) % N]

    path = find_shortest_sequence(0, 7, produce_neighbors)
    print("Shortest sequence 0 -> 7:", path)
    print("Steps:", len(path) - 1 if path else None)

    def is_valid(path, produce_neighbors):
        return all(path[i+1] in set(produce_neighbors(path[i])) for i in range(len(path)-1))
    print("Path uses only real transitions:", is_valid(path, produce_neighbors))

    def full_bfs_dist(start, produce_neighbors):
        dist = {start: 0}
        q = deque([start])
        while q:
            u = q.popleft()
            for v in produce_neighbors(u):
                if v not in dist:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist
    ref = full_bfs_dist(0, produce_neighbors)
    print("Matches independent full-BFS distance table:", ref[7] == len(path) - 1)

    print("No path from a state that only transitions to itself:", find_shortest_sequence(100, 200, lambda s: [s]))

Output (actually executed with python3):

Shortest sequence 0 -> 7: [0, 1, 2, 7]
Steps: 3
Path uses only real transitions: True
Matches independent full-BFS distance table: True
No path from a state that only transitions to itself: None

The independent full_bfs_dist helper computes distances to every reachable state from scratch, without reusing the path-returning function's logic, and its distance to state 7 (3) matches len(path) - 1 exactly, confirming the lazily-called produce_neighbors version is genuinely finding a true shortest sequence, not just any sequence.

Complexity

Time $O(N + E)$ where $N$ is the number of reachable states and $E$ is the number of transitions actually explored (both unknown in advance for a true implicit graph, unlike an explicit one where $V$ and $E$ are given). Space $O(N)$ for parent and the queue. Each call to produce_neighbors is charged whatever it costs to compute (in the example above, $O(1)$; in a real puzzle, it might be proportional to board size).

Edge cases

• start == goal: returns [start] immediately, a zero-move sequence, without ever calling produce_neighbors.
• No path exists (as demonstrated by the self-loop-only state 100 in the worked example): the queue drains completely, parent never gains an entry for goal, and the function returns None.
• produce_neighbors yielding a state already on the current path (a state with a transition back to itself, or a cycle in the state graph): handled the same as any other implicit-graph cycle, since the parent dict doubles as the visited set, a state already discovered is never re-enqueued.
• produce_neighbors raising an exception mid-search (a real risk if computing a state's neighbors can fail, for example an invalid board configuration): not handled by the implementation above, and worth flagging explicitly as something a production version would need to decide on: abort the whole search, or treat that state as having no valid neighbors and continue.

Trade-offs and pitfalls

• Common mistake: calling produce_neighbors more than once for the same state (for example, once to check if any neighbor is the goal, and again to actually enqueue them). Since neighbor generation can be expensive in a real state space, the implementation above calls it exactly once per dequeued state and processes each yielded neighbor as it arrives.
• Common mistake: pruning by a heuristic that is not admissible (can overestimate true remaining distance), which silently breaks BFS's shortest-path guarantee; a state that gets pruned because it "looks unpromising" might still sit on the actual shortest path.
• Infinite or unbounded state spaces. Unlike a finite explicit graph, an implicit state space can be infinite (an unbounded counter, an open-ended configuration). Plain BFS on such a space either runs forever if goal is unreachable, or needs an explicit depth cap or iterative-deepening strategy layered on top to guarantee termination even on a "no path exists" input.
• When to reach for A instead.* If a genuinely admissible heuristic exists (an under-estimate of remaining distance that is cheap to compute), A* dominates plain BFS by visiting fewer states while preserving the same shortest-path guarantee; if no such heuristic is available or trustworthy, plain BFS remains the safe default.

Direct answer

Marking a node visited when it is first DISCOVERED (enqueued, or pushed) versus when it is actually PROCESSED (dequeued, or popped) is not a stylistic choice, it changes correctness. Discovery-time marking guarantees each node enters the frontier exactly once, which is what breadth-first search (BFS) needs for its shortest-path guarantee to hold and what any traversal needs to bound total work to $O(V+E)$. Processing-time marking lets the same node be enqueued multiple times by different discoverers before any of those copies is ever processed, wasting work and, in a concurrent setting, creating a real race.

Structured elaboration

Mark-on-discovery (enqueue/push time). The moment a neighbor is first seen, it is marked visited and added to the frontier, before the algorithm ever looks at it again. Correctness: guarantees each node is scheduled exactly once, since every subsequent discovery of the same node is rejected by the visited check before it can be re-added. Duplicate work: none, by construction. Cycle detection: sufficient for BFS (an infinite loop on a cycle is prevented because a cycle's nodes are never rediscovered), but NOT sufficient on its own for detecting a directed cycle during DFS, since a plain boolean "seen" flag cannot distinguish a node that is still being explored (on the current path) from one that finished long ago. Multi-source: trivial, mark every source visited before the traversal begins, so no source is ever re-added by another source's exploration. Parallel traversals: safer, since the mark-and-claim step happens once, before any work is dispatched, so an atomic compare-and-set on the visited marker is enough to guarantee two workers never both claim the same node.

Mark-on-processing (dequeue/pop time). A node is only marked visited once the algorithm actually gets around to working on it. Correctness: still eventually correct for a simple existence/reachability check, but WRONG for BFS's shortest-path guarantee under certain implementations, since a node can be enqueued multiple times (once per discoverer) before any copy is processed, and depending on queue order, a node might get its distance recorded from a LATER, longer discovery rather than the first, shortest one, if the implementation naively overwrites distance on every dequeue rather than checking a distance already set. Duplicate work: real and often significant, since the same node can sit in the queue multiple times, each copy doing a full "look at my neighbors" pass when eventually processed. Cycle detection: also insufficient alone, for the same white/gray/black reason below. Multi-source: risk of the same node being queued once per source that reaches it, inflating queue size unnecessarily. Parallel traversals: genuinely problematic, since two workers can both see a node as "not yet marked" and both dispatch work on it before either finishes marking it, a textbook race condition requiring an explicit atomic claim step to fix, which mark-on-discovery gets for free by marking BEFORE dispatching any work.

Color states (white, gray, black), the mechanism that fixes what plain marking cannot. White: undiscovered. Gray: discovered, currently being explored (on the active depth-first search path). Black: fully finished, nothing reachable from it remains unexplored. This is strictly more informative than a boolean visited flag: a boolean can only say "seen or not," while color additionally distinguishes "seen and still in progress" from "seen and done." That distinction is exactly what directed-cycle detection needs: encountering an edge into a GRAY node (one still on the current path) means a back edge into an ancestor, a genuine cycle; encountering an edge into a BLACK node means the target was already fully explored via some other path, not a cycle. A plain visited-on-discovery boolean cannot tell these two cases apart, which is why cycle detection specifically needs the three-state version, not merely "was this node marked."

Worked example

Consider a small directed graph: $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$, $3 \to 1$ (a back edge creating the cycle $1 \to 3 \to 1$).

Running DFS from 0 with color states: visit 0 (white to gray), visit 1 (white to gray), visit 3 (white to gray), examine 3's edge to 1: 1 is currently GRAY (still on the active path, 0 to 1 to 3), so this is a back edge, a cycle is correctly reported. Contrast with a plain boolean visited-on-discovery DFS: visit 0 (mark visited), visit 1 (mark visited), visit 3 (mark visited), examine 3's edge to 1: 1 is marked visited, and a naive boolean check alone cannot tell whether that means "1 is an ancestor on my current path" (a cycle) or "1 was already fully explored via some unrelated path" (not a cycle); it would need the color distinction, or an equivalent explicit "currently on stack" set, to tell the two apart correctly.

Trade-offs and pitfalls

• Common mistake: using a plain visited set for DFS cycle detection and expecting it to work like BFS's visited set does. BFS never needs the three-state distinction because BFS has no notion of "still in progress on the current path" the way DFS's call stack does; a boolean is genuinely sufficient there. Porting that same boolean pattern to DFS cycle detection is the single most common source of an "our cycle detector missed a real cycle" or "false-positived on a shared-descendant DAG" bug.
• Common mistake: implementing recursive DFS with a single shared visited set across the whole traversal but forgetting to distinguish "in the current recursion's ancestor chain" from "visited by an earlier, now-finished sibling call." The gray/black split (or an explicit in_progress set that gets removed on backtrack, functionally equivalent) is exactly what an iterative, explicit-stack DFS must also replicate correctly; converting recursive DFS to iterative and dropping this distinction along the way is a real, easy-to-introduce regression.
• Parallel or distributed traversals. Beyond the local correctness question, dispatching work to multiple workers needs the CLAIM step itself to be atomic (a compare-and-set on a shared visited marker, or a lease with an expiry), not merely "check then mark" as two separate, non-atomic operations; two workers can both pass the check before either performs the mark, exactly the race mark-on-discovery avoids only if the mark itself is atomic with respect to the check.
• Recursion-vs-iterative equivalence. A recursive DFS's own call stack implicitly IS the gray set (a node is on the call stack exactly while it is gray); converting to an iterative, explicit-stack version requires either maintaining an explicit gray set alongside the stack or, if the stack contents alone are used as a proxy for "in progress," being careful that a node popped off the explicit stack for backtracking purposes is correctly treated as no longer gray, not still considered in-progress.

Direct answer

Maintaining connected components under insertions alone is a solved, cheap problem: Union-Find handles it in amortized $O(\alpha(n))$ per insertion. Deletions are the genuinely hard part, because Union-Find's tree-merging structure has no efficient inverse: once two sets are merged, there is no cheap way to ask "if I remove this one edge, does the merged set need to split back into two." The practical engineering answer is almost never "support arbitrary deletions with full generality," it is to constrain the problem: batch deletions and periodically rebuild, or accept an offline model where the full sequence of operations is known in advance, or reach for a genuinely dynamic data structure (Euler tour trees, link-cut trees) only when the deletion rate and latency requirements truly demand it.

Structured elaboration

Why insertions are easy. Each new edge is one union call. Amortized cost per operation is $O(\alpha(n))$, and the structure never needs to "undo" anything to support more insertions, so an insert-heavy or insert-only workload is a non-issue for Union-Find.

Why deletions are hard. When an edge is removed, the two nodes it connected might still be connected through some OTHER path (so nothing changes), or that edge might have been the only path between two halves of what is now two separate components (so the structure must split). Union-Find's tree shape after path compression has discarded the information needed to tell these two cases apart cheaply: it only remembers "these nodes ended up under the same root at some point," not "here is the specific set of edges that currently justifies that." Determining which case applies in general requires re-deriving connectivity from the remaining edges, which is exactly the expensive operation Union-Find was built to avoid.

Three practical strategies, in order of increasing sophistication:

1. Full rebuild on every batch of deletions. Accumulate deletions for some time window or count threshold, then rebuild the entire Union-Find structure from the current live edge set. Cost: $O(E)$ per rebuild, amortized over however many deletions triggered it. This is the simplest strategy and is often sufficient when connectivity queries can tolerate being slightly stale (answered against the last completed rebuild) rather than reflecting every deletion instantly.
2. Offline divide-and-conquer with rollback, when the full sequence of insertions, deletions, and queries is known ahead of time (a genuinely offline setting, common in batch analytics jobs). Each edge's active time interval is computed in advance, and a Union-Find variant that supports undoing unions (by NOT using path compression, only union by size, and keeping an explicit undo stack) processes the timeline via a segment tree over time, applying and rolling back unions as it recurses. This achieves $O((V + E + Q) \log T)$ total for $T$ time steps and $Q$ queries, at the cost of needing the full operation sequence upfront, which rules it out for a genuinely live, open-ended stream.
3. Fully dynamic connectivity structures (Euler tour trees, or the Holm-de Lichtenberg-Thorup structure), which support both insertion and deletion in $O(\log^2 n)$ amortized time without needing the future operation sequence in advance. These exist and are the theoretically correct answer to "support both directions online," but they carry real implementation complexity (multiple levels of spanning-forest bookkeeping) well beyond what most production systems justify building or maintaining in-house.

Amortized complexity summary:

Worked example

For a near-real-time dashboard showing which servers are currently mutually reachable (an operational monitoring use case), a reasonable strategy is strategy 1, tuned: rebuild the Union-Find structure on a fixed cadence (say, once per minute, driven by the dashboard's own refresh interval, not by a fixed edge count) from the live edge set as of that moment, and serve all connectivity queries against the most recent rebuild in between. If a specific incident-response workflow needs connectivity reflecting deletions within seconds rather than up to a minute of staleness, that workflow can additionally maintain its OWN small Union-Find rebuilt just over the specific subgraph relevant to the incident, rather than paying the cost of low-latency full dynamic connectivity across the entire graph. The batching threshold (time-based vs count-based) is a product/operational decision, not a purely algorithmic one: a time-based cadence gives predictable staleness bounds, while a count-based cadence (rebuild after every $B$ deletions) gives a predictable amortized cost per deletion but an unpredictable staleness bound if deletions arrive in bursts.

Trade-offs and pitfalls

• Common mistake: reaching for a fully dynamic connectivity structure by default. These are real, correct, and asymptotically strong, but the implementation complexity is high enough that most production systems are better served by batching plus a staleness bound the business can actually tolerate; reserve the fully dynamic structure for cases where sub-second correctness after every single deletion is a hard requirement, not a nice-to-have.
• Common mistake: conflating "offline" (full operation sequence known in advance) with "batched" (deletions grouped into windows, but the future is still unknown). The divide-and-conquer-with-rollback technique needs the FULL timeline upfront; it cannot be run incrementally against a live, open-ended stream, which makes it a poor fit for a live dashboard and a good fit for a nightly batch-analytics reprocessing job over a day's worth of logged topology changes.
• A rebuild-based strategy's staleness bound is a first-class design parameter, not an afterthought: it must be stated and monitored (rebuild latency drifting up as the graph grows is a real operational risk), not left as an implicit assumption that "the rebuild is fast enough."
• Query semantics need to be explicit about what "connected" means during a batching window: does a query answered mid-batch reflect the edges as of the LAST completed rebuild, or does it block until the next rebuild finishes? Silently mixing the two within one system produces confusing, non-reproducible answers to the same query asked moments apart.