Lines Matching full:g
31 template<class G>
32 void PrintGraph(const G &g) { in PrintGraph() argument
33 for (uptr i = 0; i < g.size(); i++) { in PrintGraph()
34 for (uptr j = 0; j < g.size(); j++) { in PrintGraph()
35 fprintf(stderr, "%d", g.hasEdge(i, j)); in PrintGraph()
51 template <class G>
52 void checkSameAs(G *g) { in checkSameAs() argument
56 EXPECT_TRUE(g->removeEdge(from, to)); in checkSameAs()
58 EXPECT_TRUE(g->empty()); in checkSameAs()
70 BVGraph<BV> g; in BasicTest() local
71 g.clear(); in BasicTest()
81 uptr idx = (uptr)my_rand() % g.size(); in BasicTest()
84 uptr from = my_rand() % g.size(); in BasicTest()
85 uptr to = my_rand() % g.size(); in BasicTest()
86 EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to)); in BasicTest()
87 EXPECT_TRUE(g.hasEdge(from, to)); in BasicTest()
89 from = my_rand() % g.size(); in BasicTest()
90 bool is_reachable = g.isReachable(from, target); in BasicTest()
95 if (g.findPath(from, target, path, len) == len) in BasicTest()
119 BVGraph<BV> g; in RemoveEdges() local
120 g.clear(); in RemoveEdges()
127 g.clear(); in RemoveEdges()
128 for (uptr j = 0; j < g.size() * 2; j++) { in RemoveEdges()
129 uptr from = my_rand() % g.size(); in RemoveEdges()
130 uptr to = my_rand() % g.size(); in RemoveEdges()
131 EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to)); in RemoveEdges()
134 uptr idx = my_rand() % g.size(); in RemoveEdges()
140 g.removeEdgesFrom(bv); in RemoveEdges()
142 for (uptr to = 0; to < g.size(); to++) in RemoveEdges()
146 g.removeEdgesTo(bv); in RemoveEdges()
148 for (uptr from = 0; from < g.size(); from++) in RemoveEdges()
152 s_g.checkSameAs(&g); in RemoveEdges()
166 BVGraph<BV> g; in Test_isReachable() local
167 g.clear(); in Test_isReachable()
171 uptr t1 = g.size() - 1; in Test_isReachable()
177 uptr f2 = g.size() / 2; in Test_isReachable()
178 uptr f3 = g.size() - 2; in Test_isReachable()
180 EXPECT_FALSE(g.isReachable(f0, target)); in Test_isReachable()
181 EXPECT_FALSE(g.isReachable(f1, target)); in Test_isReachable()
182 EXPECT_FALSE(g.isReachable(f2, target)); in Test_isReachable()
183 EXPECT_FALSE(g.isReachable(f3, target)); in Test_isReachable()
185 g.addEdge(f0, f1); in Test_isReachable()
186 g.addEdge(f1, f2); in Test_isReachable()
187 g.addEdge(f2, f3); in Test_isReachable()
188 EXPECT_FALSE(g.isReachable(f0, target)); in Test_isReachable()
189 EXPECT_FALSE(g.isReachable(f1, target)); in Test_isReachable()
190 EXPECT_FALSE(g.isReachable(f2, target)); in Test_isReachable()
191 EXPECT_FALSE(g.isReachable(f3, target)); in Test_isReachable()
193 g.addEdge(f1, t0); in Test_isReachable()
194 EXPECT_TRUE(g.isReachable(f0, target)); in Test_isReachable()
195 EXPECT_TRUE(g.isReachable(f1, target)); in Test_isReachable()
196 EXPECT_FALSE(g.isReachable(f2, target)); in Test_isReachable()
197 EXPECT_FALSE(g.isReachable(f3, target)); in Test_isReachable()
198 EXPECT_EQ(g.findPath(f0, target, path, ARRAY_SIZE(path)), 3U); in Test_isReachable()
202 EXPECT_EQ(g.findPath(f1, target, path, ARRAY_SIZE(path)), 2U); in Test_isReachable()
206 g.addEdge(f3, t1); in Test_isReachable()
207 EXPECT_TRUE(g.isReachable(f0, target)); in Test_isReachable()
208 EXPECT_TRUE(g.isReachable(f1, target)); in Test_isReachable()
209 EXPECT_TRUE(g.isReachable(f2, target)); in Test_isReachable()
210 EXPECT_TRUE(g.isReachable(f3, target)); in Test_isReachable()
222 BVGraph<BV> g; in LongCycle() local
223 g.clear(); in LongCycle()
224 vector<uptr> path_vec(g.size()); in LongCycle()
227 for (uptr i = start; i < g.size() - 1; i++) { in LongCycle()
228 g.addEdge(i, i + 1); in LongCycle()
230 g.addEdge(i, j); in LongCycle()
246 // if (g.size() <= 64) PrintGraph(g); in LongCycle()
248 for (uptr i = start + 1; i < g.size(); i += 11) { in LongCycle()
252 EXPECT_TRUE(g.isReachable(start, target)); in LongCycle()
253 EXPECT_EQ(g.findPath(start, target, path, g.size()), i - start + 1); in LongCycle()
267 BVGraph<BV> g; in ShortestPath() local
268 g.clear(); in ShortestPath()
274 g.addEdge(1, 2); in ShortestPath()
275 g.addEdge(2, 3); in ShortestPath()
276 g.addEdge(3, 4); in ShortestPath()
277 g.addEdge(4, 5); in ShortestPath()
278 g.addEdge(5, 6); in ShortestPath()
279 g.addEdge(6, 7); in ShortestPath()
280 g.addEdge(1, 7); in ShortestPath()
281 EXPECT_TRUE(g.isReachable(1, t7)); in ShortestPath()
283 EXPECT_EQ(0U, g.findPath(1, t7, path, 1)); in ShortestPath()
285 EXPECT_EQ(2U, g.findPath(1, t7, path, 2)); in ShortestPath()
286 EXPECT_EQ(2U, g.findPath(1, t7, path, 3)); in ShortestPath()
287 EXPECT_EQ(2U, g.findPath(1, t7, path, 4)); in ShortestPath()
288 EXPECT_EQ(2U, g.findPath(1, t7, path, 5)); in ShortestPath()
289 EXPECT_EQ(2U, g.findPath(1, t7, path, 6)); in ShortestPath()
291 EXPECT_EQ(7U, g.findPath(1, t7, path, 7)); in ShortestPath()
293 EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 2)); in ShortestPath()
294 EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 7)); in ShortestPath()
306 BVGraph<BV> g; in RunAddEdgesTest() local
310 g.clear(); in RunAddEdgesTest()
312 EXPECT_EQ(0U, g.addEdges(from, 0, added_edges, kMaxEdges)); in RunAddEdgesTest()
313 EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges)); in RunAddEdgesTest()
315 EXPECT_EQ(1U, g.addEdges(from, 1, added_edges, kMaxEdges)); in RunAddEdgesTest()
317 EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges)); in RunAddEdgesTest()
321 EXPECT_EQ(1U, g.addEdges(from, 4, added_edges, kMaxEdges)); in RunAddEdgesTest()
322 EXPECT_TRUE(g.hasEdge(1, 4)); in RunAddEdgesTest()
323 EXPECT_FALSE(g.hasEdge(1, 5)); in RunAddEdgesTest()
327 EXPECT_EQ(2U, g.addEdges(from, 4, added_edges, kMaxEdges)); in RunAddEdgesTest()
328 EXPECT_TRUE(g.hasEdge(2, 4)); in RunAddEdgesTest()
329 EXPECT_FALSE(g.hasEdge(2, 5)); in RunAddEdgesTest()
330 EXPECT_TRUE(g.hasEdge(3, 4)); in RunAddEdgesTest()
331 EXPECT_FALSE(g.hasEdge(3, 5)); in RunAddEdgesTest()