graphviz_pure_core/
graph.rs

1use crate::geom::{BoundingBox, Point, Spline};
2use serde::{Deserialize, Serialize};
3use std::collections::{BTreeMap, BTreeSet};
4
5#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
6pub struct NodeId(pub u32);
7
8#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
9pub struct EdgeId(pub u32);
10
11#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
12pub struct SubgraphId(pub u32);
13
14pub type AttrMap = BTreeMap<String, String>;
15
16#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
17pub enum GraphKind {
18    Undirected,
19    Directed,
20}
21
22#[derive(Debug, Clone, PartialEq, Eq, Default, Serialize, Deserialize)]
23pub struct Port {
24    pub name: Option<String>,
25    pub compass: Option<String>,
26}
27
28#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
29pub struct NodeData {
30    pub id: NodeId,
31    pub name: String,
32    pub attrs: AttrMap,
33    /// Layout center in points (72 pt/inch).
34    pub pos: Point,
35    /// Width in inches (Graphviz convention).
36    pub width: f64,
37    /// Height in inches (Graphviz convention).
38    pub height: f64,
39    pub rank: i32,
40    pub order: usize,
41}
42
43#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
44pub struct EdgeData {
45    pub id: EdgeId,
46    pub tail: NodeId,
47    pub head: NodeId,
48    pub tail_port: Port,
49    pub head_port: Port,
50    pub attrs: AttrMap,
51    pub spline: Spline,
52    pub label_pos: Option<Point>,
53    /// The layout could not place the label (`ED_label(e)->set` is false):
54    /// `lp` is still printed, but renderers do not draw it.
55    #[serde(default)]
56    pub label_unplaced: bool,
57}
58
59/// The name test of `is_a_cluster` (lib/common/utils.c): `strncasecmp(name, "cluster", 7)`.
60///
61/// This compares bytes, as C does. Slicing the `str` at byte 7 instead panics when byte 7
62/// falls inside a multi-byte character (issue #165).
63pub fn has_cluster_prefix(name: &str) -> bool {
64    name.as_bytes()
65        .get(..7)
66        .is_some_and(|p| p.eq_ignore_ascii_case(b"cluster"))
67}
68
69#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
70pub struct SubgraphData {
71    pub id: SubgraphId,
72    pub name: String,
73    pub is_cluster: bool,
74    pub graph_attrs: AttrMap,
75    pub node_defaults: AttrMap,
76    pub edge_defaults: AttrMap,
77    pub nodes: Vec<NodeId>,
78    pub edges: Vec<EdgeId>,
79    pub subgraphs: Vec<SubgraphId>,
80    pub bb: BoundingBox,
81}
82
83/// Node attribute set by a layout on a node it replaced by a cluster node
84/// (fdp's `processClusterEdges`/`undoClusterEdges`, `IS_CLUST_NODE`):
85/// renderers neither draw it nor give it layout attributes.
86pub const CLUST_NODE_KEY: &str = "\u{1}clustnode";
87
88/// Subgraph attribute set by a layout that registers a cluster without making its label
89/// (`GD_label` stays NULL, e.g. patchwork's `mkClusters`): renderers neither draw nor size it.
90pub const NO_GRAPH_LABEL_KEY: &str = "\u{1}nolabel";
91
92/// Root graph attribute set by a layout that binds edge records without calling
93/// `common_init_edge` (patchwork's `patchwork_init_edge`): edges have no labels.
94pub const NO_EDGE_INIT_KEY: &str = "\u{1}noedgeinit";
95
96/// Node or edge attribute of a [`Graph::render_view`] object: its cgraph sequence number
97/// (`AGSEQ`), which the renderers print in object ids. Without it the sequence follows the
98/// object's index.
99pub const SEQ_KEY: &str = "\u{1}seq";
100
101/// Subgraph attribute set by a layout on a cluster it did not register in
102/// `GD_clust` (e.g. clusters nested below neato's top-level ones): it keeps its
103/// input `bb`, which C prints, but renderers do not draw it.
104pub const UNREGISTERED_CLUSTER_KEY: &str = "\u{1}unregclust";
105
106/// Subgraph attribute set by a layout on a cluster it registered in `GD_clust` but never
107/// positioned (fdp stopping on a layout error): renderers draw it with its empty box.
108pub const REGISTERED_CLUSTER_KEY: &str = "\u{1}regclust";
109
110/// Root graph or cluster attribute set by a layout whose `GD_clust` list is not the
111/// subgraph tree: the subgraph indices of the list, in order and with repeats,
112/// separated by spaces. dot's pack branch (`copyClusterInfo`) builds the root's
113/// list in component order and appends a cluster once per component that kept it;
114/// `emit_clusters` draws the list as it is.
115pub const CLUSTER_LIST_KEY: &str = "\u{1}clustlist";
116
117/// Edge attribute set by a layout whose head or tail label it could not place
118/// (`ED_head_label(e)->set` false: `h`, tail: `t`): `head_lp`/`tail_lp` are still
119/// printed, but renderers do not draw the label.
120pub const UNPLACED_PORT_LABELS_KEY: &str = "\u{1}unplacedportlbl";
121/// Edge attributes holding the layout's final tail/head port names
122/// (`ED_tail_port(e).name`, `ED_head_port(e).name`), which `\E` substitutes; empty when
123/// the layout dropped the name (dot's `sameport`).
124pub const TAIL_PORT_NAME_KEY: &str = "\u{1}tailportname";
125pub const HEAD_PORT_NAME_KEY: &str = "\u{1}headportname";
126/// One spelling for [`IGNORED_EDGE_KEY`] and the [`IGNORED_EDGE_INPUT_KEYS`] built on it.
127macro_rules! ignored_edge_key {
128    ($attr:literal) => {
129        concat!("\u{1}ignorededge", $attr)
130    };
131}
132/// Edge attribute set by a layout on an edge it routed although its type is `IGNORED`
133/// (dot's `orthoEdges` under `concentrate`, which keeps the first edge of each node pair
134/// whatever its type): renderers draw its spline (`emit_edge_graphics` has no type check),
135/// but `attach_attrs_and_arrows` gives it no `pos`, `lp`, `xlp`, `head_lp` or `tail_lp`
136/// (`lib/common/output.c`). The layout keeps the edge's input label positions under
137/// [`IGNORED_EDGE_INPUT_KEYS`], since it may overwrite them to draw the labels.
138pub const IGNORED_EDGE_KEY: &str = ignored_edge_key!("");
139/// `(attribute, key)`: where the layout keeps the input value of a label position attribute
140/// of an [`IGNORED_EDGE_KEY`] edge, for the renderer to put back.
141pub const IGNORED_EDGE_INPUT_KEYS: [(&str, &str); 3] = [
142    ("head_lp", ignored_edge_key!("head_lp")),
143    ("tail_lp", ignored_edge_key!("tail_lp")),
144    ("xlp", ignored_edge_key!("xlp")),
145];
146
147/// Node attribute set by a layout whose node has `ND_lw != ND_rw` (dot keeps the self-loop
148/// space in `ND_rw` when `dot_splines_` skips `resetRW`, or with `splines=curved` undoes
149/// it): `"lw,rw"` in points. Renderers split
150/// `width` with it instead of halving it (`Mcircle_hack` uses `ND_rw` alone).
151pub const NODE_LW_RW_KEY: &str = "\u{1}lwrw";
152
153/// Arena-backed Graph representation (Fixes GV-BUG-008 and GV-BUG-010).
154#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
155pub struct Graph {
156    pub name: String,
157    pub strict: bool,
158    pub kind: GraphKind,
159    pub graph_attrs: AttrMap,
160    pub node_defaults: AttrMap,
161    pub edge_defaults: AttrMap,
162    pub nodes: Vec<NodeData>,
163    pub node_lookup: BTreeMap<String, NodeId>,
164    pub edges: Vec<EdgeData>,
165    pub subgraphs: Vec<SubgraphData>,
166    pub bb: BoundingBox,
167    /// Attribute values that were written as HTML strings (`<...>`) in the source, stored with
168    /// their delimiters. A quoted `"<x>"` is a plain string and is not recorded here.
169    #[serde(default)]
170    pub html_strings: BTreeSet<String>,
171    /// cgraph's internal ids of anonymous subgraphs (subgraph index -> id); the root graph,
172    /// anonymous subgraphs and edges draw odd ids from one counter in creation order. C
173    /// prints an anonymous subgraph's name as `%<id>`.
174    #[serde(default)]
175    pub anon_subgraph_ids: BTreeMap<u32, u64>,
176    /// cgraph attribute dictionaries (`Agdatadict_t`) as built while parsing: index 0 is the
177    /// root graph, index `i + 1` subgraph `i`. Writers that reproduce `agwrite` use them to
178    /// tell local declarations from inherited values.
179    #[serde(default)]
180    pub dicts: Vec<AttrDicts>,
181    /// The graph as renderers that run before `undoClusterEdges` see it: fdp leaves its
182    /// cluster nodes (`__0:cluster`) and cloned cluster edges in the graph it lays out, and
183    /// only the output writers (dot, xdot, json, canon, plain) undo them. `-Tsvg` draws this
184    /// graph when it is set.
185    #[serde(default, skip_serializing_if = "Option::is_none")]
186    pub render_view: Option<Box<Graph>>,
187}
188
189/// One declared attribute (`Agsym_t`): its default value and whether a root attribute
190/// statement set it (`sym->print`).
191#[derive(Debug, Clone, PartialEq, Eq, Default, Serialize, Deserialize)]
192pub struct AttrSym {
193    pub defval: String,
194    pub print: bool,
195    /// `sym->id`: declaration order in the root dictionary (cgraph's ProtoGraph
196    /// `label` first). Only meaningful in the root's dictionaries.
197    #[serde(default)]
198    pub id: usize,
199}
200
201/// The local graph, node and edge dictionaries of one graph or subgraph.
202#[derive(Debug, Clone, PartialEq, Eq, Default, Serialize, Deserialize)]
203pub struct AttrDicts {
204    pub graph: BTreeMap<String, AttrSym>,
205    pub node: BTreeMap<String, AttrSym>,
206    pub edge: BTreeMap<String, AttrSym>,
207}
208
209impl Graph {
210    pub fn new(name: impl Into<String>, kind: GraphKind, strict: bool) -> Self {
211        Self {
212            name: name.into(),
213            strict,
214            kind,
215            graph_attrs: AttrMap::new(),
216            node_defaults: AttrMap::new(),
217            edge_defaults: AttrMap::new(),
218            nodes: Vec::new(),
219            node_lookup: BTreeMap::new(),
220            edges: Vec::new(),
221            subgraphs: Vec::new(),
222            bb: BoundingBox::default(),
223            html_strings: BTreeSet::new(),
224            anon_subgraph_ids: BTreeMap::new(),
225            dicts: Vec::new(),
226            render_view: None,
227        }
228    }
229
230    pub fn ensure_node(&mut self, name: &str) -> NodeId {
231        if let Some(&id) = self.node_lookup.get(name) {
232            return id;
233        }
234        let id = NodeId(self.nodes.len() as u32);
235        let mut attrs = self.node_defaults.clone();
236        attrs
237            .entry("label".to_string())
238            .or_insert_with(|| "\\N".to_string());
239        self.nodes.push(NodeData {
240            id,
241            name: name.to_string(),
242            attrs,
243            pos: Point::default(),
244            width: 0.75,
245            height: 0.5,
246            rank: 0,
247            order: id.0 as usize,
248        });
249        self.node_lookup.insert(name.to_string(), id);
250        id
251    }
252
253    pub fn add_edge(&mut self, tail: NodeId, head: NodeId, attrs: AttrMap) -> EdgeId {
254        if self.strict
255            && let Some(existing) = self.edges.iter_mut().find(|e| {
256                (e.tail == tail && e.head == head)
257                    || (self.kind == GraphKind::Undirected && e.tail == head && e.head == tail)
258            })
259        {
260            existing.attrs.extend(attrs);
261            return existing.id;
262        }
263        let id = EdgeId(self.edges.len() as u32);
264        let mut merged_attrs = self.edge_defaults.clone();
265        merged_attrs.extend(attrs);
266        self.edges.push(EdgeData {
267            id,
268            tail,
269            head,
270            tail_port: Port::default(),
271            head_port: Port::default(),
272            attrs: merged_attrs,
273            spline: Spline::default(),
274            label_pos: None,
275            label_unplaced: false,
276        });
277        id
278    }
279}
280
281#[cfg(test)]
282mod cluster_prefix_tests {
283    use super::has_cluster_prefix;
284
285    #[test]
286    fn compares_the_first_seven_bytes_case_insensitively() {
287        assert!(has_cluster_prefix("cluster"));
288        assert!(has_cluster_prefix("Cluster_a"));
289        assert!(has_cluster_prefix("CLUSTERé"));
290        assert!(!has_cluster_prefix("cluste"));
291        assert!(!has_cluster_prefix("aaaaaaé"));
292        assert!(!has_cluster_prefix("clusé_x"));
293        assert!(!has_cluster_prefix(""));
294    }
295}
graphviz_pure_core/graph.rs

graphviz_pure_core/
graph.rs
