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 & {
    bool isSelfEdge = (&getDerived() == &targetNode);
    std::lock_guard<std::mutex> lock(edgeMutex);
    if (auto *existing = lookupOutEdge(targetNode); existing != nullptr) {
      return *existing;
    }
    auto edge = std::make_unique<EdgeType>(getDerived(), targetNode);
    auto *edgePtr = edge.get();
    outEdges.emplace_back(std::move(edge));
    insertOutEdgeIndex(&targetNode, edgePtr);
    if (isSelfEdge) {
      inEdges.push_back(edgePtr);
    } else {
      std::lock_guard<std::mutex> lock2(targetNode.edgeMutex);
      targetNode.inEdges.push_back(edgePtr);
    }
    return *edgePtr;
  }

  auto addNewEdge(NodeType &targetNode) -> EdgeType & {
    bool isSelfEdge = (&getDerived() == &targetNode);
    auto edge = std::make_unique<EdgeType>(getDerived(), targetNode);
    auto *edgePtr = edge.get();
    if (isSelfEdge) {
      std::lock_guard<std::mutex> lock(edgeMutex);
      outEdges.emplace_back(std::move(edge));
      // If no entry exists yet (caller went straight to addNewEdge), seed
      // it so a later addEdge dedupes against this edge instead of
      // creating a third parallel one.
      tryInsertOutEdgeIndex(&targetNode, edgePtr);
      inEdges.push_back(edgePtr);
    } else {
      {
        std::lock_guard<std::mutex> lock(edgeMutex);
        outEdges.emplace_back(std::move(edge));
        tryInsertOutEdgeIndex(&targetNode, edgePtr);
      }
      {
        std::lock_guard<std::mutex> lock(targetNode.edgeMutex);
        targetNode.inEdges.push_back(edgePtr);
      }
    }
    return *edgePtr;
  }

  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;
  }

  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;
 
  // 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;
  }

  auto lookupOutEdge(NodeType const &targetNode) -> EdgeType * {
    if (outEdgeIndex != nullptr) {
      auto it = outEdgeIndex->find(&targetNode);
      return it != outEdgeIndex->end() ? it->second : nullptr;
    }
    auto it = std::ranges::find_if(outEdges, [&](OutEdgePtrType const &e) {
      return &e->getTargetNode() == &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->emplace(targetNode, edgePtr);
    } else if (outEdges.size() > outEdgeIndexThreshold) {
      buildOutEdgeIndex();
    }
  }

  void tryInsertOutEdgeIndex(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 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 addNewEdge(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.addNewEdge(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