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