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_check.h"
16
17 namespace ffrt {
AddVetexByLabel(uint64_t label)18 void GraphCheckCyclic::AddVetexByLabel(uint64_t label)
19 {
20 if (vetexes.count(label) == 0) {
21 std::list<uint64_t> labelVertex;
22 vetexes[label] = labelVertex;
23 }
24 }
25
EdgeNum(void)26 uint32_t GraphCheckCyclic::EdgeNum(void)
27 {
28 uint32_t num = 0;
29 for (auto &t : vetexes) {
30 num += t.second.size();
31 }
32 return num;
33 }
34
VertexNum(void) const35 uint32_t GraphCheckCyclic::VertexNum(void) const
36 {
37 return vetexes.size();
38 }
39
AddEdgeByLabel(uint64_t startLabel,uint64_t endLabel)40 void GraphCheckCyclic::AddEdgeByLabel(uint64_t startLabel, uint64_t endLabel)
41 {
42 std::map<uint64_t, std::list<uint64_t>>::iterator it = vetexes.find(startLabel);
43 if (it != vetexes.end()) {
44 it->second.push_back(endLabel);
45 }
46 }
47
RemoveEdgeByLabel(uint64_t endLabel)48 void GraphCheckCyclic::RemoveEdgeByLabel(uint64_t endLabel)
49 {
50 std::map<uint64_t, std::list<uint64_t>>::iterator it = vetexes.find(endLabel);
51 if (it != vetexes.end()) {
52 it->second.clear();
53 }
54 }
55
IsCyclicDfs(uint64_t v,std::map<uint64_t,struct VertexStatus> & vertexStatus)56 bool GraphCheckCyclic::IsCyclicDfs(uint64_t v, std::map<uint64_t, struct VertexStatus>& vertexStatus)
57 {
58 if (!vertexStatus[v].visited) {
59 vertexStatus[v].visited = true;
60 vertexStatus[v].recStack = true;
61 std::list<uint64_t>::iterator i;
62 std::map<uint64_t, std::list<uint64_t>>::iterator it = vetexes.find(v);
63 for (i = it->second.begin(); i != it->second.end(); ++i) {
64 if (!vertexStatus[*i].visited && IsCyclicDfs(*i, vertexStatus)) {
65 return true;
66 } else if (vertexStatus[*i].recStack) {
67 return true;
68 }
69 }
70 }
71
72 vertexStatus[v].recStack = false;
73 return false;
74 }
75
IsCyclic(void)76 bool GraphCheckCyclic::IsCyclic(void)
77 {
78 std::map<uint64_t, struct VertexStatus> vertexStatus;
79 for (const auto &t : vetexes) {
80 vertexStatus[t.first].visited = false;
81 vertexStatus[t.first].recStack = false;
82 }
83
84 for (const auto &t : vetexes) {
85 if (!vertexStatus[t.first].visited && IsCyclicDfs(t.first, vertexStatus)) {
86 return true;
87 }
88 }
89
90 return false;
91 }
92 }