• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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