rust_sugiyama/
configure.rs

1use std::{env, marker::PhantomData};
2
3use log::{error, trace};
4use petgraph::stable_graph::{NodeIndex, StableDiGraph};
5
6use crate::{
7    algorithm::{self, Edge, Vertex},
8    Layouts,
9};
10
11// Default values for configuration
12pub static MINIMUM_LENGTH_DEFAULT: u32 = 1;
13pub static VERTEX_SPACING_DEFAULT: usize = 10;
14pub static DUMMY_VERTICES_DEFAULT: bool = true;
15pub static RANKING_TYPE_DEFAULT: RankingType = RankingType::MinimizeEdgeLength;
16pub static C_MINIMIZATION_DEFAULT: CrossingMinimization = CrossingMinimization::Barycenter;
17pub static TRANSPOSE_DEFAULT: bool = true;
18pub static DUMMY_SIZE_DEFAULT: f64 = 1.0;
19
20static ENV_MINIMUM_LENGTH: &str = "RUST_GRAPH_MIN_LEN";
21static ENV_VERTEX_SPACING: &str = "RUST_GRAPH_V_SPACING";
22static ENV_DUMMY_VERTICES: &str = "RUST_GRAPH_DUMMIES";
23static ENV_RANKING_TYPE: &str = "RUST_GRAPH_R_TYPE";
24static ENV_CROSSING_MINIMIZATION: &str = "RUST_GRAPH_CROSS_MIN";
25static ENV_TRANSPOSE: &str = "RUST_GRAPH_TRANSPOSE";
26static ENV_DUMMY_SIZE: &str = "RUST_GRAPH_DUMMY_SIZE";
27
28pub trait IntoCoordinates {}
29
30impl<V, E> IntoCoordinates for StableDiGraph<V, E> {}
31impl IntoCoordinates for &[(u32, u32)] {}
32impl IntoCoordinates for (&[u32], &[(u32, u32)]) {}
33
34macro_rules! read_env {
35    ($field:expr, $cb:tt, $env:ident) => {
36        #[allow(unused_parens)]
37        match env::var($env).map($cb) {
38            Ok(Ok(v)) => $field = v,
39            Ok(Err(e)) => {
40                error!(target: "initialization", "{e}");
41            }
42            _ => (),
43        }
44    };
45}
46
47/// Used to configure parameters of the graph layout.
48///
49/// Struct fields are:
50/// 1. minimum_edge: length between layers
51/// 2. vertex_spacing: minimum spacing between vertices on the same layer
52/// 3. dummy_vertices: should dummie vertices be included when calculating the layout
53/// 4. ranking_type: defines how vertices are places vertically, see [RankingType]
54/// 5. c_minimization: which heuristic to use when minimizing edge crossings, see [CrossingMinimization]
55/// 6. transpose: try to further reduce crossings, by swaping vertices in a layer, may increase runtime significantly
56#[derive(Clone, Copy, Debug)]
57pub struct Config {
58    pub minimum_length: u32,
59    pub vertex_spacing: usize,
60    pub dummy_vertices: bool,
61    pub dummy_size: f64,
62    pub ranking_type: RankingType,
63    pub c_minimization: CrossingMinimization,
64    pub transpose: bool,
65}
66
67impl Config {
68    /// Create a new config by reading in environment variables.
69    /// See [CoordinatesBuilder::configure_from_env] for a detailed description of environment variables.
70    pub fn new_from_env() -> Self {
71        let config = Self::default();
72        config.read_env()
73    }
74
75    /// Updates the config by reading in environment variables.
76    /// See [CoordinatesBuilder::configure_from_env] for a detailed description of environment variables.
77    pub fn read_env(mut self) -> Self {
78        let parse_bool = |x: String| match x.as_str() {
79            "y" => Ok(true),
80            "n" => Ok(false),
81            v => Err(format!("Invalid argument for dummy vertex env: {v}")),
82        };
83
84        read_env!(
85            self.minimum_length,
86            (|x| x.parse::<u32>()),
87            ENV_MINIMUM_LENGTH
88        );
89
90        read_env!(
91            self.c_minimization,
92            (TryFrom::try_from),
93            ENV_CROSSING_MINIMIZATION
94        );
95
96        read_env!(self.ranking_type, (TryFrom::try_from), ENV_RANKING_TYPE);
97
98        read_env!(
99            self.vertex_spacing,
100            (|x| x.parse::<usize>()),
101            ENV_VERTEX_SPACING
102        );
103
104        read_env!(self.dummy_vertices, parse_bool, ENV_DUMMY_VERTICES);
105
106        read_env!(self.dummy_size, (|x| x.parse::<f64>()), ENV_DUMMY_SIZE);
107
108        read_env!(self.transpose, parse_bool, ENV_TRANSPOSE);
109
110        self
111    }
112}
113
114impl Default for Config {
115    fn default() -> Self {
116        Self {
117            minimum_length: MINIMUM_LENGTH_DEFAULT,
118            vertex_spacing: VERTEX_SPACING_DEFAULT,
119            dummy_vertices: DUMMY_VERTICES_DEFAULT,
120            ranking_type: RANKING_TYPE_DEFAULT,
121            c_minimization: C_MINIMIZATION_DEFAULT,
122            transpose: TRANSPOSE_DEFAULT,
123            dummy_size: DUMMY_SIZE_DEFAULT,
124        }
125    }
126}
127
128/// Defines the Ranking type, i.e. how vertices are placed on each layer.
129#[derive(Clone, Copy, Debug, PartialEq, Eq)]
130pub enum RankingType {
131    /// First moves vertices as far up as possible, and then as low as possible
132    Original,
133    /// Tries to minimize edge lengths across layers
134    MinimizeEdgeLength,
135    /// Move vertices as far up as possible
136    Up,
137    /// Move vertices as far down as possible
138    Down,
139}
140
141impl TryFrom<String> for RankingType {
142    type Error = String;
143
144    fn try_from(value: String) -> Result<Self, Self::Error> {
145        match value.as_str() {
146            "original" => Ok(Self::Original),
147            "minimize" => Ok(Self::MinimizeEdgeLength),
148            "up" => Ok(Self::Up),
149            "down" => Ok(Self::Down),
150            s => Err(format!("invalid value for ranking type: {s}")),
151        }
152    }
153}
154
155impl From<RankingType> for &'static str {
156    fn from(value: RankingType) -> Self {
157        match value {
158            RankingType::Up => "up",
159            RankingType::Down => "down",
160            RankingType::Original => "original",
161            RankingType::MinimizeEdgeLength => "minimize",
162        }
163    }
164}
165
166/// Defines the heuristic used for crossing minimization.
167/// During crossing minimization, the vertices of one layer are
168/// ordered, so they're as close to neighboring vertices as possible.
169#[derive(Clone, Copy, Debug, PartialEq, Eq)]
170pub enum CrossingMinimization {
171    /// Calculates the average of the positions of adjacent neighbors
172    Barycenter,
173    /// Calculates the weighted median of the positions of adjacent neighbors
174    Median,
175}
176
177impl TryFrom<String> for CrossingMinimization {
178    type Error = String;
179
180    fn try_from(value: String) -> Result<Self, Self::Error> {
181        match value.as_str() {
182            "barycenter" => Ok(Self::Barycenter),
183            "median" => Ok(Self::Median),
184            s => Err(format!("invalid value for crossing minimization: {s}")),
185        }
186    }
187}
188
189impl From<CrossingMinimization> for &'static str {
190    fn from(value: CrossingMinimization) -> Self {
191        match value {
192            CrossingMinimization::Median => "median",
193            CrossingMinimization::Barycenter => "barycenter",
194        }
195    }
196}
197
198/// Can be used to configure the layout of the graph, via the builder pattern.
199///
200/// # Example
201/// ```
202/// use rust_sugiyama::from_edges;
203/// let edges = [(0, 1), (0, 2), (2, 3)];
204/// let coords = from_edges(&edges)
205///     .vertex_spacing(20) // vertices are at least 20px apart
206///     .dummy_vertices(false) // ignore dummy vertices when calculating layout
207///     .transpose(false) // don't use tranpose function during crossing minimization
208///     .build(); // build the layout
209/// ```
210pub struct CoordinatesBuilder<Input: IntoCoordinates> {
211    config: Config,
212    _inner: StableDiGraph<Vertex, Edge>,
213    pd: PhantomData<Input>,
214}
215
216impl<Input: IntoCoordinates> CoordinatesBuilder<Input> {
217    pub(super) fn new(graph: StableDiGraph<Vertex, Edge>) -> Self {
218        Self {
219            config: Config::default(),
220            _inner: graph,
221            pd: PhantomData,
222        }
223    }
224
225    /// Set the minimimum length, see [Config] for description
226    pub fn minimum_length(mut self, v: u32) -> Self {
227        trace!(target: "initializing",
228            "Setting minimum length to: {v}");
229        self.config.minimum_length = v;
230        self
231    }
232
233    /// Set the spacing between vertices, see [Config] for description
234    pub fn vertex_spacing(mut self, v: usize) -> Self {
235        trace!(target: "initializing",
236            "Setting vertex spacing to: {v}");
237        self.config.vertex_spacing = v;
238        self
239    }
240
241    /// Activate/deactivate dummy vertices, see [Config] for description
242    pub fn dummy_vertices(mut self, v: bool) -> Self {
243        trace!(target: "initializing",
244            "Has dummy vertices: {v}");
245        self.config.dummy_vertices = v;
246        self
247    }
248
249    /// Set the layering type, see [Config] for description
250    pub fn layering_type(mut self, v: RankingType) -> Self {
251        trace!(target: "initializing",
252            "using layering type: {v:?}");
253        self.config.ranking_type = v;
254        self
255    }
256
257    /// Set the crossing minimization heuristic, see [Config] for description
258    pub fn crossing_minimization(mut self, v: CrossingMinimization) -> Self {
259        trace!(target: "initializing",
260            "Heuristic for crossing minimization: {v:?}");
261        self.config.c_minimization = v;
262        self
263    }
264
265    /// Use transpose function during crossing minimization, see [Config]
266    pub fn transpose(mut self, v: bool) -> Self {
267        trace!(target: "initializing",
268            "Use transpose to further reduce crossings: {v}");
269        self.config.transpose = v;
270        self
271    }
272
273    /// Set the size of the dummy vertices, see [Config]
274    pub fn dummy_size(mut self, v: f64) -> Self {
275        trace!(target: "initializing",
276            "Dummy size in regards to vertex size: {v}");
277        self.config.dummy_size = v;
278        self
279    }
280
281    pub fn with_config(mut self, config: Config) -> Self {
282        trace!(target: "initializing",
283            "With config {:?}", config);
284        self.config = config;
285        self
286    }
287
288    /// Read in configuration values from environment variables.
289    ///
290    /// Envs that can be set include:
291    ///
292    /// | ENV | values | default | description |
293    /// | --- | ------ | ------- | ----------- |
294    /// | RUST_GRAPH_MIN_LEN    | integer, > 0         | 1          | minimum edge length between layers |
295    /// | RUST_GRAPH_V_SPACING  | integer, > 0         | 10         | minimum spacing between vertices on the same layer |
296    /// | RUST_GRAPH_DUMMIES    | y \| n               | y          | if dummy vertices are included in the final layout |
297    /// | RUST_GRAPH_R_TYPE     | original \| minimize \| up \| down | minimize   | defines how vertices are places vertically |
298    /// | RUST_GRAPH_CROSS_MIN  | barycenter \| median | barycenter | which heuristic to use for crossing reduction |
299    /// | RUST_GRAPH_TRANSPOSE  | y \| n               | y          | if transpose function is used to further try to reduce crossings (may increase runtime significally for large graphs) |
300    /// | RUST_GRAPH_DUMMY_SIZE | float, 1 >= v > 0    | 1.0        |size of dummy vertices in final layout, if dummy vertices are included. this will squish the graph horizontally |
301    pub fn configure_from_env(mut self) -> Self {
302        self.config = self.config.read_env();
303        self
304    }
305}
306
307impl<V, E> CoordinatesBuilder<StableDiGraph<V, E>> {
308    /// Build the layout.
309    pub fn build(self) -> Layouts<NodeIndex> {
310        let Self {
311            config,
312            _inner: graph,
313            ..
314        } = self;
315        algorithm::start(
316            graph.map(|_, _| Vertex::default(), |_, _| Edge::default()),
317            config,
318        )
319        .into_iter()
320        .map(|(l, w, h)| {
321            (
322                l.into_iter()
323                    .map(|(id, coords)| (NodeIndex::from(id as u32), coords))
324                    .collect(),
325                w,
326                h,
327            )
328        })
329        .collect()
330    }
331}
332
333impl CoordinatesBuilder<&[(u32, u32)]> {
334    /// Build the layout.
335    pub fn build(self) -> Layouts<usize> {
336        let Self {
337            config,
338            _inner: graph,
339            ..
340        } = self;
341        algorithm::start(graph, config)
342    }
343}
344
345impl CoordinatesBuilder<(&[u32], &[(u32, u32)])> {
346    /// Build the layout.
347    pub fn build(self) -> Layouts<usize> {
348        let Self {
349            config,
350            _inner: graph,
351            ..
352        } = self;
353        algorithm::start(graph, config)
354    }
355}
356
357#[test]
358fn from_env_all_valid() {
359    use super::from_edges;
360    use std::env;
361    let edges = [(1, 2), (2, 3)];
362    env::set_var(ENV_MINIMUM_LENGTH, "5");
363    env::set_var(ENV_DUMMY_VERTICES, "y");
364    env::set_var(ENV_DUMMY_SIZE, "0.1");
365    env::set_var(ENV_RANKING_TYPE, "up");
366    env::set_var(ENV_CROSSING_MINIMIZATION, "median");
367    env::set_var(ENV_TRANSPOSE, "n");
368    env::set_var(ENV_VERTEX_SPACING, "20");
369    let cfg = from_edges(&edges).configure_from_env();
370    assert_eq!(cfg.config.minimum_length, 5);
371    assert_eq!(cfg.config.dummy_vertices, true);
372    assert_eq!(cfg.config.dummy_size, 0.1);
373    assert_eq!(cfg.config.ranking_type, RankingType::Up);
374    assert_eq!(cfg.config.c_minimization, CrossingMinimization::Median);
375    assert_eq!(cfg.config.transpose, false);
376    assert_eq!(cfg.config.vertex_spacing, 20);
377}
378
379#[test]
380fn from_env_invalid_value() {
381    use super::from_edges;
382    use std::env;
383
384    let edges = [(1, 2)];
385    env::set_var(ENV_CROSSING_MINIMIZATION, "flubbeldiflap");
386    env::set_var(ENV_VERTEX_SPACING, "1.5");
387    let cfg = from_edges(&edges);
388    let default = Config::default();
389    assert_eq!(default.c_minimization, cfg.config.c_minimization);
390    assert_eq!(default.vertex_spacing, cfg.config.vertex_spacing);
391}
392
393#[test]
394fn run_algo_empty_graph() {
395    use super::from_edges;
396    let edges = [];
397    let g = from_edges(&edges).build();
398    assert!(g.is_empty());
399}
rust_sugiyama/configure.rs

rust_sugiyama/
configure.rs
