ringkernel_procint/models/
dfg.rs

1//! Directly-Follows Graph (DFG) structures for GPU processing.
2
3use super::ActivityId;
4use rkyv::{Archive, Deserialize, Serialize};
5use std::collections::HashMap;
6
7/// GPU-compatible DFG node (64 bytes, cache-line aligned).
8#[derive(Debug, Clone, Copy, Default, Archive, Serialize, Deserialize)]
9#[repr(C, align(64))]
10pub struct GpuDFGNode {
11    /// Activity identifier.
12    pub activity_id: u32,
13    /// Number of events for this activity.
14    pub event_count: u32,
15    /// Total duration across all events (ms).
16    pub total_duration_ms: u64,
17    /// Minimum duration (ms).
18    pub min_duration_ms: u32,
19    /// Maximum duration (ms).
20    pub max_duration_ms: u32,
21    /// Average duration (ms).
22    pub avg_duration_ms: f32,
23    /// Standard deviation of duration.
24    pub std_duration_ms: f32,
25    /// First occurrence timestamp.
26    pub first_seen_ms: u64,
27    /// Last occurrence timestamp.
28    pub last_seen_ms: u64,
29    /// Is this a start activity?
30    pub is_start: u8,
31    /// Is this an end activity?
32    pub is_end: u8,
33    /// Node flags.
34    pub flags: u8,
35    /// Padding.
36    pub _padding: u8,
37    /// In-degree (number of incoming edges).
38    pub incoming_count: u16,
39    /// Out-degree (number of outgoing edges).
40    pub outgoing_count: u16,
41}
42
43// Verify size
44const _: () = assert!(std::mem::size_of::<GpuDFGNode>() == 64);
45
46/// GPU-compatible DFG edge (64 bytes, cache-line aligned).
47#[derive(Debug, Clone, Copy, Default, Archive, Serialize, Deserialize)]
48#[repr(C, align(64))]
49pub struct GpuDFGEdge {
50    /// Source activity ID.
51    pub source_activity: u32,
52    /// Target activity ID.
53    pub target_activity: u32,
54    /// Transition frequency.
55    pub frequency: u32,
56    /// Number of unique cases with this transition.
57    pub unique_cases: u32,
58    /// Total transition duration (ms).
59    pub total_duration_ms: u64,
60    /// Minimum transition duration (ms).
61    pub min_duration_ms: u32,
62    /// Maximum transition duration (ms).
63    pub max_duration_ms: u32,
64    /// Average transition duration (ms).
65    pub avg_duration_ms: f32,
66    /// Standard deviation of duration.
67    pub std_duration_ms: f32,
68    /// Transition probability (frequency / source outgoing).
69    pub probability: f32,
70    /// Edge flags (is_loop, is_self_loop, is_back_edge).
71    pub flags: u32,
72    /// Reserved.
73    pub _reserved: [u8; 16],
74}
75
76// Verify size
77const _: () = assert!(std::mem::size_of::<GpuDFGEdge>() == 64);
78
79impl GpuDFGEdge {
80    /// Check if this is a self-loop (same source and target).
81    pub fn is_self_loop(&self) -> bool {
82        self.source_activity == self.target_activity
83    }
84
85    /// Check if this is marked as a loop.
86    pub fn is_loop(&self) -> bool {
87        (self.flags & 0x01) != 0
88    }
89
90    /// Check if this is a back edge.
91    pub fn is_back_edge(&self) -> bool {
92        (self.flags & 0x02) != 0
93    }
94}
95
96/// GPU-compatible DFG graph header (128 bytes).
97#[derive(Debug, Clone, Copy, Archive, Serialize, Deserialize)]
98#[repr(C, align(128))]
99pub struct GpuDFGGraph {
100    /// Number of nodes (activities).
101    pub node_count: u32,
102    /// Number of edges (transitions).
103    pub edge_count: u32,
104    /// Total number of events processed.
105    pub total_events: u64,
106    /// Total number of cases (traces).
107    pub total_cases: u32,
108    /// Number of unique activities.
109    pub unique_activities: u32,
110    /// Average trace length.
111    pub avg_trace_length: f32,
112    /// Maximum trace length.
113    pub max_trace_length: u32,
114    /// Number of start activities.
115    pub start_activity_count: u32,
116    /// Number of end activities.
117    pub end_activity_count: u32,
118    /// Graph density (edges / (nodes * (nodes - 1))).
119    pub graph_density: f32,
120    /// Number of loops detected.
121    pub loop_count: u32,
122    /// Earliest event timestamp.
123    pub timestamp_min: u64,
124    /// Latest event timestamp.
125    pub timestamp_max: u64,
126    /// Average activity duration.
127    pub avg_activity_duration: f32,
128    /// Reserved.
129    pub _reserved: [u8; 56],
130}
131
132// Verify size
133const _: () = assert!(std::mem::size_of::<GpuDFGGraph>() == 128);
134
135impl Default for GpuDFGGraph {
136    fn default() -> Self {
137        Self {
138            node_count: 0,
139            edge_count: 0,
140            total_events: 0,
141            total_cases: 0,
142            unique_activities: 0,
143            avg_trace_length: 0.0,
144            max_trace_length: 0,
145            start_activity_count: 0,
146            end_activity_count: 0,
147            graph_density: 0.0,
148            loop_count: 0,
149            timestamp_min: 0,
150            timestamp_max: 0,
151            avg_activity_duration: 0.0,
152            _reserved: [0; 56],
153        }
154    }
155}
156
157/// High-level DFG representation with all components.
158#[derive(Debug, Clone, Default)]
159pub struct DFGGraph {
160    /// Graph header/metadata.
161    pub header: GpuDFGGraph,
162    /// Activity nodes.
163    pub nodes: Vec<GpuDFGNode>,
164    /// Transition edges.
165    pub edges: Vec<GpuDFGEdge>,
166    /// Activity ID to node index mapping.
167    pub node_index: HashMap<ActivityId, usize>,
168    /// Edge key (source, target) to edge index mapping.
169    pub edge_index: HashMap<(ActivityId, ActivityId), usize>,
170}
171
172impl DFGGraph {
173    /// Create a new empty DFG.
174    pub fn new() -> Self {
175        Self::default()
176    }
177
178    /// Get all nodes.
179    pub fn nodes(&self) -> &[GpuDFGNode] {
180        &self.nodes
181    }
182
183    /// Get all edges.
184    pub fn edges(&self) -> &[GpuDFGEdge] {
185        &self.edges
186    }
187
188    /// Get node count.
189    pub fn node_count(&self) -> usize {
190        self.nodes.len()
191    }
192
193    /// Get edge count.
194    pub fn edge_count(&self) -> usize {
195        self.edges.len()
196    }
197
198    /// Create from GPU buffers.
199    pub fn from_gpu(nodes: Vec<GpuDFGNode>, edges: Vec<GpuDFGEdge>) -> Self {
200        let mut dfg = Self {
201            header: GpuDFGGraph {
202                node_count: nodes.len() as u32,
203                edge_count: edges.len() as u32,
204                ..Default::default()
205            },
206            nodes,
207            edges,
208            node_index: HashMap::new(),
209            edge_index: HashMap::new(),
210        };
211
212        // Build indices
213        for (i, node) in dfg.nodes.iter().enumerate() {
214            dfg.node_index.insert(node.activity_id, i);
215        }
216        for (i, edge) in dfg.edges.iter().enumerate() {
217            dfg.edge_index
218                .insert((edge.source_activity, edge.target_activity), i);
219        }
220
221        dfg
222    }
223
224    /// Update a node by activity ID.
225    pub fn update_node(
226        &mut self,
227        activity_id: ActivityId,
228        event_count: u32,
229        avg_duration: f32,
230        _cost: f32,
231    ) {
232        self.add_or_update_node(activity_id, |node| {
233            node.event_count = event_count;
234            node.avg_duration_ms = avg_duration;
235            // Note: cost is stored in reserved or separate tracking
236        });
237    }
238
239    /// Update an edge.
240    pub fn update_edge(
241        &mut self,
242        source: ActivityId,
243        target: ActivityId,
244        frequency: u32,
245        avg_duration: f32,
246    ) {
247        self.add_or_update_edge(source, target, |edge| {
248            edge.frequency = frequency;
249            edge.avg_duration_ms = avg_duration;
250        });
251    }
252
253    /// Get node by activity ID.
254    pub fn get_node(&self, activity_id: ActivityId) -> Option<&GpuDFGNode> {
255        self.node_index.get(&activity_id).map(|&i| &self.nodes[i])
256    }
257
258    /// Get mutable node by activity ID.
259    pub fn get_node_mut(&mut self, activity_id: ActivityId) -> Option<&mut GpuDFGNode> {
260        self.node_index
261            .get(&activity_id)
262            .map(|&i| &mut self.nodes[i])
263    }
264
265    /// Get edge by source and target.
266    pub fn get_edge(&self, source: ActivityId, target: ActivityId) -> Option<&GpuDFGEdge> {
267        self.edge_index
268            .get(&(source, target))
269            .map(|&i| &self.edges[i])
270    }
271
272    /// Add or update a node.
273    pub fn add_or_update_node(
274        &mut self,
275        activity_id: ActivityId,
276        update_fn: impl FnOnce(&mut GpuDFGNode),
277    ) {
278        if let Some(&idx) = self.node_index.get(&activity_id) {
279            update_fn(&mut self.nodes[idx]);
280        } else {
281            let idx = self.nodes.len();
282            let mut node = GpuDFGNode {
283                activity_id,
284                ..Default::default()
285            };
286            update_fn(&mut node);
287            self.nodes.push(node);
288            self.node_index.insert(activity_id, idx);
289            self.header.node_count = self.nodes.len() as u32;
290        }
291    }
292
293    /// Add or update an edge.
294    pub fn add_or_update_edge(
295        &mut self,
296        source: ActivityId,
297        target: ActivityId,
298        update_fn: impl FnOnce(&mut GpuDFGEdge),
299    ) {
300        let key = (source, target);
301        if let Some(&idx) = self.edge_index.get(&key) {
302            update_fn(&mut self.edges[idx]);
303        } else {
304            let idx = self.edges.len();
305            let mut edge = GpuDFGEdge {
306                source_activity: source,
307                target_activity: target,
308                ..Default::default()
309            };
310            update_fn(&mut edge);
311            self.edges.push(edge);
312            self.edge_index.insert(key, idx);
313            self.header.edge_count = self.edges.len() as u32;
314        }
315    }
316
317    /// Get start activities.
318    pub fn start_activities(&self) -> impl Iterator<Item = &GpuDFGNode> {
319        self.nodes.iter().filter(|n| n.is_start != 0)
320    }
321
322    /// Get end activities.
323    pub fn end_activities(&self) -> impl Iterator<Item = &GpuDFGNode> {
324        self.nodes.iter().filter(|n| n.is_end != 0)
325    }
326
327    /// Get outgoing edges for an activity.
328    pub fn outgoing_edges(&self, activity_id: ActivityId) -> impl Iterator<Item = &GpuDFGEdge> {
329        self.edges
330            .iter()
331            .filter(move |e| e.source_activity == activity_id)
332    }
333
334    /// Get incoming edges for an activity.
335    pub fn incoming_edges(&self, activity_id: ActivityId) -> impl Iterator<Item = &GpuDFGEdge> {
336        self.edges
337            .iter()
338            .filter(move |e| e.target_activity == activity_id)
339    }
340
341    /// Calculate edge probabilities.
342    pub fn calculate_probabilities(&mut self) {
343        // First, calculate outgoing totals per node
344        let mut outgoing_totals: HashMap<ActivityId, u32> = HashMap::new();
345        for edge in &self.edges {
346            *outgoing_totals.entry(edge.source_activity).or_insert(0) += edge.frequency;
347        }
348
349        // Then update edge probabilities
350        for edge in &mut self.edges {
351            if let Some(&total) = outgoing_totals.get(&edge.source_activity) {
352                edge.probability = if total > 0 {
353                    edge.frequency as f32 / total as f32
354                } else {
355                    0.0
356                };
357            }
358        }
359    }
360
361    /// Update node degrees from edges.
362    pub fn update_degrees(&mut self) {
363        // Reset degrees
364        for node in &mut self.nodes {
365            node.incoming_count = 0;
366            node.outgoing_count = 0;
367        }
368
369        // First collect the counts to avoid borrow issues
370        let mut incoming: HashMap<ActivityId, u16> = HashMap::new();
371        let mut outgoing: HashMap<ActivityId, u16> = HashMap::new();
372
373        for edge in &self.edges {
374            *outgoing.entry(edge.source_activity).or_insert(0) += 1;
375            *incoming.entry(edge.target_activity).or_insert(0) += 1;
376        }
377
378        // Then update nodes
379        for node in &mut self.nodes {
380            if let Some(&count) = outgoing.get(&node.activity_id) {
381                node.outgoing_count = count;
382            }
383            if let Some(&count) = incoming.get(&node.activity_id) {
384                node.incoming_count = count;
385            }
386        }
387    }
388}
389
390#[cfg(test)]
391mod tests {
392    use super::*;
393
394    #[test]
395    fn test_dfg_node_size() {
396        assert_eq!(std::mem::size_of::<GpuDFGNode>(), 64);
397    }
398
399    #[test]
400    fn test_dfg_edge_size() {
401        assert_eq!(std::mem::size_of::<GpuDFGEdge>(), 64);
402    }
403
404    #[test]
405    fn test_dfg_header_size() {
406        assert_eq!(std::mem::size_of::<GpuDFGGraph>(), 128);
407    }
408
409    #[test]
410    fn test_dfg_graph_operations() {
411        let mut dfg = DFGGraph::new();
412
413        dfg.add_or_update_node(1, |n| {
414            n.event_count = 10;
415            n.is_start = 1;
416        });
417
418        dfg.add_or_update_node(2, |n| {
419            n.event_count = 8;
420            n.is_end = 1;
421        });
422
423        dfg.add_or_update_edge(1, 2, |e| {
424            e.frequency = 8;
425        });
426
427        assert_eq!(dfg.nodes.len(), 2);
428        assert_eq!(dfg.edges.len(), 1);
429
430        dfg.calculate_probabilities();
431        assert_eq!(dfg.edges[0].probability, 1.0);
432    }
433}
ringkernel_procint/models/dfg.rs

ringkernel_procint/models/
dfg.rs
