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.

To solve this problem, we need to determine the length of the longest dependency chain in a Directed Acyclic Graph (DAG) represented by a dictionary of dependencies. Each key in the dictionary represents a node, and its value is a list of prerequisites that must be completed before the key node can be processed.

### Approach
1. **Graph Construction**: Convert the given dependency dictionary into a networkx DiGraph. This involves:
   - Collecting all nodes, which include both the keys and the values from the dictionary.
   - Adding edges from each prerequisite to its dependent node.
   
2. **Longest Path Calculation**: Use the `networkx.dag_longest_path` function to find the longest path in the DAG. This function returns the longest path as a list of nodes, and the length of this list gives the length of the longest dependency chain.

3. **Edge Cases Handling**: Handle cases where the input dictionary is empty by returning 0, as there are no nodes in the graph.

### Solution Code
```python
import networkx as nx

def longest_dependency_chain(deps: dict[str, list[str]]) -> int:
    if not deps:
        return 0
    g = nx.DiGraph()
    nodes = set(deps.keys())
    for key in deps:
        nodes.update(deps[key])
    g.add_nodes_from(nodes)
    for x in deps:
        for y in deps[x]:
            g.add_edge(y, x)
    longest_path = nx.dag_longest_path(g)
    return len(longest_path)
```

### Explanation
1. **Graph Construction**:
   - We start by creating an empty DiGraph.
   - We collect all nodes by taking the union of the keys and the values from the input dictionary.
   - For each node, we add edges from each of its prerequisites to the node itself.

2. **Longest Path Calculation**:
   - Using the `networkx.dag_longest_path` function, we find the longest path in the constructed DAG. This function efficiently computes the longest path in a DAG using topological sorting.
   - The length of the longest path is returned as the result.

3. **Edge Cases**:
   - If the input dictionary is empty, the function immediately returns 0, as there are no nodes to process.
   - For non-empty dictionaries, the function constructs the graph and computes the longest path, ensuring correct handling of all nodes and edges.

This approach efficiently leverages networkx's built-in functionality to handle the problem, ensuring correctness and optimal performance for finding the longest dependency chain in a DAG.

Okay, I need to solve this problem where I have to find the longest dependency chain in a given DAG. The function is called longest_dependency_chain and it takes a dictionary called deps. Each key in deps is a node, and the value is a list of prerequisites. So, for example, if deps is {"a": ["b"]}, that means 'b' must be done before 'a'.

The goal is to return the length of the longest chain, which is the number of nodes in that chain. So, a single node with no dependencies has a chain length of 1.

Hmm, I remember that in graph theory, the longest path in a DAG can be found using topological sorting. But wait, the problem says to use networkx, specifically the dag_longest_path function. Oh right, networkx has a function called dag_longest_path which returns the longest path in a directed acyclic graph.

So the plan is to:

1. Convert the given deps dictionary into a networkx DiGraph.
2. Use the dag_longest_path function to find the longest path.
3. Return the length of that path.

But wait, how do I construct the graph from the deps? Let's think. Each key in deps is a node, and each value is a list of nodes that are prerequisites. So for each node x, deps[x] is the list of nodes that must come before x. So in the graph, for each x, we need to add edges from each prerequisite to x.

Wait, no. Because in the graph, an edge from A to B means A must come before B. So if x has a prerequisite y, then y must be done before x. So in the graph, we should have an edge from y to x.

So for each x in deps, for each y in deps[x], add an edge from y to x.

But wait, what about nodes that are not keys in deps? The problem says that every key is a node, and the prerequisites are also nodes, even if they are not keys. So for example, if deps is {"a": ["b"]}, then 'b' is a node but not a key. So in the graph, 'b' must be considered as a node, but it has no prerequisites unless specified.

So to build the graph correctly, I need to make sure all nodes are included. So the nodes are all the keys in deps plus all the nodes mentioned in the values of deps.

Wait, but the keys are the nodes that have prerequisites. The nodes in the values are the prerequisites, which may or may not have their own prerequisites. So the graph should include all nodes that are either in the keys or in the values.

So first, I need to collect all the nodes. How?

I can create a set of all nodes. For each key in deps, add it to the set. Then, for each key's value (prerequisites), add each prerequisite to the set.

Once I have all the nodes, I can create a DiGraph and add edges for each prerequisite.

Wait, but in the example given:

In the first example, deps is {"a": ["b"], "b": ["c"], "c": []}. So the nodes are a, b, c. Edges are a->b, b->c, and c has no outgoing edges.

Wait, no. Wait, the edges should be from the prerequisites to the node. So for a, the prerequisites are b, so edge from b to a. For b, prerequisites are c, so edge from c to b. For c, no prerequisites, so no edges.

So the graph would have edges c->b, b->a. So the longest path is c -> b -> a, which is length 3.

So the function should return 3.

So in the graph, each node's prerequisites are the nodes that must come before it. So for each x in deps, for each y in deps[x], add an edge from y to x.

So the steps are:

1. Collect all nodes: all keys in deps, plus all values in deps (since they are nodes too).

Wait, but the values are lists of strings, each string is a node. So for example, if deps is {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}, then the nodes are a, b, c, d.

So to collect all nodes, I can do:

nodes = set(deps.keys())
for key in deps:
    nodes.update(deps[key])

So that's how I get all the nodes.

Then, for each node x in deps, for each prerequisite y in deps[x], add an edge from y to x.

So for each x in deps:
    for y in deps[x]:
        add_edge(y, x)

But wait, what if a node is not in deps? Like in the first example, 'c' is a node but not a key. So in that case, when x is 'c', deps[x] is an empty list, so no edges are added for 'c'. But 'c' is a node, so it's included in the graph.

So the process is:

- Create a DiGraph.
- Add all nodes to the graph.
- For each x in deps, add edges from each y in deps[x] to x.

Wait, but in the first example, 'c' is a node but not a key. So when x is 'a', deps[x] is ['b'], so we add an edge from 'b' to 'a'. When x is 'b', deps[x] is ['c'], so edge from 'c' to 'b'. When x is 'c', deps[x] is empty, so no edges.

So the graph will have edges c->b, b->a.

So the longest path is c->b->a, which is length 3.

So that's correct.

Now, the function in networkx is called dag_longest_path, which returns the longest path as a list of nodes. The length is the number of nodes in that list.

So, the steps in code:

1. Import networkx as nx.

2. Create a DiGraph.

3. Collect all nodes.

4. Add all nodes to the graph.

5. For each x in deps, for each y in deps[x], add an edge from y to x.

6. Use nx.dag_longest_path to find the longest path.

7. Return the length of that path.

But wait, what about the case where the graph is empty? Like deps is empty. Then, the function should return 0.

In the example, when deps is empty, the function returns 0.

So, in code:

if the graph has no nodes, return 0.

Else, find the longest path and return its length.

Wait, but in the case where deps is empty, the nodes set is empty, so the graph has no nodes. So the function returns 0.

Another example: {"solo": []} returns 1.

So, the code should handle that.

Now, let's think about the code.

First, import networkx.

Then, in the function:

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

We can proceed as follows.

First, create the graph.

g = nx.DiGraph()

Then, collect all nodes.

nodes = set(deps.keys())
for key in deps:
    nodes.update(deps[key])

g.add_nodes_from(nodes)

Then, add edges.

for x in deps:
    for y in deps[x]:
        g.add_edge(y, x)

Then, find the longest path.

longest_path = nx.dag_longest_path(g)

The length is len(longest_path).

But wait, what if the graph is empty? Like, nodes is empty. Then, the function returns 0.

But in 
…[4265 chars elided]…
 if deps is not empty, nodes is at least the keys, which are non-empty.

So, the initial 'if not deps' is sufficient to return 0.

Wait, no. Because if deps is not empty, but the nodes set is empty. How?

Wait, no. Because the nodes set is the union of the keys and the values. So if deps is not empty, the keys are non-empty, so nodes is non-empty.

So, the initial 'if not deps' is correct.

Wait, but what if deps is {"a": ["b"], "b": ["c"], "c": ["d"], ...}, but the nodes are a, b, c, d. So the graph is built correctly.

So, the code should be correct.

Wait, but what about the case where the graph has multiple components, but the function correctly finds the longest path.

Yes, because the function returns the longest path in the entire graph.

Another thing to consider: the function returns the length of the longest path, which is the number of nodes in that path.

So, the code seems correct.

Testing the examples:

First example:

deps = {"a": ["b"], "b": ["c"], "c": []}

nodes are a, b, c.

Edges: b->a, c->b.

Longest path is c->b->a, length 3.

Second example:

deps = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}

nodes are a, b, c, d.

Edges: b->a, c->a, d->b.

Longest path is d->b->a, length 3.

Third example:

deps = {"solo": []}

nodes: solo.

Edges: none.

Longest path is [solo], length 1.

Another test case: empty deps returns 0.

Another test case: deps = {"x": ["y"], "y": ["z"], "z": []}.

Longest path is z->y->x, length 3.

Another test case: deps = {"a": ["b", "c"], "b": [], "c": []}.

Longest path is a's prerequisites are b and c. So the possible paths are b->a and c->a. So the longest path is length 2.

So, the function returns 2.

So, the code seems to handle all cases.

Wait, but in the code, the initial check is 'if not deps: return 0'. But what if deps is not empty, but the graph is empty? Like, deps is {"a": []}, but the nodes set is {'a'}, so the graph has one node, and the longest path is length 1.

So the code correctly returns 1.

So, the code is correct.

I think that's the solution.