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.

Looking at this problem, I need to:

1. Build a directed graph from the dependency dictionary
2. Find the longest path in the DAG (measured by number of nodes)
3. Handle edge cases like empty graphs

The key insight is that `deps[x]` contains prerequisites of `x`, meaning edges go from prerequisites to the dependent task (i.e., from each prerequisite in `deps[x]` to `x`).

Let me implement this using networkx:

```python
import networkx as nx

def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    # Handle empty graph case
    if not deps:
        return 0
    
    # Create a directed graph
    G = nx.DiGraph()
    
    # Add all nodes and edges
    # For each node x in deps, add edges from each prerequisite to x
    for node, prerequisites in deps.items():
        G.add_node(node)
        for prereq in prerequisites:
            G.add_node(prereq)  # Ensure prerequisite nodes exist even if not keys
            G.add_edge(prereq, node)  # Edge from prerequisite to dependent
    
    # Find all nodes that might not be in deps keys but are prerequisites
    all_nodes = set(deps.keys())
    for prerequisites in deps.values():
        all_nodes.update(prerequisites)
    
    # If there are no edges, the longest chain is 1 (single node)
    if G.number_of_edges() == 0:
        return 1
    
    # Find the longest path using networkx.dag_longest_path
    # This returns a list of nodes in the longest path
    longest_path = nx.dag_longest_path(G)
    
    # Return the number of nodes in the longest path
    return len(longest_path)
```