| 232 | |
| 233 | template <class RandomIt> |
| 234 | bool findCycle(gnode<RandomIt>& start, std::vector<gnode<RandomIt>>& graph, |
| 235 | std::vector<gnode<RandomIt>>& active, std::vector<gnode<RandomIt>>& loop) |
| 236 | { |
| 237 | if (start.Visited) |
| 238 | { |
| 239 | return false; |
| 240 | } |
| 241 | |
| 242 | // add the current node to active list |
| 243 | active.push_back(start); |
| 244 | |
| 245 | // traverse the closer nodes one by one depth first |
| 246 | for (auto& close : start.Closer) |
| 247 | { |
| 248 | if (close->Visited) |
| 249 | { |
| 250 | continue; |
| 251 | } |
| 252 | |
| 253 | // is the node already in the active list? if so we have a loop |
| 254 | for (auto ait = active.begin(); ait != active.end(); ++ait) |
| 255 | { |
| 256 | if (ait->Value == close->Value) |
| 257 | { |
| 258 | loop.push_back(*ait); |
| 259 | return true; |
| 260 | } |
| 261 | } |
| 262 | // otherwise recurse |
| 263 | if (findCycle(*close, graph, active, loop)) |
| 264 | { |
| 265 | // a loop was detected, build the loop output |
| 266 | loop.push_back(*close); |
| 267 | return true; |
| 268 | } |
| 269 | } |
| 270 | |
| 271 | active.erase(std::find(active.begin(), active.end(), start)); |
| 272 | start.Visited = true; |
| 273 | return false; |
| 274 | } |
| 275 | #endif |
| 276 | |
| 277 | template <class RandomIt, typename T> |