---
slug: "DAG"
name: "DAG"
type: "Data Structures"
layer: "Infrastructure"
ref: "DAG#ed5b"
sema_id: "sema:DAG#mh:SHA-256:ed5b6bdbe8d785f1dceb6cc1c7020d9c2340be7b507a3678da2da58211e455aa"
tags: ["Infrastructure","Data Structures"]
updated: 2026-11-11
mindscape: "bootstrap"
index_url: https://mindscape.pages.dev/bootstrap/index.json
url: https://mindscape.pages.dev/bootstrap/DAG/
related: ["Parallelize","Topology","GraphOfThought"]
---

# DAG

Directed acyclic dependency graph

Layer: Infrastructure · Category: Data Structures

## Mechanism

A directed acyclic graph [Topology](https://mindscape.pages.dev/bootstrap/Topology.md) that allows branching ([Parallelize](https://mindscape.pages.dev/bootstrap/Parallelize.md)) and merging, but forbids cycles. It models complex dependency chains where tasks can run concurrently but must respect precedence.

## Invariants

- Acyclic: no path leads from a node back to itself.
- Edges are directed.
- Rooted: exactly one node has no predecessor, named by `root_id`.
- Nodes with no directed path between them may run concurrently.

## Failure modes

- Cycle on insert: an added edge closes a loop, which the acyclicity invariant forbids and which must be detected at insertion rather than at traversal.
- False precedence: an edge asserts a dependency that does not exist, serialising work that could have run concurrently.

## Data schema

```json
{
  "type": "object",
  "required": [
    "nodes",
    "edges",
    "root_id"
  ],
  "properties": {
    "nodes": {
      "type": "array",
      "description": "List of task nodes"
    },
    "edges": {
      "type": "array",
      "description": "Dependency arrows (Task A -> Task B)"
    },
    "root_id": {
      "type": "string",
      "description": "Entry point(s) for execution"
    }
  }
}
```

## Builds on

- [Parallelize](https://mindscape.pages.dev/bootstrap/Parallelize.md) (Mind; References)
- [Topology](https://mindscape.pages.dev/bootstrap/Topology.md) (Infrastructure; References)

## Used by

- [GraphOfThought](https://mindscape.pages.dev/bootstrap/GraphOfThought.md) (Mind; Composes with)

## Identity

- Sema ID: `sema:DAG#mh:SHA-256:ed5b6bdbe8d785f1dceb6cc1c7020d9c2340be7b507a3678da2da58211e455aa`
- Ref: `DAG#ed5b`
- Supersedes:
  - `sema:DAG#mh:SHA-256:ed37a1e0310857feba371491e4652f9a142905af341adbc67e6386c5b3c1672f`
  - `sema:DAG#mh:SHA-256:ed81568cef305d3f4f39c7ef157bfc4c74ef721c8ad1e9001a2d11793ce936df`
  - `sema:DAG#mh:SHA-256:cb54c9360f063d839412e33158dc205c02af684d85132f6a982caba17274f253`

## Links

- [Pattern page](https://mindscape.pages.dev/bootstrap/DAG/)
- [View in the interactive graph](https://mindscape.pages.dev/bootstrap/#DAG)
- [JSON](https://mindscape.pages.dev/bootstrap/DAG.json)
- [Index of all patterns](https://mindscape.pages.dev/bootstrap/index.json)