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

torg_core/
graph.rs
