cvkg_render_gpu/kvasir/
graph.rs

1//! KvasirGraph data structure, builder, and topological compilation.
2
3use std::collections::{HashMap, VecDeque};
4
5use super::KvasirError;
6use super::resource::ResourceId;
7
8/// Opaque key for a node in the graph.
9#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
10pub struct NodeKey(pub usize);
11
12/// Edge: producer_node --[resource]--> consumer_node.
13#[derive(Clone, Debug)]
14pub struct Edge {
15    pub producer: NodeKey,
16    pub resource: ResourceId,
17    pub consumer: NodeKey,
18}
19
20/// The render graph. Nodes and edges form a DAG. The `roots` are nodes with
21/// no inputs (scene sources); `sinks` are the final present/output nodes.
22#[derive(Default)]
23pub struct KvasirGraph {
24    nodes: Vec<Box<dyn super::node::KvasirNode>>,
25    edges: Vec<Edge>,
26    /// Adjacency: node -> [(resource, consumer)] for topological sort.
27    adjacency: HashMap<NodeKey, Vec<(ResourceId, NodeKey)>>,
28    /// Reverse adjacency: node -> [producer] for dependency tracking.
29    reverse_adj: HashMap<NodeKey, Vec<NodeKey>>,
30    next_key: usize,
31}
32
33impl KvasirGraph {
34    pub fn new() -> Self {
35        Self::default()
36    }
37
38    /// Add a node to the graph. Returns its key.
39    pub fn add_node(&mut self, node: Box<dyn super::node::KvasirNode>) -> NodeKey {
40        let key = NodeKey(self.next_key);
41        self.next_key += 1;
42        self.nodes.push(node);
43        key
44    }
45
46    /// Declare that `consumer` reads `resource` produced by `from`.
47    pub fn connect(&mut self, from: NodeKey, resource: ResourceId, to: NodeKey) {
48        self.edges.push(Edge {
49            producer: from,
50            resource,
51            consumer: to,
52        });
53        self.adjacency.entry(from).or_default().push((resource, to));
54        self.reverse_adj.entry(to).or_default().push(from);
55    }
56
57    /// Kahn's algorithm for topological sort.
58    pub fn topological_sort(&self) -> Result<Vec<NodeKey>, KvasirError> {
59        let n = self.nodes.len();
60        let mut in_degree: HashMap<NodeKey, usize> = HashMap::new();
61        for key in (0..n).map(NodeKey) {
62            in_degree.entry(key).or_insert(0);
63        }
64        for edge in &self.edges {
65            *in_degree.entry(edge.consumer).or_insert(0) += 1;
66        }
67
68        let mut queue: VecDeque<NodeKey> = in_degree
69            .iter()
70            .filter(|(_, d)| **d == 0)
71            .map(|(k, _)| *k)
72            .collect();
73        let mut order = Vec::with_capacity(n);
74
75        while let Some(node) = queue.pop_front() {
76            order.push(node);
77            if let Some(neighbors) = self.adjacency.get(&node) {
78                for (_, consumer) in neighbors {
79                    let deg = in_degree
80                        .get_mut(consumer)
81                        .expect("Graph integrity violation: dangling consumer edge");
82                    *deg -= 1;
83                    if *deg == 0 {
84                        queue.push_back(*consumer);
85                    }
86                }
87            }
88        }
89
90        if order.len() != n {
91            // Cycle detected -- find nodes still with in-degree > 0
92            let cycle_nodes: Vec<String> = in_degree
93                .iter()
94                .filter(|(_, d)| **d > 0)
95                .filter_map(|(k, _)| self.node(*k).map(|n| n.label().to_string()))
96                .collect();
97            return Err(KvasirError::CycleDetected(cycle_nodes));
98        }
99
100        Ok(order)
101    }
102
103    /// Access nodes by key (for execution).
104    pub fn node(&self, key: NodeKey) -> Option<&dyn super::node::KvasirNode> {
105        self.nodes.get(key.0).map(|b| b.as_ref())
106    }
107
108    /// Build a human-readable DOT representation for debugging.
109    pub fn to_dot(&self) -> String {
110        let mut s = String::from("digraph Kvasir {\n");
111        for (i, node) in self.nodes.iter().enumerate() {
112            s.push_str(&format!("  n{} [label=\"{}\"];\n", i, node.label()));
113        }
114        for edge in &self.edges {
115            s.push_str(&format!(
116                "  n{} -> n{} [label=\"{:?}\"];\n",
117                edge.producer.0, edge.consumer.0, edge.resource
118            ));
119        }
120        s.push_str("}\n");
121        s
122    }
123}
124
125/// Builder for declarative graph construction.
126pub struct GraphBuilder {
127    graph: KvasirGraph,
128}
129
130impl GraphBuilder {
131    pub fn new() -> Self {
132        Self {
133            graph: KvasirGraph::new(),
134        }
135    }
136
137    pub fn add_node(&mut self, node: Box<dyn super::node::KvasirNode>) -> NodeKey {
138        self.graph.add_node(node)
139    }
140
141    pub fn connect(&mut self, from: NodeKey, resource: ResourceId, to: NodeKey) {
142        self.graph.connect(from, resource, to);
143    }
144
145    pub fn build(self) -> KvasirGraph {
146        self.graph
147    }
148}
149
150impl Default for GraphBuilder {
151    fn default() -> Self {
152        Self::new()
153    }
154}
cvkg_render_gpu/kvasir/graph.rs

cvkg_render_gpu/kvasir/
graph.rs
