fault_tree.cpp

Go to the documentation of this file.

#include "faulttree/fault_tree.hpp"
 
#include <algorithm>
#include <sstream>
 
namespace faulttree {
 
namespace {
 
const char *typeName(GateType type) {
  switch (type) {
    case GateType::Basic: return "basic event";
    case GateType::And: return "AND gate";
    case GateType::Or: return "OR gate";
    case GateType::KofN: return "K/N gate";
    case GateType::Not: return "NOT gate";
  }
  return "unknown";
}
 
} // namespace
 
void FaultTree::addNode(Node node) {
  if (node.name.empty()) { throw FaultTreeError("a fault tree node must have a name"); }
  if (index_.find(node.name) != index_.end()) {
    throw FaultTreeError("duplicate fault tree node '" + node.name + "'");
  }
  index_.emplace(node.name, nodes_.size());
  nodes_.push_back(std::move(node));
}
 
bool FaultTree::hasNode(const std::string &name) const {
  return index_.find(name) != index_.end();
}
 
const Node &FaultTree::node(const std::string &name) const {
  auto it = index_.find(name);
  if (it == index_.end()) {
    throw FaultTreeError("no fault tree node named '" + name + "'");
  }
  return nodes_[it->second];
}
 
Node &FaultTree::mutableNode(const std::string &name) {
  auto it = index_.find(name);
  if (it == index_.end()) {
    throw FaultTreeError("no fault tree node named '" + name + "'");
  }
  return nodes_[it->second];
}
 
void FaultTree::setTop(const std::string &name) {
  if (!hasNode(name)) {
    throw FaultTreeError("cannot set top event to unknown node '" + name + "'");
  }
  top_ = name;
}
 
const std::string &FaultTree::top() const {
  if (top_.empty()) { throw FaultTreeError("the fault tree has no top event"); }
  return top_;
}
 
std::vector<std::string> FaultTree::basicEventNames() const {
  std::vector<std::string> names;
  for (const auto &node : nodes_) {
    if (node.type == GateType::Basic) { names.push_back(node.name); }
  }
  return names;
}
 
void FaultTree::setBasicEventProbability(const std::string &name,
                                         double probability) {
  Node &target = mutableNode(name);
  if (target.type != GateType::Basic) {
    throw FaultTreeError("'" + name + "' is a " + typeName(target.type) +
                         ", not a basic event");
  }
  if (!(probability >= 0.0 && probability <= 1.0)) {
    std::ostringstream out;
    out << "probability " << probability << " for '" << name
        << "' is outside [0, 1]";
    throw FaultTreeError(out.str());
  }
  target.probability = probability;
}
 
void FaultTree::validate() const {
  if (nodes_.empty()) { throw FaultTreeError("the fault tree is empty"); }
  if (top_.empty()) { throw FaultTreeError("the fault tree has no top event"); }
 
  for (const auto &node : nodes_) {
    switch (node.type) {
      case GateType::Basic:
        if (!node.children.empty()) {
          throw FaultTreeError("basic event '" + node.name + "' cannot have inputs");
        }
        if (!(node.probability >= 0.0 && node.probability <= 1.0)) {
          std::ostringstream out;
          out << "basic event '" << node.name << "' has probability "
              << node.probability << ", outside [0, 1]";
          throw FaultTreeError(out.str());
        }
        break;
      case GateType::Not:
        if (node.children.size() != 1) {
          throw FaultTreeError("NOT gate '" + node.name +
                               "' must have exactly one input");
        }
        break;
      case GateType::KofN:
        if (node.children.empty()) {
          throw FaultTreeError("K/N gate '" + node.name + "' has no inputs");
        }
        if (node.k < 1 || static_cast<std::size_t>(node.k) > node.children.size()) {
          std::ostringstream out;
          out << "K/N gate '" << node.name << "' has k=" << node.k << " with "
              << node.children.size() << " inputs";
          throw FaultTreeError(out.str());
        }
        break;
      case GateType::And:
      case GateType::Or:
        if (node.children.empty()) {
          throw FaultTreeError(std::string(typeName(node.type)) + " '" +
                               node.name + "' has no inputs");
        }
        break;
    }
 
    for (std::size_t i = 0; i < node.children.size(); ++i) {
      const std::string &child = node.children[i];
      if (!hasNode(child)) {
        throw FaultTreeError("node '" + node.name + "' references unknown input '" +
                             child + "'");
      }
      if (child == node.name) {
        throw FaultTreeError("node '" + node.name + "' is its own input");
      }
      // The same event wired into one gate twice is a modelling mistake: it is
      // idempotent for AND and OR, and it silently changes what k means for a
      // K/N gate. Refuse rather than guess which was intended. (An event
      // feeding *several* gates is the normal shared/common-cause case and is
      // handled exactly.)
      for (std::size_t j = 0; j < i; ++j) {
        if (node.children[j] == child) {
          throw FaultTreeError("node '" + node.name + "' lists input '" + child +
                               "' more than once");
        }
      }
    }
  }
 
  // Cycle detection: iterative depth-first search with a colour marking, so a
  // deep tree cannot overflow the stack.
  enum class Colour { White, Grey, Black };
  std::vector<Colour> colour(nodes_.size(), Colour::White);
  std::vector<std::pair<std::size_t, std::size_t>> stack; // (node, next child)
 
  for (std::size_t start = 0; start < nodes_.size(); ++start) {
    if (colour[start] != Colour::White) { continue; }
    stack.emplace_back(start, 0);
    colour[start] = Colour::Grey;
    while (!stack.empty()) {
      auto &[current, next_child] = stack.back();
      const Node &node = nodes_[current];
      if (next_child < node.children.size()) {
        std::size_t child = index_.at(node.children[next_child]);
        ++next_child;
        if (colour[child] == Colour::Grey) {
          throw FaultTreeError("the fault tree contains a cycle through '" +
                               nodes_[child].name + "'");
        }
        if (colour[child] == Colour::White) {
          colour[child] = Colour::Grey;
          stack.emplace_back(child, 0);
        }
      } else {
        colour[current] = Colour::Black;
        stack.pop_back();
      }
    }
  }
}
 
} // namespace faulttree