torg_core/
graph.rs

1//! DAG representation for TØR-G boolean circuits.
2
3use crate::token::{BoolOp, Source};
4
5/// A node in the boolean circuit.
6///
7/// Each node performs a binary boolean operation on two source operands.
8/// Nodes are stored in topological order, so evaluation can proceed
9/// sequentially without dependency resolution.
10#[derive(Debug, Clone, PartialEq, Eq)]
11#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
12pub struct Node {
13    /// The unique identifier for this node.
14    pub id: u16,
15    /// The boolean operation this node performs.
16    pub op: BoolOp,
17    /// Left operand source.
18    pub left: Source,
19    /// Right operand source.
20    pub right: Source,
21}
22
23impl Node {
24    /// Create a new node.
25    pub fn new(id: u16, op: BoolOp, left: Source, right: Source) -> Self {
26        Self {
27            id,
28            op,
29            left,
30            right,
31        }
32    }
33}
34
35/// The complete TØR-G graph (DAG).
36///
37/// A graph consists of:
38/// - Input declarations (external boolean values)
39/// - Node definitions (boolean operations on sources)
40/// - Output declarations (which node IDs are graph outputs)
41///
42/// The graph is guaranteed to be a DAG because nodes can only
43/// reference previously-defined IDs.
44#[derive(Debug, Clone, Default, PartialEq, Eq)]
45#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
46pub struct Graph {
47    /// Declared input IDs (in declaration order).
48    pub inputs: Vec<u16>,
49    /// Node definitions (in topological order).
50    pub nodes: Vec<Node>,
51    /// Output IDs (in declaration order).
52    pub outputs: Vec<u16>,
53}
54
55impl Graph {
56    /// Create an empty graph.
57    pub fn new() -> Self {
58        Self::default()
59    }
60
61    /// Number of nodes (excluding inputs).
62    pub fn node_count(&self) -> usize {
63        self.nodes.len()
64    }
65
66    /// Number of declared inputs.
67    pub fn input_count(&self) -> usize {
68        self.inputs.len()
69    }
70
71    /// Number of declared outputs.
72    pub fn output_count(&self) -> usize {
73        self.outputs.len()
74    }
75
76    /// Calculate graph depth (longest path from input to output).
77    ///
78    /// Depth is defined as the maximum number of node hops from any
79    /// input to any output. A graph with only inputs feeding directly
80    /// to outputs has depth 1.
81    pub fn depth(&self) -> usize {
82        if self.nodes.is_empty() {
83            return 0;
84        }
85
86        // Build depth map: ID -> depth
87        // Inputs and constants have depth 0
88        // Nodes have depth = 1 + max(depth of sources)
89        let mut depths = std::collections::HashMap::new();
90
91        // Initialize inputs with depth 0
92        for &id in &self.inputs {
93            depths.insert(id, 0usize);
94        }
95
96        // Compute depth for each node (nodes are in topological order)
97        for node in &self.nodes {
98            let left_depth = self.source_depth(&node.left, &depths);
99            let right_depth = self.source_depth(&node.right, &depths);
100            let node_depth = 1 + left_depth.max(right_depth);
101            depths.insert(node.id, node_depth);
102        }
103
104        // Return max depth among outputs
105        self.outputs
106            .iter()
107            .filter_map(|id| depths.get(id).copied())
108            .max()
109            .unwrap_or(0)
110    }
111
112    /// Get depth of a source operand.
113    fn source_depth(
114        &self,
115        source: &Source,
116        depths: &std::collections::HashMap<u16, usize>,
117    ) -> usize {
118        match source {
119            Source::Id(id) => depths.get(id).copied().unwrap_or(0),
120            Source::True | Source::False => 0,
121        }
122    }
123
124    /// Check if an ID is a declared input.
125    pub fn is_input(&self, id: u16) -> bool {
126        self.inputs.contains(&id)
127    }
128
129    /// Get a node by its ID.
130    pub fn get_node(&self, id: u16) -> Option<&Node> {
131        self.nodes.iter().find(|n| n.id == id)
132    }
133}
134
135#[cfg(test)]
136mod tests {
137    use super::*;
138
139    #[test]
140    fn test_empty_graph_depth() {
141        let graph = Graph::new();
142        assert_eq!(graph.depth(), 0);
143    }
144
145    #[test]
146    fn test_single_node_depth() {
147        let graph = Graph {
148            inputs: vec![0, 1],
149            nodes: vec![Node::new(2, BoolOp::Or, Source::Id(0), Source::Id(1))],
150            outputs: vec![2],
151        };
152        assert_eq!(graph.depth(), 1);
153    }
154
155    #[test]
156    fn test_chain_depth() {
157        // input(0) -> node(1) -> node(2) -> output
158        let graph = Graph {
159            inputs: vec![0],
160            nodes: vec![
161                Node::new(1, BoolOp::Or, Source::Id(0), Source::True),
162                Node::new(2, BoolOp::Or, Source::Id(1), Source::False),
163            ],
164            outputs: vec![2],
165        };
166        assert_eq!(graph.depth(), 2);
167    }
168
169    #[test]
170    fn test_parallel_depth() {
171        // Two parallel paths of depth 1
172        let graph = Graph {
173            inputs: vec![0, 1],
174            nodes: vec![
175                Node::new(2, BoolOp::Or, Source::Id(0), Source::True),
176                Node::new(3, BoolOp::Or, Source::Id(1), Source::False),
177            ],
178            outputs: vec![2, 3],
179        };
180        assert_eq!(graph.depth(), 1);
181    }
182}
torg_core/graph.rs

torg_core/
graph.rs
