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