Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: GDAL
4 : * Purpose: Implementation of topologic sorting over a directed acyclic graph
5 : * Author: Even Rouault
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2021, Even Rouault <even dot rouault at spatialys dot com>
9 : *
10 : * Permission is hereby granted, free of charge, to any person obtaining a
11 : * copy of this software and associated documentation files (the "Software"),
12 : * to deal in the Software without restriction, including without limitation
13 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 : * and/or sell copies of the Software, and to permit persons to whom the
15 : * Software is furnished to do so, subject to the following conditions:
16 : *
17 : * The above copyright notice and this permission notice shall be included
18 : * in all copies or substantial portions of the Software.
19 : *
20 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 : * DEALINGS IN THE SOFTWARE.
27 : ****************************************************************************/
28 :
29 : #ifndef DIRECTEDACYCLICGRAPH_INCLUDED_H
30 : #define DIRECTEDACYCLICGRAPH_INCLUDED_H
31 :
32 : #include <algorithm>
33 : #include <list>
34 : #include <map>
35 : #include <set>
36 : #include <stack>
37 : #include <string>
38 : #include <vector>
39 :
40 : #include <cassert>
41 :
42 : namespace gdal
43 : {
44 :
45 : // See https://en.wikipedia.org/wiki/Directed_acyclic_graph
46 : template <class T, class V = std::string> class DirectedAcyclicGraph
47 : {
48 : std::set<T> nodes{};
49 : std::map<T, std::set<T>>
50 : incomingNodes{}; // incomingNodes[j][i] means an edge from i to j
51 : std::map<T, std::set<T>>
52 : outgoingNodes{}; // outgoingNodes[i][j] means an edge from i to j
53 : std::map<T, V> names{};
54 :
55 : public:
56 1251 : DirectedAcyclicGraph() = default;
57 :
58 : void clear()
59 : {
60 : nodes.clear();
61 : incomingNodes.clear();
62 : outgoingNodes.clear();
63 : names.clear();
64 : }
65 :
66 4670 : void addNode(const T &i, const V &s)
67 : {
68 4670 : nodes.insert(i);
69 4670 : names[i] = s;
70 4670 : }
71 :
72 : void removeNode(const T &i);
73 : const char *addEdge(const T &i, const T &j);
74 : const char *removeEdge(const T &i, const T &j);
75 : bool isTherePathFromTo(const T &i, const T &j) const;
76 : std::vector<T> findStartingNodes() const;
77 : std::vector<T> getTopologicalOrdering();
78 : };
79 :
80 : template <class T, class V>
81 2 : void DirectedAcyclicGraph<T, V>::removeNode(const T &i)
82 : {
83 2 : nodes.erase(i);
84 2 : names.erase(i);
85 :
86 : {
87 2 : auto incomingIter = incomingNodes.find(i);
88 2 : if (incomingIter != incomingNodes.end())
89 : {
90 4 : for (const T &j : incomingIter->second)
91 : {
92 2 : auto outgoingIter = outgoingNodes.find(j);
93 2 : assert(outgoingIter != outgoingNodes.end());
94 2 : auto iterJI = outgoingIter->second.find(i);
95 2 : assert(iterJI != outgoingIter->second.end());
96 2 : outgoingIter->second.erase(iterJI);
97 2 : if (outgoingIter->second.empty())
98 2 : outgoingNodes.erase(outgoingIter);
99 : }
100 2 : incomingNodes.erase(incomingIter);
101 : }
102 : }
103 :
104 : {
105 2 : auto outgoingIter = outgoingNodes.find(i);
106 2 : if (outgoingIter != outgoingNodes.end())
107 : {
108 0 : for (const T &j : outgoingIter->second)
109 : {
110 0 : auto incomingIter = incomingNodes.find(j);
111 0 : assert(incomingIter != incomingNodes.end());
112 0 : auto iterJI = incomingIter->second.find(i);
113 0 : assert(iterJI != incomingIter->second.end());
114 0 : incomingIter->second.erase(iterJI);
115 0 : if (incomingIter->second.empty())
116 0 : incomingNodes.erase(incomingIter);
117 : }
118 0 : outgoingNodes.erase(outgoingIter);
119 : }
120 : }
121 2 : }
122 :
123 : template <class T, class V>
124 2251 : const char *DirectedAcyclicGraph<T, V>::addEdge(const T &i, const T &j)
125 : {
126 2251 : if (i == j)
127 : {
128 2 : return "self cycle";
129 : }
130 2249 : const auto iterI = outgoingNodes.find(i);
131 3821 : if (iterI != outgoingNodes.end() &&
132 3821 : iterI->second.find(j) != iterI->second.end())
133 : {
134 1510 : return "already inserted edge";
135 : }
136 :
137 739 : if (nodes.find(i) == nodes.end())
138 : {
139 0 : return "node i unknown";
140 : }
141 739 : if (nodes.find(j) == nodes.end())
142 : {
143 0 : return "node j unknown";
144 : }
145 :
146 739 : if (isTherePathFromTo(j, i))
147 : {
148 40 : return "can't add edge: this would cause a cycle";
149 : }
150 :
151 699 : outgoingNodes[i].insert(j);
152 699 : incomingNodes[j].insert(i);
153 699 : return nullptr;
154 : }
155 :
156 : template <class T, class V>
157 697 : const char *DirectedAcyclicGraph<T, V>::removeEdge(const T &i, const T &j)
158 : {
159 697 : auto iterI = outgoingNodes.find(i);
160 697 : if (iterI == outgoingNodes.end())
161 0 : return "no outgoing nodes from i";
162 697 : auto iterIJ = iterI->second.find(j);
163 697 : if (iterIJ == iterI->second.end())
164 0 : return "no outgoing node from i to j";
165 697 : iterI->second.erase(iterIJ);
166 697 : if (iterI->second.empty())
167 672 : outgoingNodes.erase(iterI);
168 :
169 697 : auto iterJ = incomingNodes.find(j);
170 697 : assert(iterJ != incomingNodes.end());
171 697 : auto iterJI = iterJ->second.find(i);
172 697 : assert(iterJI != iterJ->second.end());
173 697 : iterJ->second.erase(iterJI);
174 697 : if (iterJ->second.empty())
175 673 : incomingNodes.erase(iterJ);
176 :
177 697 : return nullptr;
178 : }
179 :
180 : template <class T, class V>
181 739 : bool DirectedAcyclicGraph<T, V>::isTherePathFromTo(const T &i, const T &j) const
182 : {
183 1478 : std::set<T> plannedForVisit;
184 1478 : std::stack<T> toVisit;
185 739 : toVisit.push(i);
186 739 : plannedForVisit.insert(i);
187 1612 : while (!toVisit.empty())
188 : {
189 913 : const T n = toVisit.top();
190 913 : toVisit.pop();
191 913 : if (n == j)
192 40 : return true;
193 873 : const auto iter = outgoingNodes.find(n);
194 873 : if (iter != outgoingNodes.end())
195 : {
196 384 : for (const T &k : iter->second)
197 : {
198 211 : if (plannedForVisit.find(k) == plannedForVisit.end())
199 : {
200 175 : plannedForVisit.insert(k);
201 175 : toVisit.push(k);
202 : }
203 : }
204 : }
205 : }
206 699 : return false;
207 : }
208 :
209 : template <class T, class V>
210 612 : std::vector<T> DirectedAcyclicGraph<T, V>::findStartingNodes() const
211 : {
212 612 : std::vector<T> ret;
213 1622 : for (const auto &i : nodes)
214 : {
215 1010 : if (incomingNodes.find(i) == incomingNodes.end())
216 337 : ret.emplace_back(i);
217 : }
218 612 : return ret;
219 : }
220 :
221 : // Kahn's algorithm:
222 : // https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
223 : template <class T, class V>
224 612 : std::vector<T> DirectedAcyclicGraph<T, V>::getTopologicalOrdering()
225 : {
226 612 : std::vector<T> ret;
227 612 : ret.reserve(nodes.size());
228 :
229 722 : const auto cmp = [this](const T &a, const T &b)
230 55 : { return names.find(a)->second < names.find(b)->second; };
231 1224 : std::set<T, decltype(cmp)> S(cmp);
232 :
233 1224 : const auto sn = findStartingNodes();
234 949 : for (const auto &i : sn)
235 337 : S.insert(i);
236 :
237 1010 : while (true)
238 : {
239 1622 : auto iterFirst = S.begin();
240 1622 : if (iterFirst == S.end())
241 612 : break;
242 1010 : const auto n = *iterFirst;
243 1010 : S.erase(iterFirst);
244 1010 : ret.emplace_back(n);
245 :
246 1010 : const auto iter = outgoingNodes.find(n);
247 1010 : if (iter != outgoingNodes.end())
248 : {
249 : // Need to take a copy as we remove edges during iteration
250 1344 : const std::set<T> myOutgoingNodes = iter->second;
251 1369 : for (const T &m : myOutgoingNodes)
252 : {
253 697 : const char *retRemoveEdge = removeEdge(n, m);
254 : (void)retRemoveEdge;
255 697 : assert(retRemoveEdge == nullptr);
256 697 : if (incomingNodes.find(m) == incomingNodes.end())
257 : {
258 673 : S.insert(m);
259 : }
260 : }
261 : }
262 : }
263 :
264 : // Should not happen for a direct acyclic graph
265 612 : assert(incomingNodes.empty());
266 612 : assert(outgoingNodes.empty());
267 :
268 1224 : return ret;
269 : }
270 :
271 : } // namespace gdal
272 :
273 : #endif // DIRECTEDACYCLICGRAPH_INCLUDED_H
|
