10 min read2,176 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 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:

  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.

In this section