1/*
2 * Copyright (c) 2024 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 JS_CONCURRENT_MODULE_UTILS_LOCKS_GRAPH_H
17#define JS_CONCURRENT_MODULE_UTILS_LOCKS_GRAPH_H
18
19#include <vector>
20#include <map>
21#include <string>
22#include <limits>
23#include <stack>
24#include <functional>
25
26namespace Commonlibrary::Concurrent::LocksModule {
27
28template <class VertexId = size_t, class EdgeData = void>
29class Graph {
30public:
31    using EdgeDataCPtr = const EdgeData *;
32
33private:
34    struct Vertex {
35        enum class Color { WHITE = 0, GREY = 1, BLACK = 2 };
36        Color color = Color::WHITE;
37        VertexId data = VertexId {};
38    };
39    using Vertices = std::vector<Vertex>;
40    using VIdx = size_t;
41    using VColor = typename Vertex::Color;
42    using AdjacencyMatrix = std::vector<std::vector<EdgeDataCPtr>>;
43
44    static constexpr VIdx INVALID_V_IDX = std::numeric_limits<VIdx>::max();
45
46public:
47    // from, to, what
48    using EdgeDef = std::tuple<VertexId, VertexId, EdgeDataCPtr>;
49    using AdjacencyList = std::vector<EdgeDef>;
50    // for pretty printing paths
51    using VertexPrinter = std::function<std::string(VertexId)>;
52    using EdgePrinter = std::function<std::string(EdgeDataCPtr)>;
53
54    struct Path {
55        // vertex0 -> edge0 -> vertex1 -> edge1 -> ...
56        std::vector<VertexId> vertices;
57        std::vector<EdgeDataCPtr> edges;
58        bool IsEmpty()
59        {
60            return vertices.empty();
61        }
62    };
63
64    static constexpr auto defaultVertexPrinter = [](VertexId vid) { return std::to_string(vid); };
65    static constexpr auto DEFAULT_EDGE_PRINTER = []() { return " <- "; };
66
67    explicit Graph(AdjacencyList &&adj)
68    {
69        std::map<VertexId, size_t> vDataPtrToVidx;
70        size_t size = v_.size() > 0 ? v_.size() - 1 : 0;
71        for (auto &edef : adj) {
72            // from
73            auto fromVertexPtr = std::get<0>(edef);
74            if (vDataPtrToVidx.find(fromVertexPtr) == vDataPtrToVidx.end()) {
75                v_.push_back({VColor::WHITE, fromVertexPtr});
76                vDataPtrToVidx[fromVertexPtr] = size;
77            }
78            // to
79            auto toVertexPtr = std::get<1>(edef);
80            if (vDataPtrToVidx.find(toVertexPtr) == vDataPtrToVidx.end()) {
81                v_.push_back({VColor::WHITE, toVertexPtr});
82                vDataPtrToVidx[toVertexPtr] = size;
83            }
84        }
85        // For now let's use an adjacency matrix as the storage.
86        // Will use an adjacency list later on.
87        e_.resize(v_.size());
88        for (auto &row : e_) {
89            row.resize(v_.size());
90            for (auto &eid : row) {
91                eid = nullptr;
92            }
93        }
94        for (auto &edef : adj) {
95            auto fromVertexPtr = std::get<0>(edef);
96            auto toVertexPtr = std::get<1>(edef);
97            auto edgeDataPtr = std::get<2>(edef);
98            e_[vDataPtrToVidx[fromVertexPtr]][vDataPtrToVidx[toVertexPtr]] = edgeDataPtr;
99        }
100    }
101
102    bool IsValid()
103    {
104        // NOTE: maybe its worth to add more detailed verification
105        size_t n = e_.size();
106        if (e_.empty()) {
107            return false;
108        }
109        for (auto &row : e_) {
110            if (row.size() != n) {
111                return false;
112            }
113        }
114        return true;
115    }
116
117    static std::string CycleAsString(Path cycle, std::string prompt = "L: ", std::string terminator = "|",
118                                     VertexPrinter vertexPrinter = defaultVertexPrinter,
119                                     EdgePrinter edgePrinter = DEFAULT_EDGE_PRINTER)
120    {
121        if (cycle.vertices.empty() || cycle.vertices.size() < 1 ||
122            (cycle.edges.size() != (cycle.vertices.size() - 1))) {
123            return "";
124        }
125        std::stringstream result;
126        result << prompt;
127        auto edgeIt = cycle.edges.begin();
128        for (auto vDataPtr : cycle.vertices) {
129            result << vertexPrinter(vDataPtr);
130            if (edgeIt != cycle.edges.end()) {
131                result << edgePrinter(*edgeIt);
132                ++edgeIt;
133            }
134        }
135        result << terminator;
136        return result.str();
137    }
138
139    Path FindFirstCycle()
140    {
141        // verify
142        if (!IsValid()) {
143            return Path {};
144        }
145        // run dfs
146        for (VIdx seedIdx = 0; seedIdx < NumVertices(); ++seedIdx) {
147            if (VertexColor(seedIdx) != Graph::VColor::WHITE) {
148                continue;
149            }
150            Path cycle = RunDfsFromVertex(seedIdx);
151            if (!cycle.vertices.empty()) {
152                return cycle;
153            }
154        }
155        return Path {};
156    }
157
158private:
159    VColor VertexColor(VIdx vidx)
160    {
161        return v_[vidx].color;
162    }
163
164    bool HasEdge(VIdx fromIdx, VIdx toIdx)
165    {
166        return e_[fromIdx][toIdx] != nullptr;
167    }
168
169    size_t NumVertices()
170    {
171        return v_.size();
172    }
173
174    void Mark(VIdx vidx, VColor color)
175    {
176        v_[vidx].color = color;
177    }
178
179    enum class DfsAction { RESTART = 0, FINISH = 1, PROCEED = 2 };
180    struct DfsState {
181        VIdx currentIdx;
182        VIdx childIdx;
183    };
184    using DfsStack = std::stack<DfsState>;
185
186    Path DfsBuildCycleInfo(DfsStack &dfsStack, DfsState state)
187    {
188        Path result;
189        VIdx originIdx = state.childIdx;
190        result.vertices.push_back(v_[state.childIdx].data);
191        result.vertices.push_back(v_[state.currentIdx].data);
192        result.edges.push_back(e_[state.currentIdx][state.childIdx]);
193        VIdx prevIdx = state.currentIdx;
194        while (!dfsStack.empty()) {
195            auto s = dfsStack.top();
196            dfsStack.pop();
197            result.vertices.push_back(v_[s.currentIdx].data);
198            result.edges.push_back(e_[s.currentIdx][prevIdx]);
199            prevIdx = s.currentIdx;
200            if (s.currentIdx == originIdx) {
201                break;
202            }
203        }
204        return result;
205    }
206
207    DfsAction DfsVisitChildren(DfsStack &dfsStack, DfsState &state)
208    {
209        for (; state.childIdx < NumVertices(); ++state.childIdx) {
210            if (HasEdge(state.currentIdx, state.childIdx)) {
211                // the edge v -> child exists
212                if (VertexColor(state.childIdx) == Graph::VColor::BLACK) {
213                    // the child processing is already completed
214                    continue;
215                }
216                if (VertexColor(state.childIdx) == Graph::VColor::GREY) {
217                    // the child is visited: means a cycle has been found
218                    return DfsAction::FINISH;
219                }
220                // the child is "white", i.e. not visited yet: run DFS from it
221                VIdx nextChild = state.childIdx + 1 < NumVertices() ? state.childIdx + 1 : Graph::INVALID_V_IDX;
222                dfsStack.push(DfsState {state.currentIdx, nextChild});
223                state.currentIdx = state.childIdx;
224                state.childIdx = 0;
225                return DfsAction::RESTART;
226            }
227        }
228        state.childIdx = Graph::INVALID_V_IDX;
229        return DfsAction::PROCEED;
230    }
231
232    bool DfsPopState(DfsStack &dfsStack, DfsState &state)
233    {
234        while (!dfsStack.empty()) {
235            state = dfsStack.top();
236            dfsStack.pop();
237            if (state.childIdx != Graph::INVALID_V_IDX) {
238                return true;
239            }
240            Mark(state.currentIdx, Graph::VColor::BLACK);
241        }
242        return false;
243    }
244
245    Path RunDfsFromVertex(VIdx seedVertexIdx)
246    {
247        DfsStack dfsStack;
248        DfsState state {seedVertexIdx, 0};
249        bool areUnprocessedVerticesLeft = true;
250
251        while (areUnprocessedVerticesLeft) {
252            Mark(state.currentIdx, Graph::VColor::GREY);
253            DfsAction a = DfsVisitChildren(dfsStack, state);
254            switch (a) {
255                case DfsAction::FINISH:
256                    return DfsBuildCycleInfo(dfsStack, state);
257                case DfsAction::RESTART:
258                    continue;
259                case DfsAction::PROCEED:
260                default:
261                    break;
262            }
263            Mark(state.currentIdx, Graph::VColor::BLACK);
264            areUnprocessedVerticesLeft = DfsPopState(dfsStack, state);
265        }
266        // no cycles found
267        return Path {};
268    }
269
270    Vertices v_;
271    AdjacencyMatrix e_;
272};
273
274}  // namespace Commonlibrary::Concurrent::LocksModule
275
276#endif
277