1use serde::{Deserialize, Serialize};
2use std::collections::HashMap;
3use std::io::{self, Write};
4
5use crate::node::*;
6
7#[derive(Clone, Serialize, Deserialize)]
8pub enum GraphKind {
9 Digraph,
10 Subgraph,
11}
12
13pub type AdjList<'a> = HashMap<&'a str, Vec<&'a str>>;
14
15/// Graph represents a directed graph as a list of nodes and list of edges.
16#[derive(Serialize, Deserialize)]
17pub struct Graph {
18 /// Identifier for the graph
19 pub name: String,
20
21 /// The Vector containing the Nodes
22 pub nodes: Vec<Node>,
23
24 /// The Vector containing the Edges
25 pub edges: Vec<Edge>,
26}
27
28#[derive(Clone)]
29pub struct GraphvizSettings {
30 /// The attributes of the graph in graphviz.
31 pub graph_attrs: Option<String>,
32
33 /// The attributes of the nodes in graphviz.
34 pub node_attrs: Option<String>,
35
36 /// The attributes of the edges in graphviz.
37 pub edge_attrs: Option<String>,
38
39 /// Label of the graph
40 pub graph_label: Option<String>,
41}
42
43impl Default for GraphvizSettings {
44 fn default() -> GraphvizSettings {
45 GraphvizSettings {
46 graph_attrs: None,
47 node_attrs: None,
48 edge_attrs: None,
49 graph_label: None,
50 }
51 }
52}
53
54impl Graph {
55 pub fn new(name: String, nodes: Vec<Node>, edges: Vec<Edge>) -> Graph {
56 Graph { name, nodes, edges }
57 }
58
59 /// Returns the adjacency list representation of the graph.
60 /// Adjacency list can be used to easily find the childern of a given node.
61 /// If the a node does not have any childern, then the list correspoding to that node
62 /// will be empty.
63 pub fn adj_list(&self) -> AdjList<'_> {
64 let mut m: AdjList<'_> = HashMap::new();
65 for node in &self.nodes {
66 m.insert(&node.label, Vec::new());
67 }
68 for edge in &self.edges {
69 m.entry(&edge.from).or_insert_with(Vec::new).push(&edge.to);
70 }
71 m
72 }
73
74 /// Returns the reverse adjacency list representation of the graph.
75 /// Reverse adjacency list represents the adjacency list of a directed graph where
76 /// the edges have been reversed.
77 /// Reverse adjacency list can be used to easily find the parents of a given node.
78 /// If the a node does not have any childern, then the list correspoding to that node
79 /// will be empty.
80 pub fn rev_adj_list(&self) -> AdjList<'_> {
81 let mut m: AdjList<'_> = HashMap::new();
82 for node in &self.nodes {
83 m.insert(&node.label, Vec::new());
84 }
85 for edge in &self.edges {
86 m.entry(&edge.to).or_insert_with(Vec::new).push(&edge.from);
87 }
88 m
89 }
90
91 /// Returns the node with the given label, if found.
92 pub fn get_node_by_label(&self, label: &str) -> Option<&Node> {
93 self.nodes.iter().find(|node| node.label == *label)
94 }
95
96 /// Returns the dot representation of the given graph.
97 /// This can rendered using the graphviz program.
98 pub fn to_dot<W: Write>(
99 &self,
100 w: &mut W,
101 settings: &GraphvizSettings,
102 as_subgraph: bool,
103 ) -> io::Result<()> {
104 if as_subgraph {
105 write!(w, "subgraph cluster_{}", self.name)?;
106 } else {
107 write!(w, "digraph {}", self.name)?;
108 }
109
110 writeln!(w, " {{")?;
111
112 if let Some(graph_attrs) = &settings.graph_attrs {
113 writeln!(w, r#" graph [{}];"#, graph_attrs)?;
114 }
115 if let Some(node_attrs) = &settings.node_attrs {
116 writeln!(w, r#" node [{}];"#, node_attrs)?;
117 }
118 if let Some(edge_attrs) = &settings.edge_attrs {
119 writeln!(w, r#" edge [{}];"#, edge_attrs)?;
120 }
121 if let Some(label) = &settings.graph_label {
122 writeln!(w, r#" label=<{}>;"#, label)?;
123 }
124
125 for node in self.nodes.iter() {
126 write!(w, r#" {} [shape="none", label=<"#, node.label)?;
127 node.to_dot(w)?;
128 writeln!(w, ">];")?;
129 }
130
131 for edge in self.edges.iter() {
132 edge.to_dot(w)?;
133 }
134
135 writeln!(w, "}}")
136 }
137}
138
139#[cfg(test)]
140mod tests {
141 use crate::*;
142 fn get_test_graph() -> Graph {
143 let stmts: Vec<String> = vec!["hi".into(), "hell".into()];
144 let label1: String = "bb0__0_3".into();
145 let style: NodeStyle = Default::default();
146 let node1 = Node::new(stmts, label1.clone(), "0".into(), style.clone());
147
148 let stmts: Vec<String> = vec!["_1 = const 1_i32".into(), "_2 = const 2_i32".into()];
149 let label2: String = "bb0__1_3".into();
150 let node2 = Node::new(stmts, label2.clone(), "1".into(), style.clone());
151
152 Graph::new(
153 "Mir_0_3".into(),
154 vec![node1, node2],
155 vec![Edge::new(label1, label2, "return".into())],
156 )
157 }
158
159 #[test]
160 fn test_adj_list() {
161 let g = get_test_graph();
162 let adj_list = g.adj_list();
163 let expected: AdjList = [("bb0__0_3", vec!["bb0__1_3"]), (&"bb0__1_3", vec![])]
164 .iter()
165 .cloned()
166 .collect();
167 assert_eq!(adj_list, expected);
168 }
169
170 #[test]
171 fn test_json_ser() {
172 let g = get_test_graph();
173 let json = serde_json::to_string(&g).unwrap();
174 let expected_json: String = "\
175 {\
176 \"name\":\"Mir_0_3\",\
177 \"nodes\":[\
178 {\
179 \"stmts\":[\
180 \"hi\",\
181 \"hell\"\
182 ],\
183 \"label\":\"bb0__0_3\",\
184 \"title\":\"0\",\
185 \"style\":{\
186 \"title_bg\":null,\
187 \"last_stmt_sep\":false\
188 }\
189 },\
190 {\
191 \"stmts\":[\
192 \"_1 = const 1_i32\",\
193 \"_2 = const 2_i32\"\
194 ],\
195 \"label\":\"bb0__1_3\",\
196 \"title\":\"1\",\
197 \"style\":{\
198 \"title_bg\":null,\
199 \"last_stmt_sep\":false\
200 }\
201 }\
202 ],\
203 \"edges\":[\
204 {\
205 \"from\":\"bb0__0_3\",\
206 \"to\":\"bb0__1_3\",\
207 \"label\":\"return\"\
208 }\
209 ]\
210 }"
211 .into();
212 assert_eq!(json, expected_json)
213 }
214
215 #[test]
216 fn test_json_deser() {
217 let expected = get_test_graph();
218 let struct_json: String = "\
219 {\
220 \"name\":\"Mir_0_3\",\
221 \"nodes\":[\
222 {\
223 \"stmts\":[\
224 \"hi\",\
225 \"hell\"\
226 ],\
227 \"label\":\"bb0__0_3\",\
228 \"title\":\"0\",\
229 \"style\":{\
230 \"title_bg\":null,\
231 \"last_stmt_sep\":false\
232 }\
233 },\
234 {\
235 \"stmts\":[\
236 \"_1 = const 1_i32\",\
237 \"_2 = const 2_i32\"\
238 ],\
239 \"label\":\"bb0__1_3\",\
240 \"title\":\"1\",\
241 \"style\":{\
242 \"title_bg\":null,\
243 \"last_stmt_sep\":false\
244 }\
245 }\
246 ],\
247 \"edges\":[\
248 {\
249 \"from\":\"bb0__0_3\",\
250 \"to\":\"bb0__1_3\",\
251 \"label\":\"return\"\
252 }\
253 ]\
254 }"
255 .into();
256 let got: Graph = serde_json::from_str(&struct_json).unwrap();
257
258 assert_eq!(expected.nodes.len(), got.nodes.len());
259 assert_eq!(expected.edges.len(), got.edges.len());
260
261 for (n1, n2) in expected.nodes.iter().zip(got.nodes.iter()) {
262 assert_eq!(n1.stmts, n2.stmts);
263 assert_eq!(n1.label, n2.label);
264 assert_eq!(n1.title, n2.title);
265 }
266
267 for (e1, e2) in expected.edges.iter().zip(got.edges.iter()) {
268 assert_eq!(e1.from, e2.from);
269 assert_eq!(e1.to, e2.to);
270 assert_eq!(e1.label, e2.label);
271 }
272 }
273}
274