graphviz_pure_layout/
lib.rs

1//! Graphviz layout engines in pure Rust (`dot`, `neato`, `fdp`, `sfdp`, `twopi`, `circo`, `osage`, `patchwork`).
2
3pub mod cdt;
4pub mod circogen;
5pub mod common;
6pub mod cutil;
7pub mod dotgen;
8pub mod fdpgen;
9pub mod neatogen;
10pub mod nop;
11pub mod ortho;
12pub mod osage;
13pub mod pack;
14pub mod patchwork;
15pub mod sfdpgen;
16pub mod sparse;
17pub mod twopigen;
18pub mod vpsc;
19
20use graphviz_pure_core::{Graph, GraphvizError, Result};
21
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub enum LayoutEngine {
24    Dot,
25    Neato,
26    Fdp,
27    Sfdp,
28    Twopi,
29    Circo,
30    Osage,
31    Patchwork,
32    /// `nop`/`nop1`: neato with `-n1`.
33    Nop1,
34    /// `nop2`: neato with `-n2`.
35    Nop2,
36}
37
38/// Engine options set on the command line.
39#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
40pub struct LayoutOptions {
41    /// `-n[N]`: neato keeps the input positions (`Nop` in C). 0 runs the full layout.
42    pub nop: u8,
43}
44
45impl LayoutEngine {
46    pub fn parse(name: &str) -> Result<Self> {
47        match name.trim().to_ascii_lowercase().as_str() {
48            "dot" => Ok(Self::Dot),
49            "neato" => Ok(Self::Neato),
50            "fdp" => Ok(Self::Fdp),
51            "sfdp" => Ok(Self::Sfdp),
52            "twopi" => Ok(Self::Twopi),
53            "circo" => Ok(Self::Circo),
54            "osage" => Ok(Self::Osage),
55            "patchwork" => Ok(Self::Patchwork),
56            "nop" | "nop1" => Ok(Self::Nop1),
57            "nop2" => Ok(Self::Nop2),
58            other => Err(GraphvizError::UnsupportedEngine(other.to_string())),
59        }
60    }
61}
62
63pub fn layout_graph(graph: &mut Graph, engine: LayoutEngine) -> Result<()> {
64    layout_graph_with_options(graph, engine, LayoutOptions::default())
65}
66
67pub fn layout_graph_with_options(
68    graph: &mut Graph,
69    engine: LayoutEngine,
70    options: LayoutOptions,
71) -> Result<()> {
72    graphviz_pure_core::charset::begin_layout(
73        &graph.name,
74        graph.graph_attrs.get("charset").map(String::as_str),
75    );
76    // Only dot exports its `GD_clust` lists; to C the key is an ordinary attribute, so a
77    // value from the input must not reorder the clusters of another engine's drawing.
78    let key = graphviz_pure_core::CLUSTER_LIST_KEY;
79    graph.graph_attrs.remove(key);
80    for s in &mut graph.subgraphs {
81        s.graph_attrs.remove(key);
82    }
83    // graph_init's do_graph_label(g) (lib/common/input.c:711) makes the root label before
84    // any engine's node and edge init, so its diagnostics come first; the engines' own
85    // calls do not repeat them.
86    let _ = graphviz_pure_geom::graph_label_geometry_in(
87        &graph.name,
88        &graph.graph_attrs,
89        true,
90        false,
91        &graphviz_pure_geom::NodeSizeEnv::from_graph(graph),
92    );
93    let effective_engine = if engine == LayoutEngine::Dot
94        && let Some(attr_layout) = graph.graph_attrs.get("layout")
95        && let Ok(parsed) = LayoutEngine::parse(attr_layout)
96    {
97        parsed
98    } else {
99        engine
100    };
101    // A layout of the same graph must not keep an earlier dot layout's lw/rw split.
102    for n in &mut graph.nodes {
103        n.attrs.remove(graphviz_pure_core::NODE_LW_RW_KEY);
104    }
105
106    match effective_engine {
107        LayoutEngine::Dot => dotgen::layout_dot(graph),
108        LayoutEngine::Neato if options.nop > 0 => nop::layout_nop(graph, options.nop),
109        LayoutEngine::Nop1 => nop::layout_nop(graph, 1),
110        LayoutEngine::Nop2 => nop::layout_nop(graph, 2),
111        LayoutEngine::Neato => neatogen::neatoinit::neato_layout(graph),
112        LayoutEngine::Fdp => fdpgen::layout::fdp_layout(graph),
113        LayoutEngine::Sfdp => sfdpgen::sfdpinit::sfdp_layout(graph),
114        LayoutEngine::Twopi => twopigen::twopiinit::twopi_layout(graph),
115        LayoutEngine::Circo => circogen::circularinit::circo_layout(graph),
116        LayoutEngine::Osage => osage::osage_layout(graph),
117        LayoutEngine::Patchwork => patchwork::patchwork_layout(graph),
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use super::*;
124    use graphviz_pure_core::{AttrMap, Graph, GraphKind, Point, SubgraphData, SubgraphId};
125
126    fn make_chain_graph() -> Graph {
127        let mut g = Graph::new("G", GraphKind::Directed, false);
128        let a = g.ensure_node("a");
129        let b = g.ensure_node("b");
130        let c = g.ensure_node("c");
131        g.add_edge(a, b, AttrMap::new());
132        g.add_edge(b, c, AttrMap::new());
133        g
134    }
135
136    #[test]
137    fn relayout_drops_the_previous_lw_rw_split() {
138        let mut g = Graph::new("G", GraphKind::Directed, false);
139        let a = g.ensure_node("a");
140        g.add_edge(a, a, AttrMap::new());
141        let key = graphviz_pure_core::NODE_LW_RW_KEY;
142        g.graph_attrs.insert("splines".into(), String::new());
143        layout_graph(&mut g, LayoutEngine::Dot).unwrap();
144        assert!(g.nodes[a.0 as usize].attrs.contains_key(key));
145        g.graph_attrs.insert("splines".into(), "true".into());
146        layout_graph(&mut g, LayoutEngine::Dot).unwrap();
147        assert!(!g.nodes[a.0 as usize].attrs.contains_key(key));
148    }
149
150    #[test]
151    fn test_engine_parse() {
152        assert_eq!(LayoutEngine::parse("dot").unwrap(), LayoutEngine::Dot);
153        assert_eq!(LayoutEngine::parse("NEATO").unwrap(), LayoutEngine::Neato);
154        assert_eq!(LayoutEngine::parse("fdp").unwrap(), LayoutEngine::Fdp);
155        assert_eq!(LayoutEngine::parse("sfdp").unwrap(), LayoutEngine::Sfdp);
156        assert_eq!(LayoutEngine::parse("twopi").unwrap(), LayoutEngine::Twopi);
157        assert_eq!(LayoutEngine::parse("circo").unwrap(), LayoutEngine::Circo);
158        assert_eq!(LayoutEngine::parse("osage").unwrap(), LayoutEngine::Osage);
159        assert_eq!(
160            LayoutEngine::parse("patchwork").unwrap(),
161            LayoutEngine::Patchwork
162        );
163        assert!(LayoutEngine::parse("unknown").is_err());
164    }
165
166    #[test]
167    fn test_dot_rank_assignment_and_tb_coordinates() {
168        let mut g = make_chain_graph();
169        layout_graph(&mut g, LayoutEngine::Dot).unwrap();
170
171        assert_eq!(g.nodes[0].rank, 0);
172        assert_eq!(g.nodes[1].rank, 1);
173        assert_eq!(g.nodes[2].rank, 2);
174
175        // In default TB rankdir, rank 0 is at top (highest Y) and rank 2 is at bottom (lowest Y).
176        assert!(g.nodes[0].pos.y > g.nodes[1].pos.y);
177        assert!(g.nodes[1].pos.y > g.nodes[2].pos.y);
178        // Single-chain nodes should be vertically aligned on X.
179        assert!((g.nodes[0].pos.x - g.nodes[1].pos.x).abs() < 1e-4);
180        assert!((g.nodes[1].pos.x - g.nodes[2].pos.x).abs() < 1e-4);
181
182        // Graph bounding box lower-left must be normalized to (0, 0).
183        assert_eq!(g.bb.ll, Point::new(0.0, 0.0));
184        assert!(g.bb.width() > 0.0 && g.bb.height() > 0.0);
185    }
186
187    #[test]
188    fn test_dot_rankdir_variants() {
189        // BT: rank 0 at bottom (smaller Y), rank 2 at top (larger Y)
190        let mut g_bt = make_chain_graph();
191        g_bt.graph_attrs
192            .insert("rankdir".to_string(), "BT".to_string());
193        layout_graph(&mut g_bt, LayoutEngine::Dot).unwrap();
194        assert!(g_bt.nodes[0].pos.y < g_bt.nodes[1].pos.y);
195        assert!(g_bt.nodes[1].pos.y < g_bt.nodes[2].pos.y);
196
197        // LR: rank 0 on left (smaller X), rank 2 on right (larger X)
198        let mut g_lr = make_chain_graph();
199        g_lr.graph_attrs
200            .insert("rankdir".to_string(), "LR".to_string());
201        layout_graph(&mut g_lr, LayoutEngine::Dot).unwrap();
202        assert!(g_lr.nodes[0].pos.x < g_lr.nodes[1].pos.x);
203        assert!(g_lr.nodes[1].pos.x < g_lr.nodes[2].pos.x);
204
205        // RL: rank 0 on right (larger X), rank 2 on left (smaller X)
206        let mut g_rl = make_chain_graph();
207        g_rl.graph_attrs
208            .insert("rankdir".to_string(), "RL".to_string());
209        layout_graph(&mut g_rl, LayoutEngine::Dot).unwrap();
210        assert!(g_rl.nodes[0].pos.x > g_rl.nodes[1].pos.x);
211        assert!(g_rl.nodes[1].pos.x > g_rl.nodes[2].pos.x);
212    }
213
214    #[test]
215    fn test_dot_cycle_breaking_and_rank_same() {
216        let mut g = Graph::new("Cycle", GraphKind::Directed, false);
217        let a = g.ensure_node("a");
218        let b = g.ensure_node("b");
219        let c = g.ensure_node("c");
220        let d = g.ensure_node("d");
221
222        let mut heavy = AttrMap::new();
223        heavy.insert("weight".to_string(), "10".to_string());
224        g.add_edge(a, b, heavy.clone());
225        g.add_edge(b, c, heavy);
226        // Light back-edge c -> a should be reversed during cycle breaking.
227        g.add_edge(c, a, AttrMap::new());
228        g.add_edge(b, d, AttrMap::new());
229
230        // Constrain c and d to rank=same.
231        let mut sub_attrs = AttrMap::new();
232        sub_attrs.insert("rank".to_string(), "same".to_string());
233        g.subgraphs.push(SubgraphData {
234            id: SubgraphId(0),
235            name: "same_cd".to_string(),
236            is_cluster: false,
237            graph_attrs: sub_attrs,
238            node_defaults: AttrMap::new(),
239            edge_defaults: AttrMap::new(),
240            nodes: vec![c, d],
241            edges: Vec::new(),
242            subgraphs: Vec::new(),
243            bb: Default::default(),
244        });
245
246        layout_graph(&mut g, LayoutEngine::Dot).unwrap();
247        assert!(g.nodes[a.0 as usize].rank < g.nodes[b.0 as usize].rank);
248        assert!(g.nodes[b.0 as usize].rank < g.nodes[c.0 as usize].rank);
249        assert_eq!(g.nodes[c.0 as usize].rank, g.nodes[d.0 as usize].rank);
250    }
251
252    #[test]
253    fn test_dot_crossing_minimization() {
254        // Construct a 2-layer bipartite graph where initial order (a1, a2) -> (b1, b2)
255        // has edges a1->b2 and a2->b1 that would cross unless mincross reorders one rank.
256        let mut g = Graph::new("Cross", GraphKind::Directed, false);
257        let a1 = g.ensure_node("a1");
258        let a2 = g.ensure_node("a2");
259        let b1 = g.ensure_node("b1");
260        let b2 = g.ensure_node("b2");
261        g.add_edge(a1, b2, AttrMap::new());
262        g.add_edge(a2, b1, AttrMap::new());
263
264        layout_graph(&mut g, LayoutEngine::Dot).unwrap();
265        // Either a1 is to the left of a2 AND b2 is to the left of b1, or vice versa (0 crossings).
266        let a_diff = g.nodes[a1.0 as usize].pos.x - g.nodes[a2.0 as usize].pos.x;
267        let b_diff = g.nodes[b2.0 as usize].pos.x - g.nodes[b1.0 as usize].pos.x;
268        assert!(a_diff * b_diff > 0.0);
269    }
270
271    #[test]
272    fn test_all_eight_layout_engines_succeed() {
273        let engines = [
274            LayoutEngine::Dot,
275            LayoutEngine::Neato,
276            LayoutEngine::Fdp,
277            LayoutEngine::Sfdp,
278            LayoutEngine::Twopi,
279            LayoutEngine::Circo,
280            LayoutEngine::Osage,
281            LayoutEngine::Patchwork,
282        ];
283
284        for engine in engines {
285            let mut g = Graph::new("TestAll", GraphKind::Directed, false);
286            let a = g.ensure_node("a");
287            let b = g.ensure_node("b");
288            let c = g.ensure_node("c");
289            let d = g.ensure_node("d");
290            g.add_edge(a, b, AttrMap::new());
291            g.add_edge(b, c, AttrMap::new());
292            g.add_edge(c, d, AttrMap::new());
293            g.add_edge(d, a, AttrMap::new());
294
295            layout_graph(&mut g, engine).unwrap();
296            assert_eq!(g.bb.ll, Point::new(0.0, 0.0));
297            assert!(g.bb.width() > 0.0 && g.bb.height() > 0.0);
298            for node in &g.nodes {
299                assert!(node.pos.x.is_finite() && node.pos.y.is_finite());
300                assert!(node.pos.x >= 0.0 && node.pos.y >= 0.0);
301            }
302            // patchwork draws no edges, as in C.
303            if engine != LayoutEngine::Patchwork {
304                for edge in &g.edges {
305                    assert!(!edge.spline.segments.is_empty());
306                }
307            }
308        }
309    }
310}
graphviz_pure_layout/lib.rs

graphviz_pure_layout/
lib.rs
