|
145
|
1 /* Template classes for directed graphs.
|
|
|
2 Copyright (C) 2019-2020 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 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
|
|
|
55 {
|
|
|
56 }
|
|
|
57
|
|
|
58 const char *m_name;
|
|
|
59 int m_index;
|
|
|
60 };
|
|
|
61
|
|
|
62 struct test_edge : public dedge<test_graph_traits>
|
|
|
63 {
|
|
|
64 test_edge (node_t *src, node_t *dest)
|
|
|
65 : dedge<test_graph_traits> (src, dest)
|
|
|
66 {}
|
|
|
67
|
|
|
68 void dump_dot (graphviz_out *gv, const dump_args_t &) const OVERRIDE
|
|
|
69 {
|
|
|
70 gv->println ("%s -> %s;", m_src->m_name, m_dest->m_name);
|
|
|
71 }
|
|
|
72 };
|
|
|
73
|
|
|
74 struct test_graph : public digraph<test_graph_traits>
|
|
|
75 {
|
|
|
76 test_node *add_test_node (const char *name)
|
|
|
77 {
|
|
|
78 test_node *result = new test_node (name, m_nodes.length ());
|
|
|
79 add_node (result);
|
|
|
80 return result;
|
|
|
81 }
|
|
|
82
|
|
|
83 test_edge *add_test_edge (test_node *src, test_node *dst)
|
|
|
84 {
|
|
|
85 test_edge *result = new test_edge (src, dst);
|
|
|
86 add_edge (result);
|
|
|
87 return result;
|
|
|
88 }
|
|
|
89 };
|
|
|
90
|
|
|
91 struct test_cluster : public cluster<test_graph_traits>
|
|
|
92 {
|
|
|
93 };
|
|
|
94
|
|
|
95 struct test_path
|
|
|
96 {
|
|
|
97 auto_vec<const test_edge *> m_edges;
|
|
|
98 };
|
|
|
99
|
|
|
100 /* Smoketest of digraph dumping. */
|
|
|
101
|
|
|
102 static void
|
|
|
103 test_dump_to_dot ()
|
|
|
104 {
|
|
|
105 test_graph g;
|
|
|
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);
|
|
|
109
|
|
|
110 pretty_printer pp;
|
|
|
111 pp.buffer->stream = NULL;
|
|
|
112 test_dump_args_t dump_args;
|
|
|
113 g.dump_dot_to_pp (&pp, NULL, dump_args);
|
|
|
114
|
|
|
115 ASSERT_STR_CONTAINS (pp_formatted_text (&pp),
|
|
|
116 "a -> b;\n");
|
|
|
117 }
|
|
|
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 test_shortest_paths ()
|
|
|
132 {
|
|
|
133 test_graph g;
|
|
|
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");
|
|
|
140
|
|
|
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 g.add_test_edge (e, f);
|
|
|
146 test_edge *cf = g.add_test_edge (c, f);
|
|
|
147
|
|
|
148 shortest_paths<test_graph_traits, test_path> sp (g, a);
|
|
|
149
|
|
|
150 test_path path_to_a = sp.get_shortest_path (a);
|
|
|
151 ASSERT_EQ (path_to_a.m_edges.length (), 0);
|
|
|
152
|
|
|
153 test_path path_to_b = sp.get_shortest_path (b);
|
|
|
154 ASSERT_EQ (path_to_b.m_edges.length (), 1);
|
|
|
155 ASSERT_EQ (path_to_b.m_edges[0], ab);
|
|
|
156
|
|
|
157 test_path path_to_c = sp.get_shortest_path (c);
|
|
|
158 ASSERT_EQ (path_to_c.m_edges.length (), 1);
|
|
|
159 ASSERT_EQ (path_to_c.m_edges[0], ac);
|
|
|
160
|
|
|
161 test_path path_to_d = sp.get_shortest_path (d);
|
|
|
162 ASSERT_EQ (path_to_d.m_edges.length (), 2);
|
|
|
163 ASSERT_EQ (path_to_d.m_edges[0], ac);
|
|
|
164 ASSERT_EQ (path_to_d.m_edges[1], cd);
|
|
|
165
|
|
|
166 test_path path_to_e = sp.get_shortest_path (e);
|
|
|
167 ASSERT_EQ (path_to_e.m_edges.length (), 2);
|
|
|
168 ASSERT_EQ (path_to_e.m_edges[0], ab);
|
|
|
169 ASSERT_EQ (path_to_e.m_edges[1], be);
|
|
|
170
|
|
|
171 test_path path_to_f = sp.get_shortest_path (f);
|
|
|
172 ASSERT_EQ (path_to_f.m_edges.length (), 2);
|
|
|
173 ASSERT_EQ (path_to_f.m_edges[0], ac);
|
|
|
174 ASSERT_EQ (path_to_f.m_edges[1], cf);
|
|
|
175 }
|
|
|
176
|
|
|
177 /* Run all of the selftests within this file. */
|
|
|
178
|
|
|
179 void
|
|
|
180 digraph_cc_tests ()
|
|
|
181 {
|
|
|
182 test_dump_to_dot ();
|
|
|
183 test_shortest_paths ();
|
|
|
184 }
|
|
|
185
|
|
|
186 } // namespace selftest
|
|
|
187
|
|
|
188 #endif /* #if CHECKING_P */
|
