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 #ifndef __GRAPH_CHECK_H__ 16 #define __GRAPH_CHECK_H__ 17 #include <cstdio> 18 #include <cstdlib> 19 #include <cstdint> 20 #include <map> 21 #include <list> 22 #include <stdint.h> 23 24 namespace ffrt { 25 struct VertexStatus { 26 bool visited; 27 bool recStack; 28 }; 29 30 class GraphCheckCyclic { 31 std::map<uint64_t, std::list<uint64_t>> vetexes; 32 bool IsCyclicDfs(uint64_t v, std::map<uint64_t, struct VertexStatus>& vertexStatus); 33 public: 34 void AddVetexByLabel(uint64_t label); 35 void AddEdgeByLabel(uint64_t startLabel, uint64_t endLabel); 36 void RemoveEdgeByLabel(uint64_t endLabel); 37 uint32_t EdgeNum(void); 38 uint32_t VertexNum(void) const; 39 bool IsCyclic(); 40 }; 41 } 42 #endif