flow_rs_core/auto_layout/
analysis.rs

1//! Graph analysis for automatic layout selection
2
3use std::collections::HashSet;
4
5use crate::graph::Graph;
6use crate::types::NodeId;
7
8/// Results of graph structure analysis
9#[derive(Debug)]
10pub struct GraphAnalysis {
11    pub node_count: usize,
12    pub edge_count: usize,
13    pub is_tree: bool,
14    pub is_dag: bool,
15    pub has_cycles: bool,
16    pub max_degree: usize,
17    pub density: f64,
18    pub clustering_coefficient: f64,
19}
20
21impl GraphAnalysis {
22    /// Analyze a graph structure to determine layout characteristics
23    pub fn analyze<N, E>(graph: &Graph<N, E>) -> Self {
24        let node_count = graph.node_count();
25        let edge_count = graph.edge_count();
26        let density = if node_count > 1 {
27            (2.0 * edge_count as f64) / (node_count as f64 * (node_count - 1) as f64)
28        } else {
29            0.0
30        };
31
32        // Basic cycle detection
33        let has_cycles = Self::detect_cycles(graph);
34        let is_dag = !has_cycles;
35
36        // Check if it's a tree (connected, acyclic, n-1 edges)
37        let is_tree = is_dag && edge_count == node_count.saturating_sub(1);
38
39        // Calculate max degree
40        let max_degree = graph
41            .nodes()
42            .map(|node| {
43                graph.get_incoming_edges(&node.id).len() + graph.get_outgoing_edges(&node.id).len()
44            })
45            .max()
46            .unwrap_or(0);
47
48        // Simplified clustering coefficient calculation
49        let clustering_coefficient = Self::calculate_clustering_coefficient(graph);
50
51        Self {
52            node_count,
53            edge_count,
54            is_tree,
55            is_dag,
56            has_cycles,
57            max_degree,
58            density,
59            clustering_coefficient,
60        }
61    }
62
63    /// Detect cycles in the graph using DFS
64    fn detect_cycles<N, E>(graph: &Graph<N, E>) -> bool {
65        let mut visited = HashSet::new();
66        let mut rec_stack = HashSet::new();
67
68        // Simple DFS-based cycle detection
69        for node in graph.nodes() {
70            if !visited.contains(&node.id)
71                && Self::dfs_cycle_detection(graph, &node.id, &mut visited, &mut rec_stack)
72            {
73                return true;
74            }
75        }
76        false
77    }
78
79    #[allow(clippy::only_used_in_recursion)]
80    fn dfs_cycle_detection<N, E>(
81        graph: &Graph<N, E>,
82        node_id: &NodeId,
83        visited: &mut HashSet<NodeId>,
84        rec_stack: &mut HashSet<NodeId>,
85    ) -> bool {
86        visited.insert(node_id.clone());
87        rec_stack.insert(node_id.clone());
88
89        for edge in graph.get_outgoing_edges(node_id) {
90            if !visited.contains(&edge.target) {
91                if Self::dfs_cycle_detection(graph, &edge.target, visited, rec_stack) {
92                    return true;
93                }
94            } else if rec_stack.contains(&edge.target) {
95                return true; // Back edge found = cycle
96            }
97        }
98
99        rec_stack.remove(node_id);
100        false
101    }
102
103    /// Calculate clustering coefficient (simplified implementation)
104    fn calculate_clustering_coefficient<N, E>(graph: &Graph<N, E>) -> f64 {
105        let mut total_coefficient = 0.0;
106        let mut node_count = 0;
107
108        for node in graph.nodes() {
109            let neighbors: HashSet<_> = graph
110                .get_outgoing_edges(&node.id)
111                .into_iter()
112                .map(|e| &e.target)
113                .chain(graph.get_incoming_edges(&node.id).into_iter().map(|e| &e.source))
114                .collect();
115
116            let k = neighbors.len();
117            if k < 2 {
118                continue; // Skip nodes with less than 2 neighbors
119            }
120
121            // Count edges between neighbors
122            let mut edges_between_neighbors = 0;
123            for neighbor in &neighbors {
124                for edge in graph.get_outgoing_edges(neighbor) {
125                    if neighbors.contains(&edge.target) {
126                        edges_between_neighbors += 1;
127                    }
128                }
129            }
130
131            // Clustering coefficient for this node
132            let max_possible_edges = k * (k - 1);
133            if max_possible_edges > 0 {
134                total_coefficient += edges_between_neighbors as f64 / max_possible_edges as f64;
135                node_count += 1;
136            }
137        }
138
139        if node_count > 0 {
140            total_coefficient / node_count as f64
141        } else {
142            0.0
143        }
144    }
145}
flow_rs_core/auto_layout/analysis.rs

flow_rs_core/auto_layout/
analysis.rs
