folly/experimental/observer/detail/GraphCycleDetector.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16 #pragma once
  17
  18 #include <unordered_map>
  19 #include <unordered_set>
  20
  21 namespace folly {
  22 namespace observer_detail {
  23
  24 template <typename NodeId>
  25 class GraphCycleDetector {
  26   using NodeSet = std::unordered_set<NodeId>;
  27
  28  public:
  29   /**
  30    * Add new edge. If edge creates a cycle then it's not added and false is
  31    * returned.
  32    */
  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).
  36     NodeSet visitedNodes;
  37     dfs(visitedNodes, to);
  38     if (visitedNodes.count(from)) {
  39       return false;
  40     }
  41
  42     auto& nodes = edges_[from];
  43     DCHECK_EQ(nodes.count(to), 0u);
  44     nodes.insert(to);
  45
  46     return true;
  47   }
  48
  49   void removeEdge(NodeId from, NodeId to) {
  50     auto& nodes = edges_[from];
  51     DCHECK(nodes.count(to));
  52     nodes.erase(to);
  53     if (nodes.empty()) {
  54       edges_.erase(from);
  55     }
  56   }
  57
  58  private:
  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)) {
  63       return;
  64     }
  65
  66     visitedNodes.insert(node);
  67
  68     if (!edges_.count(node)) {
  69       return;
  70     }
  71
  72     for (const auto& to : edges_[node]) {
  73       dfs(visitedNodes, to);
  74     }
  75   }
  76
  77   std::unordered_map<NodeId, NodeSet> edges_;
  78 };
  79 }
  80 }