Pathfinder

Depth-first search over the undirected bus/branch graph that enumerates every simple path from a source bus to the active fault bus. The resulting ordered branch lists are used by ElectricalNetwork to inject the mutual-coupling Norton sources with the correct sign.

Physical / modelling context

In a meshed grounding network the mutual coupling between the faulted phase and the grounding return appears only along the path that the phase current actually travels between source and fault. The phase conductor and its associated grounding conductor are inductively coupled segment by segment; the resulting per-segment voltage drop is modelled as a series-EMF that can be Thevenin–Norton-converted into a current source on the grounding-side admittance matrix. To assemble those Norton sources correctly the algorithm has to:

1. enumerate every simple (loop-free) path from the source bus to the active fault bus over the undirected bus/branch graph,
2. preserve the traversal direction along each branch — the sign of the impressed Norton current depends on it,
3. take into account the optional parallel_coefficient on each branch so that mesh and ring topologies receive the correct per-path current share.

The DFS enumeration is exhaustive (NP-hard in the worst case) but the typical grounding networks are sparse enough — handfuls to a few dozen meshed branches — that it terminates quickly. For very dense topologies the result is cached on the Network object (net.paths) so that repeated run_fault calls do not re-traverse.

Example

import groundinsight as gi
from groundinsight.pathfinder import PathFinder

# Build network and choose an active fault — see the quickstart
# for the create_* calls.
net.set_active_fault("f1")

# `create_paths` is called automatically by run_fault. To inspect
# the enumerated paths manually:
gi.create_paths(network=net)
for p in net.paths.values():
    print(p.source, "->", p.fault,
          "via", [b.name for b in p.segments])

# Direct use of the PathFinder helper:
pf = PathFinder(net)
all_paths = pf.find_paths(source_bus_name="bus_substation",
                          fault_bus_name="bus_fault")

Module-level caches

PathFinder memoises two pieces of work at module scope:

• pathfinder._GRAPH_CACHE — the adjacency list built in _build_graph. Repeated PathFinder(network) constructions on the same logical topology (the inner loop of analysis.inverse_rho_f.evaluate_max_epr_under_k) pay the DFS cost only on the first call.
• pathfinder._FIND_PATHS_CACHE — the (source, fault) → List[Path] results returned by find_paths. find_paths returns copies of the cached Path instances so downstream callers (most prominently network_operations.define_paths) can safely mutate Path.name / Path.source / Path.fault without leaking the mutation into the cache.

Both caches key on the full topology fingerprint:

(id(network), network.name,
 len(network.buses), len(network.branches),
 frozenset(active_buses), frozenset(active_branches))

The structural part (name, len(buses), len(branches)) is a defence-in-depth guard against the CPython id-recycling failure mode: once a Network is garbage-collected, Python may legitimately reuse its id; the structural component prevents a false cache hit on the new, topologically different network.

Mutating a Network in place

Flipping Bus.active / Branch.active after define_paths() has already been called leaves the previously cached topology in network.paths and in the module-level caches. Use Network.invalidate_paths() — it drops the caller's own cache entries while preserving the cache for other networks live in the same process.

clear_pathfinder_cache() accepts an optional network argument to support the same scoping at the function level:

from groundinsight.pathfinder import clear_pathfinder_cache

# Scoped: only clear this network's entries.
clear_pathfinder_cache(net_a)

# Unscoped (test fixtures, recovery paths): drop everything.
clear_pathfinder_cache()

Cache size and LRU eviction (added in 0.5.0)

Both module-level caches are OrderedDict instances with an LRU eviction policy. The default cap is 256 entries per cache, applied globally across all Network instances. A long-running dashboard or a 100-scenario outage sweep therefore no longer accumulates one cache entry per visited topology indefinitely.

import groundinsight as gi

# Inspect or change the cap. Returns the previous value.
previous = gi.set_pathfinder_cache_size(64)
print(gi.get_pathfinder_cache_size())  # -> 64

The cap is read on every insertion, so a set_pathfinder_cache_size call also evicts already-cached entries in LRU order until the new cap is satisfied. Tests that want to pin the eviction policy to a small value typically reset the cap from a pytest fixture.

When outage_context exits

outage_context clears the per-network pathfinder cache on exit as well as on entry (added in 0.5.0). The resident footprint after a long outage sweep therefore matches the externally-visible state of the network rather than carrying one cache entry per visited scenario forward.

API reference

pathfinder

PathFinder Module.

This module provides the PathFinder class, which is responsible for identifying all possible paths between sources and faults within an electrical network. It utilizes Depth-First Search (DFS) to traverse the network graph and determine the connectivity between different buses through branches.

The primary use cases include: - Determining all paths from a specific source to a fault point. - Analyzing the network's topology for fault impact assessment. - Facilitating impedance and grounding calculations based on identified paths.

PathFinder

PathFinder(network: Network)

Find all simple paths between sources and faults in a network.

Constructs an adjacency list representation of the network graph and uses depth-first search (DFS) to identify all possible paths between a given source bus and fault bus. These paths are used to inject the mutual-coupling Norton sources with the correct sign in :mod:groundinsight.electrical_network.

Parameters:

Name	Type	Description	Default
network	Network	The :class:Network instance containing buses and branches.	required

Notes

Both the adjacency graph and the per-(source, fault) path results are cached at module level, keyed on a topology fingerprint (id(network), name, n_buses, n_branches, frozenset(active_buses), frozenset(active_branches)). Repeated constructions over the same logical topology — for example the inner loop of :func:groundinsight.analysis.evaluate_max_epr_under_k — therefore pay the DFS cost only on the first call. Call :func:clear_pathfinder_cache if you mutate a :class:Network in place under the same Python identity with a changed topology.

Build the adjacency-list representation of network.

Parameters:

Name	Type	Description	Default
network	Network	The Network instance containing buses and branches.	required

Source code in src/groundinsight/pathfinder.py

def __init__(self, network: Network):
    """
    Build the adjacency-list representation of ``network``.

    Parameters
    ----------
    network : Network
        The Network instance containing buses and branches.
    """

    self.network = network
    self._topology_key = self._compute_topology_key()
    graph = _cache_get(_GRAPH_CACHE, self._topology_key)
    if graph is None:
        graph = self._build_graph()
        _cache_set(_GRAPH_CACHE, self._topology_key, graph)
    self.graph = graph

find_paths

find_paths(
    source_bus_name: str, fault_bus_name: str
) -> List[Path]

Find all simple paths between a source bus and a fault bus.

Uses depth-first search (DFS) to enumerate every loop-free route from the source to the fault over the active sub-graph.

Parameters:

Name	Type	Description	Default
source_bus_name	str	The name of the source bus.	required
fault_bus_name	str	The name of the fault bus.	required

Returns:

Type	Description
list of Path	All discovered paths, each as an ordered branch list.

Source code in src/groundinsight/pathfinder.py

def find_paths(self, source_bus_name: str, fault_bus_name: str) -> List[Path]:
    """
    Find all simple paths between a source bus and a fault bus.

    Uses depth-first search (DFS) to enumerate every loop-free route
    from the source to the fault over the active sub-graph.

    Parameters
    ----------
    source_bus_name : str
        The name of the source bus.
    fault_bus_name : str
        The name of the fault bus.

    Returns
    -------
    list of Path
        All discovered paths, each as an ordered branch list.
    """
    cache_key = (
        *self._topology_key,
        source_bus_name,
        fault_bus_name,
    )
    cached = _cache_get(_FIND_PATHS_CACHE, cache_key)
    if cached is not None:
        # Return *copies* — callers (notably ``define_paths``) mutate
        # the returned ``Path`` instances (assigning ``name``,
        # ``source``, ``fault``) and that mutation must not bleed into
        # the cache.
        return [
            Path(
                name="",
                source="",
                fault="",
                segments=list(p.segments),
            )
            for p in cached
        ]

    all_paths = []
    visited_buses = set()
    path = []

    # Source or fault on an inactive (filtered) bus -> no path possible.
    if source_bus_name not in self.graph or fault_bus_name not in self.graph:
        _cache_set(_FIND_PATHS_CACHE, cache_key, [])
        return []

    self._dfs(source_bus_name, fault_bus_name, visited_buses, path, all_paths)

    # Convert each list of Branch objects to a Path object
    paths = []
    for branch_path in all_paths:
        path = Path(
            name="",  # Name will be assigned in define_paths()
            source="",  # Will be set in define_paths()
            fault="",  # Will be set in define_paths()
            segments=branch_path,
        )
        paths.append(path)
    _cache_set(_FIND_PATHS_CACHE, cache_key, paths)
    return [
        Path(
            name="",
            source="",
            fault="",
            segments=list(p.segments),
        )
        for p in paths
    ]

clear_pathfinder_cache

clear_pathfinder_cache(
    network: Optional[Network] = None,
) -> None

Drop module-level PathFinder caches.

Parameters:

Name	Type	Description	Default
network	Optional[Network]	If None (default), every cache entry — across all Network instances seen by the current Python process — is dropped. This is the safe but coarse fallback used by e.g. test fixtures or "I lost track of which networks are live" recovery paths. If a :class:Network instance is given, only entries whose key is keyed on that exact instance are dropped. This is the network-scoped invalidation that :meth:Network.invalidate_paths invokes so that a second, unrelated network's cache survives.	None

Notes

Call the network-scoped form after mutating a single :class:Network in place if the same Python identity will be reused with a changed topology. The unscoped form is appropriate for global resets, e.g. inside a pytest conftest.py autouse fixture.

Source code in src/groundinsight/pathfinder.py

def clear_pathfinder_cache(network: Optional[Network] = None) -> None:
    """Drop module-level PathFinder caches.

    Parameters
    ----------
    network:
        If ``None`` (default), every cache entry — across *all*
        ``Network`` instances seen by the current Python process — is
        dropped. This is the safe but coarse fallback used by
        e.g. test fixtures or "I lost track of which networks are
        live" recovery paths.

        If a :class:`Network` instance is given, only entries whose key
        is keyed on that exact instance are dropped. This is the
        network-scoped invalidation that :meth:`Network.invalidate_paths`
        invokes so that a second, unrelated network's cache survives.

    Notes
    -----
    Call the network-scoped form after mutating a single :class:`Network`
    in place if the same Python identity will be reused with a changed
    topology. The unscoped form is appropriate for global resets, e.g.
    inside a pytest ``conftest.py`` autouse fixture.
    """
    if network is None:
        _GRAPH_CACHE.clear()
        _FIND_PATHS_CACHE.clear()
        return

    net_id = id(network)
    # Network-scoped invalidation: drop every entry keyed on this exact
    # instance. Scoping by ``id`` only (not by name) means two distinct but
    # equally-named live networks no longer evict each other; the topology
    # key now carries connectivity, so id-recycling cannot cause a false hit.
    for key in [k for k in _GRAPH_CACHE if k[0] == net_id]:
        _GRAPH_CACHE.pop(key, None)
    for key in [k for k in _FIND_PATHS_CACHE if k[0] == net_id]:
        _FIND_PATHS_CACHE.pop(key, None)

get_pathfinder_cache_size

get_pathfinder_cache_size() -> int

Return the currently configured pathfinder cache cap.

Source code in src/groundinsight/pathfinder.py

def get_pathfinder_cache_size() -> int:
    """Return the currently configured pathfinder cache cap."""
    return _CACHE_SIZE

set_pathfinder_cache_size

set_pathfinder_cache_size(maxsize: int) -> int

Configure the maximum number of cached pathfinder entries.

Parameters:

Name	Type	Description	Default
maxsize	int	Maximum number of entries kept in both _GRAPH_CACHE and _FIND_PATHS_CACHE. Must be a positive integer. The cap applies independently to each cache.	required

Returns:

Type	Description
int	The previously configured cache size.

Raises:

Type	Description
ValueError	If maxsize is not a positive integer.

Notes

Reducing the cap also evicts already-present entries in LRU order so the new limit is immediately respected. The default value is 256; long-running dashboards iterating over many outage scenarios may want to raise it, tests that explicitly want to pin the eviction policy may want to lower it to 8 or 16.

Source code in src/groundinsight/pathfinder.py

def set_pathfinder_cache_size(maxsize: int) -> int:
    """Configure the maximum number of cached pathfinder entries.

    Parameters
    ----------
    maxsize : int
        Maximum number of entries kept in both ``_GRAPH_CACHE`` and
        ``_FIND_PATHS_CACHE``. Must be a positive integer. The cap
        applies independently to each cache.

    Returns
    -------
    int
        The previously configured cache size.

    Raises
    ------
    ValueError
        If ``maxsize`` is not a positive integer.

    Notes
    -----
    Reducing the cap also evicts already-present entries in LRU order
    so the new limit is immediately respected. The default value is
    ``256``; long-running dashboards iterating over many outage
    scenarios may want to raise it, tests that explicitly want to
    pin the eviction policy may want to lower it to ``8`` or ``16``.
    """
    global _CACHE_SIZE

    if not isinstance(maxsize, int) or maxsize <= 0:
        raise ValueError(
            f"pathfinder cache size must be a positive integer; got {maxsize!r}."
        )
    previous = _CACHE_SIZE
    _CACHE_SIZE = maxsize
    while len(_GRAPH_CACHE) > _CACHE_SIZE:
        _GRAPH_CACHE.popitem(last=False)
    while len(_FIND_PATHS_CACHE) > _CACHE_SIZE:
        _FIND_PATHS_CACHE.popitem(last=False)
    return previous