packages/engine/scram/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 | |
|---|---|
| class | scram::core::Preprocessor <br>The class provides main preprocessing operations over a PDAG to simplify the fault tree and to help analysis run more efficiently. |
| class | scram::core::CustomPreprocessor< Bdd > <br>Specialization of preprocessing for BDD based analyses. |
| class | scram::core::CustomPreprocessor< Zbdd > <br>Specialization of preprocessing for ZBDD based analyses. |
| class | scram::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 <optional>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#include <boost/unordered_map.hpp>
#include "pdag.h"
#include "settings.h"
namespace scram::core {
namespace pdag {
template <typename T, typename... Ts>
void Transform(Pdag* graph, T&& unary_op, Ts&&... unary_ops) {
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) ;
void TopologicalOrder(Pdag* graph) ;
void LayeredTopologicalOrder(Pdag* graph) ;
void MarkCoherence(Pdag* graph) ;
} // namespace pdag
class Preprocessor : private boost::noncopyable {
public:
explicit Preprocessor(Pdag *graph) ;
explicit Preprocessor(Pdag* graph, const std::optional<Settings> &settings);
virtual ~Preprocessor() = default;
void operator()() ;
protected:
enum NormalizationType {
NONE,
XOR,
ATLEAST,
ALL,
};
class GateSet;
virtual void Run() = 0;
void RunPhaseOne() ;
void RunPhaseTwo() ;
void RunPhaseThree() ;
void RunPhaseFour() ;
void RunPhaseFive() ;
void NormalizeGates(bool full);
void NormalizeGates(NormalizationType type);
void NotifyParentsOfNegativeGates(const GatePtr& gate) ;
void NormalizeGate(const GatePtr& gate, bool full) ;
void NormalizeGate(const GatePtr& gate, NormalizationType type) ;
void NormalizeXorGate(const GatePtr& gate) ;
void NormalizeAtleastGate(const GatePtr& gate) ;
void
PropagateComplements(const GatePtr& gate, bool keep_modules,
std::unordered_map<int, GatePtr>* complements) ;
bool CoalesceGates(bool common) ;
bool CoalesceGates(const GatePtr& gate, bool common) ;
bool ProcessMultipleDefinitions() ;
void DetectMultipleDefinitions(
const GatePtr& gate,
std::unordered_map<GatePtr, std::vector<GateWeakPtr>>* multi_def,
GateSet* unique_gates) ;
void DetectModules() ;
int AssignTiming(int time, const GatePtr& gate) ;
void FindModules(const GatePtr& gate) ;
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) ;
GatePtr
CreateNewModule(const GatePtr& gate,
const std::vector<std::pair<int, NodePtr>>& args) ;
void FilterModularArgs(
std::vector<std::pair<int, NodePtr>>* modular_args,
std::vector<std::pair<int, NodePtr>>* non_modular_args) ;
void GroupModularArgs(
std::vector<std::pair<int, NodePtr>>* modular_args,
std::vector<std::vector<std::pair<int, NodePtr>>>* groups) ;
void CreateNewModules(
const GatePtr& gate,
const std::vector<std::pair<int, NodePtr>>& modular_args,
const std::vector<std::vector<std::pair<int, NodePtr>>>& groups) ;
std::vector<GateWeakPtr> GatherModules() ;
bool MergeCommonArgs() ;
bool MergeCommonArgs(Connective op) ;
void MarkCommonArgs(const GatePtr& gate, Connective op) ;
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) ;
void FilterMergeCandidates(MergeTable::Candidates* candidates) ;
void
GroupCandidatesByArgs(MergeTable::Candidates* candidates,
std::vector<MergeTable::Candidates>* groups) ;
void GroupCommonParents(int num_common_args,
const MergeTable::Candidates& group,
MergeTable::Collection* parents) ;
void GroupCommonArgs(const MergeTable::Collection& options,
MergeTable* table) ;
void FindOptionGroup(MergeTable::MergeGroup* all_options,
MergeTable::OptionGroup* best_group) ;
void FindBaseOption(MergeTable::MergeGroup* all_options,
MergeTable::MergeGroup::iterator* best_option) ;
void TransformCommonArgs(MergeTable::MergeGroup* group) ;
bool DetectDistributivity() ;
bool DetectDistributivity(const GatePtr& gate) ;
bool HandleDistributiveArgs(const GatePtr& gate, Connective distr_type,
std::vector<GatePtr>* candidates) ;
bool FilterDistributiveArgs(const GatePtr& gate,
std::vector<GatePtr>* candidates) ;
void GroupDistributiveArgs(const MergeTable::Collection& options,
MergeTable* table) ;
void TransformDistributiveArgs(const GatePtr& gate, Connective distr_type,
MergeTable::MergeGroup* group) ;
void BooleanOptimization() ;
void GatherCommonNodes(
std::vector<GateWeakPtr>* common_gates,
std::vector<std::weak_ptr<Variable>>* common_variables) ;
template <class N>
void ProcessCommonNode(const std::weak_ptr<N>& common_node) ;
void MarkAncestors(const NodePtr& node, GatePtr* module) ;
int PropagateState(const GatePtr& gate, const NodePtr& node) ;
void DetermineGateState(const GatePtr& gate, int num_failure,
int num_success) ;
int CollectStateDestinations(
const GatePtr& gate, int index,
std::unordered_map<int, GateWeakPtr>* destinations) ;
void CollectRedundantParents(
const NodePtr& node, std::unordered_map<int, GateWeakPtr>* destinations,
std::vector<GateWeakPtr>* redundant_parents) ;
void ProcessRedundantParents(
const NodePtr& node,
const std::vector<GateWeakPtr>& redundant_parents) ;
template <class N>
void ProcessStateDestinations(
const std::shared_ptr<N>& node,
const std::unordered_map<int, GateWeakPtr>& destinations) ;
void ClearStateMarks(const GatePtr& gate) ;
bool DecomposeCommonNodes() ;
class DecompositionProcessor {
public:
bool operator()(const std::weak_ptr<Node>& common_node,
Preprocessor* preprocessor) ;
private:
void MarkDestinations(const GatePtr& parent) ;
bool ProcessDestinations(const std::vector<GateWeakPtr>& dest) ;
bool ProcessAncestors(const GatePtr& ancestor, bool state,
const GatePtr& root) ;
static bool IsAncestryWithinGraph(const GatePtr& gate,
const GatePtr& root) ;
static void ClearAncestorMarks(const GatePtr& gate,
const GatePtr& root) ;
NodePtr node_;
Preprocessor* preprocessor_ = nullptr;
};
void ReplaceGate(const GatePtr& gate, const GatePtr& replacement) ;
bool RegisterToClear(const GatePtr& gate) ;
void GatherNodes(std::vector<GatePtr>* gates,
std::vector<VariablePtr>* variables) ;
void GatherNodes(const GatePtr& gate, std::vector<GatePtr>* gates,
std::vector<VariablePtr>* variables) ;
Pdag* graph_;
std::optional<Settings> settings_;
};
template <class Algorithm>
class CustomPreprocessor;
class Bdd;
template <>
class CustomPreprocessor<Bdd> : public Preprocessor {
public:
using Preprocessor::Preprocessor;
private:
void Run() override;
};
class Zbdd;
template <>
class CustomPreprocessor<Zbdd> : public Preprocessor {
public:
using Preprocessor::Preprocessor;
protected:
void Run() override;
};
class Mocus;
template <>
class CustomPreprocessor<Mocus> : public CustomPreprocessor<Zbdd> {
public:
using CustomPreprocessor<Zbdd>::CustomPreprocessor;
private:
void Run() override;
void InvertOrder() ;
};
} // namespace scram::coreUpdated on 2026-01-09 at 21:59:13 +0000