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:
    if not deps:
        return 0
    
    G = nx.DiGraph()
    
    # Collect all nodes (keys and all prerequisites)
    all_nodes = set(deps.keys())
    for prerequisites in deps.values():
        all_nodes.update(prerequisites)
    
    G.add_nodes_from(all_nodes)
    
    # Add edges: prerequisite -> node (prerequisite must come before node)
    for node, prerequisites in deps.items():
        for prereq in prerequisites:
            G.add_edge(prereq, node)
    
    # Find longest path in the DAG and return its length (number of nodes)
    longest_path = nx.dag_longest_path(G)
    return len(longest_path)
```

Let me break down this problem:

1. I need to implement `longest_dependency_chain` that takes a dictionary where keys are nodes and values are lists of prerequisites (dependencies)
2. I need to use networkx to build a DiGraph and find the longest path
3. The result should be the number of nodes in the longest chain

Key considerations:
- `deps[x]` contains prerequisites of `x`, meaning edges go from prerequisites to `x`
- So if `deps["a"] = ["b"]`, there's an edge from `b` to `a` (b must be done before a)
- The longest chain is the longest path in this DAG
- Empty graph returns 0
- Single node with no dependencies returns 1

Let me think about the networkx approach:
1. Create a DiGraph
2. Add edges: for each node `x` with prerequisites `[p1, p2, ...]`, add edges from each prerequisite to `x`
3. Use `networkx.dag_longest_path` to get the longest path
4. Return the length of that path (number of nodes)

Wait, I need to be careful about nodes that only appear as prerequisites but not as keys. According to the problem:
- "Prerequisites listed in the values are also nodes even if they never appear as keys (they implicitly have no prerequisites)"

So I need to make sure all nodes (both keys and all prerequisites) are in the graph.

Let me write the solution:

```python
import networkx as nx

def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    if not deps:
        return 0
    
    G = nx.DiGraph()
    
    # Add all nodes (keys and all prerequisites)
    all_nodes = set(deps.keys())
    for prerequisites in deps.values():
        all_nodes.update(prerequisites)
    
    G.add_nodes_from(all_nodes)
    
    # Add edges: prerequisite -> node
    for node, prerequisites in deps.items():
        for prereq in prerequisites:
            G.add_edge(prereq, node)
    
    # Find longest path
    longest_path = nx.dag_longest_path(G)
    
    return len(longest_path)
```

Wait, let me verify with the examples:

Example 1: `{"a": ["b"], "b": ["c"], "c": []}`
- Nodes: a, b, c
- Edges: b -> a, c -> b
- Longest path: c -> b -> a (length 3) ✓

Example 2: `{"a": ["b", "c"], "b": ["d"], "c": [], "d": []}`
- Nodes: a, b, c, d
- Edges: b -> a, c -> a, d -> b
- Longest path: d -> b -> a (length 3) ✓

Example 3: `{"solo": []}`
- Nodes: solo
- No edges
- Longest path: solo (length 1) ✓

All examples check out. The solution correctly handles nodes that only appear as prerequisites and returns the right chain lengths. I need to verify the edge direction matches the dependency semantics. In a dependency graph, if `b` is a prerequisite for `a`, the edge should flow from `b` to `a`, representing the prerequisite relationship.

With `nx.dag_longest_path`, the algorithm finds the longest path in the DAG. Since edges go from prerequisites to dependents, the path naturally represents the dependency chain from earliest prerequisite to final dependent.

For the empty graph case, I should return 0 as specified. The current implementation handles this by checking if `deps` is empty before proceeding.

Let me verify the edge cases work correctly:
- Empty dictionary returns 0
- Single node with no dependencies returns 1
- Multiple nodes with dependencies returns the longest chain length

The solution looks correct. I'll add the import and finalize the implementation.