unexpected overlapping behavior for `from_vertices_and_edges`

[MathieuDuponchelle]

I want to create layouts for vertices with varying dimensions, and I get unexpected results:

use rust_sugiyama::{configure::Config, from_vertices_and_edges};

fn main() {
    let vertices = [(0, (40.0, 8.0)), (1, (7.0, 3.0)), (2, (39.0, 3.0))];

    let edges = [(0, 1), (0, 2)];

    let layouts = from_vertices_and_edges(
        &vertices,
        &edges,
        &Config {
            vertex_spacing: 6.0,
            ..Default::default()
        },
    );

    for (layout, width, height) in layouts {
        println!("Coordinates: {:?}", layout);
        println!("width: {width}, height: {height}");
    }
}

This prints:

Coordinates: [(0, (22.75, 0.0)), (1, (37.5, 11.5)), (2, (0.0, 11.5))]
width: 2, height: 2

Meaning node 2 with width 39 actually overlaps with node 1 by 1.5 units, even though I specified a vertex spacing of 6.

The visual result in my application looks like:

I think this is probably related to this comment : #18 (comment) , @andriyDev any thoughts here?

[MathieuDuponchelle]

To follow up on this, after re-reading that comment my assumption is that I need to treat the returned coordinates as the center rather than the top left corner, I'll try to do a little dance to shift coordinates accordingly in my application and report back, if it turns out to be the proper fix it could be nice to have this taken care of automagically, perhaps through a config option :)

[MathieuDuponchelle]

Yeah that did the trick, I'll post the snippet here for now in case that helps someone, this could probably be done in two loops instead of three but that way was easier to reason about :)

        let mut shifted_and_transposed_layouts: Vec<(Vec<(usize, (i32, i32))>, f64, f64)> = vec![];                                         
                                                                                                                                            
        let layouts = rust_sugiyama::from_vertices_and_edges(&vertices, &graph_edges, &config);                                                                                                           
                                                                                                                                            
        // rust-sugiyama returns the coordinates of the center of vertices                                                                  
        // and lays them top to bottom by default, shift all coordinates                                                                    
        // to top left and transpose when left-to-right was selected                                                                        
        for layout in layouts {                                                                                                             
            let mut max_width_shift = 0;                                                                                                    
            let mut max_height_shift = 0;                                                                                                   
            let mut shifted_and_transposed_layout = vec![];                                                                                 
                                                                                                                                            
            for (id, (x, y)) in layout.0.iter() {                                                                                           
                // Invert x and y for horizontal rendering                                                                                  
                let (x, y) = if self.ltr {                                                                                                  
                    (*y as i32, *x as i32)                                                                                                  
                } else {                                                                                                                    
                    (*x as i32, *y as i32)                                                                                                  
                };                                                                                                                          
                // Adapt these two lines
                let vertex_name = id_to_vertex.get(&id).expect("unknown vertex id");                                                        
                let vertex = self.graph_vertices.get_mut(vertex_name).unwrap();                                                             
                                                                                                                                            
                let width_shift = (vertex.width / 2) as i32;                                                                                
                let height_shift = (vertex.height / 2) as i32;                                                                              
                                                                                                                                            
                max_width_shift = max_width_shift.max(width_shift);                                                                         
                max_height_shift = max_height_shift.max(height_shift);                                                                      
                                                                                                                                            
                shifted_and_transposed_layout.push((*id, (x - width_shift, y - height_shift)));                                             
            }                                                                                                                               
                                                                                                                                            
            let mut x_zero_offset = std::i32::MAX;
            let mut y_zero_offset = std::i32::MAX;

            for (_, (x, y)) in shifted_and_transposed_layout.iter_mut() {
                *x += max_width_shift;
                *y += max_height_shift;

                x_zero_offset = x_zero_offset.min(*x);
                y_zero_offset = y_zero_offset.min(*y);
            }

            for (_, (x, y)) in shifted_and_transposed_layout.iter_mut() {
                *x -= x_zero_offset;
                *y -= y_zero_offset;
            }

            shifted_and_transposed_layouts.push((shifted_and_transposed_layout, layout.1, layout.2));
        }

[MathieuDuponchelle]

the type casts might need adapting as well, my target coordinate system is u16 (ratatui), so casting to i32 is sufficient for me

[MathieuDuponchelle]

after shifting