OpenPRA Documentation

packages/engine/scram-node/src/preprocessor.h ​

A collection of PDAG transformation/preprocessing algorithms that simplify fault trees for analysis.

Namespaces ​

Name
scram
scram::core
scram::core::pdag

Classes ​

Name
classscram::core::Preprocessor <br>The class provides main preprocessing operations over a PDAG to simplify the fault tree and to help analysis run more efficiently.
classscram::core::CustomPreprocessor< Bdd > <br>Specialization of preprocessing for BDD based analyses.
classscram::core::CustomPreprocessor< Zbdd > <br>Specialization of preprocessing for ZBDD based analyses.
classscram::core::CustomPreprocessor< Mocus > <br>Specialization of preprocessing for MOCUS based analyses.

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 <memory>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

#include <boost/noncopyable.hpp>
#include <boost/unordered_map.hpp>

#include "pdag.h"

namespace scram::core {

namespace pdag {

template <typename T, typename... Ts>
void Transform(Pdag* graph, T&& unary_op, Ts&&... unary_ops) noexcept {
  if (graph->IsTrivial())
    return;

  unary_op(graph);

  if constexpr (sizeof...(unary_ops))
    Transform(graph, std::forward<Ts>(unary_ops)...);
}

template <class T>
std::vector<T*> OrderArguments(Gate* gate) noexcept;

void TopologicalOrder(Pdag* graph) noexcept;

void MarkCoherence(Pdag* graph) noexcept;

}  // namespace pdag

class Preprocessor : private boost::noncopyable {
 public:
  explicit Preprocessor(Pdag* graph) noexcept;

  virtual ~Preprocessor() = default;

  void operator()() noexcept;

 protected:
  class GateSet;  

  virtual void Run() noexcept = 0;

  void RunPhaseOne() noexcept;

  void RunPhaseTwo() noexcept;

  void RunPhaseThree() noexcept;

  void RunPhaseFour() noexcept;

  void RunPhaseFive() noexcept;

  void NormalizeGates(bool full) noexcept;

  void NotifyParentsOfNegativeGates(const GatePtr& gate) noexcept;

  void NormalizeGate(const GatePtr& gate, bool full) noexcept;

  void NormalizeXorGate(const GatePtr& gate) noexcept;

  void NormalizeAtleastGate(const GatePtr& gate) noexcept;

  void
  PropagateComplements(const GatePtr& gate, bool keep_modules,
                       std::unordered_map<int, GatePtr>* complements) noexcept;

  bool CoalesceGates(bool common) noexcept;

  bool CoalesceGates(const GatePtr& gate, bool common) noexcept;

  bool ProcessMultipleDefinitions() noexcept;

  void DetectMultipleDefinitions(
      const GatePtr& gate,
      std::unordered_map<GatePtr, std::vector<GateWeakPtr>>* multi_def,
      GateSet* unique_gates) noexcept;

  void DetectModules() noexcept;

  int AssignTiming(int time, const GatePtr& gate) noexcept;

  void FindModules(const GatePtr& gate) noexcept;

  void ProcessModularArgs(
      const GatePtr& gate,
      const std::vector<std::pair<int, NodePtr>>& non_shared_args,
      std::vector<std::pair<int, NodePtr>>* modular_args,
      std::vector<std::pair<int, NodePtr>>* non_modular_args) noexcept;

  GatePtr
  CreateNewModule(const GatePtr& gate,
                  const std::vector<std::pair<int, NodePtr>>& args) noexcept;

  void FilterModularArgs(
      std::vector<std::pair<int, NodePtr>>* modular_args,
      std::vector<std::pair<int, NodePtr>>* non_modular_args) noexcept;

  void GroupModularArgs(
      std::vector<std::pair<int, NodePtr>>* modular_args,
      std::vector<std::vector<std::pair<int, NodePtr>>>* groups) noexcept;

  void CreateNewModules(
      const GatePtr& gate,
      const std::vector<std::pair<int, NodePtr>>& modular_args,
      const std::vector<std::vector<std::pair<int, NodePtr>>>& groups) noexcept;

  std::vector<GateWeakPtr> GatherModules() noexcept;

  bool MergeCommonArgs() noexcept;

  bool MergeCommonArgs(Connective op) noexcept;

  void MarkCommonArgs(const GatePtr& gate, Connective op) noexcept;

  struct MergeTable {
    using CommonArgs = std::vector<int>;  
    using CommonParents = std::set<GatePtr>;  
    using Option = std::pair<CommonArgs, CommonParents>;  
    using OptionGroup = std::vector<Option*>;  
    using MergeGroup = std::vector<Option>;  

    using Candidate = std::pair<GatePtr, CommonArgs>;
    using Candidates = std::vector<Candidate>;
    using Collection = boost::unordered_map<CommonArgs, CommonParents>;

    std::vector<MergeGroup> groups;  
  };

  void GatherCommonArgs(const GatePtr& gate, Connective op,
                        MergeTable::Candidates* group) noexcept;

  void FilterMergeCandidates(MergeTable::Candidates* candidates) noexcept;

  void
  GroupCandidatesByArgs(MergeTable::Candidates* candidates,
                        std::vector<MergeTable::Candidates>* groups) noexcept;

  void GroupCommonParents(int num_common_args,
                          const MergeTable::Candidates& group,
                          MergeTable::Collection* parents) noexcept;

  void GroupCommonArgs(const MergeTable::Collection& options,
                       MergeTable* table) noexcept;

  void FindOptionGroup(MergeTable::MergeGroup* all_options,
                       MergeTable::OptionGroup* best_group) noexcept;

  void FindBaseOption(MergeTable::MergeGroup* all_options,
                      MergeTable::MergeGroup::iterator* best_option) noexcept;

  void TransformCommonArgs(MergeTable::MergeGroup* group) noexcept;

  bool DetectDistributivity() noexcept;

  bool DetectDistributivity(const GatePtr& gate) noexcept;

  bool HandleDistributiveArgs(const GatePtr& gate, Connective distr_type,
                              std::vector<GatePtr>* candidates) noexcept;

  bool FilterDistributiveArgs(const GatePtr& gate,
                              std::vector<GatePtr>* candidates) noexcept;

  void GroupDistributiveArgs(const MergeTable::Collection& options,
                             MergeTable* table) noexcept;

  void TransformDistributiveArgs(const GatePtr& gate, Connective distr_type,
                                 MergeTable::MergeGroup* group) noexcept;

  void BooleanOptimization() noexcept;

  void GatherCommonNodes(
      std::vector<GateWeakPtr>* common_gates,
      std::vector<std::weak_ptr<Variable>>* common_variables) noexcept;

  template <class N>
  void ProcessCommonNode(const std::weak_ptr<N>& common_node) noexcept;

  void MarkAncestors(const NodePtr& node, GatePtr* module) noexcept;

  int PropagateState(const GatePtr& gate, const NodePtr& node) noexcept;

  void DetermineGateState(const GatePtr& gate, int num_failure,
                          int num_success) noexcept;

  int CollectStateDestinations(
      const GatePtr& gate, int index,
      std::unordered_map<int, GateWeakPtr>* destinations) noexcept;

  void CollectRedundantParents(
      const NodePtr& node, std::unordered_map<int, GateWeakPtr>* destinations,
      std::vector<GateWeakPtr>* redundant_parents) noexcept;

  void ProcessRedundantParents(
      const NodePtr& node,
      const std::vector<GateWeakPtr>& redundant_parents) noexcept;

  template <class N>
  void ProcessStateDestinations(
      const std::shared_ptr<N>& node,
      const std::unordered_map<int, GateWeakPtr>& destinations) noexcept;

  void ClearStateMarks(const GatePtr& gate) noexcept;

  bool DecomposeCommonNodes() noexcept;

  class DecompositionProcessor {
   public:
    bool operator()(const std::weak_ptr<Node>& common_node,
                    Preprocessor* preprocessor) noexcept;

   private:
    void MarkDestinations(const GatePtr& parent) noexcept;

    bool ProcessDestinations(const std::vector<GateWeakPtr>& dest) noexcept;

    bool ProcessAncestors(const GatePtr& ancestor, bool state,
                          const GatePtr& root) noexcept;

    static bool IsAncestryWithinGraph(const GatePtr& gate,
                                      const GatePtr& root) noexcept;

    static void ClearAncestorMarks(const GatePtr& gate,
                                   const GatePtr& root) noexcept;

    NodePtr node_;  
    Preprocessor* preprocessor_ = nullptr;  
  };

  void ReplaceGate(const GatePtr& gate, const GatePtr& replacement) noexcept;

  bool RegisterToClear(const GatePtr& gate) noexcept;

  void GatherNodes(std::vector<GatePtr>* gates,
                   std::vector<VariablePtr>* variables) noexcept;

  void GatherNodes(const GatePtr& gate, std::vector<GatePtr>* gates,
                   std::vector<VariablePtr>* variables) noexcept;

  Pdag* graph_;  
};

template <class Algorithm>
class CustomPreprocessor;

class Bdd;

template <>
class CustomPreprocessor<Bdd> : public Preprocessor {
 public:
  using Preprocessor::Preprocessor;

 private:
  void Run() noexcept override;
};

class Zbdd;

template <>
class CustomPreprocessor<Zbdd> : public Preprocessor {
 public:
  using Preprocessor::Preprocessor;

 protected:
  void Run() noexcept override;
};

class Mocus;

template <>
class CustomPreprocessor<Mocus> : public CustomPreprocessor<Zbdd> {
 public:
  using CustomPreprocessor<Zbdd>::CustomPreprocessor;

 private:
  void Run() noexcept override;

  void InvertOrder() noexcept;
};

}  // namespace scram::core

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