folly::observer_detail::GraphCycleDetector< NodeId > Class Template Reference

#include <GraphCycleDetector.h>

Public Member Functions
bool	addEdge (NodeId from, NodeId to)
void	removeEdge (NodeId from, NodeId to)

Private Types
using	NodeSet = std::unordered_set< NodeId >

Private Member Functions
void	dfs (NodeSet &visitedNodes, NodeId node)

Private Attributes
std::unordered_map< NodeId, NodeSet >	edges_

Detailed Description

template<typename NodeId>
class folly::observer_detail::GraphCycleDetector< NodeId >

Definition at line 27 of file GraphCycleDetector.h.

Member Typedef Documentation

template<typename NodeId >

using folly::observer_detail::GraphCycleDetector< NodeId >::NodeSet = std::unordered_set<NodeId>

private

Definition at line 28 of file GraphCycleDetector.h.

Member Function Documentation

template<typename NodeId >

bool folly::observer_detail::GraphCycleDetector< NodeId >::addEdge ( NodeId  from, NodeId  to  )

inline

Add new edge. If edge creates a cycle then it's not added and false is returned.

Definition at line 35 of file GraphCycleDetector.h.

References folly::observer_detail::GraphCycleDetector< NodeId >::dfs(), folly::observer_detail::GraphCycleDetector< NodeId >::edges_, and folly::pushmi::operators::from.

Referenced by folly::observer_detail::ObserverManager::DependencyRecorder::markRefreshDependency().

                                       {
    // In general case DFS may be expensive here, but in most cases to-node will
    // have no edges, so it should be O(1).
    NodeSet visitedNodes;
    dfs(visitedNodes, to);
    if (visitedNodes.count(from)) {
      return false;
    }

    auto& nodes = edges_[from];
    DCHECK_EQ(nodes.count(to), 0u);
    nodes.insert(to);

    return true;
  }

template<typename NodeId >

void folly::observer_detail::GraphCycleDetector< NodeId >::dfs ( NodeSet &  visitedNodes, NodeId  node  )

inlineprivate

Definition at line 61 of file GraphCycleDetector.h.

References folly::observer_detail::GraphCycleDetector< NodeId >::edges_, and folly::to().

Referenced by folly::observer_detail::GraphCycleDetector< NodeId >::addEdge().

                                               {
    // We don't terminate early if cycle is detected, because this is considered
    // an error condition, so not worth optimizing for.
    if (visitedNodes.count(node)) {
      return;
    }

    visitedNodes.insert(node);

    if (!edges_.count(node)) {
      return;
    }

    for (const auto& to : edges_[node]) {
      dfs(visitedNodes, to);
    }
  }

template<typename NodeId >

void folly::observer_detail::GraphCycleDetector< NodeId >::removeEdge ( NodeId  from, NodeId  to  )

inline

Definition at line 51 of file GraphCycleDetector.h.

References folly::observer_detail::GraphCycleDetector< NodeId >::edges_, and folly::pushmi::operators::from.

Referenced by folly::observer_detail::ObserverManager::DependencyRecorder::unmarkRefreshDependency().

                                          {
    auto& nodes = edges_[from];
    DCHECK(nodes.count(to));
    nodes.erase(to);
    if (nodes.empty()) {
      edges_.erase(from);
    }
  }

Member Data Documentation

template<typename NodeId >

std::unordered_map<NodeId, NodeSet> folly::observer_detail::GraphCycleDetector< NodeId >::edges_

private

Definition at line 79 of file GraphCycleDetector.h.

Referenced by folly::observer_detail::GraphCycleDetector< NodeId >::addEdge(), folly::observer_detail::GraphCycleDetector< NodeId >::dfs(), and folly::observer_detail::GraphCycleDetector< NodeId >::removeEdge().

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/experimental/observer/detail/GraphCycleDetector.h