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