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 : 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 */
|
