1 /*
2  * Copyright (c) 2023 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 #define LOG_TAG "GraphTest"
16 #include <gtest/gtest.h>
17 
18 #include <unistd.h>
19 
20 #include "logger.h"
21 #include "utd_common.h"
22 #include "graph.h"
23 
24 using namespace testing::ext;
25 using namespace OHOS::UDMF;
26 using namespace OHOS;
27 namespace OHOS::Test {
28 enum TestNodes : uint32_t {
29     POINT_A = 0,
30     POINT_B,
31     POINT_C,
32     POINT_D,
33     POINT_E,
34     POINT_F,
35     POINT_G,
36     POINT_H
37 };
38 class GraphTest : public testing::Test {
39 public:
40     static void SetUpTestCase();
41     static void TearDownTestCase();
42     void SetUp() override;
43     void TearDown() override;
44 };
45 
SetUpTestCase()46 void GraphTest::SetUpTestCase()
47 {
48 }
49 
TearDownTestCase()50 void GraphTest::TearDownTestCase()
51 {
52 }
53 
SetUp()54 void GraphTest::SetUp()
55 {
56 }
57 
TearDown()58 void GraphTest::TearDown()
59 {
60 }
61 
62 /**
63 * @tc.name: DfsUnconnectedGraph001
64 * @tc.desc: is connectedGraph: A -> A
65 * @tc.type: FUNC
66 */
67 HWTEST_F(GraphTest, DfsUnconnectedGraph001, TestSize.Level1)
68 {
69     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph001 begin.");
70     uint32_t vextexNum = 1;
71     vector<vector<uint32_t>> edges={{TestNodes::POINT_A, TestNodes::POINT_A},
72     };
73     Graph graph(vextexNum, {});
74     for (uint32_t i = 0; i < edges.size(); i++) {
75         graph.AddEdge(edges[i][0], edges[i][1]);
76     }
77     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290102(uint32_t currNode) 78                                                   { return false; });
79     EXPECT_EQ(isDAGFlag, false);
80     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph001 end.");
81 }
82 
83 /**
84 * @tc.name: DfsUnconnectedGraph002
85 * @tc.desc: is connectedGraph: A -> B -> A
86 * @tc.type: FUNC
87 */
88 HWTEST_F(GraphTest, DfsUnconnectedGraph002, TestSize.Level1)
89 {
90     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph002 begin.");
91     uint32_t vextexNum = 2;
92     vector<vector<uint32_t>> edges={{TestNodes::POINT_A, TestNodes::POINT_B},
93                                     {TestNodes::POINT_B, TestNodes::POINT_A},
94     };
95     Graph graph(vextexNum, {});
96     for (uint32_t i = 0; i < edges.size(); i++) {
97         graph.AddEdge(edges[i][0], edges[i][1]);
98     }
99     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290202(uint32_t currNode) 100                                                   { return false; });
101     EXPECT_EQ(isDAGFlag, false);
102     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph002 end.");
103 }
104 
105 /**
106 * @tc.name: DfsUnconnectedGraph003
107 * @tc.desc: is connectedGraph: A -> B -> C -> A
108 * @tc.type: FUNC
109 */
110 HWTEST_F(GraphTest, DfsUnconnectedGraph003, TestSize.Level1)
111 {
112     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph003 begin.");
113     uint32_t vextexNum = 3;  // total point
114     vector<vector<uint32_t>> edges={{TestNodes::POINT_A, TestNodes::POINT_B},
115                                     {TestNodes::POINT_B, TestNodes::POINT_C},
116                                     {TestNodes::POINT_C, TestNodes::POINT_A}
117     };
118     Graph graph(vextexNum, {});
119     for (uint32_t i = 0; i < edges.size(); i++) {
120         graph.AddEdge(edges[i][0], edges[i][1]);
121     }
122     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290302(uint32_t currNode) 123                                                   { return false; });
124     EXPECT_EQ(isDAGFlag, false);
125     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph003 end.");
126 }
127 
128 /**
129 * @tc.name: DfsUnconnectedGraph004
130 * @tc.desc: is connectedGraph: A -> B -> C -> B
131 * @tc.type: FUNC
132 */
133 HWTEST_F(GraphTest, DfsUnconnectedGraph004, TestSize.Level1)
134 {
135     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph004 begin.");
136     uint32_t vextexNum = 3;
137     vector<vector<uint32_t>> edges={{TestNodes::POINT_A, TestNodes::POINT_B},
138                                     {TestNodes::POINT_B, TestNodes::POINT_C},
139                                     {TestNodes::POINT_C, TestNodes::POINT_B},
140     };
141     Graph graph(vextexNum, {});
142     for (uint32_t i = 0; i < edges.size(); i++) {
143         graph.AddEdge(edges[i][0], edges[i][1]);
144     }
145     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290402(uint32_t currNode) 146                                                   { return false; });
147     EXPECT_EQ(isDAGFlag, false);
148     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph004 end.");
149 }
150 
151 /**
152 * @tc.name: DfsUnconnectedGraph005
153 * @tc.desc: is connectedGraph: A -> B -> C -> D -> E -> F   D -> E -> G -> H -> E
154 * @tc.type: FUNC
155 */
156 HWTEST_F(GraphTest, DfsUnconnectedGraph005, TestSize.Level1)
157 {
158     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph005 begin.");
159     uint32_t vextexNum = 8;
160     vector<vector<uint32_t>> edges = {
161         {TestNodes::POINT_A, TestNodes::POINT_B},
162         {TestNodes::POINT_B, TestNodes::POINT_C},
163         {TestNodes::POINT_C, TestNodes::POINT_D},
164         {TestNodes::POINT_D, TestNodes::POINT_E},
165         {TestNodes::POINT_D, TestNodes::POINT_E},
166         {TestNodes::POINT_E, TestNodes::POINT_F},
167         {TestNodes::POINT_E, TestNodes::POINT_G},
168         {TestNodes::POINT_G, TestNodes::POINT_H},
169         {TestNodes::POINT_H, TestNodes::POINT_E},
170     };
171     Graph graph(vextexNum, {});
172     for (uint32_t i = 0; i < edges.size(); i++) {
173         graph.AddEdge(edges[i][0], edges[i][1]);
174     }
175     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290502(uint32_t currNode) 176                                                   { return false; });
177     EXPECT_EQ(isDAGFlag, false);
178     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph005 end.");
179 }
180 
181 /**
182 * @tc.name: DfsUnconnectedGraph006
183 * @tc.desc: is not connectedGraph: A -> B -> C -> D -> E -> F   D -> E -> G -> H
184 * @tc.type: FUNC
185 */
186 HWTEST_F(GraphTest, DfsUnconnectedGraph006, TestSize.Level1)
187 {
188     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph006 begin.");
189     uint32_t vextexNum = 8;
190     vector<vector<uint32_t>> edges = {
191         {TestNodes::POINT_A, TestNodes::POINT_B},
192         {TestNodes::POINT_B, TestNodes::POINT_C},
193         {TestNodes::POINT_C, TestNodes::POINT_D},
194         {TestNodes::POINT_D, TestNodes::POINT_E},
195         {TestNodes::POINT_D, TestNodes::POINT_E},
196         {TestNodes::POINT_E, TestNodes::POINT_F},
197         {TestNodes::POINT_E, TestNodes::POINT_G},
198         {TestNodes::POINT_G, TestNodes::POINT_H},
199     };
200     Graph graph(vextexNum, {});
201     for (uint32_t i = 0; i < edges.size(); i++) {
202         graph.AddEdge(edges[i][0], edges[i][1]);
203     }
204     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290602(uint32_t currNode) 205                                                   { return false; });
206     EXPECT_EQ(isDAGFlag, true);
207     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph006 end.");
208 }
209 
210 /**
211 * @tc.name: DfsUnconnectedGraph007
212 * @tc.desc: is not connectedGraph: A -> B   A -> C   B -> D   C -> D   B -> C
213 * @tc.type: FUNC
214 */
215 HWTEST_F(GraphTest, DfsUnconnectedGraph007, TestSize.Level1)
216 {
217     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph007 begin.");
218     uint32_t vextexNum = 4;
219     vector<vector<uint32_t>> edges = {
220         {TestNodes::POINT_A, TestNodes::POINT_B},
221         {TestNodes::POINT_A, TestNodes::POINT_C},
222         {TestNodes::POINT_B, TestNodes::POINT_D},
223         {TestNodes::POINT_C, TestNodes::POINT_D},
224         {TestNodes::POINT_B, TestNodes::POINT_C},
225     };
226     Graph graph(vextexNum, {});
227     for (uint32_t i = 0; i < edges.size(); i++) {
228         graph.AddEdge(edges[i][0], edges[i][1]);
229     }
230     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290702(uint32_t currNode) 231                                                   { return false; });
232     EXPECT_EQ(isDAGFlag, true);
233     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph007 end.");
234 }
235 
236 /**
237 * @tc.name: DfsUnconnectedGraph008
238 * @tc.desc: is not connectedGraph: A -> B -> C   D -> E   F -> G -> H
239 * @tc.type: FUNC
240 */
241 HWTEST_F(GraphTest, DfsUnconnectedGraph008, TestSize.Level1)
242 {
243     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph008 begin.");
244     uint32_t vextexNum = 8;
245     vector<vector<uint32_t>> edges = {
246         {TestNodes::POINT_A, TestNodes::POINT_B},
247         {TestNodes::POINT_B, TestNodes::POINT_C},
248         {TestNodes::POINT_D, TestNodes::POINT_E},
249         {TestNodes::POINT_F, TestNodes::POINT_G},
250         {TestNodes::POINT_G, TestNodes::POINT_H},
251     };
252     Graph graph(vextexNum, {});
253     for (uint32_t i = 0; i < edges.size(); i++) {
254         graph.AddEdge(edges[i][0], edges[i][1]);
255     }
256     bool isDAGFlag = graph.DfsUnconnectedGraph([&](uint32_t currNode) -> bool
__anonad9e34290802(uint32_t currNode) 257                                                   { return false; });
258     EXPECT_EQ(isDAGFlag, true);
259     LOG_INFO(UDMF_TEST, "DfsUnconnectedGraph008 end.");
260 }
261 
262 /**
263 * @tc.name: DfsHasData001
264 * @tc.desc: is not connectedGraph: A -> B -> C -> D -> E -> F   D -> E -> G -> H
265 * @tc.type: FUNC
266 */
267 HWTEST_F(GraphTest, DfsHasData001, TestSize.Level1)
268 {
269     LOG_INFO(UDMF_TEST, "DfsHasData001 begin.");
270     uint32_t vextexNum = 8;
271     vector<vector<uint32_t>> edges = {
272         {TestNodes::POINT_A, TestNodes::POINT_B},
273         {TestNodes::POINT_B, TestNodes::POINT_C},
274         {TestNodes::POINT_C, TestNodes::POINT_D},
275         {TestNodes::POINT_D, TestNodes::POINT_E},
276         {TestNodes::POINT_D, TestNodes::POINT_E},
277         {TestNodes::POINT_E, TestNodes::POINT_F},
278         {TestNodes::POINT_E, TestNodes::POINT_G},
279         {TestNodes::POINT_G, TestNodes::POINT_H},
280     };
281     Graph graph(vextexNum, {});
282     for (uint32_t i = 0; i < edges.size(); i++) {
283         graph.AddEdge(edges[i][0], edges[i][1]);
284     }
285 
286     bool isFind = false;
__anonad9e34290902(uint32_t currNode) 287     graph.Dfs(TestNodes::POINT_A, [&](uint32_t currNode) -> bool {
288         if (currNode == TestNodes::POINT_H) {
289             isFind = true;
290             return true;
291         }
292         return false;
293     });
294     EXPECT_EQ(isFind, true);
295 
296     isFind = false;
__anonad9e34290a02(uint32_t currNode) 297     graph.Dfs(TestNodes::POINT_A, [&](uint32_t currNode) -> bool {
298         if (currNode == TestNodes::POINT_F) {
299             isFind = true;
300             return true;
301         }
302         return false;
303     });
304     EXPECT_EQ(isFind, true);
305 
306     isFind = false;
__anonad9e34290b02(uint32_t currNode) 307     graph.Dfs(TestNodes::POINT_E, [&](uint32_t currNode) -> bool {
308         if (currNode == TestNodes::POINT_D) {
309             isFind = true;
310             return true;
311         }
312         return false;
313     });
314     EXPECT_EQ(isFind, false);
315     LOG_INFO(UDMF_TEST, "DfsHasData001 end.");
316 }
317 
318 /**
319 * @tc.name: DfsHasData002
320 * @tc.desc: is not connectedGraph: A -> B -> C   D -> E   F -> G -> H
321 * @tc.type: FUNC
322 */
323 HWTEST_F(GraphTest, DfsHasData002, TestSize.Level1)
324 {
325     LOG_INFO(UDMF_TEST, "DfsHasData002 begin.");
326     uint32_t vextexNum = 8;
327     vector<vector<uint32_t>> edges = {
328         {TestNodes::POINT_A, TestNodes::POINT_B},
329         {TestNodes::POINT_B, TestNodes::POINT_C},
330         {TestNodes::POINT_D, TestNodes::POINT_E},
331         {TestNodes::POINT_F, TestNodes::POINT_G},
332         {TestNodes::POINT_G, TestNodes::POINT_H},
333     };
334     Graph graph(vextexNum, {});
335     for (uint32_t i = 0; i < edges.size(); i++) {
336         graph.AddEdge(edges[i][0], edges[i][1]);
337     }
338 
339     bool isFind = false;
__anonad9e34290c02(uint32_t currNode) 340     graph.Dfs(TestNodes::POINT_F, [&](uint32_t currNode) -> bool {
341         if (currNode == TestNodes::POINT_H) {
342             isFind = true;
343             return true;
344         }
345         return false;
346     });
347     EXPECT_EQ(isFind, true);
348 
349     isFind = false;
__anonad9e34290d02(uint32_t currNode) 350     graph.Dfs(TestNodes::POINT_A, [&](uint32_t currNode) -> bool {
351         if (currNode == TestNodes::POINT_H) {
352             isFind = true;
353             return true;
354         }
355         return false;
356     });
357     EXPECT_EQ(isFind, false);
358     LOG_INFO(UDMF_TEST, "DfsHasData002 end.");
359 }
360 } // OHOS::Test