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 "Graph"
16 #include "graph.h"
17 #include "logger.h"
18 namespace OHOS {
19 namespace UDMF {
Graph(uint32_t vertexNum,const std::map<std::string,uint32_t> & typeIdIndex)20 Graph::Graph(uint32_t vertexNum, const std::map<std::string, uint32_t> &typeIdIndex)
21 : vertexNum_(vertexNum), typeIdIndex_(typeIdIndex)
22 {
23 for (uint32_t node = 0; node < vertexNum_; node++) {
24 adjList_.push_back({node, nullptr});
25 }
26 visited_.resize(vertexNum_);
27 fill(visited_.begin(), visited_.end(), 0);
28 }
29
~Graph()30 Graph::~Graph()
31 {
32 for (const auto &vertexNode : adjList_) {
33 EdgeNode *edge = vertexNode.firstEdge;
34 while (edge != nullptr) {
35 EdgeNode *nextEdge = edge->next;
36 delete edge;
37 edge = nextEdge;
38 }
39 }
40 }
41
AddEdge(const std::string & startNode,const std::string & endNode)42 void Graph::AddEdge(const std::string &startNode, const std::string &endNode)
43 {
44 int32_t start = GetIndex(startNode);
45 int32_t end = GetIndex(endNode);
46 if (start < 0 || end < 0) {
47 LOG_WARN(UDMF_CLIENT, "abnormal edge, startNode:%{public}s, endNode:%{public}s. ",
48 startNode.c_str(), endNode.c_str());
49 return;
50 }
51 AddEdge(start, end);
52 }
53
AddEdge(uint32_t start,uint32_t end)54 void Graph::AddEdge(uint32_t start, uint32_t end)
55 {
56 EdgeNode *edge = new (std::nothrow) EdgeNode; // add new edge
57 if (edge == nullptr) {
58 LOG_ERROR(UDMF_CLIENT, "edge is nullptr");
59 return;
60 }
61 edge->adjIndex = end;
62 edge->next = adjList_[start].firstEdge;
63 adjList_[start].firstEdge = edge;
64 }
65
Dfs(uint32_t startNode,Action action,bool isInit)66 bool Graph::Dfs(uint32_t startNode, Action action, bool isInit)
67 {
68 if (isInit) {
69 visited_.resize(vertexNum_);
70 fill(visited_.begin(), visited_.end(), 0);
71 }
72 std::stack<uint32_t> nodes;
73 EdgeNode *edge = nullptr;
74 visited_[startNode] = 1;
75 nodes.push(startNode);
76 if (action(adjList_[startNode].value)) {
77 return true;
78 }
79 while (!nodes.empty()) {
80 edge = adjList_[nodes.top()].firstEdge;
81 while (edge) {
82 if (visited_[edge->adjIndex] == 0) {
83 visited_[edge->adjIndex] = 1;
84 nodes.push(edge->adjIndex);
85 if (action(adjList_[edge->adjIndex].value)) {
86 return true;
87 }
88 edge = adjList_[edge->adjIndex].firstEdge;
89 } else if (visited_[edge->adjIndex] == 1) {
90 return false;
91 } else {
92 edge = edge->next;
93 }
94 }
95 visited_[nodes.top()] = 2; // 2: all edge of the adj is visited.
96 nodes.pop();
97 }
98 return true;
99 }
100
DfsUnconnectedGraph(Action action)101 bool Graph::DfsUnconnectedGraph(Action action)
102 {
103 visited_.resize(vertexNum_);
104 fill(visited_.begin(), visited_.end(), 0);
105 for (uint32_t node = 0; node < vertexNum_; node++) {
106 if (!visited_[node]) {
107 if (!Dfs(node, action, false)) {
108 return false;
109 }
110 }
111 }
112 return true;
113 }
114
IsValidType(const std::string & node)115 bool Graph::IsValidType(const std::string &node)
116 {
117 if (typeIdIndex_.find(node) == typeIdIndex_.end()) {
118 LOG_ERROR(UDMF_CLIENT, "invalid typeId");
119 return false;
120 }
121 return true;
122 }
123
GetIndex(const std::string & node)124 int32_t Graph::GetIndex(const std::string &node)
125 {
126 auto idx = typeIdIndex_.find(node);
127 if (idx == typeIdIndex_.end()) {
128 return -1;
129 }
130 return idx->second;
131 }
132
IsDAG()133 bool Graph::IsDAG()
134 {
135 return DfsUnconnectedGraph([&](uint32_t currNode) -> bool { return false; });
136 }
137 } // namespace UDMF
138 } // namespace OHOS
139