14 min read3,152 words

Upstream & Downstream Tracing Algorithms

Upstream and downstream tracing algorithms are the computational core of utility network analysis: they turn a static spatial dataset into a directed graph that answers operational questions like “what feeds this meter?” and “what loses service if this valve closes?” Within the broader Topology & Tracing Workflows discipline, these routines drive hydraulic isolation, fault propagation analysis, and service-area delineation. The hard part is not writing a breadth-first search — it is making traversal logic agree with real asset behavior, connectivity constraints, and live barrier states. This guide is written for utility engineers, GIS technicians, Python automation builders, and infrastructure teams who need traces that are deterministic, auditable, and trustworthy in production.

Problem Statement: Silent Trace Failures

The dominant failure mode in production tracing is not a crash — it is a trace that returns confidently wrong results. Three patterns cause the majority of incidents:

  • Premature termination. A misconfigured terminal pairing or a dangling edge stops traversal short, so an upstream trace reports a clean isolation when service is still pressurized downstream of the supposed shutoff. This is the most dangerous outcome because the operator acts on a false “isolated” signal.
  • Phantom propagation. Containment relationships (a fiber strand inside a conduit, a cable inside a duct bank) are treated as topological connectivity, so a downstream trace bleeds across physically separate subnetworks and over-reports the affected customer count.
  • Stale barrier state. The graph is correct but the valve/switch states are from the design dataset, not the field. The algorithm faithfully traverses a network that no longer exists.

Each of these produces no error message. Detecting them requires that the connectivity model, the barrier model, and the field-state feed are validated before a trace is trusted — which is the through-line of every section below.

Prerequisite Checklist

Confirm each item before enabling automated traces against production data:

Core Algorithm: Directed Graph & Barrier Evaluation

A utility network is modeled as a directed graph G = (V, E). Edges represent linear assets — pipes, cables, conduits — and nodes represent junctions, terminals, and fittings. Flow directionality on each edge is derived from one of three sources: digitized static orientation, hydraulic/electrical model output, or a computed gradient (pressure for water, voltage/source-rank for electric).

An upstream walk halting at the first closed barrier, with the containment edge it must not follow The walk starts at the origin and moves against flow direction toward the controller. It passes an open valve, which is traversable, and halts at the closed one: that device is the isolation boundary and everything beyond it is outside the result. The dotted link is a containment association — a strand inside a conduit — and it carries no flow. A trace that follows it produces phantom propagation, reporting features as connected that share only an enclosure. upstream propagation halts here containment — not traversable Origin trace start J-41 V-8 OPEN — traversed X V-9 CLOSED — barrier Controller never reached Conduit containment only traversed barrier containment The result set is everything the solid arrows reached, and nothing else.

An upstream trace starts at an origin and walks incoming edges (toward the source) recursively until it reaches a source terminal, a closed barrier, or a configured depth limit. A downstream trace walks outgoing edges to delineate everything fed by the origin — the natural primitive for service-area and fault-propagation analysis. Both are deterministic only when terminal connectivity is unambiguous: lateral-to-main, pipe-to-fitting, and cable-to-switch relationships must each resolve to a single, well-defined traversal path with no accidental branching.

Barriers are the part that makes utility tracing different from generic graph search. An isolation valve, pressure regulator, sectionalizing switch, or check valve is a conditional node: whether traversal passes through it depends on its current state. The cleanest implementation keeps barrier evaluation as a predicate applied at each candidate node, rather than baking it into the graph structure — so the same graph can be re-traced under different field states without a rebuild.

import networkx as nx

def trace(graph: nx.DiGraph, origin, direction="upstream",
          max_depth=None, barrier_states=None):
    """
    Deterministic directed traversal with state-aware barriers.

    direction      : "upstream" (walk predecessors) or "downstream" (walk successors)
    barrier_states : {node_id: "closed"|"open"} overlay from SCADA/field feed
    Returns the set of visited node ids (origin included).
    """
    barrier_states = barrier_states or {}
    step = graph.predecessors if direction == "upstream" else graph.successors

    visited, stack = set(), [(origin, 0)]
    while stack:
        node, depth = stack.pop()
        if node in visited:
            continue
        visited.add(node)

        # A closed barrier is traversed (so the device itself is in the result)
        # but its onward edges are not expanded — flow stops here.
        if barrier_states.get(node) == "closed":
            continue
        if max_depth is not None and depth >= max_depth:
            continue

        for nxt in step(node):
            if nxt not in visited:
                stack.append((nxt, depth + 1))
    return visited

The key design choice above: a closed barrier is included in the result set (so the operator sees which device isolates the network) but its downstream/upstream edges are not expanded. A normally open tie switch is simply absent from barrier_states, so it behaves as a permeable node — exactly what fault-isolation scenarios require.

Step-by-Step Implementation

The procedure below builds a graph from a utility network, overlays live barrier state, and runs an isolation trace end to end. For a fully worked water-isolation example with CMMS integration, see Python automation for upstream water valve tracing.

  1. Validate topology first. Never trace a dirty topology. With arcpy, run validation and abort on severity-2 messages:

    import arcpy

def assert_clean_topology(un_path: str) -> None:
    arcpy.un.ValidateTopology(un_path)
    errors = arcpy.GetMessages(2)  # severity 2 = errors only
    if errors:
        raise RuntimeError(f"Topology errors block tracing:\n{errors}")

  2. Construct the directed graph. Read edges and junctions, orienting each edge by its flow-direction field. Keep the asset’s global ID as the node key so results map cleanly back to features:

    import networkx as nx

def build_graph(edges, junctions, flow_field="FLOWDIR") -> nx.DiGraph:
    g = nx.DiGraph()
    for j in junctions:
        g.add_node(j["globalid"], asset_type=j["assettype"])
    for e in edges:
        a, b = e["from_node"], e["to_node"]
        # Reverse the edge when the digitized direction opposes flow.
        if e.get(flow_field) == "REVERSED":
            a, b = b, a
        g.add_edge(a, b, asset_type=e["assettype"])
    return g

  3. Resolve barrier states. Build the {node_id: state} overlay from the freshest available source, falling back to design state only when no live tag exists (and flagging the fallback for the audit trail).

  4. Execute the traversal. Call trace(graph, origin, direction="upstream", barrier_states=states) from the Core Algorithm section. For multi-origin queries (e.g., several leaks reported simultaneously), union the result sets rather than re-walking shared upstream paths.

  5. Serialize the result. Emit the visited feature IDs, the set of barriers that terminated the trace, the trace parameters, and the barrier-state provenance as a single structured record — this is the artifact compliance review will ask for.

When the traversal sequence branches in non-obvious ways (state-dependent routing through tie switches), a flow diagram clarifies the decision logic.

State-aware upstream trace decision flow with the barrier predicate A top-down flowchart. The trace starts at the origin and loops while the stack is non-empty: pop a node, mark it visited, then evaluate the barrier predicate fed by a SCADA and field-state overlay. A node whose state is closed is included in the result but its predecessors are not expanded. A node that is open or has no barrier state passes the depth-limit check and pushes its predecessor edges back onto the stack. When the stack drains at source terminals, the visited set, terminating barriers, and parameters are serialized to an audit-ready record. Origin node → stack Pop node, mark visited walk predecessors (upstream) Barrier state? predicate per node Field-state overlay SCADA / replica / CMMS closed Include device, stop expansion open / none depth < max_depth? push predecessors loop while stack Stack empty at source terminals → serialize visited set + terminating barriers + parameters → audit record
State-aware upstream trace: the barrier predicate, fed by the live field-state overlay, decides at each node whether to terminate (closed) or expand toward the source (open / none), and the drained stack serializes to an audit record.

Diagnostic Protocol

When a trace returns suspicious results, work this checklist in order — the most common root cause is first:

Separating a wrong trace caused by the graph from one caused by stale state The first question is whether the topology is clean over the trace extent, because dirty areas and unvalidated edits are the leading cause of a wrong result and invalidate every other measurement. With a clean topology the question becomes whether the trace under-reports or over-reports. Under-reporting points at an unconnected origin terminal, a reversed or null flow direction, or a dangling edge that terminates the walk early. Over-reporting points at a containment association being read as connectivity, or at a barrier whose state value falls outside its coded domain and is therefore treated as no barrier at all. Is the topology clean over the trace extent? no — dirty areas present Validate before anything else stop here Every other measurement is unreliable until this clears yes — clean Too few features, or too many? under-reports Too few — unconnected terminal, null FLOWDIR, dangle over-reports Too many — containment read as connectivity contradicts the field Right shape, wrong reality — the barrier overlay is stale Under-reporting is a safety problem; over-reporting is a cost problem. Both start here.
  1. Is the topology clean? Re-run validation over the trace extent. Dirty areas and unvalidated edits are the leading cause of wrong traces. Nothing else matters until this passes.
  2. Do origin terminals connect? Confirm the origin feature’s terminal is actually associated with an edge. An unconnected origin yields a trace of size one and reads as “nothing downstream.”
  3. Connectivity vs. containment confusion. Check whether a containment association is being read as connectivity — the signature is a trace that crosses into a physically separate subnetwork (phantom propagation). Validate against published connectivity rules.
  4. Domain-code mismatches on barriers. A barrier whose state field holds a value outside the coded domain is silently treated as “not a barrier,” so closed valves leak. Audit the device-state domain and reject unknown codes loudly.
  5. Flow-direction errors. A reversed or null FLOWDIR on a single edge can sever an entire branch from an upstream trace. Compare trace extent against the hydraulic/electrical model’s expected source.
  6. Orphaned features and dangles. Dangling edges and orphaned junctions cause premature termination. Detect them with a degree check ([n for n in g if g.degree(n) == 0]) before trusting any trace.
  7. Stale field state. If topology and connectivity check out but the result contradicts the field, the barrier overlay is stale — verify the SCADA/replica timestamp against your freshness tolerance.

Performance & Scale Considerations

Enterprise networks (millions of edges) demand engineering beyond a naive in-memory walk:

  • Bound every trace. Always pass max_depth for interactive queries; an unbounded trace on a meshed network can walk the whole system. Reserve unbounded traces for batch jobs.
  • Build the graph once, trace many. Graph construction dominates runtime. Cache the directed graph and re-apply barrier overlays per scenario instead of rebuilding — this is what lets you compare isolation options interactively.
  • Version isolation. Run batch traces against a dedicated version or a read-only topology snapshot so concurrent field edits cannot mutate the graph mid-run, and so you avoid lock contention on the default version.
  • Snapshot strategy. For repeatable analytics, materialize a timestamped topology snapshot per run; this also gives the audit trail a stable graph to reference. These same snapshots feed batch topology processing with Python jobs.
  • Multi-origin batching. Union shared upstream paths rather than re-walking them; memoize visited sets across origins in the same batch.
  • Choose the right engine. Use the native Utility Network trace for rule-aware, server-side queries at scale; drop to NetworkX when you need custom traversal logic, offline analysis, or platform independence.

Compliance Notes

Trace outputs frequently underpin safety-critical decisions, so they must be auditable. Record, per trace: the origin(s), direction, depth limit, the full set of barrier states applied (with provenance and timestamp), the terminating barrier set, and the resulting affected-feature list. For water systems, this metadata supports AWWA G400 asset-management audit expectations; for electric isolation it underpins switching-order and NERC-aligned operational records. Where a trace fell back to design-state barriers because no live tag was available, that fallback must be flagged in the record — an “isolated” determination based on stale state is a reportable risk, not a clean result. Persist these records immutably alongside the topology snapshot used, so any past isolation decision can be reconstructed exactly.

For reference implementations and validation semantics, consult the NetworkX traversal algorithms documentation and the ArcGIS Pro Trace tool documentation.

Multi-Origin Traces and Overlapping Barrier Sets

A single-origin trace is the textbook case. Real work is usually multi-origin: every service point on a feeder, every hydrant in a zone, every device a storm has reported. Running the single-origin algorithm in a loop is correct and wasteful, and at scale the waste is the whole runtime.

The first economy is memoisation across origins in one batch. Traces from origins on the same feeder share most of their upstream path, so a visited set kept across the batch turns the second and subsequent walks into short hops onto an already-explored trunk. The second is ordering: process origins in an order that maximises sharing — grouped by feeder or zone rather than by asset identifier — so the shared trunk is already in the visited set when the next origin starts.

Overlapping barrier sets need more care. When the same trace is run under several barrier scenarios — this valve closed, that switch open, both — the graph is constant and only the overlay changes, so build the graph once and apply overlays per scenario. What must not be shared across scenarios is the visited set: a memoised path computed under one barrier configuration is invalid under another, and reusing it is the subtle bug that produces plausible results for scenarios nobody checked by hand.

Proving a Trace Against the Field

A trace is an assertion about the physical world, and the only way to know it is right is to compare it against the world. Two practices make that routine rather than heroic.

The first is a certification network: a small feeder or pressure zone whose correct upstream and downstream sets have been established by hand and agreed by an engineer. Every change to the graph, the rules, the barrier logic or the engine runs against it, and any divergence is a regression until proven otherwise. It costs a day to build and it is the only test in this domain that measures correctness rather than absence of exceptions.

The second is reconciling against field events. Every switching operation and every isolation performed during an event is an experiment: the model predicted a set of affected customers, the field discovered the real one. Capturing that comparison after each event, even informally, builds a record of where the model diverges systematically — a feeder where the count is always high, a district where isolation always misses a valve. Those patterns point at model defects that no amount of internal validation will surface, because internally the model is perfectly consistent with itself.

Caching Trace Results Without Serving Stale Ones

Traces are expensive and repetitive, so results get cached — and a cached isolation boundary that outlives the device state it was computed from is the most dangerous artefact in this whole domain.

Key the cache on everything the result depends on: the topology snapshot identifier, the barrier overlay’s as-of timestamp, the origin, and the trace parameters. A key built on the origin alone will serve a boundary computed before a valve was closed. Invalidate on device state change rather than on a timer, because a five-minute expiry is five minutes of wrong answers during the only period when the answer matters.

Publish the age with the result wherever a person will read it. A boundary stamped with the device-state time it assumed lets an operator judge it; the same boundary with no timestamp invites them to assume it is current.

In this section