Line data Source code
1 : /* Template classes for directed graphs.
2 : Copyright (C) 2019-2026 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 76 : void append_edge (const test_edge *edge) { m_edges.safe_push (edge); }
100 72 : void reverse () { m_edges.reverse (); }
101 :
102 : auto_vec<const test_edge *> m_edges;
103 : };
104 :
105 : /* Smoketest of digraph dumping. */
106 :
107 : static void
108 4 : test_dump_to_dot ()
109 : {
110 4 : test_graph g;
111 4 : test_node *a = g.add_test_node ("a");
112 4 : test_node *b = g.add_test_node ("b");
113 4 : g.add_test_edge (a, b);
114 :
115 4 : pretty_printer pp;
116 4 : pp.set_output_stream (nullptr);
117 4 : test_dump_args_t dump_args;
118 4 : g.dump_dot_to_pp (&pp, NULL, dump_args);
119 :
120 4 : ASSERT_STR_CONTAINS (pp_formatted_text (&pp),
121 : "a -> b;\n");
122 4 : }
123 :
124 : /* Test shortest paths from A in this digraph,
125 : where edges run top-to-bottom if not otherwise labeled:
126 :
127 : A
128 : / \
129 : B C-->D
130 : | |
131 : E |
132 : \ /
133 : F. */
134 :
135 : static void
136 4 : test_shortest_paths ()
137 : {
138 4 : test_graph g;
139 4 : test_node *a = g.add_test_node ("a");
140 4 : test_node *b = g.add_test_node ("b");
141 4 : test_node *c = g.add_test_node ("d");
142 4 : test_node *d = g.add_test_node ("d");
143 4 : test_node *e = g.add_test_node ("e");
144 4 : test_node *f = g.add_test_node ("f");
145 :
146 4 : test_edge *ab = g.add_test_edge (a, b);
147 4 : test_edge *ac = g.add_test_edge (a, c);
148 4 : test_edge *cd = g.add_test_edge (c, d);
149 4 : test_edge *be = g.add_test_edge (b, e);
150 4 : test_edge *ef = g.add_test_edge (e, f);
151 4 : test_edge *cf = g.add_test_edge (c, f);
152 :
153 : /* Use "A" as the origin; all nodes should be reachable. */
154 4 : {
155 4 : shortest_paths<test_graph_traits, test_path> sp (g, a,
156 4 : SPS_FROM_GIVEN_ORIGIN);
157 :
158 4 : test_path path_to_a = sp.get_shortest_path (a);
159 4 : ASSERT_EQ (path_to_a.m_edges.length (), 0); /* Trivial path. */
160 :
161 4 : test_path path_to_b = sp.get_shortest_path (b);
162 4 : ASSERT_EQ (path_to_b.m_edges.length (), 1);
163 4 : ASSERT_EQ (path_to_b.m_edges[0], ab);
164 :
165 4 : test_path path_to_c = sp.get_shortest_path (c);
166 4 : ASSERT_EQ (path_to_c.m_edges.length (), 1);
167 4 : ASSERT_EQ (path_to_c.m_edges[0], ac);
168 :
169 4 : test_path path_to_d = sp.get_shortest_path (d);
170 4 : ASSERT_EQ (path_to_d.m_edges.length (), 2);
171 4 : ASSERT_EQ (path_to_d.m_edges[0], ac);
172 4 : ASSERT_EQ (path_to_d.m_edges[1], cd);
173 :
174 4 : test_path path_to_e = sp.get_shortest_path (e);
175 4 : ASSERT_EQ (path_to_e.m_edges.length (), 2);
176 4 : ASSERT_EQ (path_to_e.m_edges[0], ab);
177 4 : ASSERT_EQ (path_to_e.m_edges[1], be);
178 :
179 4 : test_path path_to_f = sp.get_shortest_path (f);
180 4 : ASSERT_EQ (path_to_f.m_edges.length (), 2);
181 4 : ASSERT_EQ (path_to_f.m_edges[0], ac);
182 4 : ASSERT_EQ (path_to_f.m_edges[1], cf);
183 4 : }
184 :
185 : /* Verify that we gracefully handle an origin from which some nodes
186 : aren't reachable. */
187 :
188 : /* Use "B" as the origin, so only E and F are reachable. */
189 4 : {
190 4 : shortest_paths<test_graph_traits, test_path> sp (g, b,
191 4 : SPS_FROM_GIVEN_ORIGIN);
192 :
193 4 : test_path path_to_a = sp.get_shortest_path (a);
194 4 : ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */
195 :
196 4 : test_path path_to_b = sp.get_shortest_path (b);
197 4 : ASSERT_EQ (path_to_b.m_edges.length (), 0); /* Trivial path. */
198 :
199 4 : test_path path_to_c = sp.get_shortest_path (c);
200 4 : ASSERT_EQ (path_to_c.m_edges.length (), 0); /* No path. */
201 :
202 4 : test_path path_to_d = sp.get_shortest_path (d);
203 4 : ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */
204 :
205 4 : test_path path_to_e = sp.get_shortest_path (e);
206 4 : ASSERT_EQ (path_to_e.m_edges.length (), 1);
207 4 : ASSERT_EQ (path_to_e.m_edges[0], be);
208 :
209 4 : test_path path_to_f = sp.get_shortest_path (f);
210 4 : ASSERT_EQ (path_to_f.m_edges.length (), 2);
211 4 : ASSERT_EQ (path_to_f.m_edges[0], be);
212 4 : ASSERT_EQ (path_to_f.m_edges[1], ef);
213 4 : }
214 :
215 : /* Use "C" as the origin, so only D and F are reachable. */
216 4 : {
217 4 : shortest_paths<test_graph_traits, test_path> sp (g, c,
218 4 : SPS_FROM_GIVEN_ORIGIN);
219 :
220 4 : test_path path_to_a = sp.get_shortest_path (a);
221 4 : ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */
222 :
223 4 : test_path path_to_b = sp.get_shortest_path (b);
224 4 : ASSERT_EQ (path_to_b.m_edges.length (), 0); /* No path. */
225 :
226 4 : test_path path_to_c = sp.get_shortest_path (c);
227 4 : ASSERT_EQ (path_to_c.m_edges.length (), 0); /* Trivial path. */
228 :
229 4 : test_path path_to_d = sp.get_shortest_path (d);
230 4 : ASSERT_EQ (path_to_d.m_edges.length (), 1);
231 4 : ASSERT_EQ (path_to_d.m_edges[0], cd);
232 :
233 4 : test_path path_to_e = sp.get_shortest_path (e);
234 4 : ASSERT_EQ (path_to_e.m_edges.length (), 0); /* No path. */
235 :
236 4 : test_path path_to_f = sp.get_shortest_path (f);
237 4 : ASSERT_EQ (path_to_f.m_edges.length (), 1);
238 4 : ASSERT_EQ (path_to_f.m_edges[0], cf);
239 4 : }
240 :
241 : /* Test of SPS_TO_GIVEN_TARGET. Use "F" as the target. */
242 4 : {
243 4 : shortest_paths<test_graph_traits, test_path> sp (g, f,
244 4 : SPS_TO_GIVEN_TARGET);
245 :
246 4 : test_path path_to_a = sp.get_shortest_path (a);
247 4 : ASSERT_EQ (path_to_a.m_edges.length (), 2);
248 4 : ASSERT_EQ (path_to_a.m_edges[0], ac);
249 4 : ASSERT_EQ (path_to_a.m_edges[1], cf);
250 :
251 4 : test_path path_to_b = sp.get_shortest_path (b);
252 4 : ASSERT_EQ (path_to_b.m_edges.length (), 2);
253 4 : ASSERT_EQ (path_to_b.m_edges[0], be);
254 4 : ASSERT_EQ (path_to_b.m_edges[1], ef);
255 :
256 4 : test_path path_to_c = sp.get_shortest_path (c);
257 4 : ASSERT_EQ (path_to_c.m_edges.length (), 1);
258 4 : ASSERT_EQ (path_to_c.m_edges[0], cf);
259 :
260 4 : test_path path_to_d = sp.get_shortest_path (d);
261 4 : ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */
262 :
263 4 : test_path path_to_e = sp.get_shortest_path (e);
264 4 : ASSERT_EQ (path_to_e.m_edges.length (), 1);
265 4 : ASSERT_EQ (path_to_e.m_edges[0], ef);
266 :
267 4 : test_path path_to_f = sp.get_shortest_path (f);
268 4 : ASSERT_EQ (path_to_f.m_edges.length (), 0);
269 8 : }
270 4 : }
271 :
272 : /* Run all of the selftests within this file. */
273 :
274 : void
275 4 : digraph_cc_tests ()
276 : {
277 4 : test_dump_to_dot ();
278 4 : test_shortest_paths ();
279 4 : }
280 :
281 : } // namespace selftest
282 :
283 : #endif /* #if CHECKING_P */
|
