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
25namespace OHOS {
26namespace UDMF {
27struct EdgeNode {
28    uint32_t adjIndex;
29    EdgeNode* next;
30};
31
32struct VertexNode {
33    uint32_t value;
34    EdgeNode* firstEdge;
35};
36class Graph {
37public:
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();
48private:
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