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()

    for node, prerequisites in deps.items():
        G.add_node(node)
        for prereq in prerequisites:
            G.add_edge(prereq, node)

    longest_path = nx.dag_longest_path(G)
    return len(longest_path)
```

The user wants a Python function `longest_dependency_chain` that takes a dictionary `deps` representing a DAG of dependencies and returns the length of the longest dependency chain (number of nodes).

Key requirements:
1. Use networkx
2. Build a DiGraph
3. Use `networkx.dag_longest_path` or similar
4. Handle edge cases: empty graph returns 0, single node returns 1
5. Prerequisites that don't appear as keys are still nodes (implicitly with no prerequisites)

Let me think about the graph construction:
- `deps[x]` is the list of prerequisites of x
- So if `deps["a"] = ["b"]`, then b must be done before a
- In terms of edges: b -> a (b is a prerequisite of a)
- Or we could think of it as: a depends on b, so there's an edge from b to a

Wait, let me reconsider. In networkx DiGraph, if we add edge (u, v), it means u -> v.

If `deps["a"] = ["b"]`, then b is a prerequisite of a. So b must come before a. The dependency chain would be b -> a.

So for each key x and each prerequisite p in deps[x], we add an edge from p to x.

Then `dag_longest_path` will give us the longest path in this DAG, and we return its length.

Let me verify with the examples:

Example 1: `{"a": ["b"], "b": ["c"], "c": []}`
- a depends on b: edge b -> a
- b depends on c: edge c -> b
- c has no dependencies
- Graph: c -> b -> a
- Longest path: [c, b, a], length 3 ✓

Example 2: `{"a": ["b", "c"], "b": ["d"], "c": [], "d": []}`
- a depends on b: edge b -> a
- a depends on c: edge c -> a
- b depends on d: edge d -> b
- c has no dependencies
- d has no dependencies
- Graph: d -> b -> a, c -> a
- Longest path: [d, b, a], length 3 ✓

Example 3: `{"solo": []}`
- solo has no dependencies
- Graph: just node "solo"
- Longest path: ["solo"], length 1 ✓

Empty graph: `{}`
- No nodes
- Longest path: [], length 0 ✓

Now let me implement this:

```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 their prerequisites)
    for node, prerequisites in deps.items():
        G.add_node(node)
        for prereq in prerequisites:
            G.add_node(prereq)
            G.add_edge(prereq, node)
    
    # Find longest path
    longest_path = nx.dag_longest_path(G)
    return len(longest_path)
```

Wait, I need to be careful. If deps is empty, there are no nodes, so the longest path is empty with length 0. That's handled.

But what if there are nodes with no dependencies? Like `{"solo": []}`. The graph will have node "solo" with no edges. `dag_longest_path` should return ["solo"] with length 1.

Actually, let me double-check: does `nx.dag_longest_path` work on a graph with isolated nodes? Yes, it should return one of them.

Let me also consider: what if there are prerequisites that are never keys? Like `{"a": ["b"]}` where "b" is not a key. My code adds "b" as a node via `G.add_node(prereq)`, so that's handled.

Actually, I can simplify: when I add an edge, networkx automatically adds the nodes. So I don't need explicit `add_node` calls. But I do need to add nodes that have no edges (like nodes with empty prerequisite lists that are keys).

Let me refine:

```python
import networkx as nx

def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    if not deps:
        return 0
    
    G = nx.DiGraph()
    
    for node, prerequisites in deps.items():
        for prereq in prerequisites:
            G.add_edge(prereq, node)
    
    # Add nodes that have no edges (keys with empty prerequisites)
    for node in deps.keys():
        if node not in G:
            G.add_node(node)
    
    longest_path = nx.dag_longest_path(G)
    return len(longest_path)
```

Hmm, but this is getting complicated. Let me think again.

Actually, the simplest approach:
1. Add all keys as nodes
2. For each key and its prerequisites, add edges from prerequisite to key

```python
import networkx as nx

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

This should work because:
- All keys are added as nodes
- All prerequisites are added as nodes automatically when edges are added
- Edges go from prerequisite to dependent (prereq -> node)

Let me verify once more with example 1:
- deps = {"a": ["b"], "b": ["c"], "c": []}
- Process "a": add node "a", add edge "b" -> "a" (adds node "b" automatically)
- Process "b": add node "b", add edge "c" -> "b" (adds node "c" automatically)
- Process "c": add node "c"
- Graph: c -> b -> a
- Longest path: [c, b, a], length 3 ✓

Looks good. Let me write the final solution.