1 /* Template classes for directed graphs.
2 Copyright (C) 2019-2021 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
24 #include "diagnostic.h"
27 #include "shortest-paths.h"
34 /* A family of digraph classes for writing selftests. */
39 struct test_dump_args_t
{};
42 struct test_graph_traits
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
;
51 struct test_node
: public dnode
<test_graph_traits
>
53 test_node (const char *name
, int index
) : m_name (name
), m_index (index
) {}
54 void dump_dot (graphviz_out
*, const dump_args_t
&) const OVERRIDE
62 struct test_edge
: public dedge
<test_graph_traits
>
64 test_edge (node_t
*src
, node_t
*dest
)
65 : dedge
<test_graph_traits
> (src
, dest
)
68 void dump_dot (graphviz_out
*gv
, const dump_args_t
&) const OVERRIDE
70 gv
->println ("%s %s %s%c", m_src
->m_name
, "->", m_dest
->m_name
, ';');
74 struct test_graph
: public digraph
<test_graph_traits
>
76 test_node
*add_test_node (const char *name
)
78 test_node
*result
= new test_node (name
, m_nodes
.length ());
83 test_edge
*add_test_edge (test_node
*src
, test_node
*dst
)
85 test_edge
*result
= new test_edge (src
, dst
);
91 struct test_cluster
: public cluster
<test_graph_traits
>
97 auto_vec
<const test_edge
*> m_edges
;
100 /* Smoketest of digraph dumping. */
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
);
111 pp
.buffer
->stream
= NULL
;
112 test_dump_args_t dump_args
;
113 g
.dump_dot_to_pp (&pp
, NULL
, dump_args
);
115 ASSERT_STR_CONTAINS (pp_formatted_text (&pp
),
119 /* Test shortest paths from A in this digraph,
120 where edges run top-to-bottom if not otherwise labeled:
131 test_shortest_paths ()
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");
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
);
145 test_edge
*ef
= g
.add_test_edge (e
, f
);
146 test_edge
*cf
= g
.add_test_edge (c
, f
);
148 /* Use "A" as the origin; all nodes should be reachable. */
150 shortest_paths
<test_graph_traits
, test_path
> sp (g
, a
);
152 test_path path_to_a
= sp
.get_shortest_path (a
);
153 ASSERT_EQ (path_to_a
.m_edges
.length (), 0); /* Trivial path. */
155 test_path path_to_b
= sp
.get_shortest_path (b
);
156 ASSERT_EQ (path_to_b
.m_edges
.length (), 1);
157 ASSERT_EQ (path_to_b
.m_edges
[0], ab
);
159 test_path path_to_c
= sp
.get_shortest_path (c
);
160 ASSERT_EQ (path_to_c
.m_edges
.length (), 1);
161 ASSERT_EQ (path_to_c
.m_edges
[0], ac
);
163 test_path path_to_d
= sp
.get_shortest_path (d
);
164 ASSERT_EQ (path_to_d
.m_edges
.length (), 2);
165 ASSERT_EQ (path_to_d
.m_edges
[0], ac
);
166 ASSERT_EQ (path_to_d
.m_edges
[1], cd
);
168 test_path path_to_e
= sp
.get_shortest_path (e
);
169 ASSERT_EQ (path_to_e
.m_edges
.length (), 2);
170 ASSERT_EQ (path_to_e
.m_edges
[0], ab
);
171 ASSERT_EQ (path_to_e
.m_edges
[1], be
);
173 test_path path_to_f
= sp
.get_shortest_path (f
);
174 ASSERT_EQ (path_to_f
.m_edges
.length (), 2);
175 ASSERT_EQ (path_to_f
.m_edges
[0], ac
);
176 ASSERT_EQ (path_to_f
.m_edges
[1], cf
);
179 /* Verify that we gracefully handle an origin from which some nodes
182 /* Use "B" as the origin, so only E and F are reachable. */
184 shortest_paths
<test_graph_traits
, test_path
> sp (g
, b
);
186 test_path path_to_a
= sp
.get_shortest_path (a
);
187 ASSERT_EQ (path_to_a
.m_edges
.length (), 0); /* No path. */
189 test_path path_to_b
= sp
.get_shortest_path (b
);
190 ASSERT_EQ (path_to_b
.m_edges
.length (), 0); /* Trivial path. */
192 test_path path_to_c
= sp
.get_shortest_path (c
);
193 ASSERT_EQ (path_to_c
.m_edges
.length (), 0); /* No path. */
195 test_path path_to_d
= sp
.get_shortest_path (d
);
196 ASSERT_EQ (path_to_d
.m_edges
.length (), 0); /* No path. */
198 test_path path_to_e
= sp
.get_shortest_path (e
);
199 ASSERT_EQ (path_to_e
.m_edges
.length (), 1);
200 ASSERT_EQ (path_to_e
.m_edges
[0], be
);
202 test_path path_to_f
= sp
.get_shortest_path (f
);
203 ASSERT_EQ (path_to_f
.m_edges
.length (), 2);
204 ASSERT_EQ (path_to_f
.m_edges
[0], be
);
205 ASSERT_EQ (path_to_f
.m_edges
[1], ef
);
208 /* Use "C" as the origin, so only D and F are reachable. */
210 shortest_paths
<test_graph_traits
, test_path
> sp (g
, c
);
212 test_path path_to_a
= sp
.get_shortest_path (a
);
213 ASSERT_EQ (path_to_a
.m_edges
.length (), 0); /* No path. */
215 test_path path_to_b
= sp
.get_shortest_path (b
);
216 ASSERT_EQ (path_to_b
.m_edges
.length (), 0); /* No path. */
218 test_path path_to_c
= sp
.get_shortest_path (c
);
219 ASSERT_EQ (path_to_c
.m_edges
.length (), 0); /* Trivial path. */
221 test_path path_to_d
= sp
.get_shortest_path (d
);
222 ASSERT_EQ (path_to_d
.m_edges
.length (), 1);
223 ASSERT_EQ (path_to_d
.m_edges
[0], cd
);
225 test_path path_to_e
= sp
.get_shortest_path (e
);
226 ASSERT_EQ (path_to_e
.m_edges
.length (), 0); /* No path. */
228 test_path path_to_f
= sp
.get_shortest_path (f
);
229 ASSERT_EQ (path_to_f
.m_edges
.length (), 1);
230 ASSERT_EQ (path_to_f
.m_edges
[0], cf
);
234 /* Run all of the selftests within this file. */
240 test_shortest_paths ();
243 } // namespace selftest
245 #endif /* #if CHECKING_P */