# UNDF: UNDF-2026-000000460
# metaflow-0001 — O(N²) Graph Traversal: list.remove() and list membership in _traverse_graph

**Severity:** HIGH
**Complexity:** O(N²) → O(N)
**CWE:** CWE-407 (Algorithmic Complexity)

## Affected File

| File | Lines | Notes |
|------|-------|-------|
| `metaflow/graph.py` | 300–340 | `_traverse_graph` inner `traverse()` function |

## Defective Code

### `metaflow/graph.py` lines 300–340

```python
def traverse(node, seen, split_parents, split_branches):
    add_split_branch = False
    try:
        self.sorted_nodes.remove(node.name)   # ← O(N) scan of list every call
    except ValueError:
        pass
    self.sorted_nodes.append(node.name)
    ...
    for n in node.out_funcs:
        if n not in seen:                      # ← O(N) scan of list per edge
            if n in self:
                child = self[n]
                child.in_funcs.add(node.name)
                traverse(
                    child,
                    seen + [n],               # ← new list allocation per recursion
                    split_parents,
                    split_branches + ([n] if add_split_branch else []),
                )
```

**Two interlocking defects:**

1. `self.sorted_nodes.remove(node.name)` — O(N) linear scan of the growing `sorted_nodes` list,
   called once per node visit. For a flow with N steps, this is O(N) scans × O(N) visits = **O(N²)**.

2. `if n not in seen` — `seen` is a Python list passed down through recursion. For a linear chain
   of N steps, checking `n not in seen` at depth D costs O(D). Summed over all depths: O(N²).
   Additionally, `seen + [n]` allocates a new list at every recursive call.

## Fix

Replace `sorted_nodes` (list) with a `dict` for O(1) membership/remove, and replace the `seen`
list with a `set`:

```python
def _traverse_graph(self):
    sorted_nodes_set = {}   # dict preserves insertion order in Python 3.7+
    seen_set = set()

    def traverse(node, split_parents, split_branches):
        add_split_branch = False
        # O(1) remove + append via ordered dict
        sorted_nodes_set.pop(node.name, None)
        sorted_nodes_set[node.name] = True

        if node.type in ("split", "foreach"):
            node.split_parents = split_parents
            node.split_branches = split_branches
            add_split_branch = True
            split_parents = split_parents + [node.name]
        elif node.type == "split-switch":
            node.split_parents = split_parents
            node.split_branches = split_branches
        elif node.type == "join":
            if split_parents:
                self[split_parents[-1]].matching_join = node.name
                node.split_parents = split_parents
                node.split_branches = split_branches[:-1]
                split_parents = split_parents[:-1]
                split_branches = split_branches[:-1]
        else:
            node.split_parents = split_parents
            node.split_branches = split_branches

        for n in node.out_funcs:
            if n not in seen_set:            # O(1) set lookup
                if n in self:
                    seen_set.add(n)
                    child = self[n]
                    child.in_funcs.add(node.name)
                    traverse(
                        child,
                        split_parents,
                        split_branches + ([n] if add_split_branch else []),
                    )

    if "start" in self:
        seen_set.add("start")
        traverse(self["start"], [], [])

    self.sorted_nodes = list(sorted_nodes_set.keys())

    for node in self.nodes.values():
        node.in_funcs = sorted(node.in_funcs)
```

## Complexity

| Metric | Before | After |
|--------|--------|-------|
| `sorted_nodes.remove` per node | O(N) | O(1) |
| `n not in seen` per edge | O(depth) | O(1) |
| `seen + [n]` allocation | O(depth) | eliminated |
| Total traverse | O(N²) | O(N + E) |

## Impact

Every `@step`-decorated Metaflow flow compiles its DAG at startup via `FlowGraph._traverse_graph`.
For flows with many steps (e.g. 500-step ML training pipelines), the quadratic traversal adds
measurable startup latency and proportionally worse latency in any system that repeatedly
re-parses flow definitions (live-reloading, CI validation pipelines).
