py-09-networkx-dep-chain

# Longest dependency chain (networkx)

Implement **`solution.py`** with:

```python
def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    ...
```

`deps` describes a **DAG** of build/task dependencies: `deps[x]` is the list of
**prerequisites** of `x` (the things that must be done before `x`).

Return the **length of the longest dependency chain**, measured as the **number of
nodes** in that chain (a single node with no dependencies has a chain length of 1).

Details:

- Every key in `deps` is a node. Prerequisites listed in the values are also nodes
  even if they never appear as keys (they implicitly have no prerequisites).
- The empty graph (`deps == {}`) has a longest-chain length of `0`.
- The input is guaranteed to be acyclic.
- Use **networkx**: build a `DiGraph` and use a topological/DAG routine such as
  `networkx.dag_longest_path` (note that `dag_longest_path` returns a list of
  nodes, and you want its node count).

Example:

```python
longest_dependency_chain({"a": ["b"], "b": ["c"], "c": []})
# 3   (chain c -> b -> a)

longest_dependency_chain({"a": ["b", "c"], "b": ["d"], "c": [], "d": []})
# 3   (chain d -> b -> a)

longest_dependency_chain({"solo": []})
# 1
```

from solution import longest_dependency_chain


def test_linear_chain():
    assert longest_dependency_chain({"a": ["b"], "b": ["c"], "c": []}) == 3


def test_branch():
    deps = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}
    assert longest_dependency_chain(deps) == 3  # d -> b -> a


def test_single_node():
    assert longest_dependency_chain({"solo": []}) == 1


def test_empty_graph():
    assert longest_dependency_chain({}) == 0


def test_implicit_prereq_nodes():
    # "c" is never a key but is a prerequisite of "b"
    deps = {"a": ["b"], "b": ["c"]}
    assert longest_dependency_chain(deps) == 3


def test_two_disconnected_chains():
    deps = {"a": ["b"], "b": [], "x": ["y"], "y": ["z"], "z": []}
    # longest is x -> y -> z reversed: z -> y -> x = 3
    assert longest_dependency_chain(deps) == 3


def test_diamond():
    deps = {"top": ["l", "r"], "l": ["base"], "r": ["base"], "base": []}
    assert longest_dependency_chain(deps) == 3


def test_all_independent():
    deps = {"a": [], "b": [], "c": []}
    assert longest_dependency_chain(deps) == 1

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
import networkx as nx

def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    graph = nx.DiGraph()
    for node, prereqs in deps.items():
        for prereq in prereqs:
            graph.add_edge(prereq, node)
    if not graph:
        return 0
    longest_path = nx.dag_longest_path(graph)
    return len(longest_path)
```

[
  {
    "total": 8,
    "answer": "```python\nimport networkx as nx\n\ndef longest_dependency_chain(deps: dict[str, list[str]]) -> int:\n    graph = nx.DiGraph()\n    for node, prereqs in deps.items():\n        for prereq in prereqs:\n            graph.add_edge(prereq, node)\n    if not graph:\n        return 0\n    longest_path = nx.dag_longest_path(graph)\n    return len(longest_path)\n```",
    "passed": 6,
    "test_error": "..F....F                                                                 [100%]\n=================================== FAILURES ===================================\n_______________________________ test_single_node _______________________________\n\n    def test_single_node():\n>       assert longest_dependency_chain({\"solo\": []}) == 1\nE       AssertionError: assert 0 == 1\nE        +  where 0 = longest_dependency_chain({'solo': []})\n\ntest_dep_chain.py:14: AssertionError\n_____________________________ test_all_independent _____________________________\n\n    def test_all_independent():\n        deps = {\"a\": [], \"b\": [], \"c\": []}\n>       assert longest_dependency_chain(deps) == 1\nE       AssertionError: assert 0 == 1\nE        +  where 0 = longest_dependency_chain({'a': [], 'b': [], 'c': []})\n\ntest_dep_chain.py:40: AssertionError\n=========================== short test summary info ============================\nFAILED test_dep_chain.py::test_single_node - AssertionError: assert 0 == 1\nFAILED test_dep_chain.py::test_all_independent - AssertionError: assert 0 == 1\n2 failed, 6 passed in 0.07s"
  },
  {
    "total": 8,
    "answer": "```python\nimport networkx as nx\n\ndef longest_dependency_chain(deps: dict[str, list[str]]) -> int:\n    graph = nx.DiGraph()\n    for node, prereqs in deps.items():\n        graph.add_node(node)\n        for prereq in prereqs:\n            graph.add_edge(prereq, node)\n    if not graph:\n        return 0\n    longest_path = nx.dag_longest_path(graph)\n    return len(longest_path)\n```",
    "passed": 8,
    "test_error": ""
  }
]