# Traverse (walking a graph)

> Walk a relation recursively — an org chart up to its root, a category tree down to its leaves, a bill of materials, a reply thread — and get back every row on the way. It is one recursive SQL query with cycle detection and a depth bound, which is the thing you cannot write with a loop of ordinary queries without paying a round trip per level.

<!-- id: query-traverse · area: query · stability: stable · html: https://osysharp.com/reference/query/traverse/ -->

## Summary        {#summary}
`Traverse` follows a relation over and over, and returns everything it reaches:

```osy title="everyone under a manager, however deep" test app=query-traverse
entity Employee {
  [Required, MaxLength(120)] string Name;
  Employee Manager;                                     // the relation to walk
  [ForeignKey(Manager)] Employee[] Reports;
  bool Active;
}

Employee[] EveryoneUnder(Employee boss) {
  return Employee.Traverse(
    from:   boss,
    follow: e => e.Reports,          // walk DOWN the collection
    depth:  10,
    where:  e => e.Active);          // …skipping anyone inactive (and everyone below them)
}
```

That is **one** query — a recursive one — not a loop that fires a query per level. It detects cycles and it is bounded
by `depth`, so a self-referencing row cannot hang it.

## Signature      {#signature}
```osy syntax
<Entity>.Traverse(
  from:          <seed> | [<seed>, <seed>],   // REQUIRED — one row, or several
  follow:        e => e.<Relation>,           // REQUIRED — an entity reference (up) or a collection (down)
  depth:         <positive int literal>,      // optional — default 10
  where:         e => <predicate>,            // optional — pruned at each hop
  match:         e => e.<Column>,             // optional — walk an edge table by VALUE (see below)
  bidirectional: true                         // optional — requires `match:`
)
```

**Named arguments only** — a positional argument is a compile error, because six positional arguments would be
unreadable and easy to get subtly wrong. `depth` must be an integer *literal*, not a variable.

## Description    {#description}

### Up or down — the direction is the relation you follow   {#direction}
`follow:` names a relation on the entity, and its *kind* decides which way you walk:

- **An entity reference** (`e => e.Manager`) walks **up** — from a row to the one it points at. Seed with an employee
  and you get their management chain to the root.
- **A collection** (`e => e.Reports`) walks **down** — from a row to the rows that point at it. Seed with a manager and
  you get their whole subtree.

Same verb, same query shape, opposite direction. It is the relation that says which.

```osy title="the chain of command above someone" test app=query-traverse
Employee[] ChainOfCommand(Employee e) {
  return Employee.Traverse(from: e, follow: x => x.Manager);   // an entity REF → walks up
}
```

### `where:` prunes, it does not filter   {#where-prunes}
This is the distinction that matters, and it is not the one people expect.

A `where:` predicate is applied **at each hop**, so a row that fails it is not just left out of the result — **it is
not walked through.** Everything beneath it is unreachable too. That is usually exactly what you want (an inactive
manager's whole branch is out of scope), and occasionally a surprise (you wanted the branch, minus that one row).

If you want to *filter* the result rather than prune the walk, traverse without a `where:` and filter what comes back.

### `depth:` is a fuse, not a target   {#depth}
`depth:` bounds how far the walk goes; it defaults to **10**. It is not a promise that the graph is that deep — it is
the thing that stops a walk running away. Combined with cycle detection (a row is never visited twice), a
self-referencing hierarchy fails safe rather than hanging.

Raise it when your hierarchy is genuinely deeper; do not remove it, because there is no removing it.

### Edges held by value: `match:` and `bidirectional:`   {#match}
Sometimes the graph is not a declared relation at all — it is an edge table holding two references (a "related
product", a "duplicate of", a follower graph). `match:` walks by **column value** rather than by relation:

- `follow:` names the column to leave by, `match:` names the column to arrive at.
- **`bidirectional: true`** walks the edge in both directions — the shape a symmetric relationship ("is related to")
  actually has, where an edge recorded one way should be found from either end.

### What it gives back   {#result}
A collection of the rows it reached — the same entity type you started from. It is not a chain: you cannot `Where` or
`OrderBy` a `Traverse`. Materialise it and work on the result.

**Entity-only.** There is nothing to traverse on a local [list](https://osysharp.com/reference/query/in-memory-linq/).

## Examples       {#examples}
A category tree, and why a hand-rolled loop is not the same thing:

```osy title="a category and every category beneath it" test app=query-traverse
entity Category {
  [Required, MaxLength(80)] string Name;
  Category Parent;
  [ForeignKey(Parent)] Category[] Children;
}

Category[] Subtree(Category root) {
  return Category.Traverse(from: root, follow: c => c.Children, depth: 6);
}

Category[] Roots(Category a, Category b) {
  return Category.Traverse(from: [a, b], follow: c => c.Parent);   // several seeds at once
}
```

Written by hand, the first one is a queue, a visited-set, a cycle check, and one query per level — and it is a query
per level that makes it slow on a deep tree, which is precisely the thing a recursive query avoids.

## See also       {#see-also}
- [Child collections (navigating a relation)](https://osysharp.com/reference/query/collections/) — a single hop: a parent's children
- [Include (pre-loading relations)](https://osysharp.com/reference/query/include/) — pre-loading a *known* depth of graph, rather than an unknown one
- [relations](https://osysharp.com/reference/entity/relations/) — declaring the self-relation a traverse walks
- [Querying data](https://osysharp.com/reference/query/index/) — where `Traverse` sits (it is not a chain verb)