packages/engine/scram-node/src/cycle.h

Validation facilities to detect and print cycles in graphs.

Namespaces

Name
scram
scram::mef
scram::mef::cycle

Source code

/*
 * Copyright (C) 2014-2018 Olzhas Rakhimov
 * Copyright (C) 2023 OpenPRA ORG Inc.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */


#pragma once

#include <array>
#include <string>
#include <vector>

#include <boost/algorithm/string/join.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/adaptor/transformed.hpp>

#include "element.h"
#include "error.h"
#include "event.h"
#include "event_tree.h"
#include "instruction.h"
#include "parameter.h"

namespace scram::mef::cycle {

inline const Formula* GetConnector(Gate* node) { return &node->formula(); }
inline Expression* GetConnector(Parameter* node) { return node; }
inline Branch* GetConnector(NamedBranch* node) { return node; }
inline const Instruction* GetConnector(Rule* node) { return node; }
inline const EventTree* GetConnector(Link* node) { return &node->event_tree(); }

inline auto GetNodes(const Formula* connector) {
  return connector->args() |
         boost::adaptors::transformed([](const Formula::Arg& arg) -> Gate* {
           if (auto* arg_gate = std::get_if<Gate*>(&arg.event))
             return *arg_gate;
           return nullptr;
         }) |
         boost::adaptors::filtered([](auto* ptr) { return ptr != nullptr; });
}
inline auto GetNodes(Expression* connector) {
  return connector->args() | boost::adaptors::transformed([](Expression* arg) {
           return dynamic_cast<Parameter*>(arg);
         }) |
         boost::adaptors::filtered([](auto* ptr) { return ptr != nullptr; });
}

inline auto GetConnectors(const Formula* connector) {
  (void)connector;
  return std::array<const Formula*, 0>();  // Empty range.
}
inline auto GetConnectors(Expression* connector) {
  return connector->args() | boost::adaptors::filtered([](Expression* arg) {
           return dynamic_cast<Parameter*>(arg) == nullptr;
         });
}

template <class T, class N>
bool ContinueConnector(T* connector, std::vector<N*>* cycle);

template <class T>
bool DetectCycle(T* node, std::vector<T*>* cycle) {
  if (!node->mark()) {
    node->mark(NodeMark::kTemporary);
    if (ContinueConnector(GetConnector(node), cycle)) {
      if (cycle->size() == 1 || cycle->back() != cycle->front())
        cycle->push_back(node);
      return true;
    }
    node->mark(NodeMark::kPermanent);
  } else if (node->mark() == NodeMark::kTemporary) {
    assert(cycle->empty() && "The report container must be provided empty.");
    cycle->push_back(node);
    return true;
  }
  assert(node->mark() == NodeMark::kPermanent);
  return false;
}

template <class T, class N>
bool ContinueConnector(T* connector, std::vector<N*>* cycle) {
  for (N* node : GetNodes(connector)) {
    if (DetectCycle(node, cycle))
      return true;
  }
  for (auto* link : GetConnectors(connector)) {
    if (ContinueConnector(link, cycle))
      return true;
  }
  return false;
}

template <>
bool ContinueConnector(Branch* connector, std::vector<NamedBranch*>* cycle);

template <>
bool ContinueConnector(const Instruction* connector, std::vector<Rule*>* cycle);

template <>
bool ContinueConnector(const EventTree* connector, std::vector<Link*>* cycle);

template <class T>
const std::string& GetUniqueName(const T* node) {
  return Id::unique_name(*node);
}

template <>
inline const std::string& GetUniqueName(const Link* node) {
  return node->event_tree().name();
}

template <class T>
std::string PrintCycle(const std::vector<T*>& cycle) {
  assert(cycle.size() > 1);
  assert(cycle.front() == cycle.back() && "No cycle is provided.");
  return boost::join(
      boost::adaptors::reverse(cycle) |
          boost::adaptors::transformed(
              [](T* node) -> decltype(auto) { return GetUniqueName(node); }),
      "->");
}

template <class T, class SinglePassRange>
void CheckCycle(const SinglePassRange& container, const char* type) {
  std::vector<T*> cycle;
  for (T& node : container) {
    if (DetectCycle(&node, &cycle)) {
      SCRAM_THROW(CycleError()) << errinfo_element(GetUniqueName(&node), type)
                                << errinfo_cycle(PrintCycle(cycle));
    }
  }
}

}  // namespace scram::mef::cycle

---

Updated on 2025-11-11 at 16:51:08 +0000