networkx 3.6.1: Graph, DiGraph, shortest_path

# NetworkX Graph Construction, Pathfinding, Connectivity, and Centrality

## Prior Solution Found
`search_known_solution` returned `NO_SAFE_MATCH` for `pkg:pypi/networkx@3.6.1`.

## What a Model Would Have Written
A model writing graph analysis code often:
1. Assumes `nx.shortest_path(G, s, t)` defaults to taking edge weights into account; in NetworkX, `weight=None` (unweighted shortest hop path) is the default unless `weight="weight"` is explicitly specified.
2. Catches generic `Exception` or expects `None` / empty list when no path exists or when nodes are missing, instead of catching specific `nx.NetworkXNoPath` or `nx.NodeNotFound` exceptions.
3. Conflates `nx.is_connected` (which only works on undirected graphs and raises `NetworkXNotImplemented` on `DiGraph`) with `nx.is_strongly_connected` or `nx.is_weakly_connected` for directed graphs.
4. Assumes centrality algorithms require external numerical libraries like SciPy; core NetworkX functions (`degree_centrality`, `betweenness_centrality`, `closeness_centrality`) execute in pure Python out of the box.

## How the Wrong Version Fails
- Calling `nx.is_connected(DiGraph)` fails with `networkx.exception.NetworkXNotImplemented: not implemented for directed type`.
- Calling `nx.shortest_path(G, s, t)` on weighted graphs without `weight="weight"` silently returns sub-optimal high-weight paths with fewer hops.
- Querying unreachable nodes without catching `NetworkXNoPath` crashes calling pipelines.
- Missing nodes passed to path functions raise `NodeNotFound` rather than `KeyError` or returning empty results.

Clean-room public code sample — generation instructions

Write a brand-new, minimal, self-contained code sample in this clean-room directory.
Do not copy, paraphrase, or reference any existing project source. Work only from this spec.

A csx.json manifest scaffold already exists. Do not recreate it from memory. Preserve its case.goal, packages and symbols; fill its empty case.contract with exact assertions and correct its environment, commands and verifierAdapter for the files you generate.

Goal: verify pkg:pypi/networkx@3.6.1
Kind: HOW

Use EXACTLY these public packages and versions:
  - pkg:pypi/networkx@3.6.1

Rules:
  - One focused purpose; the smallest project that proves the goal.
  - Include a contract test (test/contract.*) that runs OFFLINE and exits 0 exactly when the goal behavior works.
  - Pin every dependency with a lockfile so resolution is reproducible.
  - No secrets, credentials, or tokens. No real URLs (only example.com or localhost). No absolute paths.
  - No personal names, emails, company names, or project identifiers of any kind.
  - No binaries and no generated output (node_modules, dist, target, venv, .git, .env).
  - Keep it under 200 files and 256KB packed.

{"case":{"caseId":"case:sha256:525c47e4970ceadf5f9464911dc15f66b1b41e579cf2622ef1d678c943b0f9ef","contract":["assert shortest_path and dijkstra_path_length find the minimum-weight path and total weight on weighted graphs","assert has_path returns False and shortest_path raises NetworkXNoPath for disconnected nodes in the same graph","assert shortest_path raises NodeNotFound when either source or target node does not exist in the graph","assert is_connected and connected_components accurately identify connected components in undirected graphs","assert is_strongly_connected, is_weakly_connected and strongly_connected_components identify directed graph connectivity","assert minimum_spanning_tree computes the minimal spanning tree and preserves edge weight attributes","assert degree_centrality, betweenness_centrality and closeness_centrality compute standard structural metrics without optional dependencies","assert all_pairs_shortest_path_length and density compute global distance matrices and topological density"],"goal":"verify pkg:pypi/networkx@3.6.1","kind":"HOW","packages":["pkg:pypi/networkx@3.6.1"],"schemaVersion":1,"symbols":["networkx.Graph","networkx.DiGraph","networkx.shortest_path","networkx.dijkstra_path_length","networkx.has_path","networkx.is_connected","networkx.connected_components","networkx.is_strongly_connected","networkx.is_weakly_connected","networkx.strongly_connected_components","networkx.minimum_spanning_tree","networkx.degree_centrality","networkx.betweenness_centrality","networkx.closeness_centrality","networkx.NetworkXNoPath","networkx.NodeNotFound"]},"contractCommand":["python","test/contract.py"],"environment":{"arch":"x64","distro":"ubuntu","ecosystem":"pypi","executionContext":"python","language":"python","libc":"glibc","libcVersion":"2.39","os":"linux","osVersionBucket":"24","packageManager":"pip","runtime":"python","schemaVersion":1},"license":"MIT-0","packages":["pkg:pypi/networkx@3.6.1"],"schemaVersion":1,"subject":"pkg:pypi/networkx@3.6.1","symbols":["networkx.Graph","networkx.DiGraph","networkx.shortest_path","networkx.dijkstra_path_length","networkx.has_path","networkx.is_connected","networkx.connected_components","networkx.is_strongly_connected","networkx.is_weakly_connected","networkx.strongly_connected_components","networkx.minimum_spanning_tree","networkx.degree_centrality","networkx.betweenness_centrality","networkx.closeness_centrality","networkx.NetworkXNoPath","networkx.NodeNotFound"],"verifierAdapter":"python@1"}

networkx==3.6.1

{
  "schemaVersion": 1,
  "goal": "verify pkg:pypi/networkx@3.6.1",
  "kind": "HOW",
  "packages": [
    "pkg:pypi/networkx@3.6.1"
  ]
}

"""NetworkX graph analytics and algorithm validation."""

"""Graph construction, pathfinding, connectivity, and centrality utilities using NetworkX."""

from typing import Any, Dict, List, Optional, Set, Tuple
import networkx as nx


def build_weighted_graph(edges: List[Tuple[Any, Any, float]]) -> nx.Graph:
    """Build an undirected graph with weighted edges."""
    g = nx.Graph()
    for u, v, w in edges:
        g.add_edge(u, v, weight=w)
    return g


def find_shortest_path(g: nx.Graph, source: Any, target: Any, weight: Optional[str] = "weight") -> Tuple[List[Any], float]:
    """Find the shortest path and its total length between source and target nodes."""
    path = nx.shortest_path(g, source=source, target=target, weight=weight)
    length = nx.dijkstra_path_length(g, source=source, target=target, weight=weight)
    return path, length


def get_connected_components(g: nx.Graph) -> List[Set[Any]]:
    """Return connected components for an undirected graph."""
    return list(nx.connected_components(g))


def build_directed_graph(edges: List[Tuple[Any, Any]]) -> nx.DiGraph:
    """Build a directed graph from an edge list."""
    dg = nx.DiGraph()
    dg.add_edges_from(edges)
    return dg


def get_directed_connectivity(dg: nx.DiGraph) -> Dict[str, Any]:
    """Inspect strongly and weakly connected components in a directed graph."""
    return {
        "is_strongly_connected": nx.is_strongly_connected(dg),
        "is_weakly_connected": nx.is_weakly_connected(dg),
        "strongly_connected_components": list(nx.strongly_connected_components(dg)),
    }


def compute_minimum_spanning_tree(g: nx.Graph, algorithm: str = "kruskal") -> Tuple[nx.Graph, float]:
    """Compute the minimum spanning tree and its total weight."""
    mst = nx.minimum_spanning_tree(g, algorithm=algorithm)
    total_weight = sum(data.get("weight", 1.0) for _, _, data in mst.edges(data=True))
    return mst, float(total_weight)


def compute_centralities(g: nx.Graph) -> Dict[str, Dict[Any, float]]:
    """Compute degree, betweenness, and closeness centrality metrics."""
    return {
        "degree": nx.degree_centrality(g),
        "betweenness": nx.betweenness_centrality(g),
        "closeness": nx.closeness_centrality(g),
    }

"""Contract verification suite for pkg:pypi/networkx@3.6.1."""

from pathlib import Path
import sys

sys.path.insert(0, str(Path(__file__).resolve().parents[1]))

import networkx as nx
from src import graph_ops

# Verify version
assert nx.__version__ == "3.6.1", f"Expected networkx 3.6.1, got {nx.__version__}"

# ============================================================================
# 1. Weighted Shortest Path & Dijkstra Length
# ============================================================================
# A triangle graph where direct edge A-C is heavy (weight 10), but path A-B-C is light (4 + 1 = 5)
edges = [("A", "B", 4.0), ("B", "C", 1.0), ("A", "C", 10.0)]
g = graph_ops.build_weighted_graph(edges)

# Weighted path chooses minimum total weight path A -> B -> C
path, length = graph_ops.find_shortest_path(g, "A", "C", weight="weight")
assert path == ["A", "B", "C"]
assert length == 5.0
assert nx.has_path(g, "A", "C") is True

# Unweighted path chooses minimum hop count path A -> C
unweighted_path = nx.shortest_path(g, "A", "C", weight=None)
assert unweighted_path == ["A", "C"]

# ============================================================================
# 2. Disconnected Paths and NetworkXNoPath Handling
# ============================================================================
g.add_node("ISOLATED")
assert nx.has_path(g, "A", "ISOLATED") is False

try:
    nx.shortest_path(g, "A", "ISOLATED")
    assert False, "shortest_path between disconnected nodes must raise NetworkXNoPath"
except nx.NetworkXNoPath:
    pass

try:
    nx.dijkstra_path(g, "A", "ISOLATED", weight="weight")
    assert False, "dijkstra_path between disconnected nodes must raise NetworkXNoPath"
except nx.NetworkXNoPath:
    pass

# ============================================================================
# 3. Non-existent Node and NodeNotFound Handling
# ============================================================================
try:
    nx.shortest_path(g, "A", "NON_EXISTENT")
    assert False, "shortest_path with non-existent target must raise NodeNotFound"
except nx.NodeNotFound:
    pass

try:
    nx.shortest_path(g, "NON_EXISTENT", "A")
    assert False, "shortest_path with non-existent source must raise NodeNotFound"
except nx.NodeNotFound:
    pass

# ============================================================================
# 4. Undirected Connectivity and Connected Components
# ============================================================================
assert nx.is_connected(g) is False
components = graph_ops.get_connected_components(g)
assert len(components) == 2
assert {"A", "B", "C"} in components
assert {"ISOLATED"} in components

# Removing isolated node restores graph connectivity
g.remove_node("ISOLATED")
assert nx.is_connected(g) is True
assert len(graph_ops.get_connected_components(g)) == 1

# ============================================================================
# 5. Directed Graph Connectivity: Strong vs Weak
# ============================================================================
# Directed cycle 1 -> 2 -> 3 -> 1 with an outgoing branch 3 -> 4
directed_edges = [(1, 2), (2, 3), (3, 1), (3, 4)]
dg = graph_ops.build_directed_graph(directed_edges)
dg_conn = graph_ops.get_directed_connectivity(dg)

assert dg_conn["is_strongly_connected"] is False
assert dg_conn["is_weakly_connected"] is True
scc = dg_conn["strongly_connected_components"]
assert len(scc) == 2
assert {1, 2, 3} in scc
assert {4} in scc

# Adding return edge 4 -> 1 creates a strongly connected graph
dg.add_edge(4, 1)
assert nx.is_strongly_connected(dg) is True
assert len(list(nx.strongly_connected_components(dg))) == 1

# ============================================================================
# 6. Minimum Spanning Tree (MST)
# ============================================================================
mst_edges = [
    ("A", "B", 1.0),
    ("B", "C", 2.0),
    ("A", "C", 3.0),
    ("C", "D", 4.0),
    ("B", "D", 5.0),
]
mst_graph = graph_ops.build_weighted_graph(mst_edges)
mst, total_mst_weight = graph_ops.compute_minimum_spanning_tree(mst_graph, algorithm="kruskal")

# MST should select edges (A, B: 1), (B, C: 2), (C, D: 4) with total weight 7.0
assert total_mst_weight == 7.0
assert mst.number_of_nodes() == 4
assert mst.number_of_edges() == 3
assert nx.is_tree(mst) is True

# Verify Prim algorithm yields equivalent total weight
prim_mst = nx.minimum_spanning_tree(mst_graph, algorithm="prim")
prim_weight = sum(d["weight"] for _, _, d in prim_mst.edges(data=True))
assert prim_weight == 7.0

# ============================================================================
# 7. Centrality Metrics
# ============================================================================
# Line graph: 0 - 1 - 2
# Node 1 is central bridge: highest degree, betweenness, and closeness
path_g = nx.path_graph(3)
centralities = graph_ops.compute_centralities(path_g)

deg = centralities["degree"]
assert deg[1] == 1.0 and deg[0] == 0.5 and deg[2] == 0.5

bet = centralities["betweenness"]
assert bet[1] == 1.0 and bet[0] == 0.0 and bet[2] == 0.0

close = centralities["closeness"]
assert close[1] == 1.0 and abs(close[0] - (2.0 / 3.0)) < 1e-6 and abs(close[2] - (2.0 / 3.0)) < 1e-6

# ============================================================================
# 8. All Pairs Shortest Path & Density
# ============================================================================
all_lengths = dict(nx.all_pairs_shortest_path_length(path_g))
assert all_lengths[0][2] == 2
assert all_lengths[0][1] == 1
assert all_lengths[0][0] == 0

# Graph density: 2 edges out of max 3 possible edges in 3-node graph -> 2/3
assert abs(nx.density(path_g) - (2.0 / 3.0)) < 1e-6

print(f"CONTRACT PASS: networkx {nx.__version__} graph algorithms, paths, connectivity, MST, and centralities verified.")