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 
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 
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