2 * Copyright 2016-present Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 #include <unordered_map>
19 #include <unordered_set>
22 namespace observer_detail {
24 template <typename NodeId>
25 class GraphCycleDetector {
26 using NodeSet = std::unordered_set<NodeId>;
30 * Add new edge. If edge creates a cycle then it's not added and false is
33 bool addEdge(NodeId from, NodeId to) {
34 // In general case DFS may be expensive here, but in most cases to-node will
35 // have no edges, so it should be O(1).
37 dfs(visitedNodes, to);
38 if (visitedNodes.count(from)) {
42 auto& nodes = edges_[from];
43 DCHECK_EQ(nodes.count(to), 0u);
49 void removeEdge(NodeId from, NodeId to) {
50 auto& nodes = edges_[from];
51 DCHECK(nodes.count(to));
59 void dfs(NodeSet& visitedNodes, NodeId node) {
60 // We don't terminate early if cycle is detected, because this is considered
61 // an error condition, so not worth optimizing for.
62 if (visitedNodes.count(node)) {
66 visitedNodes.insert(node);
68 if (!edges_.count(node)) {
72 for (const auto& to : edges_[node]) {
73 dfs(visitedNodes, to);
77 std::unordered_map<NodeId, NodeSet> edges_;
79 } // namespace observer_detail