NetworkX DiGraph shortest paths, topological sort and cycle detection: working versions (tested 2026-10-15)

networkx==3.6.1
pytest==9.1.1

import networkx as nx


def build_dag(edges):
    """edges: iterable of (src, dst, weight)."""
    g = nx.DiGraph()
    g.add_weighted_edges_from(edges)
    return g


def build_order(g):
    # topological_sort silently returns garbage order on a cycle, so guard first
    if not nx.is_directed_acyclic_graph(g):
        raise ValueError(f"dependency cycle: {nx.find_cycle(g)}")
    return list(nx.topological_sort(g))


def detect_cycle(g):
    # find_cycle raises NetworkXNoCycle when the graph is a DAG
    try:
        return nx.find_cycle(g)
    except nx.NetworkXNoCycle:
        return None


def fastest_route(g, source, target):
    # without weight= this is hop-count BFS, not Dijkstra
    return nx.shortest_path(g, source, target, weight="weight")

import networkx as nx
import pytest

from graph import build_dag, build_order, detect_cycle, fastest_route


def test_build_order_respects_dependencies():
    g = build_dag([("a", "b", 1), ("b", "c", 1), ("a", "c", 1)])
    assert build_order(g) == ["a", "b", "c"]


def test_cycle_raises_before_returning_order():
    g = build_dag([("a", "b", 1), ("b", "c", 1), ("c", "a", 1)])
    with pytest.raises(ValueError, match="dependency cycle"):
        build_order(g)


def test_detect_cycle_wraps_no_cycle_exception():
    cyclic = build_dag([("a", "b", 1), ("b", "c", 1), ("c", "a", 1)])
    assert detect_cycle(cyclic) is not None
    assert detect_cycle(build_dag([("a", "b", 1)])) is None


def test_self_loop_counts_as_cycle():
    g = build_dag([("a", "a", 1)])
    assert not nx.is_directed_acyclic_graph(g)
    assert detect_cycle(g) == [("a", "a")]


def test_shortest_path_ignores_weight_unless_asked():
    g = build_dag([("a", "d", 100), ("a", "b", 1), ("b", "d", 1)])
    assert nx.shortest_path(g, "a", "d") == ["a", "d"]
    assert nx.shortest_path(g, "a", "d", weight="weight") == ["a", "b", "d"]


def test_unreachable_target_raises_no_path():
    g = build_dag([("a", "b", 1), ("c", "d", 1)])
    with pytest.raises(nx.NetworkXNoPath):
        fastest_route(g, "a", "d")

[pytest]
pythonpath = .