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 16 #ifndef UDMF_GRAPH_H 17 #define UDMF_GRAPH_H 18 19 #include <vector> 20 #include <iostream> 21 #include <stack> 22 #include <string> 23 24 namespace OHOS { 25 namespace UDMF { 26 struct EdgeNode { 27 uint32_t adjIndex; 28 EdgeNode* next; 29 }; 30 31 struct VertexNode { 32 uint32_t value; 33 EdgeNode* firstEdge; 34 }; 35 class Graph { 36 public: 37 explicit Graph(uint32_t vertexNum); 38 using Action = std::function<bool(uint32_t node)>; 39 void AddEdge(uint32_t start, uint32_t end); 40 bool Dfs(uint32_t startNode, Action action, bool isInit = true); 41 bool DfsUnconnectedGraph(Action action); 42 private: 43 uint32_t vertexNum_; 44 std::vector<VertexNode> adjList_; // Adjacency List 45 std::vector<uint32_t> visited_; // Determine whether the vertex has been accessed, index=vertex value 46 std::vector<uint32_t> result_; 47 }; 48 } // namespace UDMF 49 } // namespace OHOS 50 #endif // UDMF_GRAPH_H 51