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 EdgeNode; // add new edge
57 edge->adjIndex = end;
58 edge->next = adjList_[start].firstEdge;
59 adjList_[start].firstEdge = edge;
60 }
61
Dfs(uint32_t startNode,Action action,bool isInit)62 bool Graph::Dfs(uint32_t startNode, Action action, bool isInit)
63 {
64 if (isInit) {
65 visited_.resize(vertexNum_);
66 fill(visited_.begin(), visited_.end(), 0);
67 }
68 std::stack<uint32_t> nodes;
69 EdgeNode *edge = nullptr;
70 visited_[startNode] = 1;
71 nodes.push(startNode);
72 if (action(adjList_[startNode].value)) {
73 return true;
74 }
75 while (!nodes.empty()) {
76 edge = adjList_[nodes.top()].firstEdge;
77 while (edge) {
78 if (visited_[edge->adjIndex] == 0) {
79 visited_[edge->adjIndex] = 1;
80 nodes.push(edge->adjIndex);
81 if (action(adjList_[edge->adjIndex].value)) {
82 return true;
83 }
84 edge = adjList_[edge->adjIndex].firstEdge;
85 } else if (visited_[edge->adjIndex] == 1) {
86 return false;
87 } else {
88 edge = edge->next;
89 }
90 }
91 visited_[nodes.top()] = 2; // 2: all edge of the adj is visited.
92 nodes.pop();
93 }
94 return true;
95 }
96
DfsUnconnectedGraph(Action action)97 bool Graph::DfsUnconnectedGraph(Action action)
98 {
99 visited_.resize(vertexNum_);
100 fill(visited_.begin(), visited_.end(), 0);
101 for (uint32_t node = 0; node < vertexNum_; node++) {
102 if (!visited_[node]) {
103 if (!Dfs(node, action, false)) {
104 return false;
105 }
106 }
107 }
108 return true;
109 }
110
IsValidType(const std::string & node)111 bool Graph::IsValidType(const std::string &node)
112 {
113 if (typeIdIndex_.find(node) == typeIdIndex_.end()) {
114 LOG_ERROR(UDMF_CLIENT, "invalid typeId. typeId:%{public}s ", node.c_str());
115 return false;
116 }
117 return true;
118 }
119
GetIndex(const std::string & node)120 int32_t Graph::GetIndex(const std::string &node)
121 {
122 auto idx = typeIdIndex_.find(node);
123 if (idx == typeIdIndex_.end()) {
124 return -1;
125 }
126 return idx->second;
127 }
128
IsDAG()129 bool Graph::IsDAG()
130 {
131 return DfsUnconnectedGraph([&](uint32_t currNode) -> bool { return false; });
132 }
133 } // namespace UDMF
134 } // namespace OHOS
135