The Spec Said Recompute Everything. I Modeled It as a Graph Instead.

Recently at work I had to build a seemingly simple allocation algorithm. Given:

• a list of resources with available amounts
• a list of allocation requests with their required amounts
• a link map connecting the requests to the resources

sort the input using a partial order with predefined business rules (which I won’t go into) and allocate the resources sequentially.

The catch was where the data came from. It was merged from two sources:

• the application itself, where the user could create resources and allocation requests
• an external API, from which data was ingested and then left available for modification

This is where the requirement that prompted this article came in: as long as the user hadn’t modified the externally ingested data, the system had to show the allocations exactly as they were received. At the first change, the supplied allocations had to be invalidated and recomputed.

The spec’s proposed solution was terribly simple: “as soon as the user makes any change to the configuration, recompute all of it”. That is trivial to implement, but it throws away imported allocations the user never touched and expected to keep. So I pushed back. I argued that such a solution would’ve been too destructive and possibly confusing for the user. I was confident I could achieve a more surgical implementation with minimal extra development time. Thus the problem to solve was the following: after a change, which imported allocations are still safe to keep?

To answer this question, we first need to notice how the input naturally forms an undirected, bipartite graph: one partition contains resources, the other contains allocation requests, and an edge indicates that a resource is available to satisfy a request.

Then it’s sufficient to realize that a change to any vertex invalidates its entire connected component; components no one touched keep their original allocation.

Using this representation, a vertex is safe to copy if and only if:

1. it was received through the external API
2. it has not been modified by the user in any way; that is, its required and available amounts are unchanged and no link has been added or removed
3. it is not connected, directly or indirectly, to any vertex that was created in the app or modified by the user

Stated precisely, we can solve this problem by first finding the connected components, and then marking an entire component unsafe if it contains even one unsafe vertex. There are several efficient ways to compute it. I shipped one of them; the three sections below solve the same problem from different angles, partly because comparing them makes the structure clearer. Each takes the graph and a safeToCopy boolean array, prefilled with whether each vertex satisfies conditions 1 and 2, and updates that array so only vertices satisfying all three remain marked safe to copy.

Depth-First Search

The first solution uses a DFS traversal, checking every vertex reachable from the current root to see whether it is safe to copy. Each traversal from an unvisited root discovers exactly one connected component, so checking everything reachable from that root is the same as checking the whole component. If any vertex in it is unsafe, every vertex encountered becomes unsafe.

Following is the pseudocode for this algorithm.

DFS(G):
  # initialize a list to keep
  # track of visited vertices
  for each v in V:
    visited[v] ← false

  # visit the whole graph
  # starting from each node
  for each v in V:
    if visited[v]:
      continue

    # initialize a new
    # stack containing v
    stack ← [v]
    # keep track of the
    # vertices reached using v as root
    reached ← empty list

    hasUnsafe ← false

    while stack ≠ ∅:
      u ← pop(stack)

      if visited[u]: continue
      visited[u] ← true

      if not safeToCopy[u]:
        hasUnsafe ← true

      append(reached, u)

      for each w in Adj[u]:
        if not visited[w]:
          push(stack, w)

    # if any vertex reached during the
    # visit was unsafe to copy
    if hasUnsafe:
      # set all the reached vertices
      # as unsafe
      for each u in reached:
        safeToCopy[u] ← false

Time Complexity: $O(|V| + |E|)$, since the traversal has to go through the whole graph.

Additional Space Complexity: $O(|E|)$, since the stack can contain duplicate vertices.

Union-Find

DFS discovers the connected components implicitly, then verifies whether every vertex in each one is safe to copy. We can build those components explicitly with a Disjoint-Set data structure, also known as Union-Find.

With Union-Find we grow the connected components as disjoint sets of vertices. We start with singleton sets, and then we simply iterate on the edges to join the sets containing the adjacent vertices. At the end, just like with DFS, we check whether every vertex within each component is safe to copy.

Here is the pseudocode implementation.

MakeSet(v):
  parent[v] ← v
  rank[v] ← 0

Find(v):
  if parent[v] ≠ v:
    # path compression
    parent[v] ← Find(parent[v])
  return parent[v]

Union(a, b):
  root_a ← Find(a)
  root_b ← Find(b)
  if root_a = root_b: return

  # union by rank
  if rank[root_a] < rank[root_b]:
    parent[root_a] ← root_b
  else if rank[root_a] > rank[root_b]:
    parent[root_b] ← root_a
  else:
    parent[root_b] ← root_a
    rank[root_a] ← rank[root_a] + 1

UnionFind(G):
  # instantiate a singleton set for each vertex
  for each v in V:
    MakeSet(v)

  # merge vertices connected by edges
  for each (u, v) in E:
    Union(u, v)

  # create a map which shows for each connected
  # component if it contains only safe nodes
  safeComponent ← empty map
  for each v in V:
    parent ← Find(v)
    if parent not in safeComponent:
      safeComponent[parent] ← true
    isParentSafe ← safeComponent[parent]
    isCurrentSafe ← safeToCopy[v]
    safeComponent[parent] ← isParentSafe ∧ isCurrentSafe

  # update the safeToCopy input array with
  # the values associated with the connected components
  for each v in V:
    safeToCopy[v] ← safeComponent[Find(v)]

Time Complexity: $O((|V| + |E|) \cdot \alpha(|V|)) \approx O(|V| + |E|)$ amortized, where $\alpha$ is the inverse Ackermann function.

Additional Space Complexity: $O(|V|)$, since parent, rank, and safeComponent can contain at most $|V|$ elements.

Flood Fill

The two algorithms we’ve seen so far compute the partition using connected components. This last approach reaches the same result by inverting the logic: instead of asking whether every vertex in a component is safe, we start from the unsafe ones and propagate the unsafe marking outward. Any vertex that satisfies conditions 1 and 2 but is adjacent to an unsafe vertex becomes unsafe as well.

Flood fill was originally devised for transforming multi-dimensional arrays of pixels, but we can picture our graph the same way by treating neighbors as adjacent cells. The unsafe vertices act like the boundary color in a pixel fill, and we propagate the unsafe marking outward.

The grid metaphor in the widget assumes a vertex has at most eight neighbors; the algorithm itself has no such limit, since it propagates along edges regardless of degree.

To implement this we use a BFS traversal, which works much like DFS but it utilizes a queue instead of a stack as the supporting data structure, which gets initialized with all the unsafe vertices. Every time a safe vertex is encountered, we mark it unsafe and push it on the queue.

Here is the pseudocode implementation.

FloodFill(G):
  queue ← ∅
  for each v in V:
    if not safeToCopy[v]:
      enqueue(queue, v)

  while queue ≠ ∅:
    v ← dequeue(queue)

    for each u in Adj[v]:
      if safeToCopy[u]:
        safeToCopy[u] ← false
        enqueue(queue, u)

Time Complexity: $O(|V| + |E|)$, since it potentially traverses the whole graph. In practice, if the input graph contains entire connected components without unsafe vertices, those will be skipped entirely.

Additional Space Complexity: $O(|V|)$, since the queue holds up to $|V|$ elements.

Allocation Algorithm

All three algorithms compute the same partition; they just disagree on how to see it. DFS shows that the problem is fundamentally about connected components, even when you do not build them explicitly. Union-Find makes that structure tangible by directly growing connected components. Flood Fill, my favorite of the three, inverts the logic: instead of asking “is this entire connected component safe?”, it starts from the unsafe vertices and floods outward.

At the scale I was working at, with typically less than ~40 vertices, the differences between them were negligible, so I shipped Flood Fill for its simplicity and clarity.

After this step, it was as simple as running the allocation algorithm from the spec on the vertices not marked safe to copy.

Takeaway

The hard part was never the algorithm. Connected components are a basic data structures topic, and any of the three approaches above would have worked. The real challenge was recognizing, before writing any line of code, that the obvious specification would’ve quietly erased work users expected to keep. Once I recognized that the requirement was really a graph problem, the implementation became straightforward, and I had a clear basis for pushing back on the initial proposal.

Thus I shipped the simplest solution that solved it: preserve the components no one touched, and recompute the rest. The next time a requirement arrives as a tangle of business rules or data dependencies, it’s worth asking what shape it really has. Often, it’s one you already know.