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