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()
    G.add_nodes_from(deps.keys())
    for task, prerequisites in deps.items():
        for prereq in prerequisites:
            G.add_edge(prereq, task)
            
    return len(nx.dag_longest_path(G))
```

The user wants a Python function `longest_dependency_chain` that calculates the length of the longest dependency chain in a DAG described by a dictionary.
The dictionary `deps` maps a node to a list of its prerequisites.
I need to use `networkx` to build a `DiGraph` and find the longest path.
The length is the number of nodes in the longest path.
If `deps` is empty, return 0.
The graph is guaranteed to be acyclic.

Let's understand the direction of edges.
`deps[x]` is the list of prerequisites of `x`. This means prerequisites must be done before `x`.
So, if `b` is a prerequisite of `a`, then `b` -> `a` in the dependency chain.
The chain is `c -> b -> a` for `{"a": ["b"], "b": ["c"], "c": []}`.
So edges should go from prerequisite to dependent.
That is, for each `x` in `deps`, and for each `p` in `deps[x]`, add edge `p -> x`.

Wait, `networkx.dag_longest_path` finds the longest path in a DAG.
The length of the path in terms of nodes is `len(nx.dag_longest_path(G))`.
If the graph is empty, `nx.dag_longest_path` might raise an error or return empty list. I should handle `deps == {}` explicitly or check if graph has nodes.

Let's construct the graph:
```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 first to ensure nodes with no dependencies and not appearing as keys are included?
    # Actually, the problem says: "Every key in deps is a node. Prerequisites listed in the values are also nodes even if they never appear as keys"
    # So we should add all nodes from keys and values.
    nodes = set(deps.keys())
    for prereqs in deps.values():
        nodes.update(prereqs)
    G.add_nodes_from(nodes)
    
    for x, prereqs in deps.items():
        for p in prereqs:
            G.add_edge(p, x)
            
    if G.number_of_nodes() == 0:
        return 0
        
    longest_path = nx.dag_longest_path(G)
    return len(longest_path)
```

Wait, `nx.dag_longest_path` works on DAGs. The problem guarantees it's a DAG.
Does `nx.dag_longest_path` require the graph to be connected? No, it finds the longest path in the whole DAG.
Let's test mentally:
`{"a": ["b"], "b": ["c"], "c": []}`
Nodes: a, b, c
Edges: b->a, c->b
Longest path: c -> b -> a, length 3. Correct.

`{"a": ["b", "c"], "b": ["d"], "c": [], "d": []}`
Nodes: a, b, c, d
Edges: b->a, c->a, d->b
Paths: d->b->a (len 3), c->a (len 2). Longest is 3. Correct.

`{"solo": []}`
Nodes: solo
Edges: none
Longest path: [solo], len 1. Correct.

Empty dict: returns 0. Correct.

One detail: `networkx.dag_longest_path` might be slow for very large graphs, but the problem doesn't specify constraints, and it explicitly says to use it.
Also, `nx.dag_longest_path` returns a list of nodes. `len()` gives the number of nodes.

Is there any case where `deps` has keys but no nodes? No, keys are nodes.
What if `deps` has nodes but they are disconnected? `dag_longest_path` handles disconnected DAGs correctly.

Wait, should I import networkx inside the function or at the top? Usually at the top.
The prompt says "Implement solution.py with: ...". I'll put the import at the top.

Let's double check `nx.dag_longest_path` behavior on empty graph.
If `G` has 0 nodes, `nx.dag_longest_path(G)` raises `NetworkXPointlessConcept: Graph has no nodes.` or similar. So handling `if not deps: return 0` is good. But what if `deps` has keys but all lists are empty? Then `G` has nodes, `dag_longest_path` returns a list with one node. That's fine.
Actually, `if not deps: return 0` covers the empty dict case.

One minor point: `nodes` set construction.
`nodes = set(deps.keys())`
`for prereqs in deps.values(): nodes.update(prereqs)`
This is correct.

Alternatively, I can just add edges, and `networkx` automatically adds nodes when adding edges. But isolated nodes (those only in values, or keys with empty lists) need to be added explicitly if they aren't part of any edge. Actually, if a node is only in values, it will be added as a source node when adding edges. If a node is a key with empty list, it won't be added by edges, so I need to add it.
So `G.add_nodes_from(deps.keys())` is enough, because values will be added via edges. Wait, if a prerequisite is listed but never a key, it will be added via `add_edge`. If a key has empty list, it needs to be added. So `G.add_nodes_from(deps.keys())` covers keys. Values are covered by edges.
But to be safe, `G.add_nodes_from(nodes)` is fine.

Let's refine:
```python
import networkx as nx

def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    if not deps:
        return 0
    
    G = nx.DiGraph()
    G.add_nodes_from(deps.keys())
    for x, prereqs in deps.items():
        for p in prereqs:
            G.add_edge(p, x)
            
    return len(nx.dag_longest_path(G))
```

Wait, what if `deps` contains nodes that are only in values and not keys? They will be added by `add_edge`.
What if `deps` is `{"a": []}`? `G` has node `a`. `dag_longest_path` returns `['a']`. Length 1. Correct.
What if `deps` is `{"a": ["b"]}`? `G` has nodes `a`, `b`. Edge `b->a`. Longest path `['b', 'a']`. Length 2. Correct.

Is there any case where `deps` has keys but `dag_longest_path` fails? Only if graph has cycles, but problem guarantees DAG.
One thing: `nx.dag_longest_path` might be deprecated in newer networkx versions in favor of `nx.dag_longest_path_length`? Actually, `nx.dag_longest_path` is still standard. `nx.dag_longest_path_length` returns the number of edges, not nodes. The problem asks for number of nodes. So `len(nx.dag_longest_path(G))` is correct. Or `nx.dag_longest_path_length(G) + 1`. But `len()` is safer and matches the prompt's hint: "note that `dag_longest_path` returns a list of nodes, and you want its node count".

Let's stick to `len(nx.dag_longest_path(G))`.

Check imports: `import networkx as nx` at the top.
The function signature matches.
Code looks solid.

One detail: `deps` might contain duplicate prerequisites? The problem says `list[str]`, doesn't specify uniqueness, but `add_edge` handles duplicates fine.
What about `deps` having nodes tha
…[3343 chars elided]…
and `a`. So `b` is in graph. Correct.
What if `deps` is `{"a": []}`? `G` has `a`. `dag_longest_path` returns `['a']`. Length 1. Correct.
What if `deps` has multiple disconnected components? `dag_longest_path` finds the longest across all. Correct.
The code handles all cases correctly.
I will write it out. 
One detail: `import networkx as nx` should be at the top of the file.
The prompt asks to implement `solution.py` with the function. I'll provide the full file content.
All good. 
Output matches request. 
Proceeds. 
```python
import networkx as nx

def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    if not deps:
        return 0
        
    G = nx.DiGraph()
    G.add_nodes_from(deps.keys())
    for task, prerequisites in deps.items():
        for prereq in prerequisites:
            G.add_edge(prereq, task)
            
    return len(nx.dag_longest_path(G))
```
This looks solid. I'll output it. 
Wait, should I handle the case where `deps` is not empty but `G` has no nodes? That's impossible because keys are nodes.
What about `nx.dag_longest_path` on a graph with 1 node? Returns list of 1 node. Length 1. Correct.
All good.
Output matches. 
Proceeds. 
[Final Check]
The prompt says: "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)."
My code does exactly that.
I will produce the solution. 
One minor point: `networkx` might need to be imported. I'll include it.
The function signature matches exactly.
Ready. 
Output generation. 
(Self-Correction/Refinement during thought)
Actually, `nx.dag_longest_path` might raise an error if the graph is empty, but I handle `if not deps: return 0`. What if `deps` has keys but they are all empty lists? `G` has nodes, `dag_longest_path` works.
What if `deps` is `{"a": ["b"], "b": []}`? `G` has a, b. Edge b->a. Path b->a. Len 2. Correct.
Everything is fine.
I will output the code. 
No extra text.
Done. 
[Output Generation] -> *Proceeds*