| 87 | } |
| 88 | |
| 89 | bool is_cyclic(const std::set<El::Int>& nodes, |
| 90 | const std::map<El::Int, std::set<El::Int>>& edges) |
| 91 | { |
| 92 | |
| 93 | // Check that graph is valid |
| 94 | if (!is_closure(nodes, edges)) { |
| 95 | LBANN_ERROR("graph is not a closure"); |
| 96 | } |
| 97 | |
| 98 | // Topologically sorted graphs are not cyclic |
| 99 | if (is_topologically_sorted(nodes, edges)) { |
| 100 | return false; |
| 101 | } |
| 102 | |
| 103 | // Perform depth-first searches to detect cycles |
| 104 | std::unordered_map<El::Int, bool> is_visited, is_sorted; |
| 105 | std::stack<El::Int> search_stack; |
| 106 | for (auto&& it = nodes.rbegin(); it != nodes.rend(); ++it) { |
| 107 | search_stack.push(*it); |
| 108 | } |
| 109 | while (!search_stack.empty()) { |
| 110 | const auto& node = search_stack.top(); |
| 111 | search_stack.pop(); |
| 112 | if (!is_sorted[node]) { |
| 113 | if (is_visited[node]) { |
| 114 | is_sorted[node] = true; |
| 115 | } |
| 116 | else { |
| 117 | is_visited[node] = true; |
| 118 | search_stack.push(node); |
| 119 | for (const auto& neighbor : get_neighbors(node, edges)) { |
| 120 | if (is_visited[neighbor] && !is_sorted[neighbor]) { |
| 121 | return true; |
| 122 | } |
| 123 | search_stack.push(neighbor); |
| 124 | } |
| 125 | } |
| 126 | } |
| 127 | } |
| 128 | return false; |
| 129 | } |
| 130 | |
| 131 | std::map<El::Int, std::set<El::Int>> |
| 132 | transpose(const std::set<El::Int>& nodes, |
no test coverage detected