]>
Commit | Line | Data |
---|---|---|
757bf1df | 1 | /* Template classes for directed graphs. |
7adcbafe | 2 | Copyright (C) 2019-2022 Free Software Foundation, Inc. |
757bf1df DM |
3 | Contributed by David Malcolm <dmalcolm@redhat.com>. |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 3, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "diagnostic.h" | |
25 | #include "graphviz.h" | |
26 | #include "digraph.h" | |
27 | #include "shortest-paths.h" | |
28 | #include "selftest.h" | |
29 | ||
30 | #if CHECKING_P | |
31 | ||
32 | namespace selftest { | |
33 | ||
34 | /* A family of digraph classes for writing selftests. */ | |
35 | ||
36 | struct test_node; | |
37 | struct test_edge; | |
38 | struct test_graph; | |
39 | struct test_dump_args_t {}; | |
40 | struct test_cluster; | |
41 | ||
42 | struct test_graph_traits | |
43 | { | |
44 | typedef test_node node_t; | |
45 | typedef test_edge edge_t; | |
46 | typedef test_graph graph_t; | |
47 | typedef test_dump_args_t dump_args_t; | |
48 | typedef test_cluster cluster_t; | |
49 | }; | |
50 | ||
51 | struct test_node : public dnode<test_graph_traits> | |
52 | { | |
53 | test_node (const char *name, int index) : m_name (name), m_index (index) {} | |
ff171cb1 | 54 | void dump_dot (graphviz_out *, const dump_args_t &) const override |
757bf1df DM |
55 | { |
56 | } | |
57 | ||
58 | const char *m_name; | |
59 | int m_index; | |
60 | }; | |
61 | ||
62 | struct test_edge : public dedge<test_graph_traits> | |
63 | { | |
64 | test_edge (node_t *src, node_t *dest) | |
26d949c8 | 65 | : dedge<test_graph_traits> (src, dest) |
757bf1df DM |
66 | {} |
67 | ||
ff171cb1 | 68 | void dump_dot (graphviz_out *gv, const dump_args_t &) const override |
757bf1df | 69 | { |
ca23341b | 70 | gv->println ("%s %s %s%c", m_src->m_name, "->", m_dest->m_name, ';'); |
757bf1df DM |
71 | } |
72 | }; | |
73 | ||
74 | struct test_graph : public digraph<test_graph_traits> | |
75 | { | |
76 | test_node *add_test_node (const char *name) | |
77 | { | |
78 | test_node *result = new test_node (name, m_nodes.length ()); | |
79 | add_node (result); | |
80 | return result; | |
81 | } | |
82 | ||
83 | test_edge *add_test_edge (test_node *src, test_node *dst) | |
84 | { | |
85 | test_edge *result = new test_edge (src, dst); | |
86 | add_edge (result); | |
87 | return result; | |
88 | } | |
89 | }; | |
90 | ||
91 | struct test_cluster : public cluster<test_graph_traits> | |
92 | { | |
93 | }; | |
94 | ||
95 | struct test_path | |
96 | { | |
97 | auto_vec<const test_edge *> m_edges; | |
98 | }; | |
99 | ||
100 | /* Smoketest of digraph dumping. */ | |
101 | ||
102 | static void | |
103 | test_dump_to_dot () | |
104 | { | |
105 | test_graph g; | |
106 | test_node *a = g.add_test_node ("a"); | |
107 | test_node *b = g.add_test_node ("b"); | |
108 | g.add_test_edge (a, b); | |
109 | ||
110 | pretty_printer pp; | |
111 | pp.buffer->stream = NULL; | |
112 | test_dump_args_t dump_args; | |
113 | g.dump_dot_to_pp (&pp, NULL, dump_args); | |
114 | ||
115 | ASSERT_STR_CONTAINS (pp_formatted_text (&pp), | |
116 | "a -> b;\n"); | |
117 | } | |
118 | ||
119 | /* Test shortest paths from A in this digraph, | |
120 | where edges run top-to-bottom if not otherwise labeled: | |
121 | ||
122 | A | |
123 | / \ | |
124 | B C-->D | |
125 | | | | |
126 | E | | |
127 | \ / | |
128 | F. */ | |
129 | ||
130 | static void | |
131 | test_shortest_paths () | |
132 | { | |
133 | test_graph g; | |
134 | test_node *a = g.add_test_node ("a"); | |
135 | test_node *b = g.add_test_node ("b"); | |
136 | test_node *c = g.add_test_node ("d"); | |
137 | test_node *d = g.add_test_node ("d"); | |
138 | test_node *e = g.add_test_node ("e"); | |
139 | test_node *f = g.add_test_node ("f"); | |
140 | ||
141 | test_edge *ab = g.add_test_edge (a, b); | |
142 | test_edge *ac = g.add_test_edge (a, c); | |
143 | test_edge *cd = g.add_test_edge (c, d); | |
144 | test_edge *be = g.add_test_edge (b, e); | |
3f958348 | 145 | test_edge *ef = g.add_test_edge (e, f); |
757bf1df DM |
146 | test_edge *cf = g.add_test_edge (c, f); |
147 | ||
3f958348 DM |
148 | /* Use "A" as the origin; all nodes should be reachable. */ |
149 | { | |
5e33e5b0 DM |
150 | shortest_paths<test_graph_traits, test_path> sp (g, a, |
151 | SPS_FROM_GIVEN_ORIGIN); | |
3f958348 DM |
152 | |
153 | test_path path_to_a = sp.get_shortest_path (a); | |
154 | ASSERT_EQ (path_to_a.m_edges.length (), 0); /* Trivial path. */ | |
155 | ||
156 | test_path path_to_b = sp.get_shortest_path (b); | |
157 | ASSERT_EQ (path_to_b.m_edges.length (), 1); | |
158 | ASSERT_EQ (path_to_b.m_edges[0], ab); | |
159 | ||
160 | test_path path_to_c = sp.get_shortest_path (c); | |
161 | ASSERT_EQ (path_to_c.m_edges.length (), 1); | |
162 | ASSERT_EQ (path_to_c.m_edges[0], ac); | |
163 | ||
164 | test_path path_to_d = sp.get_shortest_path (d); | |
165 | ASSERT_EQ (path_to_d.m_edges.length (), 2); | |
166 | ASSERT_EQ (path_to_d.m_edges[0], ac); | |
167 | ASSERT_EQ (path_to_d.m_edges[1], cd); | |
168 | ||
169 | test_path path_to_e = sp.get_shortest_path (e); | |
170 | ASSERT_EQ (path_to_e.m_edges.length (), 2); | |
171 | ASSERT_EQ (path_to_e.m_edges[0], ab); | |
172 | ASSERT_EQ (path_to_e.m_edges[1], be); | |
173 | ||
174 | test_path path_to_f = sp.get_shortest_path (f); | |
175 | ASSERT_EQ (path_to_f.m_edges.length (), 2); | |
176 | ASSERT_EQ (path_to_f.m_edges[0], ac); | |
177 | ASSERT_EQ (path_to_f.m_edges[1], cf); | |
178 | } | |
179 | ||
180 | /* Verify that we gracefully handle an origin from which some nodes | |
181 | aren't reachable. */ | |
182 | ||
183 | /* Use "B" as the origin, so only E and F are reachable. */ | |
184 | { | |
5e33e5b0 DM |
185 | shortest_paths<test_graph_traits, test_path> sp (g, b, |
186 | SPS_FROM_GIVEN_ORIGIN); | |
757bf1df | 187 | |
3f958348 DM |
188 | test_path path_to_a = sp.get_shortest_path (a); |
189 | ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */ | |
757bf1df | 190 | |
3f958348 DM |
191 | test_path path_to_b = sp.get_shortest_path (b); |
192 | ASSERT_EQ (path_to_b.m_edges.length (), 0); /* Trivial path. */ | |
757bf1df | 193 | |
3f958348 DM |
194 | test_path path_to_c = sp.get_shortest_path (c); |
195 | ASSERT_EQ (path_to_c.m_edges.length (), 0); /* No path. */ | |
757bf1df | 196 | |
3f958348 DM |
197 | test_path path_to_d = sp.get_shortest_path (d); |
198 | ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */ | |
757bf1df | 199 | |
3f958348 DM |
200 | test_path path_to_e = sp.get_shortest_path (e); |
201 | ASSERT_EQ (path_to_e.m_edges.length (), 1); | |
202 | ASSERT_EQ (path_to_e.m_edges[0], be); | |
757bf1df | 203 | |
3f958348 DM |
204 | test_path path_to_f = sp.get_shortest_path (f); |
205 | ASSERT_EQ (path_to_f.m_edges.length (), 2); | |
206 | ASSERT_EQ (path_to_f.m_edges[0], be); | |
207 | ASSERT_EQ (path_to_f.m_edges[1], ef); | |
208 | } | |
209 | ||
210 | /* Use "C" as the origin, so only D and F are reachable. */ | |
211 | { | |
5e33e5b0 DM |
212 | shortest_paths<test_graph_traits, test_path> sp (g, c, |
213 | SPS_FROM_GIVEN_ORIGIN); | |
3f958348 DM |
214 | |
215 | test_path path_to_a = sp.get_shortest_path (a); | |
216 | ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */ | |
217 | ||
218 | test_path path_to_b = sp.get_shortest_path (b); | |
219 | ASSERT_EQ (path_to_b.m_edges.length (), 0); /* No path. */ | |
220 | ||
221 | test_path path_to_c = sp.get_shortest_path (c); | |
222 | ASSERT_EQ (path_to_c.m_edges.length (), 0); /* Trivial path. */ | |
223 | ||
224 | test_path path_to_d = sp.get_shortest_path (d); | |
225 | ASSERT_EQ (path_to_d.m_edges.length (), 1); | |
226 | ASSERT_EQ (path_to_d.m_edges[0], cd); | |
227 | ||
228 | test_path path_to_e = sp.get_shortest_path (e); | |
229 | ASSERT_EQ (path_to_e.m_edges.length (), 0); /* No path. */ | |
230 | ||
231 | test_path path_to_f = sp.get_shortest_path (f); | |
232 | ASSERT_EQ (path_to_f.m_edges.length (), 1); | |
233 | ASSERT_EQ (path_to_f.m_edges[0], cf); | |
234 | } | |
5e33e5b0 DM |
235 | |
236 | /* Test of SPS_TO_GIVEN_TARGET. Use "F" as the target. */ | |
237 | { | |
238 | shortest_paths<test_graph_traits, test_path> sp (g, f, | |
239 | SPS_TO_GIVEN_TARGET); | |
240 | ||
241 | test_path path_to_a = sp.get_shortest_path (a); | |
242 | ASSERT_EQ (path_to_a.m_edges.length (), 2); | |
243 | ASSERT_EQ (path_to_a.m_edges[0], ac); | |
244 | ASSERT_EQ (path_to_a.m_edges[1], cf); | |
245 | ||
246 | test_path path_to_b = sp.get_shortest_path (b); | |
247 | ASSERT_EQ (path_to_b.m_edges.length (), 2); | |
248 | ASSERT_EQ (path_to_b.m_edges[0], be); | |
249 | ASSERT_EQ (path_to_b.m_edges[1], ef); | |
250 | ||
251 | test_path path_to_c = sp.get_shortest_path (c); | |
252 | ASSERT_EQ (path_to_c.m_edges.length (), 1); | |
253 | ASSERT_EQ (path_to_c.m_edges[0], cf); | |
254 | ||
255 | test_path path_to_d = sp.get_shortest_path (d); | |
256 | ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */ | |
257 | ||
258 | test_path path_to_e = sp.get_shortest_path (e); | |
259 | ASSERT_EQ (path_to_e.m_edges.length (), 1); | |
260 | ASSERT_EQ (path_to_e.m_edges[0], ef); | |
261 | ||
262 | test_path path_to_f = sp.get_shortest_path (f); | |
263 | ASSERT_EQ (path_to_f.m_edges.length (), 0); | |
264 | } | |
757bf1df DM |
265 | } |
266 | ||
267 | /* Run all of the selftests within this file. */ | |
268 | ||
269 | void | |
270 | digraph_cc_tests () | |
271 | { | |
272 | test_dump_to_dot (); | |
273 | test_shortest_paths (); | |
274 | } | |
275 | ||
276 | } // namespace selftest | |
277 | ||
278 | #endif /* #if CHECKING_P */ |