Principle:Diagram of thought Diagram of thought DAG Reconstruction
Overview
Reconstructing a directed acyclic graph from parsed structural records with formal acyclicity verification (library-agnostic).
Description
DAG Reconstruction is the process of building a graph data structure from parsed nodes and edges emitted during DoT reasoning. After typed records (@node, @edge, @status) have been extracted from the model's output, they must be assembled into a coherent directed acyclic graph suitable for downstream analysis.
The critical property is acyclicity: the edge constraint (src < dst) guarantees forward progress and prevents circular reasoning. Every edge in the graph points from a lower-numbered node to a higher-numbered node, which means cycles are structurally impossible. Node metadata -- including roles (problem, proposer, critic, summarizer) and validation status marks (validated, invalidated) -- enriches the graph for downstream analysis, visualization, and formal verification.
Usage
Apply DAG Reconstruction after parsing typed records from the model's output and before any reasoning path analysis or visualization. This step transforms a flat sequence of extracted records into a structured graph that can be queried, traversed, and verified.
Theoretical Basis
A directed acyclic graph (DAG) is a directed graph with no cycles. In DoT, acyclicity is enforced by construction: edge records require src < dst (monotonically increasing node IDs). This is a topological ordering built into the protocol -- the node ID assignment itself defines a valid topological sort of the graph.
The resulting graph structure is a poset (partially ordered set) where node ID defines the partial order. Not every pair of nodes need be connected by a directed path (the order is partial, not total), but no node can reach itself through any sequence of edges. This guarantees that reasoning flows strictly forward, from earlier steps to later ones, without circular dependencies.
Formally:
- Nodes: where each node carries a role attribute from
{problem, proposer, critic, summarizer}. - Edges: where each edge carries a kind attribute from
{use, critique, refine}. - Acyclicity: Guaranteed by the constraint on all edges. Since every edge points strictly forward in the node ID ordering, no directed cycle can exist.
The reconstruction procedure assembles these components into a graph data structure and attaches status metadata to nodes. The following pseudo-code captures the essential algorithm:
dag = empty_graph()
for node in parsed_nodes:
dag.add_node(node.id, role=node.role)
for edge in parsed_edges:
assert edge.src < edge.dst # acyclicity check
dag.add_edge(edge.src, edge.dst, kind=edge.kind)
for status in parsed_statuses:
dag.nodes[status.target].mark = status.mark
The assertion edge.src < edge.dst serves as a runtime acyclicity check: if any edge violates this constraint, the model's output is structurally malformed and must be rejected or corrected. This check is computationally trivial (O(1) per edge) compared to a general cycle-detection algorithm, which is one of the practical advantages of DoT's monotonic ID convention.