gen_sugiyama/
lib.rs

1//! The implementation roughly follows sugiyamas algorithm for creating
2//! a layered graph layout.
3//!
4//! Usually Sugiyamas algorithm consists of 4 Phases:
5//! 1. Remove Cycles
6//! 2. Assign each vertex to a rank/layer
7//! 3. Reorder vertices in each rank to reduce crossings
8//! 4. Calculate the final coordinates.
9//!
10//! Currently, phase 2 to 4 are implemented, Cycle removal might be added at
11//! a later time.
12//!
13//! The whole algorithm roughly follows the 1993 paper "A technique for drawing
14//! directed graphs" by Gansner et al. It can be found
15//! [here](https://ieeexplore.ieee.org/document/221135).
16//!
17//! See the submodules for each phase for more details on the implementation
18//! and references used.
19use std::collections::{BTreeMap, HashMap};
20
21use log::info;
22use petgraph::stable_graph::{EdgeIndex, NodeIndex, StableDiGraph};
23
24// Internal module dependencies for self-contained algorithm
25mod config;
26pub mod types;
27mod util;
28
29// Re-export types for external use
30pub use config::{Config, CrossingMinimization, RankingType, VERTEX_SPACING_DEFAULT};
31// Algorithm phases
32#[allow(unused_imports)]
33use p0_cycle_removal as p0;
34use p1_layering as p1;
35use p2_reduce_crossings as p2;
36use p3_calculate_coordinates as p3;
37
38//use self::p3_calculate_coordinates::VDir;
39
40mod p0_cycle_removal;
41mod p1_layering;
42mod p2_reduce_crossings;
43mod p3_calculate_coordinates;
44
45// Changes made to the original implementation:
46// - Changed id (usize) to original_id:Option<NodeIndex> that refers to
47// the original node in the graph and None for dummy nodes
48#[derive(Debug, Clone, Copy, PartialEq)]
49pub struct Vertex {
50    pub input_node_idx: Option<NodeIndex>,
51    /// Optional stable ordering preference used only as a *tiebreaker* during
52    /// crossing reduction when multiple orders yield equal heuristic scores.
53    ///
54    /// Default is 0. Positive/negative values allow callers to bias tied
55    /// vertices to one side or the other.
56    sort_bias: i32,
57    size: (f64, f64),
58    rank: i32,
59    pos: usize,
60    low: u32,
61    lim: u32,
62    parent: Option<NodeIndex>,
63    is_tree_vertex: bool,
64    is_dummy: bool,
65    root: NodeIndex,
66    align: NodeIndex,
67    shift: f64,
68    sink: NodeIndex,
69    block_max_vertex_width: f64,
70}
71
72impl Vertex {
73    pub fn new(original_id: NodeIndex) -> Self {
74        Self {
75            input_node_idx: Some(original_id),
76            ..Default::default()
77        }
78    }
79
80    pub fn new_dummy() -> Self {
81        Self {
82            input_node_idx: None,
83            is_dummy: true,
84            ..Default::default()
85        }
86    }
87
88    pub fn with_sort_bias(mut self, sort_bias: i32) -> Self {
89        self.sort_bias = sort_bias;
90        self
91    }
92
93    pub fn set_sort_bias(&mut self, sort_bias: i32) {
94        self.sort_bias = sort_bias;
95    }
96
97    pub fn sort_bias(&self) -> i32 {
98        self.sort_bias
99    }
100
101    pub fn set_size(&mut self, (width, height): (u64, u64), vertex_spacing: f64) {
102        // Vertex spacing isn't actually taken into account by itself,
103        // it's just padding to the size of the vertex. So if we change the
104        // size of the vertex, we need include the padding as well.
105        // TODO: don't hardcode the transposition here either
106        self.size = (
107            (height.max(1) as f64 + vertex_spacing),
108            (width.max(1) as f64 + vertex_spacing),
109        );
110    }
111
112    pub fn get_size(&self, vertex_spacing: f64) -> (u64, u64) {
113        // Inverse operation of set_size
114        let (width, height) = self.size;
115        // TODO: don't hardcode the transposition here either
116        (
117            (height - vertex_spacing).round() as u64,
118            (width - vertex_spacing).round() as u64,
119        )
120    }
121
122    pub fn is_dummy(&self) -> bool {
123        self.is_dummy
124    }
125
126    pub fn get_rank(&self) -> i32 {
127        self.rank
128    }
129}
130
131impl Default for Vertex {
132    fn default() -> Self {
133        Self {
134            input_node_idx: None,
135            sort_bias: 0,
136            size: (1.0, 1.0),
137            rank: 0,
138            pos: 0,
139            low: 0,
140            lim: 0,
141            parent: None,
142            is_tree_vertex: false,
143            is_dummy: false,
144            root: 0.into(),
145            align: 0.into(),
146            shift: f64::INFINITY,
147            sink: 0.into(),
148            block_max_vertex_width: 0.0,
149        }
150    }
151}
152
153#[derive(Clone, Copy, Debug)]
154pub struct Edge {
155    pub weight: i32,
156    cut_value: Option<i32>,
157    is_tree_edge: bool,
158    has_type_1_conflict: bool,
159    pub input_node_idx_pair: Option<(NodeIndex, NodeIndex)>,
160}
161
162impl Default for Edge {
163    fn default() -> Self {
164        Self {
165            weight: 1,
166            cut_value: None,
167            is_tree_edge: false,
168            has_type_1_conflict: false,
169            input_node_idx_pair: None,
170        }
171    }
172}
173
174impl Edge {
175    pub fn with_label(self, (tail, head): (NodeIndex, NodeIndex)) -> Self {
176        Self {
177            input_node_idx_pair: Some((tail, head)),
178            ..self
179        }
180    }
181}
182
183/// Runs the Sugiyama algorithm and returns the layers and vertex graph.
184/// This is the computationally expensive part that only needs to be run once.
185pub fn run_sugiyama_algorithm(
186    vertex_graph: &mut StableDiGraph<Vertex, Edge>,
187    config: &Config,
188) -> Vec<Vec<NodeIndex>> {
189    info!(target: "layouting", "Start building layout");
190    info!(target: "layouting", "Configuration is: {:?}", config);
191
192    // Phase 0: Cycle Removal
193    info!(target: "layouting", "Skipping phase 0: Cycle Removal");
194    //info!(target: "layouting", "Executing phase 0: Cycle Removal");
195    //let _reversed_edges = p0::remove_cycles(&mut vertex_graph);
196
197    // Phase 1: Layering/Ranking
198    info!(target: "layouting", "Executing phase 1: Ranking");
199    p1::rank(
200        vertex_graph,
201        config.minimum_length as i32,
202        config.ranking_type,
203    );
204
205    // Phase 2: Reorder vertices in ranks to reduce crossings.
206    info!(target: "layouting", "Executing phase 2: Crossing Reduction");
207    info!(target: "layouting",
208        "dummy vertex size: {:?}, heuristic for crossing minimization: {:?}, using transpose: {}",
209        config.dummy_size,
210        config.c_minimization,
211        config.transpose
212    );
213
214    let _dropped_edges = p2::insert_dummy_vertices(
215        vertex_graph,
216        config.minimum_length as i32,
217        config.dummy_size,
218    );
219
220    let mut layers = p2::ordering(vertex_graph, config.c_minimization, config.transpose);
221    if !config.dummy_vertices {
222        p2::remove_dummy_vertices(vertex_graph, &mut layers);
223    }
224
225    layers
226}
227
228/// Assigns final coordinates to vertices using the computed algorithm state and a label dimensions map.
229/// This can be called multiple times with different size maps to create different layout variants.
230pub fn assign_coordinates(
231    layers: &mut [Vec<NodeIndex>],
232    vertex_graph: &mut StableDiGraph<Vertex, Edge>,
233) -> Vec<(NodeIndex, (i64, i64))> {
234    // Phase 3: Coordinate Assignment
235    info!(target: "layouting", "Executing phase 3: Coordinate Calculation on a vertex graph with {} nodes and {} edges", vertex_graph.node_count(), vertex_graph.edge_count());
236    let mut layouts = p3::create_layouts(vertex_graph, layers);
237    p3::align_to_smallest_width_layout(&mut layouts);
238
239    // Calculate and normalize X coordinates
240    let mut x_coordinates = p3::calculate_relative_coords(layouts);
241    let min = x_coordinates
242        .iter()
243        .min_by(|a, b| a.1.total_cmp(&b.1))
244        .unwrap()
245        .1;
246    for (_, c) in &mut x_coordinates {
247        *c -= min;
248    }
249
250    // Calculate Y coordinates
251    let mut rank_to_max_height = BTreeMap::<i32, f64>::new();
252    for vertex in vertex_graph.node_weights() {
253        let max = rank_to_max_height.entry(vertex.rank).or_default();
254        *max = max.max(vertex.size.1);
255    }
256
257    let mut rank_to_y_offset = HashMap::new();
258    let mut current_rank_top_offset = *rank_to_max_height.iter().next().unwrap().1 * -0.5;
259    for (rank, max_height) in rank_to_max_height {
260        rank_to_y_offset.insert(rank, current_rank_top_offset + max_height * 0.5);
261        current_rank_top_offset += max_height;
262    }
263
264    // Compute provisional coordinates, transposed and rounded to the nearest integer.
265    // TODO: don't hardcode the horizontal vs vertical orientation, use a config option
266
267    x_coordinates
268        .into_iter()
269        .map(|(v, x)| {
270            (
271                v,
272                (x, *rank_to_y_offset.get(&vertex_graph[v].rank).unwrap()),
273            )
274        })
275        // if we round() instead of floor() the layout will be off by 1 cell
276        .map(|(i, (x, y))| (i, (y.floor() as i64, x.floor() as i64)))
277        .collect::<Vec<(NodeIndex, (i64, i64))>>()
278}
279
280fn slack(graph: &StableDiGraph<Vertex, Edge>, edge: EdgeIndex, minimum_length: i32) -> i32 {
281    let (tail, head) = graph.edge_endpoints(edge).unwrap();
282    graph[head].rank - graph[tail].rank - minimum_length
283}
gen_sugiyama/lib.rs

gen_sugiyama/
lib.rs
