cycle_test.h

Go to the documentation of this file.

// NIST-developed software is provided by NIST as a public service. You may use, copy and distribute copies of the
// software in any medium, provided that you keep intact this entire notice. You may improve, modify and create
// derivative works of the software or any portion of the software, and you may copy and distribute such modifications
// or works. Modified works should carry a notice stating that you changed the software and should note the date and
// nature of any such change. Please explicitly acknowledge the National Institute of Standards and Technology as the
// source of the software. NIST-developed software is expressly provided "AS IS." NIST MAKES NO WARRANTY OF ANY KIND,
// EXPRESS, IMPLIED, IN FACT OR ARISING BY OPERATION OF LAW, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTY OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, NON-INFRINGEMENT AND DATA ACCURACY. NIST NEITHER REPRESENTS NOR
// WARRANTS THAT THE OPERATION OF THE SOFTWARE WILL BE UNINTERRUPTED OR ERROR-FREE, OR THAT ANY DEFECTS WILL BE
// CORRECTED. NIST DOES NOT WARRANT OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF THE SOFTWARE OR THE RESULTS
// THEREOF, INCLUDING BUT NOT LIMITED TO THE CORRECTNESS, ACCURACY, RELIABILITY, OR USEFULNESS OF THE SOFTWARE. You
// are solely responsible for determining the appropriateness of using and distributing the software and you assume
// all risks associated with its use, including but not limited to the risks and costs of program errors, compliance
// with applicable laws, damage to or loss of data, programs or equipment, and the unavailability or interruption of
// operation. This software is not intended to be used in any situation where a failure could cause risk of injury or
// damage to property. The software developed by NIST employees is not subject to copyright protection within the
// United States.
 
#ifndef HEDGEHOG_CYCLE_TEST_H_
#define HEDGEHOG_CYCLE_TEST_H_
 
#ifdef HH_ENABLE_HH_CX
#include "abstract_test.h"
 
namespace hh_cx {
 
template<tool::HedgehogDynamicGraphForStaticAnalysis GraphType>
class CycleTest : public hh_cx::AbstractTest<GraphType> {
  class SimpleSubGraph {
    using pointer_const_abstract_node = hh_cx::behavior::AbstractNode const *;
 
    std::vector<pointer_const_abstract_node>
        registeredNodes_{}; 
 
    std::vector<std::vector<bool>>
        adjacencyMatrix_{}; 
 
   public:
    constexpr SimpleSubGraph() = default;
 
    constexpr SimpleSubGraph(hh_cx::Graph<GraphType> const *graph, size_t minNodeId) {
      for (size_t nodeIdSrc = minNodeId; nodeIdSrc < graph->numberNodesRegistered(); ++nodeIdSrc) {
        for (size_t nodeIdDest = minNodeId; nodeIdDest < graph->numberNodesRegistered(); ++nodeIdDest) {
          if (graph->isLinked(nodeIdSrc, nodeIdDest)) {
            this->addEdge(graph->node(nodeIdSrc), graph->node(nodeIdDest));
          }
        }
      }
    }
 
    virtual ~SimpleSubGraph() = default;
 
    [[nodiscard]] constexpr std::vector<pointer_const_abstract_node> const &registeredNodes() const {
      return registeredNodes_;
    }
 
    [[nodiscard]] constexpr size_t numberNodes() const { return registeredNodes_.size(); }
 
    [[nodiscard]] constexpr std::vector<pointer_const_abstract_node>
    adjacentNodes(pointer_const_abstract_node origin) const {
      std::vector<pointer_const_abstract_node> adjacentNodes{};
      auto senderId = nodeId(origin);
      for (size_t receiverId = 0; receiverId < numberNodes(); ++receiverId) {
        if (isLinked(senderId, receiverId)) {
          adjacentNodes.push_back(node(receiverId));
        }
      }
      return adjacentNodes;
    }
 
    [[nodiscard]] constexpr size_t numberNodesRegistered() const { return registeredNodes_.size(); }
 
    [[nodiscard]] constexpr bool isLinked(pointer_const_abstract_node sender,
                                          pointer_const_abstract_node receiver) const {
      auto
          idSender = nodeId(sender),
          idReceiver = nodeId(receiver);
 
      if (idSender == numberNodes() || idReceiver == numberNodes()) { return false; }
      return adjacencyMatrix_[idSender][idReceiver];
    }
 
    [[nodiscard]] constexpr bool isLinked(size_t idSender, size_t idReceiver) const {
      if (idSender >= numberNodes() || idReceiver >= numberNodes()) {
        throw (std::runtime_error("The nodes you are trying to test do not exist in the graph."));
      }
      return adjacencyMatrix_[idSender][idReceiver];
    }
 
    [[nodiscard]]  constexpr size_t nodeId(pointer_const_abstract_node node) const {
      if (!isNodeRegistered(node)) {
        throw (std::runtime_error("The node you are trying to get does not exist in the graph."));
      }
      size_t nodeId = 0;
      for (auto registeredNode : registeredNodes_) {
        if (registeredNode == node) { return nodeId; }
        else { ++nodeId; }
      }
      return nodeId;
    }
 
    [[nodiscard]] constexpr pointer_const_abstract_node node(size_t id) const {
      if (id >= registeredNodes_.size()) {
        throw (std::runtime_error("The node you are requesting does not exist."));
      } else {
        return registeredNodes_.at(id);
      }
    }
 
    constexpr void addEdge(pointer_const_abstract_node sender, pointer_const_abstract_node receiver) {
      registerNode(sender);
      registerNode(receiver);
      adjacencyMatrix_.at(nodeId(sender)).at(nodeId(receiver)) = true;
    }
   private:
    constexpr bool isNodeRegistered(pointer_const_abstract_node node) const {
      return std::find(registeredNodes_.cbegin(), registeredNodes_.cend(), node) != registeredNodes_.cend();
    }
 
    constexpr void registerNode(pointer_const_abstract_node node) {
      if (!isNodeRegistered(node)) { registeredNodes_.push_back(node); }
      for (auto &line : adjacencyMatrix_) {
        line.push_back(false);
      }
      adjacencyMatrix_.emplace_back(adjacencyMatrix_.size() + 1, false);
    }
  };
 
  std::vector<size_t>
      tarjanNodeNumbers_{}, 
  tarjanLowLink_{}; 
 
  std::vector<bool>
      tarjanIsOnStack_{}, 
  johnsonBlockedSetArray_{}; 
 
  std::vector<hh_cx::behavior::AbstractNode const *>
      tarjanStack_{}, 
  johnsonStack_{}; 
 
  std::vector<std::vector<hh_cx::behavior::AbstractNode const *>>
      tarjanConnectedComponent_{}, 
  johnsonCycles_{}, 
  johnsonBlockedMap_{}; 
 
  size_t
      numberOfNodes_{}; 
 public:
  constexpr explicit CycleTest() : AbstractTest<GraphType>("Cycle test") {}
 
  constexpr ~CycleTest() override = default;
 
  constexpr void test(hh_cx::Graph<GraphType> const *graph) override {
    numberOfNodes_ = graph->numberNodesRegistered();
    findAllCycles(graph);
    removeCyclesWhereNodesRedefineCanTerminate();
    if (johnsonCycles_.empty()) {
      this->graphValid(true);
    } else {
      this->graphValid(false);
      this->appendErrorMessage("Cycles found, the canTerminate() method needs to be defined for each of these cycles.");
      for (const auto &cycle : johnsonCycles_) {
        this->appendErrorMessage("\n\t");
        auto origin = cycle.at(0);
        for (const auto &node : cycle) {
          this->appendErrorMessage(node->name());
          this->appendErrorMessage(" -> ");
        }
        this->appendErrorMessage(origin->name());
      }
    }
  }
 
 private:
  constexpr void findAllCycles(hh_cx::Graph<GraphType> const *graph) {
    size_t startIndex = 0;
    while (startIndex < graph->numberNodesRegistered()) {
      initTarjan();
      SimpleSubGraph subGraph(graph, startIndex);
      tarjanAllStrongConnect(subGraph);
 
      auto [leastIndex, minSubGraph] = leastIndexStrongConnectedComponents(subGraph);
 
      if (leastIndex == numberOfNodes_) {
        break;
      } else {
        initJohnson();
        auto node = subGraph.node(leastIndex);
        findCyclesInSCC(node, node, minSubGraph);
        ++startIndex;
      }
    }
  }
 
  constexpr void initTarjan() {
    tarjanNodeNumbers_ = std::vector<size_t>(numberOfNodes_);
    tarjanLowLink_ = std::vector<size_t>(numberOfNodes_);
    tarjanIsOnStack_ = std::vector<bool>(numberOfNodes_, false);
    tarjanStack_.clear();
    tarjanConnectedComponent_.clear();
  }
 
  constexpr void initJohnson() {
    johnsonStack_.clear();
    johnsonBlockedSetArray_ = std::vector<bool>(numberOfNodes_, false);
    for (size_t nodeId = 0; nodeId < numberOfNodes_; ++nodeId) {
      johnsonBlockedMap_.emplace_back();
    }
  }
 
  constexpr void tarjanAllStrongConnect(SimpleSubGraph const &subGraph) {
    size_t num = 1;
    for (size_t nodeId = 0; nodeId < subGraph.numberNodesRegistered(); ++nodeId) {
      if (tarjanNodeNumbers_[nodeId] == 0) { tarjanStrongConnect(num, nodeId, subGraph); }
    }
  }
 
  constexpr void tarjanStrongConnect(size_t &num, size_t &nodeId, SimpleSubGraph const &subGraph) {
    auto node = subGraph.node(nodeId);
    tarjanNodeNumbers_[nodeId] = num;
    tarjanLowLink_[nodeId] = num;
    tarjanIsOnStack_[nodeId] = true;
    tarjanStack_.push_back(node);
    num += 1;
 
    for (auto &neighbor : subGraph.adjacentNodes(node)) {
      size_t neighborId = subGraph.nodeId(neighbor);
      if (tarjanNodeNumbers_[neighborId] == 0) {
        tarjanStrongConnect(num, neighborId, subGraph);
        tarjanLowLink_[nodeId] = std::min(tarjanLowLink_[nodeId], tarjanLowLink_[neighborId]);
      } else if (tarjanIsOnStack_[neighborId]) {
        tarjanLowLink_[nodeId] = std::min(tarjanLowLink_[nodeId], tarjanNodeNumbers_[neighborId]);
      }
    }
 
    if (tarjanLowLink_[nodeId] == tarjanNodeNumbers_[nodeId]) {
      std::vector<hh_cx::behavior::AbstractNode const *> component{};
      hh_cx::behavior::AbstractNode const *nodeStack = nullptr;
      do {
        nodeStack = tarjanStack_.back();
        tarjanStack_.pop_back();
        tarjanIsOnStack_[subGraph.nodeId(nodeStack)] = false;
        component.push_back(nodeStack);
      } while (node != nodeStack);
      tarjanConnectedComponent_.push_back(component);
    }
  }
 
  constexpr std::pair<size_t, SimpleSubGraph> leastIndexStrongConnectedComponents(SimpleSubGraph const &subGraph) {
    size_t min = numberOfNodes_;
    std::vector<hh_cx::behavior::AbstractNode const *> minSCC(numberOfNodes_, nullptr);
 
    for (auto connectedComponent : tarjanConnectedComponent_) {
      if (connectedComponent.size() == 1) {
        auto node = connectedComponent.at(0);
        if (subGraph.isLinked(node, node)) {
          johnsonCycles_.push_back({node});
        }
      } else {
        for (auto node : connectedComponent) {
          if (subGraph.nodeId(node) < min) {
            min = subGraph.nodeId(node);
            minSCC = connectedComponent;
          }
        }
      }
    }
 
    if (min == numberOfNodes_) { return {numberOfNodes_, SimpleSubGraph{}}; }
    else {
      SimpleSubGraph minSubGraph{};
 
      std::vector<size_t> minIndexes{};
      for (auto &sender : subGraph.registeredNodes()) {
        for (auto &receiver : subGraph.registeredNodes()) {
          if (subGraph.isLinked(sender, receiver)) {
            if (std::find(minSCC.cbegin(), minSCC.cend(), sender) != minSCC.cend()
                && std::find(minSCC.cbegin(), minSCC.cend(), receiver) != minSCC.cend()) {
              minSubGraph.addEdge(sender, receiver);
              minIndexes.push_back(subGraph.nodeId(sender));
              minIndexes.push_back(subGraph.nodeId(receiver));
            }
          }
        }
      }
      return {*std::min_element(minIndexes.cbegin(), minIndexes.cend()), minSubGraph};
    }
  }
 
  constexpr bool findCyclesInSCC(
      hh_cx::behavior::AbstractNode const *startNode,
      hh_cx::behavior::AbstractNode const *currentNode,
      SimpleSubGraph const &subGraph) {
    bool cycleFound = false;
    johnsonStack_.push_back(currentNode);
    johnsonBlockedSetArray_.at(subGraph.nodeId(currentNode)) = true;
 
    for (auto neighbor : subGraph.adjacentNodes(currentNode)) {
      if (neighbor == startNode) {
        std::vector<hh_cx::behavior::AbstractNode const *> cycle{};
        auto tempStack(johnsonStack_);
        while (!tempStack.empty()) {
          cycle.push_back(tempStack.back());
          tempStack.pop_back();
        }
        std::reverse(cycle.begin(), cycle.end());
 
        bool johnsonCycleFound = false;
        for (auto const &johnsonCycle : johnsonCycles_) {
          if (johnsonCycle.size() == cycle.size()) {
            bool cycleSame = true;
            for (size_t nodeId = 0; nodeId < johnsonCycle.size(); ++nodeId) {
              cycleSame &= (johnsonCycle.at(nodeId) == cycle.at(nodeId));
            }
            johnsonCycleFound |= cycleSame;
          }
        }
 
        if (!johnsonCycleFound) {
          johnsonCycles_.push_back(cycle);
        }
        cycleFound = true;
      } else if (!johnsonBlockedSetArray_.at(subGraph.nodeId(neighbor))) {
        cycleFound |= findCyclesInSCC(startNode, neighbor, subGraph);
      }
    }
 
    if (cycleFound) { unblock(currentNode, subGraph); }
    else {
      for (auto neighbors : subGraph.adjacentNodes(currentNode)) {
        auto nodes = johnsonBlockedMap_.at(subGraph.nodeId(neighbors));
        if (std::find(nodes.cbegin(), nodes.cend(), currentNode) == nodes.cend()) {
          nodes.push_back(currentNode);
          johnsonBlockedMap_.at(subGraph.nodeId(neighbors)) = nodes;
        }
      }
    }
 
    johnsonStack_.pop_back();
    return cycleFound;
  }
 
  constexpr void removeCyclesWhereNodesRedefineCanTerminate() {
    std::vector<std::vector<hh_cx::behavior::AbstractNode const *>> temp{};
    for (const auto &cycle : johnsonCycles_) {
      if (!std::any_of(cycle.cbegin(), cycle.cend(),
                       [](auto const &node) { return node->isCanTerminateOverloaded(); })) {
        temp.push_back(cycle);
      }
    }
    johnsonCycles_ = temp;
  }
 
  constexpr void unblock(hh_cx::behavior::AbstractNode const *node, SimpleSubGraph const &subGraph) {
    johnsonBlockedSetArray_.at(subGraph.nodeId(node)) = false;
    for (auto nodeBlocked : johnsonBlockedMap_.at(subGraph.nodeId(node))) {
      if (johnsonBlockedSetArray_.at(subGraph.nodeId(nodeBlocked))) {
        unblock(nodeBlocked, subGraph);
      }
    }
    johnsonBlockedMap_.at(subGraph.nodeId(node)) = {};
  }
 
};
 
}
#endif //HH_ENABLE_HH_CX
#endif //HEDGEHOG_CYCLE_TEST_H_