Branch data Line data Source code
1 : : /* Template classes for directed graphs.
2 : : Copyright (C) 2019-2024 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 : : #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 : 32 : test_node (const char *name, int index) : m_name (name), m_index (index) {}
54 : 8 : void dump_dot (graphviz_out *, const dump_args_t &) const override
55 : : {
56 : 8 : }
57 : :
58 : : const char *m_name;
59 : : int m_index;
60 : : };
61 : :
62 : : struct test_edge : public dedge<test_graph_traits>
63 : : {
64 : 28 : test_edge (node_t *src, node_t *dest)
65 : 28 : : dedge<test_graph_traits> (src, dest)
66 : : {}
67 : :
68 : 4 : void dump_dot (graphviz_out *gv, const dump_args_t &) const override
69 : : {
70 : 4 : gv->println ("%s %s %s%c", m_src->m_name, "->", m_dest->m_name, ';');
71 : 4 : }
72 : : };
73 : :
74 : 24 : struct test_graph : public digraph<test_graph_traits>
75 : : {
76 : 32 : test_node *add_test_node (const char *name)
77 : : {
78 : 56 : test_node *result = new test_node (name, m_nodes.length ());
79 : 32 : add_node (result);
80 : 32 : return result;
81 : : }
82 : :
83 : 28 : test_edge *add_test_edge (test_node *src, test_node *dst)
84 : : {
85 : 28 : test_edge *result = new test_edge (src, dst);
86 : 28 : add_edge (result);
87 : 28 : return result;
88 : : }
89 : : };
90 : :
91 : : struct test_cluster : public cluster<test_graph_traits>
92 : : {
93 : : };
94 : :
95 : 96 : struct test_path
96 : : {
97 : : auto_vec<const test_edge *> m_edges;
98 : : };
99 : :
100 : : /* Smoketest of digraph dumping. */
101 : :
102 : : static void
103 : 4 : test_dump_to_dot ()
104 : : {
105 : 4 : test_graph g;
106 : 4 : test_node *a = g.add_test_node ("a");
107 : 4 : test_node *b = g.add_test_node ("b");
108 : 4 : g.add_test_edge (a, b);
109 : :
110 : 4 : pretty_printer pp;
111 : 4 : pp.set_output_stream (nullptr);
112 : 4 : test_dump_args_t dump_args;
113 : 4 : g.dump_dot_to_pp (&pp, NULL, dump_args);
114 : :
115 : 4 : ASSERT_STR_CONTAINS (pp_formatted_text (&pp),
116 : : "a -> b;\n");
117 : 4 : }
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 : 4 : test_shortest_paths ()
132 : : {
133 : 4 : test_graph g;
134 : 4 : test_node *a = g.add_test_node ("a");
135 : 4 : test_node *b = g.add_test_node ("b");
136 : 4 : test_node *c = g.add_test_node ("d");
137 : 4 : test_node *d = g.add_test_node ("d");
138 : 4 : test_node *e = g.add_test_node ("e");
139 : 4 : test_node *f = g.add_test_node ("f");
140 : :
141 : 4 : test_edge *ab = g.add_test_edge (a, b);
142 : 4 : test_edge *ac = g.add_test_edge (a, c);
143 : 4 : test_edge *cd = g.add_test_edge (c, d);
144 : 4 : test_edge *be = g.add_test_edge (b, e);
145 : 4 : test_edge *ef = g.add_test_edge (e, f);
146 : 4 : test_edge *cf = g.add_test_edge (c, f);
147 : :
148 : : /* Use "A" as the origin; all nodes should be reachable. */
149 : 4 : {
150 : 4 : shortest_paths<test_graph_traits, test_path> sp (g, a,
151 : 4 : SPS_FROM_GIVEN_ORIGIN);
152 : :
153 : 4 : test_path path_to_a = sp.get_shortest_path (a);
154 : 4 : ASSERT_EQ (path_to_a.m_edges.length (), 0); /* Trivial path. */
155 : :
156 : 4 : test_path path_to_b = sp.get_shortest_path (b);
157 : 4 : ASSERT_EQ (path_to_b.m_edges.length (), 1);
158 : 4 : ASSERT_EQ (path_to_b.m_edges[0], ab);
159 : :
160 : 4 : test_path path_to_c = sp.get_shortest_path (c);
161 : 4 : ASSERT_EQ (path_to_c.m_edges.length (), 1);
162 : 4 : ASSERT_EQ (path_to_c.m_edges[0], ac);
163 : :
164 : 4 : test_path path_to_d = sp.get_shortest_path (d);
165 : 4 : ASSERT_EQ (path_to_d.m_edges.length (), 2);
166 : 4 : ASSERT_EQ (path_to_d.m_edges[0], ac);
167 : 4 : ASSERT_EQ (path_to_d.m_edges[1], cd);
168 : :
169 : 4 : test_path path_to_e = sp.get_shortest_path (e);
170 : 4 : ASSERT_EQ (path_to_e.m_edges.length (), 2);
171 : 4 : ASSERT_EQ (path_to_e.m_edges[0], ab);
172 : 4 : ASSERT_EQ (path_to_e.m_edges[1], be);
173 : :
174 : 4 : test_path path_to_f = sp.get_shortest_path (f);
175 : 4 : ASSERT_EQ (path_to_f.m_edges.length (), 2);
176 : 4 : ASSERT_EQ (path_to_f.m_edges[0], ac);
177 : 4 : ASSERT_EQ (path_to_f.m_edges[1], cf);
178 : 4 : }
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 : 4 : {
185 : 4 : shortest_paths<test_graph_traits, test_path> sp (g, b,
186 : 4 : SPS_FROM_GIVEN_ORIGIN);
187 : :
188 : 4 : test_path path_to_a = sp.get_shortest_path (a);
189 : 4 : ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */
190 : :
191 : 4 : test_path path_to_b = sp.get_shortest_path (b);
192 : 4 : ASSERT_EQ (path_to_b.m_edges.length (), 0); /* Trivial path. */
193 : :
194 : 4 : test_path path_to_c = sp.get_shortest_path (c);
195 : 4 : ASSERT_EQ (path_to_c.m_edges.length (), 0); /* No path. */
196 : :
197 : 4 : test_path path_to_d = sp.get_shortest_path (d);
198 : 4 : ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */
199 : :
200 : 4 : test_path path_to_e = sp.get_shortest_path (e);
201 : 4 : ASSERT_EQ (path_to_e.m_edges.length (), 1);
202 : 4 : ASSERT_EQ (path_to_e.m_edges[0], be);
203 : :
204 : 4 : test_path path_to_f = sp.get_shortest_path (f);
205 : 4 : ASSERT_EQ (path_to_f.m_edges.length (), 2);
206 : 4 : ASSERT_EQ (path_to_f.m_edges[0], be);
207 : 4 : ASSERT_EQ (path_to_f.m_edges[1], ef);
208 : 4 : }
209 : :
210 : : /* Use "C" as the origin, so only D and F are reachable. */
211 : 4 : {
212 : 4 : shortest_paths<test_graph_traits, test_path> sp (g, c,
213 : 4 : SPS_FROM_GIVEN_ORIGIN);
214 : :
215 : 4 : test_path path_to_a = sp.get_shortest_path (a);
216 : 4 : ASSERT_EQ (path_to_a.m_edges.length (), 0); /* No path. */
217 : :
218 : 4 : test_path path_to_b = sp.get_shortest_path (b);
219 : 4 : ASSERT_EQ (path_to_b.m_edges.length (), 0); /* No path. */
220 : :
221 : 4 : test_path path_to_c = sp.get_shortest_path (c);
222 : 4 : ASSERT_EQ (path_to_c.m_edges.length (), 0); /* Trivial path. */
223 : :
224 : 4 : test_path path_to_d = sp.get_shortest_path (d);
225 : 4 : ASSERT_EQ (path_to_d.m_edges.length (), 1);
226 : 4 : ASSERT_EQ (path_to_d.m_edges[0], cd);
227 : :
228 : 4 : test_path path_to_e = sp.get_shortest_path (e);
229 : 4 : ASSERT_EQ (path_to_e.m_edges.length (), 0); /* No path. */
230 : :
231 : 4 : test_path path_to_f = sp.get_shortest_path (f);
232 : 4 : ASSERT_EQ (path_to_f.m_edges.length (), 1);
233 : 4 : ASSERT_EQ (path_to_f.m_edges[0], cf);
234 : 4 : }
235 : :
236 : : /* Test of SPS_TO_GIVEN_TARGET. Use "F" as the target. */
237 : 4 : {
238 : 4 : shortest_paths<test_graph_traits, test_path> sp (g, f,
239 : 4 : SPS_TO_GIVEN_TARGET);
240 : :
241 : 4 : test_path path_to_a = sp.get_shortest_path (a);
242 : 4 : ASSERT_EQ (path_to_a.m_edges.length (), 2);
243 : 4 : ASSERT_EQ (path_to_a.m_edges[0], ac);
244 : 4 : ASSERT_EQ (path_to_a.m_edges[1], cf);
245 : :
246 : 4 : test_path path_to_b = sp.get_shortest_path (b);
247 : 4 : ASSERT_EQ (path_to_b.m_edges.length (), 2);
248 : 4 : ASSERT_EQ (path_to_b.m_edges[0], be);
249 : 4 : ASSERT_EQ (path_to_b.m_edges[1], ef);
250 : :
251 : 4 : test_path path_to_c = sp.get_shortest_path (c);
252 : 4 : ASSERT_EQ (path_to_c.m_edges.length (), 1);
253 : 4 : ASSERT_EQ (path_to_c.m_edges[0], cf);
254 : :
255 : 4 : test_path path_to_d = sp.get_shortest_path (d);
256 : 4 : ASSERT_EQ (path_to_d.m_edges.length (), 0); /* No path. */
257 : :
258 : 4 : test_path path_to_e = sp.get_shortest_path (e);
259 : 4 : ASSERT_EQ (path_to_e.m_edges.length (), 1);
260 : 4 : ASSERT_EQ (path_to_e.m_edges[0], ef);
261 : :
262 : 4 : test_path path_to_f = sp.get_shortest_path (f);
263 : 4 : ASSERT_EQ (path_to_f.m_edges.length (), 0);
264 : 8 : }
265 : 4 : }
266 : :
267 : : /* Run all of the selftests within this file. */
268 : :
269 : : void
270 : 4 : digraph_cc_tests ()
271 : : {
272 : 4 : test_dump_to_dot ();
273 : 4 : test_shortest_paths ();
274 : 4 : }
275 : :
276 : : } // namespace selftest
277 : :
278 : : #endif /* #if CHECKING_P */
|
