flow_rs_core/layout/algorithms/
hierarchical.rs

1//! Hierarchical layout algorithm implementation
2
3use crate::error::{FlowError, Result};
4use crate::graph::Graph;
5use crate::layout::LayoutAlgorithm;
6use crate::types::{NodeId, Position, Size};
7
8/// Hierarchical layout algorithm for tree-like structures
9#[derive(Debug, Clone)]
10pub struct HierarchicalLayout {
11    pub node_separation: f64,
12    pub level_separation: f64,
13    pub edge_routing: EdgeRouting,
14    pub direction: LayoutDirection,
15    pub root_node: Option<NodeId>,
16}
17
18/// Edge routing style for hierarchical layouts
19#[derive(Debug, Clone, Copy, PartialEq)]
20pub enum EdgeRouting {
21    Straight,
22    Orthogonal,
23    Curved,
24}
25
26/// Layout direction
27#[derive(Debug, Clone, Copy, PartialEq)]
28pub enum LayoutDirection {
29    TopToBottom,
30    BottomToTop,
31    LeftToRight,
32    RightToLeft,
33}
34
35impl Default for HierarchicalLayout {
36    fn default() -> Self {
37        Self::new()
38    }
39}
40
41impl HierarchicalLayout {
42    /// Create a new hierarchical layout with default settings
43    pub fn new() -> Self {
44        Self {
45            node_separation: 80.0,
46            level_separation: 100.0,
47            edge_routing: EdgeRouting::Straight,
48            direction: LayoutDirection::TopToBottom,
49            root_node: None,
50        }
51    }
52
53    /// Builder pattern for configuration
54    pub fn builder() -> HierarchicalLayoutBuilder {
55        HierarchicalLayoutBuilder::default()
56    }
57
58    /// Set the root node for the hierarchy
59    pub fn with_root(mut self, root_id: NodeId) -> Self {
60        self.root_node = Some(root_id);
61        self
62    }
63
64    /// Build the tree structure from the graph
65    fn build_tree<N, E>(&self, graph: &Graph<N, E>) -> Result<TreeNode> {
66        let root_id = if let Some(ref root) = self.root_node {
67            root.clone()
68        } else {
69            let root_nodes = self.find_root_nodes(graph)?;
70            root_nodes.into_iter().next()
71                .ok_or_else(|| FlowError::layout("No root node found for hierarchical layout"))?
72        };
73
74        self.build_tree_recursive(&root_id, graph, &mut std::collections::HashSet::new())
75    }
76
77    /// Find nodes with no incoming edges
78    fn find_root_nodes<N, E>(&self, graph: &Graph<N, E>) -> Result<Vec<NodeId>> {
79        let mut root_nodes = Vec::new();
80
81        for node in graph.nodes() {
82            let incoming_edges = graph.get_incoming_edges(&node.id);
83            if incoming_edges.is_empty() {
84                root_nodes.push(node.id.clone());
85            }
86        }
87
88        if root_nodes.is_empty() {
89            return Err(FlowError::layout(
90                "No root nodes found - graph may be cyclic",
91            ));
92        }
93
94        Ok(root_nodes)
95    }
96
97    /// Recursively build tree structure
98    #[allow(clippy::only_used_in_recursion)]
99    fn build_tree_recursive<N, E>(
100        &self,
101        node_id: &NodeId,
102        graph: &Graph<N, E>,
103        visited: &mut std::collections::HashSet<NodeId>,
104    ) -> Result<TreeNode> {
105        if visited.contains(node_id) {
106            return Err(FlowError::layout("Cycle detected in graph"));
107        }
108
109        visited.insert(node_id.clone());
110
111        let node = graph
112            .get_node(node_id)
113            .ok_or_else(|| FlowError::node_not_found(node_id.as_str()))?;
114
115        let mut children = Vec::new();
116        let outgoing_edges = graph.get_outgoing_edges(node_id);
117
118        for edge in outgoing_edges {
119            let child_tree = self.build_tree_recursive(&edge.target, graph, visited)?;
120            children.push(child_tree);
121        }
122
123        visited.remove(node_id);
124
125        Ok(TreeNode {
126            id: node_id.clone(),
127            size: node.size,
128            children,
129            position: Position::zero(), // Will be calculated during layout
130            width: 0.0,                 // Will be calculated
131            height: 0.0,                // Will be calculated
132        })
133    }
134
135    /// Calculate layout positions using Walker's algorithm
136    fn calculate_positions(&self, tree: &mut TreeNode) {
137        // Phase 1: Calculate initial positions using post-order traversal
138        self.first_walk(tree, 0);
139
140        // Phase 2: Calculate final positions using pre-order traversal
141        self.second_walk(tree, 0.0, 0);
142    }
143
144    /// First walk - calculate preliminary x coordinates
145    #[allow(clippy::only_used_in_recursion)]
146    fn first_walk(&self, node: &mut TreeNode, level: usize) {
147        if node.children.is_empty() {
148            // Leaf node
149            node.width = node.size.width;
150            node.height = node.size.height;
151        } else {
152            // Internal node - process children first
153            for child in &mut node.children {
154                self.first_walk(child, level + 1);
155            }
156
157            // Calculate width as sum of children plus separations
158            let total_child_width: f64 = node.children.iter().map(|child| child.width).sum();
159            let separations = (node.children.len().saturating_sub(1)) as f64 * self.node_separation;
160
161            node.width = total_child_width + separations;
162            node.height = node.size.height;
163
164            // Position children
165            let mut current_x = 0.0;
166            for child in &mut node.children {
167                child.position.x = current_x + child.width / 2.0;
168                current_x += child.width + self.node_separation;
169            }
170        }
171    }
172
173    /// Second walk - calculate final coordinates
174    fn second_walk(&self, node: &mut TreeNode, x_offset: f64, level: usize) {
175        let y_position = match self.direction {
176            LayoutDirection::TopToBottom => level as f64 * self.level_separation,
177            LayoutDirection::BottomToTop => -(level as f64 * self.level_separation),
178            LayoutDirection::LeftToRight => level as f64 * self.level_separation,
179            LayoutDirection::RightToLeft => -(level as f64 * self.level_separation),
180        };
181
182        // Set final position
183        match self.direction {
184            LayoutDirection::TopToBottom | LayoutDirection::BottomToTop => {
185                node.position.x += x_offset;
186                node.position.y = y_position;
187            }
188            LayoutDirection::LeftToRight | LayoutDirection::RightToLeft => {
189                node.position.x = y_position;
190                node.position.y += x_offset;
191            }
192        }
193
194        // Process children
195        let children_start_x = node.position.x - node.width / 2.0;
196        for child in &mut node.children {
197            self.second_walk(child, children_start_x, level + 1);
198        }
199    }
200
201    /// Apply tree positions to graph nodes
202    #[allow(clippy::only_used_in_recursion)]
203    fn apply_tree_to_graph<N, E>(&self, tree: &TreeNode, graph: &mut Graph<N, E>) {
204        if let Some(node) = graph.get_node_mut(&tree.id) {
205            node.position = tree.position;
206        }
207
208        for child in &tree.children {
209            self.apply_tree_to_graph(child, graph);
210        }
211    }
212}
213
214impl<N, E> LayoutAlgorithm<N, E> for HierarchicalLayout {
215    fn name(&self) -> &str {
216        "Hierarchical"
217    }
218
219    fn apply(&mut self, graph: &mut Graph<N, E>) -> Result<()> {
220        if graph.is_empty() {
221            return Ok(());
222        }
223
224        // Build tree structure
225        let mut tree = self.build_tree(graph)?;
226
227        // Calculate positions
228        self.calculate_positions(&mut tree);
229
230        // Apply to graph
231        self.apply_tree_to_graph(&tree, graph);
232
233        Ok(())
234    }
235}
236
237/// Tree node for hierarchical layout calculation
238#[derive(Debug, Clone)]
239struct TreeNode {
240    id: NodeId,
241    size: Size,
242    children: Vec<TreeNode>,
243    position: Position,
244    width: f64,
245    height: f64,
246}
247
248/// Builder for hierarchical layout
249#[derive(Debug, Clone, Default)]
250pub struct HierarchicalLayoutBuilder {
251    layout: HierarchicalLayout,
252}
253
254impl HierarchicalLayoutBuilder {
255    /// Set node separation distance
256    pub fn node_separation(mut self, separation: f64) -> Self {
257        self.layout.node_separation = separation;
258        self
259    }
260
261    /// Set level separation distance
262    pub fn level_separation(mut self, separation: f64) -> Self {
263        self.layout.level_separation = separation;
264        self
265    }
266
267    /// Set edge routing style
268    pub fn edge_routing(mut self, routing: EdgeRouting) -> Self {
269        self.layout.edge_routing = routing;
270        self
271    }
272
273    /// Set layout direction
274    pub fn direction(mut self, direction: LayoutDirection) -> Self {
275        self.layout.direction = direction;
276        self
277    }
278
279    /// Set root node
280    pub fn root_node(mut self, root_id: impl Into<NodeId>) -> Self {
281        self.layout.root_node = Some(root_id.into());
282        self
283    }
284
285    /// Build the layout algorithm
286    pub fn build(self) -> HierarchicalLayout {
287        self.layout
288    }
289}
flow_rs_core/layout/algorithms/hierarchical.rs

flow_rs_core/layout/algorithms/
hierarchical.rs
