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

Classes and facilities to represent fault trees as PDAGs with event and gate indices instead of ID names. More...
Namespaces

Name
scram
scram::mef
scram::core
Classes

	Name
class	scram::core::NodeParentManager <br>A manager of information about parents.
class	scram::core::Node <br>An abstract base class that represents a node in a PDAG.
class	scram::core::Constant <br>Representation of a node that is a Boolean constant TRUE.
class	scram::core::Variable <br>Boolean variables in a Boolean formula or graph.
class	scram::core::Gate <br>An indexed gate for use in a PDAG.
class	scram::core::Pdag <br>PDAG is a propositional directed acyclic graph.
class	scram::core::Pdag::NodeIndexGenerator <br>Generator of unique indices for graph nodes.
class	scram::core::Pdag::NullGateRegistrar <br>Registers pass-through or Null logic gates belonging to the graph.
struct	scram::core::Pdag::Substitution <br>Non-declarative substitutions.
Detailed Description

Classes and facilities to represent fault trees as PDAGs with event and gate indices instead of ID names.
These facilities are designed to work with FaultTreeAnalysis and Preprocessor classes.
The terminologies of the graphs and Boolean logic are mixed to represent the PDAG; however, if there is a conflict, the Boolean terminology is preferred. For example, instead of "children", "arguments" are preferred.
Source code

cpp
/*
 * 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 <cstdint>
#include <cstdlib>

#include <algorithm>
#include <iosfwd>
#include <memory>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <variant>
#include <vector>

#include <boost/container/flat_set.hpp>
#include <boost/noncopyable.hpp>
#include <boost/range/adaptor/transformed.hpp>

#include "ext/find_iterator.h"
#include "ext/index_map.h"
#include "ext/linear_map.h"

namespace scram::mef {  // Declarations to decouple from the MEF initialization.
class Model;  // Provider of substitutions.
class Substitution;
class Gate;
class BasicEvent;
class HouseEvent;
class Formula;
}  // namespace scram::mef

namespace scram::core {

class Gate;  // An indexed gate parent of nodes.
using GatePtr = std::shared_ptr<Gate>;  
using GateWeakPtr = std::weak_ptr<Gate>;  

class NodeParentManager : private boost::noncopyable {
  friend class Gate;  

 public:
  using Parent = std::pair<int, GateWeakPtr>;  

  using ParentMap = ext::linear_map<int, GateWeakPtr, ext::MoveEraser>;

  const ParentMap& parents() const { return parents_; }

 protected:
  ~NodeParentManager() = default;

 private:
  void AddParent(const GatePtr& gate);

  void EraseParent(int index) {
    assert(parents_.count(index) && "No parent with the given index exists.");
    parents_.erase(index);
  }

  ParentMap parents_;  
};

class Pdag;  // Manager of the graph, node indices and uniqueness.

class Node : public NodeParentManager {
 public:
  explicit Node(Pdag* graph) noexcept;

  virtual ~Node() = 0;  

  Pdag& graph() { return graph_; }

  int index() const { return index_; }

  int order() const { return order_; }

  void order(int val) { order_ = val; }

  int opti_value() const { return opti_value_; }

  void opti_value(int val) { opti_value_ = val; }

  bool Visit(int time) {
    assert(time > 0);
    if (!visits_[0]) {
      visits_[0] = time;
    } else if (!visits_[1]) {
      visits_[1] = time;
    } else {
      visits_[2] = time;
      return true;
    }
    return false;
  }

  int EnterTime() const { return visits_[0]; }

  int ExitTime() const { return visits_[1]; }

  int LastVisit() const { return visits_[2] ? visits_[2] : visits_[1]; }

  virtual int min_time() const { return visits_[0]; }

  virtual int max_time() const { return LastVisit(); }

  bool Revisited() const { return visits_[2]; }

  bool Visited() const { return visits_[0]; }

  void ClearVisits() { std::fill_n(visits_, 3, 0); }

  int pos_count() const { return pos_count_; }

  int neg_count() const { return neg_count_; }

  void AddCount(bool positive) { positive ? ++pos_count_ : ++neg_count_; }

  void ResetCount() {
    pos_count_ = 0;
    neg_count_ = 0;
  }

 private:
  int index_;  
  int order_;  
  int visits_[3];  
  int opti_value_;  
  int pos_count_;  
  int neg_count_;  
  Pdag& graph_;  
};

class Constant : public Node {
  friend class Pdag;  // Only one constant per graph must be enforced by PDAG.

 public:
  bool value() const { return true; }

 private:
  using Node::Node;
};

class Variable : public Node {
 public:
  using Node::Node;
};

using NodePtr = std::shared_ptr<Node>;  
using ConstantPtr = std::shared_ptr<Constant>;  
using VariablePtr = std::shared_ptr<Variable>;  

enum Connective : std::uint8_t {
  kAnd = 0,  
  kOr,  
  kAtleast,  
  kXor,  
  kNot,  
  kNand,  
  kNor,  
  kNull  
};

const int kNumConnectives = 8;  // Update this number if connectives change.

class Gate : public Node, public std::enable_shared_from_this<Gate> {
 public:
  template <class T>
  using Arg = std::pair<int, std::shared_ptr<T>>;
  template <class T>
  using ConstArg = std::pair<int, const T&>;

  template <class T>
  using ArgMap = ext::linear_map<int, std::shared_ptr<T>, ext::MoveEraser>;

  using ArgSet = boost::container::flat_set<int>;

  Gate(Connective type, Pdag* graph) noexcept;

  ~Gate() noexcept {
    assert(Node::parents().empty());
    EraseArgs();
  }

  GatePtr Clone() noexcept;

  Connective type() const { return type_; }

  void type(Connective type);

  int min_number() const { return min_number_; }

  void min_number(int number) { min_number_ = number; }

  bool constant() const { return constant_ != nullptr; }

  const ArgSet& args() const { return args_; }

  template <class T>
  const ArgMap<T>& args() {
    if constexpr (std::is_same_v<T, Gate>) {
      return gate_args_;

    } else {
      static_assert(std::is_same_v<T, Variable>, "No container for const args");
      return variable_args_;
    }
  }

  template <class T>
  auto args() const {
    return boost::adaptors::transform(
        const_cast<Gate*>(this)->args<T>(), [](const Arg<T>& arg) {
          return ConstArg<T>{arg.first, *arg.second};
        });
  }

  bool mark() const { return mark_; }

  void mark(bool flag) { mark_ = flag; }

  int descendant() const { return descendant_; }

  void descendant(int index) { descendant_ = index; }

  int ancestor() { return ancestor_; }

  void ancestor(int index) { ancestor_ = index; }

  int min_time() const override { return min_time_; }

  void min_time(int time) {
    assert(time > 0);
    min_time_ = time;
  }

  int max_time() const override { return max_time_; }

  void max_time(int time) {
    assert(time > 0);
    max_time_ = time;
  }

  bool coherent() const { return coherent_; }

  void coherent(bool flag) { coherent_ = flag; }

  bool module() const { return module_; }

  void module(bool flag) {
    assert(module_ != flag);
    module_ = flag;
  }

  int GetArgSign(const NodePtr& arg) const noexcept {
    assert(arg->parents().count(Node::index()) && "Invalid argument.");
    return args_.count(arg->index()) ? 1 : -1;
  }

  NodePtr GetArg(int index) const noexcept {
    assert(args_.count(index));
    if (auto it = ext::find(gate_args_, index))
      return it->second;

    if (auto it = ext::find(variable_args_, index))
      return it->second;
    assert(constant_ && std::abs(index) == constant_->index());
    return constant_;
  }

  template <class T>
  void AddArg(int index, const std::shared_ptr<T>& arg) noexcept {
    assert(index);
    assert(std::abs(index) == arg->index());
    assert(!constant_);
    assert(!((type_ == kNot || type_ == kNull) && !args_.empty()));
    assert(!(type_ == kXor && args_.size() > 1));
    assert(min_number_ >= 0);

    if (args_.count(index))
      return ProcessDuplicateArg(index);
    if (args_.count(-index))
      return ProcessComplementArg(index);

    args_.insert(index);
    mutable_args<T>().data().emplace_back(index, arg);
    arg->AddParent(shared_from_this());
  }
  template <class T>
  void AddArg(const std::shared_ptr<T>& arg, bool complement = false) noexcept {
    return AddArg(complement ? -arg->index() : arg->index(), arg);
  }
  template <class T>
  void AddArg(const Arg<T>& arg) noexcept {
    return AddArg(arg.first, arg.second);
  }

  void TransferArg(int index, const GatePtr& recipient) noexcept;

  void ShareArg(int index, const GatePtr& recipient) noexcept;

  void NegateArgs() noexcept;

  void NegateArg(int existing_arg) noexcept;

  void NegateNonCoherentGateArgs() noexcept {
    for (Arg<Gate>& arg : gate_args_) {
      switch (arg.second->type()) {
        case kNor:
        case kNand:
        case kNot:
          args_.erase(arg.first);
          args_.insert(-arg.first);
          arg.first = -arg.first;
          break;
        default:
          assert("Update the logic if new gate types are introduced.");
      }
    }
  }

  void CoalesceGate(const GatePtr& arg_gate) noexcept;

  void JoinNullGate(int index) noexcept;

  void ProcessConstantArg(const NodePtr& arg, bool state) noexcept;

  void EraseArg(int index) noexcept;

  void EraseArgs() noexcept;

  void MakeConstant(bool state) noexcept;

 private:
  using std::enable_shared_from_this<Gate>::shared_from_this;

  template <class T>
  ArgMap<T>& mutable_args() {
    return const_cast<ArgMap<T>&>(args<T>());
  }

  void ProcessDuplicateArg(int index) noexcept;

  void ProcessAtleastGateDuplicateArg(int index) noexcept;

  void ProcessComplementArg(int index) noexcept;

  template <bool State>
  void AddConstantArg() noexcept;

  void ReduceLogic(Connective target_type, int num_args = 1) noexcept {
    assert(!args_.empty());
    if (args_.size() == num_args)
      type(target_type);
  }

  Connective type_;  
  bool mark_;  
  bool module_;  
  bool coherent_;  
  int min_number_;  
  int descendant_;  
  int ancestor_;  
  int min_time_;  
  int max_time_;  
  ArgSet args_;  
  ArgMap<Gate> gate_args_;
  ArgMap<Variable> variable_args_;

  ConstantPtr constant_;
};

template <>
void Gate::AddArg<Constant>(int index, const ConstantPtr& arg) noexcept;

class Pdag : private boost::noncopyable {
 public:
  static const int kVariableStartIndex = 2;  
  template <typename T>
  using IndexMap = ext::index_map<kVariableStartIndex, T>;

  class NodeIndexGenerator {
    friend class Node;  // Access for a new index request.
    int operator()(Pdag* graph) const { return ++graph->node_index_; }
  };

  class NullGateRegistrar {
    friend class Gate;
    void operator()(GatePtr gate) const {
      assert(gate->type() == kNull && "Only Null logic gates are expected.");
      if (gate->graph().register_null_gates_)
        gate->graph().null_gates_.emplace_back(std::move(gate));
    }
  };

  struct Substitution {
    const std::vector<int> hypothesis;
    const std::vector<int> source;
    const int target;
  };

  enum NodeMark {
    kGateMark,  
    kVisit,  
    kCount,
    kOptiValue,
    kDescendant,
    kAncestor,
    kOrder
  };

  Pdag() noexcept;

  explicit Pdag(const mef::Gate& root, bool ccf = false,
                const mef::Model* model = nullptr) noexcept;

  const std::vector<Substitution>& substitutions() const {
    return substitutions_;
  }

  bool coherent() const { return coherent_; }

  void coherent(bool flag) { coherent_ = flag; }

  bool normal() const { return normal_; }

  void normal(bool flag) { normal_ = flag; }

  const GatePtr& root() { return root_; }

  const Gate& root() const { return *root_; }

  void root(const GatePtr& gate) {
    assert(gate && "The graph cannot be made root-less.");
    assert(this == &gate->graph() && "The gate is from a different graph.");
    root_ = gate;
  }

  bool complement() const { return complement_; }
  bool& complement() { return complement_; }  // Allows XOR setting.

  const ConstantPtr& constant() const { return constant_; }

  bool HasConstants() const { return !constant_->parents().empty(); }

  bool HasNullGates() const { return !null_gates_.empty(); }

  bool IsTrivial() const {
    return !complement_ && root_->type() == kNull &&
           root_->args<Gate>().empty();
  }

  bool IsTrivial() noexcept;

  const IndexMap<const mef::BasicEvent*>& basic_events() const {
    return basic_events_;
  }

  void Print();

  void Log() noexcept;

  void RemoveNullGates() noexcept;

  template <NodeMark Mark>
  void Clear() noexcept {
    if constexpr (Mark == kGateMark) {
      Clear<kGateMark>(root_);

    } else {
      Clear<kGateMark>();
      Clear<Mark>(root_);
      Clear<kGateMark>();
    }
  }

  template <NodeMark Mark>
  void Clear(const GatePtr& gate) noexcept;

 private:
  struct ProcessedNodes {  
    std::unordered_map<const mef::Gate*, GatePtr> gates;
    std::unordered_map<const mef::BasicEvent*, VariablePtr> variables;
  };  

  void GatherVariables(const mef::Formula& formula, bool ccf,
                       ProcessedNodes* nodes) noexcept;

  void GatherVariables(const mef::BasicEvent& basic_event, bool ccf,
                       ProcessedNodes* nodes) noexcept;

  void GatherVariables(const mef::Substitution& substitution, bool ccf,
                       ProcessedNodes* nodes) noexcept;

  GatePtr ConstructGate(const mef::Formula& formula, bool ccf,
                        ProcessedNodes* nodes) noexcept;

  GatePtr ConstructComplexGate(const mef::Formula& formula, bool ccf,
                               ProcessedNodes* nodes) noexcept;

  GatePtr ConstructSubstitution(const mef::Substitution& substitution, bool ccf,
                                ProcessedNodes* nodes) noexcept;

  void CollectSubstitution(const mef::Substitution& substitution,
                           ProcessedNodes* nodes) noexcept;

  template <class T>
  void AddArg(const GatePtr& parent, const T& event, bool complement, bool ccf,
              ProcessedNodes* nodes) noexcept;
  void AddArg(
      const GatePtr& parent,
      const std::variant<mef::Gate*, mef::BasicEvent*, mef::HouseEvent*>& event,
      bool complement, bool ccf, ProcessedNodes* nodes) noexcept;

  void PropagateNullGate(const GatePtr& gate) noexcept;

  int node_index_;  
  bool complement_;  
  bool coherent_;  
  bool normal_;  
  bool register_null_gates_;  
  GatePtr root_;  
  ConstantPtr constant_;  
  IndexMap<const mef::BasicEvent*> basic_events_;
  std::vector<GateWeakPtr> null_gates_;
  std::vector<Substitution> substitutions_;  
};

template <bool Mark = true, typename T>
void TraverseGates(const GatePtr& gate, T&& visit) noexcept {
  if (gate->mark() == Mark)
    return;
  gate->mark(Mark);
  visit(gate);
  for (const auto& arg : gate->args<Gate>()) {
    TraverseGates<Mark>(arg.second, visit);
  }
}
template <typename T>
void TraverseNodes(const GatePtr& gate, T&& visit) noexcept {
  if (gate->mark())
    return;
  gate->mark(true);
  visit(gate);
  for (const auto& arg : gate->args<Gate>()) {
    TraverseNodes(arg.second, visit);
  }
  for (const auto& arg : gate->args<Variable>()) {
    visit(arg.second);
  }
}

template <Pdag::NodeMark Mark>
void Pdag::Clear(const GatePtr& gate) noexcept {
  if constexpr (Mark == kGateMark) {
    TraverseGates<false>(gate, [](auto&&) {});

  } else if constexpr (Mark == kDescendant) {
    TraverseGates(gate, [](const GatePtr& arg) { arg->descendant(0); });

  } else if constexpr (Mark == kAncestor) {
    TraverseGates(gate, [](const GatePtr& arg) { arg->ancestor(0); });

  } else {
    TraverseNodes(gate, [](auto&& node) {
      if constexpr (Mark == kVisit) {
        if (node->Visited())
          node->ClearVisits();

      } else if constexpr (Mark == kOrder) {
        if (node->order())
          node->order(0);

      } else if constexpr (Mark == kOptiValue) {
        node->opti_value(0);

      } else {
        static_assert(Mark == kCount, "The node mark is not covered.");
        node->ResetCount();
      }
    });
  }
}

std::ostream& operator<<(std::ostream& os, const Constant& constant);
std::ostream& operator<<(std::ostream& os, const Variable& variable);
std::ostream& operator<<(std::ostream& os, const GatePtr& gate);

std::ostream& operator<<(std::ostream& os, Pdag* graph);

}  // namespace scram::core
Updated on 2025-11-11 at 16:51:08 +0000
packages/engine/scram-node/src/pdag.h ​

Namespaces ​

Classes ​

Detailed Description ​

Source code ​

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

Namespaces

Classes

Detailed Description

Source code
