DirectedGraph.hpp

Go to the documentation of this file.

#pragma once
 
#include <algorithm>
#include <cassert>
#include <limits>
#include <memory>
#include <mutex>
#include <vector>
 
#include "slang/util/FlatMap.h"
 
namespace slang::netlist {

template <class NodeType, class EdgeType> class DirectedEdge {
public:
  DirectedEdge(NodeType &sourceNode, NodeType &targetNode)
      : sourceNode(sourceNode), targetNode(targetNode) {}
 
  auto operator=(const DirectedEdge<NodeType, EdgeType> &edge)
      -> DirectedEdge<NodeType, EdgeType> & = default;

  friend auto operator==(const EdgeType &A, const EdgeType &B) noexcept
      -> bool {
    return A.getDerived().isEqualTo(B);
  }
  auto operator==(const EdgeType &E) const -> bool {
    return getDerived().isEqualTo(E);
  }

  auto getSourceNode() const -> NodeType & { return sourceNode; }

  auto getTargetNode() const -> NodeType & { return targetNode; }
 
protected:
  // As the default implementation use address comparison for equality.
  auto isEqualTo(const EdgeType &edge) const -> bool { return this == &edge; }
 
  // Cast the 'this' pointer to the derived type and return a reference.
  auto getDerived() -> EdgeType & { return *static_cast<EdgeType *>(this); }
  auto getDerived() const -> const EdgeType & {
    return *static_cast<const EdgeType *>(this);
  }
 
  NodeType &sourceNode;
  NodeType &targetNode;
};

template <class NodeType, class EdgeType> class Node {
public:
  using OutEdgePtrType = std::unique_ptr<EdgeType>;
  using OutEdgeListType = std::vector<OutEdgePtrType>;
  using InEdgeListType = std::vector<EdgeType *>;
  using iterator = typename OutEdgeListType::iterator;
  using const_iterator = typename OutEdgeListType::const_iterator;
  using in_iterator = typename InEdgeListType::iterator;
  using const_in_iterator = typename InEdgeListType::const_iterator;
  using edge_descriptor = EdgeType *;
 
  Node() = default;
  virtual ~Node() = default;
 
  // Non-copyable/non-movable: edgeMutex is not movable.
  Node(const Node &) = delete;
  Node(Node &&) = delete;
  auto operator=(const Node &) -> Node & = delete;
  auto operator=(Node &&) -> Node & = delete;
 
  // Iterator methods for outgoing edges.
  auto begin() const -> const_iterator { return outEdges.begin(); }
  auto end() const -> const_iterator { return outEdges.end(); }
  auto begin() -> iterator { return outEdges.begin(); }
  auto end() -> iterator { return outEdges.end(); }
 
  // Iterator methods for incoming edges.
  auto inBegin() -> in_iterator { return inEdges.begin(); }
  auto inEnd() -> in_iterator { return inEdges.end(); }
  auto inBegin() const -> const_in_iterator { return inEdges.begin(); }
  auto inEnd() const -> const_in_iterator { return inEdges.end(); }

  friend auto operator==(NodeType const &A, NodeType const &B) noexcept
      -> bool {
    return A.getDerived().isEqualTo(B);
  }
 
  auto operator==(const NodeType &N) const -> bool {
    return getDerived().isEqualTo(N);
  }

  auto findEdgeFrom(const NodeType &sourceNode) -> in_iterator {
    return std::ranges::find_if(inEdges, [&](EdgeType *e) {
      return &e->getSourceNode() == &sourceNode;
    });
  }

  auto findEdgeFrom(const NodeType &sourceNode) const -> const_in_iterator {
    return std::ranges::find_if(inEdges, [&](EdgeType const *e) {
      return &e->getSourceNode() == &sourceNode;
    });
  }

  auto findEdgeTo(const NodeType &targetNode) -> iterator {
    return std::ranges::find_if(outEdges, [&](OutEdgePtrType const &e) {
      return &e->getTargetNode() == &targetNode;
    });
  }

  auto findEdgeTo(const NodeType &targetNode) const -> const_iterator {
    return std::ranges::find_if(outEdges, [&](OutEdgePtrType const &e) {
      return &e->getTargetNode() == &targetNode;
    });
  }

  auto addEdge(NodeType &targetNode) -> EdgeType & {
    return withEndpointsLocked(targetNode, [&] {
      parallelOutEdges = true;
      return appendEdge(targetNode);
    });
  }

  auto getOrAddEdge(NodeType &targetNode) -> EdgeType & {
    return withEndpointsLocked(targetNode, [&] {
      if (auto *existing = lookupOutEdge(targetNode); existing != nullptr) {
        return existing;
      }
      return appendEdge(targetNode);
    });
  }

  auto removeEdge(NodeType &targetNode) -> bool {
    auto edgeIt = findEdgeTo(targetNode);
    if (edgeIt != outEdges.end()) {
      auto success = targetNode.removeInEdge(getDerived());
      assert(success && "No corresponding in edge reference");
      outEdges.erase(edgeIt);
      // Re-point or drop the index entry: a parallel edge to the same
      // target may still survive in outEdges.
      if (outEdgeIndex != nullptr) {
        auto survivor = std::ranges::find_if(outEdges, [&](auto &e) {
          return &e->getTargetNode() == &targetNode;
        });
        if (survivor == outEdges.end()) {
          outEdgeIndex->erase(&targetNode);
        } else {
          (*outEdgeIndex)[&targetNode] = survivor->get();
        }
      }
      return success;
    }
    return false;
  }

  auto mayHaveParallelOutEdges() const -> bool { return parallelOutEdges; }

  template <typename Predicate> void removeOutEdgesIf(Predicate pred) {
    std::vector<NodeType *> targets;
    for (auto const &edge : outEdges) {
      if (pred(*edge)) {
        targets.push_back(&edge->getTargetNode());
      }
    }
    if (targets.empty()) {
      return;
    }
    // Visit each target once, however many of its in-edges are going.
    std::ranges::sort(targets);
    targets.erase(std::ranges::unique(targets).begin(), targets.end());
    auto *self = &getDerived();
    for (auto *target : targets) {
      std::erase_if(target->inEdges, [&](EdgeType *edge) {
        return &edge->getSourceNode() == self && pred(*edge);
      });
    }
    std::erase_if(outEdges,
                  [&](OutEdgePtrType const &edge) { return pred(*edge); });
    if (outEdgeIndex != nullptr) {
      buildOutEdgeIndex();
    }
  }

  void clearAllEdges() {
    // Remove outgoing edges.
    for (auto &edge : outEdges) {
      edge->getTargetNode().removeInEdge(getDerived());
    }
    outEdges.clear();
    outEdgeIndex.reset();
    // Remove incoming edges, creating a temporary list to avoid
    // invalidating the iterator.
    std::vector<NodeType *> sourceNodes;
    for (auto &edge : inEdges) {
      sourceNodes.push_back(&edge->getSourceNode());
    }
    for (auto *sourceNode : sourceNodes) {
      sourceNode->removeEdge(getDerived());
    }
    assert(inEdges.empty());
  }

  auto getEdgesTo(const NodeType &targetNode, std::vector<EdgeType *> &result)
      -> bool {
    assert(result.empty() && "Expected the results parameter to be empty");
    for (auto &edge : outEdges) {
      if (edge->getTargetNode() == targetNode) {
        result.push_back(edge.get());
      }
    }
    return !result.empty();
  }

  auto getInEdges() const -> const InEdgeListType & { return inEdges; }
  auto getOutEdges() const -> const OutEdgeListType & { return outEdges; }

  auto inDegree() const -> size_t { return inEdges.size(); }

  auto outDegree() const -> size_t { return outEdges.size(); }
 
protected:
  mutable std::mutex edgeMutex;
 
  InEdgeListType inEdges;
  OutEdgeListType outEdges;

  using OutEdgeIndex = flat_hash_map<NodeType const *, EdgeType *>;
  std::unique_ptr<OutEdgeIndex> outEdgeIndex;

  static constexpr size_t outEdgeIndexThreshold = 16;

  bool parallelOutEdges{false};
 
  // As the default implementation use address comparison for equality.
  auto isEqualTo(const NodeType &node) const -> bool { return this == &node; }
 
  // Cast the 'this' pointer to the derived type and return a reference.
  auto getDerived() -> NodeType & { return *static_cast<NodeType *>(this); }
  auto getDerived() const -> const NodeType & {
    return *static_cast<const NodeType *>(this);
  }
 
private:
  auto removeInEdge(NodeType &sourceNode) -> bool {
    auto edgeIt = findEdgeFrom(sourceNode);
    if (edgeIt != inEdges.end()) {
      inEdges.erase(edgeIt);
      return true;
    }
    return false;
  }

  template <typename Fn>
  auto withEndpointsLocked(NodeType &targetNode, Fn fn) -> EdgeType & {
    if (&getDerived() == &targetNode) {
      std::lock_guard<std::mutex> lock(edgeMutex);
      return *fn();
    }
    std::scoped_lock lock(edgeMutex, targetNode.edgeMutex);
    return *fn();
  }

  auto appendEdge(NodeType &targetNode) -> EdgeType * {
    auto edge = std::make_unique<EdgeType>(getDerived(), targetNode);
    auto *edgePtr = edge.get();
    outEdges.emplace_back(std::move(edge));
    insertOutEdgeIndex(&targetNode, edgePtr);
    targetNode.inEdges.push_back(edgePtr);
    return edgePtr;
  }

  auto lookupOutEdge(NodeType const &targetNode) -> EdgeType * {
    if (outEdgeIndex != nullptr) {
      auto it = outEdgeIndex->find(&targetNode);
      return it != outEdgeIndex->end() ? it->second : nullptr;
    }
    auto it = findEdgeTo(targetNode);
    return it != outEdges.end() ? it->get() : nullptr;
  }

  void buildOutEdgeIndex() {
    outEdgeIndex = std::make_unique<OutEdgeIndex>();
    outEdgeIndex->reserve(outEdges.size());
    for (auto &e : outEdges) {
      outEdgeIndex->try_emplace(&e->getTargetNode(), e.get());
    }
  }

  void insertOutEdgeIndex(NodeType const *targetNode, EdgeType *edgePtr) {
    if (outEdgeIndex != nullptr) {
      outEdgeIndex->try_emplace(targetNode, edgePtr);
    } else if (outEdges.size() > outEdgeIndexThreshold) {
      buildOutEdgeIndex();
    }
  }
};

template <class NodeType, class EdgeType> class DirectedGraph {
public:
  using NodePtrType = std::unique_ptr<NodeType>;
  using NodeListType = std::vector<NodePtrType>;
  using iterator = typename NodeListType::iterator;
  using const_iterator = typename NodeListType::const_iterator;
  using node_descriptor = size_t;
  using edge_descriptor = EdgeType *;
  using DirectedGraphType = DirectedGraph<NodeType, EdgeType>;
 
  static const size_t null_node = std::numeric_limits<size_t>::max();
 
  DirectedGraph() = default;
 
  auto begin() const -> const_iterator { return nodes.begin(); }
  auto end() const -> const_iterator { return nodes.end(); }
  auto begin() -> iterator { return nodes.begin(); }
  auto end() -> iterator { return nodes.end(); }
 
  auto findNode(const NodeType &nodeToFind) const -> node_descriptor {
    auto it =
        std::ranges::find_if(nodes, [&nodeToFind](const NodePtrType &node) {
          return const_cast<const NodeType &>(*node) == nodeToFind;
        });
    if (it != nodes.end()) {
      return it - nodes.begin();
    }
    return null_node;
  }

  auto getNode(node_descriptor node) const -> NodeType & {
    assert(node < nodes.size() && "Node does not exist");
    return *nodes[node];
  }

  auto addNode() -> NodeType & {
    std::lock_guard<std::mutex> lock(nodesMutex);
    nodes.push_back(std::make_unique<NodeType>());
    return *(nodes.back().get());
  }

  auto addNode(std::unique_ptr<NodeType> node) -> NodeType & {
    std::lock_guard<std::mutex> lock(nodesMutex);
    nodes.push_back(std::move(node));
    return *(nodes.back().get());
  }

  auto removeNode(NodeType &nodeToRemove) -> bool {
    auto nodeToRemoveDesc = findNode(nodeToRemove);
    if (nodeToRemoveDesc >= nodes.size()) {
      // The node is not in the graph.
      return false;
    }
    // Remove all edges to and from the node for removal.
    nodeToRemove.clearAllEdges();
    // Remove the node itself.
    nodes.erase(std::ranges::next(nodes.begin(), nodeToRemoveDesc));
    return true;
  }

  auto getOrAddEdge(NodeType &sourceNode, NodeType &targetNode) -> EdgeType & {
    assert(findNode(sourceNode) < nodes.size() && "Source node does not exist");
    assert(findNode(targetNode) < nodes.size() && "Target node does not exist");
    return sourceNode.getOrAddEdge(targetNode);
  }

  auto addEdge(NodeType &sourceNode, NodeType &targetNode) -> EdgeType & {
    assert(findNode(sourceNode) < nodes.size() && "Source node does not exist");
    assert(findNode(targetNode) < nodes.size() && "Target node does not exist");
    return sourceNode.addEdge(targetNode);
  }

  auto removeEdge(NodeType &sourceNode, NodeType &targetNode) -> bool {
    assert(findNode(sourceNode) < nodes.size() && "Source node does not exist");
    assert(findNode(targetNode) < nodes.size() && "Target node does not exist");
    return sourceNode.removeEdge(targetNode);
  }

  auto outDegree(const NodeType &node) const -> size_t {
    assert(findNode(node) < nodes.size() && "Node does not exist");
    return node.outDegree();
  }

  auto inDegree(const NodeType &node) const -> size_t {
    assert(findNode(node) < nodes.size() && "Node does not exist");
    return node.inDegree();
  }

  auto numNodes() const -> size_t { return nodes.size(); }

  auto numEdges() const -> size_t {
    size_t count = 0;
    for (auto &node : nodes) {
      count += node->outDegree();
    }
    return count;
  }
 
protected:
  mutable std::mutex nodesMutex;
 
  NodeListType nodes;
};
 
} // namespace slang::netlist