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 #include "graph.h"
16 namespace OHOS {
17 namespace UDMF {
Graph(uint32_t vertexNum)18 Graph::Graph(uint32_t vertexNum):vertexNum_(vertexNum)
19 {
20 for (uint32_t node = 0; node < vertexNum_; node++) {
21 adjList_.push_back({node, nullptr});
22 }
23 visited_.resize(vertexNum_);
24 fill(visited_.begin(), visited_.end(), 0);
25 }
26
AddEdge(uint32_t start,uint32_t end)27 void Graph::AddEdge(uint32_t start, uint32_t end)
28 {
29 EdgeNode *edge = new EdgeNode; // add new edge
30 edge->adjIndex = end;
31 edge->next = adjList_[start].firstEdge;
32 adjList_[start].firstEdge = edge;
33 }
34
Dfs(uint32_t startNode,Action action,bool isInit)35 bool Graph::Dfs(uint32_t startNode, Action action, bool isInit)
36 {
37 if (isInit) {
38 visited_.resize(vertexNum_);
39 fill(visited_.begin(), visited_.end(), 0);
40 }
41 std::stack<uint32_t> nodes;
42 EdgeNode *edge = nullptr;
43 visited_[startNode] = 1;
44 nodes.push(startNode);
45 result_.push_back(startNode);
46 if (action(adjList_[startNode].value)) {
47 return true;
48 }
49 while (!nodes.empty()) {
50 edge = adjList_[nodes.top()].firstEdge;
51 while (edge) {
52 if (visited_[edge->adjIndex] == 0) {
53 visited_[edge->adjIndex] = 1;
54 if (adjList_[edge->adjIndex].firstEdge != nullptr) {
55 auto iter = find(result_.begin(), result_.end(), adjList_[edge->adjIndex].firstEdge->adjIndex);
56 if (iter != result_.end() && visited_[adjList_[edge->adjIndex].firstEdge->adjIndex] == 1) {
57 return false; // current node, iscycle
58 }
59 }
60 if (action(adjList_[edge->adjIndex].value)) {
61 return true;
62 }
63 result_.push_back(startNode);
64 nodes.push(edge->adjIndex);
65 edge = adjList_[edge->adjIndex].firstEdge;
66 } else {
67 edge = edge->next;
68 }
69 }
70 if (edge == nullptr) {
71 visited_[nodes.top()] = 2; // 2: all edge of the adj is visited.
72 nodes.pop();
73 }
74 }
75 return true;
76 }
77
DfsUnconnectedGraph(Action action)78 bool Graph::DfsUnconnectedGraph(Action action)
79 {
80 visited_.resize(vertexNum_);
81 fill(visited_.begin(), visited_.end(), 0);
82 result_.clear();
83 for (uint32_t node = 0; node < vertexNum_; node++) {
84 if (!visited_[node]) {
85 if (!Dfs(node, action, false)) {
86 return false;
87 }
88 }
89 }
90 return true;
91 }
92 } // namespace UDMF
93 } // namespace OHOS
94