oak_visualize/graph/
mod.rs

1#![doc = "Graph layout algorithms for dependency and relationship visualization"]
2
3use crate::{
4    geometry::{Point, Rect, Size},
5    layout::{Edge, Layout},
6};
7use serde::{Deserialize, Serialize};
8use std::collections::{HashMap, HashSet};
9
10/// Graph node for visualization
11#[derive(Debug, Clone, Serialize, Deserialize)]
12pub struct GraphNode {
13    pub id: String,
14    pub label: String,
15    pub node_type: String,
16    pub size: Option<Size>,
17    pub attributes: HashMap<String, String>,
18    pub weight: f64,
19}
20
21impl GraphNode {
22    pub fn new(id: String, label: String) -> Self {
23        Self { id, label, node_type: "default".to_string(), size: None, attributes: HashMap::new(), weight: 1.0 }
24    }
25
26    pub fn with_type(mut self, node_type: String) -> Self {
27        self.node_type = node_type;
28        self
29    }
30
31    pub fn with_size(mut self, size: Size) -> Self {
32        self.size = Some(size);
33        self
34    }
35
36    pub fn with_attribute(mut self, key: String, value: String) -> Self {
37        self.attributes.insert(key, value);
38        self
39    }
40
41    pub fn with_weight(mut self, weight: f64) -> Self {
42        self.weight = weight;
43        self
44    }
45}
46
47/// Graph edge for visualization
48#[derive(Debug, Clone, Serialize, Deserialize)]
49pub struct GraphEdge {
50    pub from: String,
51    pub to: String,
52    pub label: Option<String>,
53    pub edge_type: String,
54    pub weight: f64,
55    pub directed: bool,
56    pub attributes: HashMap<String, String>,
57}
58
59impl GraphEdge {
60    pub fn new(from: String, to: String) -> Self {
61        Self { from, to, label: None, edge_type: "default".to_string(), weight: 1.0, directed: true, attributes: HashMap::new() }
62    }
63
64    pub fn with_label(mut self, label: String) -> Self {
65        self.label = Some(label);
66        self
67    }
68
69    pub fn with_type(mut self, edge_type: String) -> Self {
70        self.edge_type = edge_type;
71        self
72    }
73
74    pub fn with_weight(mut self, weight: f64) -> Self {
75        self.weight = weight;
76        self
77    }
78
79    pub fn undirected(mut self) -> Self {
80        self.directed = false;
81        self
82    }
83
84    pub fn with_attribute(mut self, key: String, value: String) -> Self {
85        self.attributes.insert(key, value);
86        self
87    }
88}
89
90/// Graph representation
91#[derive(Debug, Clone)]
92pub struct Graph {
93    pub nodes: HashMap<String, GraphNode>,
94    pub edges: Vec<GraphEdge>,
95    pub directed: bool,
96}
97
98impl Graph {
99    pub fn new(directed: bool) -> Self {
100        Self { nodes: HashMap::new(), edges: Vec::new(), directed }
101    }
102
103    pub fn add_node(&mut self, node: GraphNode) {
104        self.nodes.insert(node.id.clone(), node);
105    }
106
107    pub fn add_edge(&mut self, edge: GraphEdge) {
108        self.edges.push(edge);
109    }
110
111    pub fn get_neighbors(&self, node_id: &str) -> Vec<&str> {
112        let mut neighbors = Vec::new();
113
114        for edge in &self.edges {
115            if edge.from == node_id {
116                neighbors.push(edge.to.as_str());
117            }
118            if !self.directed && edge.to == node_id {
119                neighbors.push(edge.from.as_str());
120            }
121        }
122
123        neighbors
124    }
125
126    pub fn get_degree(&self, node_id: &str) -> usize {
127        self.get_neighbors(node_id).len()
128    }
129
130    pub fn is_connected(&self) -> bool {
131        if self.nodes.is_empty() {
132            return true;
133        }
134
135        let start_node = self.nodes.keys().next().unwrap();
136        let mut visited = HashSet::new();
137        let mut stack = vec![start_node.as_str()];
138
139        while let Some(node) = stack.pop() {
140            if visited.contains(node) {
141                continue;
142            }
143
144            visited.insert(node);
145
146            for neighbor in self.get_neighbors(node) {
147                if !visited.contains(neighbor) {
148                    stack.push(neighbor);
149                }
150            }
151        }
152
153        visited.len() == self.nodes.len()
154    }
155
156    pub fn find_cycles(&self) -> Vec<Vec<String>> {
157        let mut cycles = Vec::new();
158        let mut visited = HashSet::new();
159        let mut rec_stack = HashSet::new();
160        let mut path = Vec::new();
161
162        for node_id in self.nodes.keys() {
163            if !visited.contains(node_id) {
164                self.dfs_cycles(node_id, &mut visited, &mut rec_stack, &mut path, &mut cycles);
165            }
166        }
167
168        cycles
169    }
170
171    fn dfs_cycles(&self, node: &str, visited: &mut HashSet<String>, rec_stack: &mut HashSet<String>, path: &mut Vec<String>, cycles: &mut Vec<Vec<String>>) {
172        visited.insert(node.to_string());
173        rec_stack.insert(node.to_string());
174        path.push(node.to_string());
175
176        for neighbor in self.get_neighbors(node) {
177            if !visited.contains(neighbor) {
178                self.dfs_cycles(neighbor, visited, rec_stack, path, cycles);
179            }
180            else if rec_stack.contains(neighbor) {
181                // Found a cycle
182                if let Some(cycle_start) = path.iter().position(|n| n == neighbor) {
183                    cycles.push(path[cycle_start..].to_vec());
184                }
185            }
186        }
187
188        rec_stack.remove(node);
189        path.pop();
190    }
191}
192
193impl crate::Visualize for Graph {
194    fn visualize(&self) -> crate::Result<String> {
195        GraphLayout::new().visualize(self)
196    }
197}
198
199/// Graph layout engine
200pub struct GraphLayout {
201    algorithm: GraphLayoutAlgorithm,
202    config: GraphLayoutConfig,
203}
204
205impl Default for GraphLayout {
206    fn default() -> Self {
207        Self { algorithm: GraphLayoutAlgorithm::ForceDirected, config: GraphLayoutConfig::default() }
208    }
209}
210
211impl GraphLayout {
212    pub fn new() -> Self {
213        Self::default()
214    }
215
216    pub fn force_directed() -> Self {
217        Self::new().with_algorithm(GraphLayoutAlgorithm::ForceDirected)
218    }
219
220    pub fn circular() -> Self {
221        Self::new().with_algorithm(GraphLayoutAlgorithm::Circular)
222    }
223
224    pub fn with_algorithm(mut self, algorithm: GraphLayoutAlgorithm) -> Self {
225        self.algorithm = algorithm;
226        self
227    }
228
229    pub fn with_config(mut self, config: GraphLayoutConfig) -> Self {
230        self.config = config;
231        self
232    }
233
234    pub fn with_repulsion(mut self, repulsion: f64) -> Self {
235        self.config.repulsion_strength = repulsion;
236        self
237    }
238
239    pub fn with_attraction(mut self, attraction: f64) -> Self {
240        self.config.spring_strength = attraction;
241        self
242    }
243
244    pub fn with_iterations(mut self, iterations: usize) -> Self {
245        self.config.iterations = iterations;
246        self
247    }
248
249    pub fn visualize(&self, graph: &Graph) -> crate::Result<String> {
250        let layout = self.layout_graph(graph)?;
251        crate::render::SvgRenderer::new().render_layout(&layout)
252    }
253
254    pub fn layout_graph(&self, graph: &Graph) -> crate::Result<Layout> {
255        match self.algorithm {
256            GraphLayoutAlgorithm::ForceDirected => self.force_directed_layout(graph),
257            GraphLayoutAlgorithm::Circular => self.circular_layout(graph),
258            GraphLayoutAlgorithm::Hierarchical => self.hierarchical_layout(graph),
259            GraphLayoutAlgorithm::Grid => self.grid_layout(graph),
260            GraphLayoutAlgorithm::Organic => self.organic_layout(graph),
261        }
262    }
263
264    /// Force-directed layout using spring-mass model
265    fn force_directed_layout(&self, graph: &Graph) -> crate::Result<Layout> {
266        let mut layout = Layout::new();
267
268        if graph.nodes.is_empty() {
269            return Ok(layout);
270        }
271
272        let mut positions: HashMap<String, Point> = HashMap::new();
273        let mut velocities: HashMap<String, Point> = HashMap::new();
274
275        // Initialize random positions
276        for (i, node_id) in graph.nodes.keys().enumerate() {
277            let angle = 2.0 * std::f64::consts::PI * i as f64 / graph.nodes.len() as f64;
278            let radius = 100.0;
279            positions.insert(node_id.clone(), Point::new(radius * angle.cos(), radius * angle.sin()));
280            velocities.insert(node_id.clone(), Point::origin());
281        }
282
283        // Run simulation
284        for _ in 0..self.config.iterations {
285            let mut forces: HashMap<String, Point> = HashMap::new();
286
287            // Initialize forces
288            for node_id in graph.nodes.keys() {
289                forces.insert(node_id.clone(), Point::origin());
290            }
291
292            // Repulsion forces between all nodes
293            let node_ids: Vec<_> = graph.nodes.keys().collect();
294            for i in 0..node_ids.len() {
295                for j in (i + 1)..node_ids.len() {
296                    let node1_id = node_ids[i];
297                    let node2_id = node_ids[j];
298
299                    if let (Some(pos1), Some(pos2)) = (positions.get(node1_id), positions.get(node2_id)) {
300                        let diff = *pos1 - *pos2;
301                        let distance = pos1.distance_to(pos2).max(1.0);
302                        let force_magnitude = self.config.repulsion_strength / (distance * distance);
303                        let force_direction = Point::new(diff.x / distance, diff.y / distance);
304                        let force = Point::new(force_direction.x * force_magnitude, force_direction.y * force_magnitude);
305
306                        *forces.get_mut(node1_id).unwrap() = *forces.get(node1_id).unwrap() + force;
307                        *forces.get_mut(node2_id).unwrap() = *forces.get(node2_id).unwrap() - force;
308                    }
309                }
310            }
311
312            // Attraction forces along edges
313            for edge in &graph.edges {
314                if let (Some(pos1), Some(pos2)) = (positions.get(&edge.from), positions.get(&edge.to)) {
315                    let diff = *pos2 - *pos1;
316                    let distance = pos1.distance_to(pos2);
317                    let ideal_length = self.config.ideal_edge_length;
318                    let force_magnitude = self.config.spring_strength * (distance - ideal_length) * edge.weight;
319
320                    if distance > 0.0 {
321                        let force_direction = Point::new(diff.x / distance, diff.y / distance);
322                        let force = Point::new(force_direction.x * force_magnitude, force_direction.y * force_magnitude);
323
324                        *forces.get_mut(&edge.from).unwrap() = *forces.get(&edge.from).unwrap() + force;
325                        *forces.get_mut(&edge.to).unwrap() = *forces.get(&edge.to).unwrap() - force;
326                    }
327                }
328            }
329
330            // Update positions
331            for node_id in graph.nodes.keys() {
332                if let (Some(force), Some(velocity), Some(position)) = (forces.get(node_id), velocities.get_mut(node_id), positions.get_mut(node_id)) {
333                    *velocity = Point::new(velocity.x * self.config.damping + force.x, velocity.y * self.config.damping + force.y);
334
335                    // Limit velocity
336                    let speed = (velocity.x * velocity.x + velocity.y * velocity.y).sqrt();
337                    if speed > self.config.max_velocity {
338                        let scale = self.config.max_velocity / speed;
339                        velocity.x *= scale;
340                        velocity.y *= scale;
341                    }
342
343                    *position = *position + *velocity;
344                }
345            }
346        }
347
348        // Convert positions to layout
349        for (node_id, node) in &graph.nodes {
350            if let Some(position) = positions.get(node_id) {
351                let size = node.size.unwrap_or(Size::new(self.config.node_width, self.config.node_height));
352                let rect = Rect::new(Point::new(position.x - size.width / 2.0, position.y - size.height / 2.0), size);
353                let nt = match node.node_type.as_str() {
354                    "function" => crate::layout::NodeType::Function,
355                    "struct" => crate::layout::NodeType::Struct,
356                    "module" => crate::layout::NodeType::Module,
357                    _ => crate::layout::NodeType::Default,
358                };
359                layout.add_node_with_metadata(node_id.clone(), node.label.clone(), rect, nt);
360            }
361        }
362
363        // Add edges
364        for edge in &graph.edges {
365            if let (Some(from_node), Some(to_node)) = (layout.nodes.get(&edge.from), layout.nodes.get(&edge.to)) {
366                let layout_edge = Edge::new(edge.from.clone(), edge.to.clone()).with_points(vec![from_node.rect.center(), to_node.rect.center()]);
367                layout.add_edge(layout_edge);
368            }
369        }
370
371        Ok(layout)
372    }
373
374    /// Circular layout - arrange nodes in a circle
375    fn circular_layout(&self, graph: &Graph) -> crate::Result<Layout> {
376        let mut layout = Layout::new();
377
378        if graph.nodes.is_empty() {
379            return Ok(layout);
380        }
381
382        let node_count = graph.nodes.len();
383        let radius = self.config.circle_radius;
384        let angle_step = 2.0 * std::f64::consts::PI / node_count as f64;
385
386        for (i, (node_id, node)) in graph.nodes.iter().enumerate() {
387            let angle = i as f64 * angle_step;
388            let position = Point::new(radius * angle.cos(), radius * angle.sin());
389            let size = node.size.unwrap_or(Size::new(self.config.node_width, self.config.node_height));
390            let rect = Rect::new(Point::new(position.x - size.width / 2.0, position.y - size.height / 2.0), size);
391            let nt = match node.node_type.as_str() {
392                "function" => crate::layout::NodeType::Function,
393                "struct" => crate::layout::NodeType::Struct,
394                "module" => crate::layout::NodeType::Module,
395                _ => crate::layout::NodeType::Default,
396            };
397            layout.add_node_with_metadata(node_id.clone(), node.label.clone(), rect, nt);
398        }
399
400        // Add edges
401        for edge in &graph.edges {
402            if let (Some(from_node), Some(to_node)) = (layout.nodes.get(&edge.from), layout.nodes.get(&edge.to)) {
403                let layout_edge = Edge::new(edge.from.clone(), edge.to.clone()).with_points(vec![from_node.rect.center(), to_node.rect.center()]);
404                layout.add_edge(layout_edge);
405            }
406        }
407
408        Ok(layout)
409    }
410
411    /// Hierarchical layout - arrange nodes in layers
412    fn hierarchical_layout(&self, graph: &Graph) -> crate::Result<Layout> {
413        let mut layout = Layout::new();
414
415        if graph.nodes.is_empty() {
416            return Ok(layout);
417        }
418
419        // Perform topological sort to determine layers
420        let layers = self.topological_layers(graph)?;
421
422        // Position nodes layer by layer
423        for (layer_index, layer) in layers.iter().enumerate() {
424            let y = layer_index as f64 * self.config.layer_distance;
425            let layer_width = layer.len() as f64 * (self.config.node_width + self.config.node_spacing);
426            let start_x = -layer_width / 2.0;
427
428            for (node_index, node_id) in layer.iter().enumerate() {
429                let x = start_x + node_index as f64 * (self.config.node_width + self.config.node_spacing);
430                let node = &graph.nodes[node_id];
431                let size = node.size.unwrap_or(Size::new(self.config.node_width, self.config.node_height));
432                let rect = Rect::new(Point::new(x, y), size);
433                let nt = match node.node_type.as_str() {
434                    "function" => crate::layout::NodeType::Function,
435                    "struct" => crate::layout::NodeType::Struct,
436                    "module" => crate::layout::NodeType::Module,
437                    _ => crate::layout::NodeType::Default,
438                };
439                layout.add_node_with_metadata(node_id.clone(), node.label.clone(), rect, nt);
440            }
441        }
442
443        // Add edges
444        for edge in &graph.edges {
445            if let (Some(from_node), Some(to_node)) = (layout.nodes.get(&edge.from), layout.nodes.get(&edge.to)) {
446                let layout_edge = Edge::new(edge.from.clone(), edge.to.clone()).with_points(vec![from_node.rect.center(), to_node.rect.center()]);
447                layout.add_edge(layout_edge);
448            }
449        }
450
451        Ok(layout)
452    }
453
454    /// Grid layout - arrange nodes in a regular grid
455    fn grid_layout(&self, graph: &Graph) -> crate::Result<Layout> {
456        let mut layout = Layout::new();
457
458        if graph.nodes.is_empty() {
459            return Ok(layout);
460        }
461
462        let node_count = graph.nodes.len();
463        let cols = (node_count as f64).sqrt().ceil() as usize;
464        let _rows = (node_count + cols - 1) / cols;
465
466        for (i, (node_id, node)) in graph.nodes.iter().enumerate() {
467            let row = i / cols;
468            let col = i % cols;
469            let x = col as f64 * (self.config.node_width + self.config.node_spacing);
470            let y = row as f64 * (self.config.node_height + self.config.node_spacing);
471            let size = node.size.unwrap_or(Size::new(self.config.node_width, self.config.node_height));
472            let rect = Rect::new(Point::new(x, y), size);
473            let nt = match node.node_type.as_str() {
474                "function" => crate::layout::NodeType::Function,
475                "struct" => crate::layout::NodeType::Struct,
476                "module" => crate::layout::NodeType::Module,
477                _ => crate::layout::NodeType::Default,
478            };
479            layout.add_node_with_metadata(node_id.clone(), node.label.clone(), rect, nt);
480        }
481
482        // Add edges
483        for edge in &graph.edges {
484            if let (Some(from_node), Some(to_node)) = (layout.nodes.get(&edge.from), layout.nodes.get(&edge.to)) {
485                let layout_edge = Edge::new(edge.from.clone(), edge.to.clone()).with_points(vec![from_node.rect.center(), to_node.rect.center()]);
486                layout.add_edge(layout_edge);
487            }
488        }
489
490        Ok(layout)
491    }
492
493    /// Organic layout - natural-looking arrangement
494    fn organic_layout(&self, graph: &Graph) -> crate::Result<Layout> {
495        // For now, use force-directed with different parameters
496        let mut organic_config = self.config.clone();
497        organic_config.spring_strength *= 0.5;
498        organic_config.repulsion_strength *= 1.5;
499        organic_config.damping = 0.95;
500
501        let organic_layout = GraphLayout::new().with_algorithm(GraphLayoutAlgorithm::ForceDirected).with_config(organic_config);
502
503        organic_layout.force_directed_layout(graph)
504    }
505
506    /// Perform topological sort to determine node layers
507    fn topological_layers(&self, graph: &Graph) -> crate::Result<Vec<Vec<String>>> {
508        let mut in_degree: HashMap<String, usize> = HashMap::new();
509        let mut layers = Vec::new();
510
511        // Initialize in-degrees
512        for node_id in graph.nodes.keys() {
513            in_degree.insert(node_id.clone(), 0);
514        }
515
516        // Calculate in-degrees
517        for edge in &graph.edges {
518            *in_degree.get_mut(&edge.to).unwrap() += 1;
519        }
520
521        // Process layers
522        while !in_degree.is_empty() {
523            let mut current_layer = Vec::new();
524
525            // Find nodes with in-degree 0
526            let zero_in_degree: Vec<_> = in_degree.iter().filter(|&(_, &degree)| degree == 0).map(|(id, _)| id.clone()).collect();
527
528            if zero_in_degree.is_empty() {
529                // Cycle detected - break it by selecting node with minimum in-degree
530                if let Some((min_node, _)) = in_degree.iter().min_by_key(|&(_, &degree)| degree) {
531                    current_layer.push(min_node.clone());
532                }
533            }
534            else {
535                current_layer = zero_in_degree;
536            }
537
538            // Remove processed nodes and update in-degrees
539            for node_id in &current_layer {
540                in_degree.remove(node_id);
541
542                // Decrease in-degree of neighbors
543                for edge in &graph.edges {
544                    if edge.from == *node_id {
545                        if let Some(degree) = in_degree.get_mut(&edge.to) {
546                            *degree = degree.saturating_sub(1);
547                        }
548                    }
549                }
550            }
551
552            layers.push(current_layer);
553        }
554
555        Ok(layers)
556    }
557}
558
559/// Graph layout configuration
560#[derive(Debug, Clone)]
561pub struct GraphLayoutConfig {
562    pub node_width: f64,
563    pub node_height: f64,
564    pub node_spacing: f64,
565    pub layer_distance: f64,
566    pub circle_radius: f64,
567    pub iterations: usize,
568    pub spring_strength: f64,
569    pub repulsion_strength: f64,
570    pub damping: f64,
571    pub max_velocity: f64,
572    pub ideal_edge_length: f64,
573}
574
575impl Default for GraphLayoutConfig {
576    fn default() -> Self {
577        Self { node_width: 80.0, node_height: 40.0, node_spacing: 20.0, layer_distance: 100.0, circle_radius: 200.0, iterations: 100, spring_strength: 0.1, repulsion_strength: 1000.0, damping: 0.9, max_velocity: 10.0, ideal_edge_length: 100.0 }
578    }
579}
580
581/// Graph layout algorithms
582#[derive(Debug, Clone, Copy, PartialEq, Eq)]
583pub enum GraphLayoutAlgorithm {
584    ForceDirected, // Spring-mass model
585    Circular,      // Circular arrangement
586    Hierarchical,  // Layered arrangement
587    Grid,          // Regular grid
588    Organic,       // Natural-looking
589}
oak_visualize/graph/mod.rs

oak_visualize/graph/
mod.rs
