1 //=== llvm/unittest/ADT/BreadthFirstIteratorTest.cpp - BFS iterator tests -===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/ADT/BreadthFirstIterator.h"
10 #include "TestGraph.h"
11 #include "gtest/gtest.h"
12
13 using namespace llvm;
14
15 namespace llvm {
16
TEST(BreadthFristIteratorTest,Basic)17 TEST(BreadthFristIteratorTest, Basic) {
18 typedef bf_iterator<Graph<4>> BFIter;
19
20 Graph<4> G;
21 G.AddEdge(0, 1);
22 G.AddEdge(0, 2);
23 G.AddEdge(1, 3);
24
25 auto It = BFIter::begin(G);
26 auto End = BFIter::end(G);
27 EXPECT_EQ(It.getLevel(), 0U);
28 EXPECT_EQ(*It, G.AccessNode(0));
29 ++It;
30 EXPECT_EQ(It.getLevel(), 1U);
31 EXPECT_EQ(*It, G.AccessNode(1));
32 ++It;
33 EXPECT_EQ(It.getLevel(), 1U);
34 EXPECT_EQ(*It, G.AccessNode(2));
35 ++It;
36 EXPECT_EQ(It.getLevel(), 2U);
37 EXPECT_EQ(*It, G.AccessNode(3));
38 ++It;
39 EXPECT_EQ(It, End);
40 }
41
TEST(BreadthFristIteratorTest,Cycle)42 TEST(BreadthFristIteratorTest, Cycle) {
43 typedef bf_iterator<Graph<4>> BFIter;
44
45 Graph<4> G;
46 G.AddEdge(0, 1);
47 G.AddEdge(1, 0);
48 G.AddEdge(1, 2);
49 G.AddEdge(2, 1);
50 G.AddEdge(2, 1);
51 G.AddEdge(2, 3);
52 G.AddEdge(3, 2);
53 G.AddEdge(3, 1);
54 G.AddEdge(3, 0);
55
56 auto It = BFIter::begin(G);
57 auto End = BFIter::end(G);
58 EXPECT_EQ(It.getLevel(), 0U);
59 EXPECT_EQ(*It, G.AccessNode(0));
60 ++It;
61 EXPECT_EQ(It.getLevel(), 1U);
62 EXPECT_EQ(*It, G.AccessNode(1));
63 ++It;
64 EXPECT_EQ(It.getLevel(), 2U);
65 EXPECT_EQ(*It, G.AccessNode(2));
66 ++It;
67 EXPECT_EQ(It.getLevel(), 3U);
68 EXPECT_EQ(*It, G.AccessNode(3));
69 ++It;
70 EXPECT_EQ(It, End);
71 }
72
73 } // end namespace llvm
74