9 min read1,919 words

Modelling Switching Order Dependencies as a DAG

A switching order written as a numbered list encodes two different things in one structure: what must happen before what, and what somebody decided to do first. The router cannot tell them apart, so it either respects the whole sequence — serialising work that could run in parallel and leaving crews idle — or it reorders freely and produces a plan that opens a switch after the repair it was supposed to isolate. Modelling the order as a directed acyclic graph separates the two: each step declares only its real dependencies, the sort produces a valid order, and levelling the graph reveals which steps can be executed at the same time. This guide builds that model and wires it into the dispatch loop described in crew dispatch and route optimization.

Environment Prerequisites

  • Python 3.11 with networkx>=3.0 for the graph operations; the rest is standard library.
  • Work orders carrying explicit dependencies — a depends_on list of order identifiers rather than a sequence number.
  • A step type per order: isolation, repair, test, restoration. The type is what lets the validator catch a plan that restores before it tests.
  • The isolation set for the fault, from an isolation trace, because the isolation steps are derived from it rather than authored by hand.
  • Crew skills and availability as the router sees them, since levelling only helps if there are crews to fill a wave.
  • A completion feed from the field, so a finished step releases its dependents promptly.

Schema-Aware Validation Protocol — Run Before Publishing a Plan

  1. Assert the graph is acyclic. A cycle means the plan cannot be executed in any order, and the correct response is to stop rather than to break the cycle arbitrarily.
  2. Check every dependency resolves. A reference to a cancelled or superseded order is a dangling edge, and the plan built on it is missing a constraint.
  3. Verify type ordering. Every repair must depend on at least one isolation step, and every restoration must depend on a test. These are cheap assertions that catch an authored plan with a missing safety step.
  4. Confirm each isolation step names an operable device. A plan that depends on a seized valve is unexecutable, which the valve operability audit is there to prevent.
  5. Check the levels against crew availability. A wave of six parallel steps with two crews is not parallelism; it is a queue, and the plan should say so.

Minimal Reproducible Implementation

from __future__ import annotations

import logging
from dataclasses import dataclass, field

import networkx as nx

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
LOG = logging.getLogger("switching-dag")

ISOLATION, REPAIR, TEST, RESTORATION = "ISOLATION", "REPAIR", "TEST", "RESTORATION"


@dataclass
class Step:
    order_id: str
    step_type: str
    device_id: str | None = None
    depends_on: list[str] = field(default_factory=list)


@dataclass
class Plan:
    waves: list[list[str]] = field(default_factory=list)
    problems: list[str] = field(default_factory=list)

    @property
    def executable(self) -> bool:
        return not self.problems


def build_plan(steps: list[Step], operable: set[str]) -> Plan:
    """Turn declared dependencies into levelled waves of independently executable steps.

    Levelling is what exposes parallelism: every step whose dependencies are already
    satisfied belongs in the same wave and may be assigned to a different crew. A cycle
    or a dangling dependency stops the plan, because a switching order that cannot be
    sorted has no safe execution order at all.
    """
    plan = Plan()
    graph = nx.DiGraph()
    by_id = {s.order_id: s for s in steps}

    for step in steps:
        graph.add_node(step.order_id, type=step.step_type)
    for step in steps:
        for dep in step.depends_on:
            if dep not in by_id:
                plan.problems.append(
                    f"{step.order_id} depends on {dep}, which does not exist")
                continue
            graph.add_edge(dep, step.order_id)

    if not nx.is_directed_acyclic_graph(graph):
        cycle = nx.find_cycle(graph)
        plan.problems.append(f"dependency cycle: {cycle}")
        return plan

    for step in steps:
        deps = {by_id[d].step_type for d in step.depends_on if d in by_id}
        if step.step_type == REPAIR and ISOLATION not in deps:
            plan.problems.append(f"{step.order_id}: repair with no isolation dependency")
        if step.step_type == RESTORATION and TEST not in deps:
            plan.problems.append(f"{step.order_id}: restoration with no test dependency")
        if step.step_type == ISOLATION and step.device_id not in operable:
            plan.problems.append(
                f"{step.order_id}: device {step.device_id} is not operable")

    if plan.problems:
        return plan

    for wave in nx.topological_generations(graph):
        plan.waves.append(sorted(wave))

    LOG.info("plan: %d wave(s), widest %d step(s)", len(plan.waves),
             max((len(w) for w in plan.waves), default=0))
    return plan
A switching order as a dependency graph rather than a list Isolating the fault requires two switches opened before the repair can start, and the restoration switch cannot close until the repair is complete. Written as a numbered list the order looks strictly sequential; as a graph it is clear that the two isolation switches are independent of each other and can be assigned to two crews in parallel, while everything else is genuinely ordered. Open SW-12 isolation Open SW-19 isolation Repair the work itself Test prove dead / prove live Close SW-12 restoration parallelisable strictly ordered Two independent steps at the front; everything after them is a chain.

nx.topological_generations is doing the levelling in one call, and it is the difference between a plan and a schedule. A list tells a dispatcher what order to work in; a set of waves tells them how many crews they can usefully deploy right now.

What a cycle or a dangling reference in the switching graph actually means A topological sort that fails is reporting a modelling error rather than an impossible network. A cycle means two steps each claim to depend on the other, which is almost always a copied dependency. A dangling reference means a step depends on one that was cancelled or never created. Both must stop the plan: a switching order that cannot be sorted cannot be safely executed in any order. The topological sort failed a cycle Two steps depend on each other cause Usually a copied dependency on a duplicated step action Stop the plan — no execution order is safe a dangling reference Depends on a step that does not exist cause A cancelled or superseded work order action Re-derive dependencies from the current order set An unsortable switching order is a stop condition, not a warning.

Executing Against the Graph

Publishing waves rather than a list changes how completion is handled. A crew finishing a step does not advance a pointer; it satisfies a dependency, and whichever steps that releases become available. Two consequences follow.

The first is that a delayed step blocks only what actually depended on it. In a linear plan, a crew held up at switch nineteen stops everything behind it; in a levelled plan, the other isolation step and anything else independent continues. Dispatchers know this intuitively and work around linear plans by ignoring them, which is precisely the behaviour that makes plans and reality diverge.

The second is that the plan can be re-levelled mid-event without being rewritten. A step that turns out to be impossible — a device that will not operate — is marked failed, its dependents stay blocked, and an alternative isolation step can be inserted with its own dependencies. The graph absorbs the change; a numbered list would have to be reissued.

From work orders to an executable, parallelised switching plan Each work order declares what it depends on rather than a position in a sequence. The dependency graph is built and sorted; failure to sort stops the plan. The sorted graph is then levelled — steps with no unmet dependencies form a wave that can run in parallel — and the router assigns crews within each wave. Completion of a step releases the steps that depended on it, and the next wave is published. DECLARE depends_on per work order SORT topological stop on failure LEVEL waves of independent steps ASSIGN route within each wave RELEASE completion unlocks the next wave Declaring dependencies instead of positions is what makes parallelism visible.

Production Deployment Pattern

  1. Derive isolation steps from the trace, not by hand. Hand-authored isolation is where missing steps come from, and the trace already knows the minimal set.
  2. Refuse to publish an unsortable plan. A cycle or a dangling dependency is a stop condition, and breaking it arbitrarily produces an order somebody will execute.
  3. Assert the type rules on every plan. Repair after isolation, restoration after test. They are trivial checks and they catch the plans that matter.
  4. Publish waves with crew counts. A wave wider than the available crews should be shown as what it is, so nobody plans around parallelism that does not exist.
  5. Release on completion, not on a schedule. The completion feed is what makes the graph worth having; polling for it hourly discards most of the benefit.
  6. Log the executed order alongside the planned one. The difference between them is the best available evidence about whether the dependency model matches how the work is really done.

Conclusion

Modelling a switching order as a dependency graph separates what must be ordered from what merely was. The sort produces a valid sequence, the levelling exposes the parallelism a numbered list hides, and the type assertions catch the plans that skip a safety step. Executing against the graph rather than a pointer means a delay blocks only its dependents and an alternative can be inserted without reissuing anything — which is closer to how switching is actually run, and therefore likelier to survive contact with an event.

For authoritative reference, consult the NetworkX DAG documentation and the Python dataclasses library.

Related pages