Mercurial > hg > CbC > CbC_gcc
comparison gcc/digraph.cc @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
131:84e7813d76e9 | 145:1830386684a0 |
---|---|
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 */ |