/*
* Copyright (C) 2014-2018 Olzhas Rakhimov
*
* 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 .
*/
/// @file
/// A collection of PDAG transformation/preprocessing algorithms
/// that simplify fault trees for analysis.
#pragma once
#include
#include
#include
#include
#include
#include
#include
#include "pdag.h"
namespace scram::core {
namespace pdag {
/// Applies graph transformations consecutively.
///
/// @param[in,out] graph The graph to be transformed.
/// @param[in] unary_op The first operation to be applied.
/// @param[in] unary_ops The rest of transformations to apply.
template
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(unary_ops)...);
}
/// Determines the order of traversal for gate arguments.
/// This function does not assign the order of nodes.
///
/// @tparam T Type of the arguments.
///
/// @param[in] gate The host gate parent.
///
/// @returns An ordered, stable list of arguments.
template
std::vector OrderArguments(Gate* gate) noexcept;
/// Assigns topological ordering to nodes of the PDAG.
/// The ordering is assigned to the node order marks.
/// The nodes are sorted in descending optimization value.
/// The highest order value belongs to the root.
///
/// @param[in,out] graph The graph to be processed.
///
/// @post The root and descendant node order marks contain the ordering.
void TopologicalOrder(Pdag* graph) noexcept;
/// Marks coherence of the whole graph.
///
/// @param[in,out] graph The graph to be processed.
///
/// @post Gate traversal marks are dirty.
void MarkCoherence(Pdag* graph) noexcept;
} // namespace pdag
/// The class provides main preprocessing operations
/// over a PDAG
/// to simplify the fault tree
/// and to help analysis run more efficiently.
class Preprocessor : private boost::noncopyable {
public:
/// Constructs a preprocessor of a PDAG
/// representing a fault tree.
///
/// @param[in] graph The PDAG to be preprocessed.
///
/// @warning There should not be another shared pointer to the root gate
/// outside of the passed PDAG.
/// Upon preprocessing a new root gate may be assigned to the graph,
/// and, if there is an extra pointer to the previous top gate
/// outside of the graph,
/// the destructor will not be called
/// as expected by the preprocessing algorithms,
/// which will mess the new structure of the PDAG.
explicit Preprocessor(Pdag* graph) noexcept;
virtual ~Preprocessor() = default;
/// Runs the graph preprocessing.
void operator()() noexcept;
protected:
class GateSet; ///< Container of unique gates by semantics.
/// Runs the default preprocessing
/// that achieves the graph in a normal form.
virtual void Run() noexcept = 0;
/// The initial phase of preprocessing.
/// The most basic cleanup algorithms are applied.
/// The cleanup should benefit all other phases
/// and algorithms.
///
/// @note The constants or house events in the graph are cleaned.
/// Any constant state gates must be removed
/// by the future preprocessing algorithms
/// as they introduce these constant state gates.
/// @note NULL type (pass-through) gates are processed.
/// Any NULL type gates must be processed and removed
/// by the future preprocessing algorithms
/// as they introduce these NULL type gates.
///
/// @warning This phase also runs partial normalization of gates;
/// however, the preprocessing algorithms should not rely on this.
/// If the partial normalization messes some significant algorithm,
/// it may be removed from this phase in future.
void RunPhaseOne() noexcept;
/// Preprocessing phase of the original structure of the graph.
/// This phase attempts to leverage
/// the existing information from the structure of the graph
/// to maximize the optimization
/// and to make the preprocessing techniques efficient.
///
/// @note Multiple definitions of gates are detected and processed.
/// @note Modules are detected and created.
/// @note Non-module and non-multiple gates are coalesced.
/// @note Boolean optimization is applied.
void RunPhaseTwo() noexcept;
/// Application of gate normalization.
/// After this phase,
/// the graph is in normal form.
///
/// @note Gate normalization is conducted.
void RunPhaseThree() noexcept;
/// Propagation of complements.
/// Complements are propagated down to the variables in the graph.
/// After this phase,
/// the graph is in negation normal form.
///
/// @note Complements are propagated to the variables of the graph.
void RunPhaseFour() noexcept;
/// The final phase
/// that cleans up the graph,
/// and puts the structure of the graph ready for analysis.
/// This phase makes the graph structure
/// alternating AND/OR gate layers.
void RunPhaseFive() noexcept;
/// Normalizes the gates of the whole PDAG
/// into OR, AND gates.
///
/// @param[in] full A flag to handle complex gates like XOR and K/N,
/// which generate a lot more new gates
/// and make the structure of the graph more complex.
///
/// @note The negation of the top gate is saved
/// and handled as a special case for negation propagation
/// because it does not have a parent.
/// @note New gates are created only upon full normalization
/// of complex gates like XOR and K/N.
/// @note The full normalization is meant to be called only once.
///
/// @warning The root get may still be NULL type.
/// @warning Gate marks are used.
/// @warning Node ordering may be used for full normalization.
/// @warning Node visit information is used.
void NormalizeGates(bool full) noexcept;
/// Notifies all parents of negative gates,
/// such as NOT, NOR, and NAND,
/// before transforming these gates
/// into basic gates of OR and AND.
/// The argument gates are swapped with a negative sign.
///
/// @param[in] gate The gate to start processing.
///
/// @note This function is a helper function for NormalizeGates().
///
/// @warning Gate marks must be clear.
/// @warning This function does not change the types of gates.
/// @warning The root gate does not have parents,
/// so it is not handled here.
void NotifyParentsOfNegativeGates(const GatePtr& gate) noexcept;
/// Normalizes complex gates into OR, AND gates.
///
/// @param[in,out] gate The gate to be processed.
/// @param[in] full A flag to handle complex gates like XOR and K/N.
///
/// @note This is a helper function for NormalizeGates().
///
/// @note This function registers NULL type gates for future removal.
///
/// @warning Gate marks must be clear.
/// @warning The parents of negative gates are assumed to be
/// notified about the change of their arguments' types.
void NormalizeGate(const GatePtr& gate, bool full) noexcept;
/// Normalizes a gate with XOR logic.
/// This is a helper function
/// for the main gate normalization function.
///
/// @param[in,out] gate The gate to normalize.
///
/// @note This is a helper function for NormalizeGate.
void NormalizeXorGate(const GatePtr& gate) noexcept;
/// Normalizes a VOTE gate with a vote number.
/// The gate is turned into an OR gate of
/// recursively normalized VOTE and AND arg gates
/// according to the formula
/// K/N(x, y_i) = OR(AND(x, K-1/N-1(y_i)), K/N-1(y_i)))
/// with y_i being the rest of formula arguments,
/// which exclude x.
/// This representation is more friendly
/// to other preprocessing and analysis techniques
/// than the alternative,
/// which is OR of AND gates of combinations.
/// Normalization of K/N gates is aware of variable ordering.
///
/// @param[in,out] gate The VOTE gate to normalize.
///
/// @pre Variable ordering is assigned to arguments.
/// @pre This helper function is called from NormalizeGate.
void NormalizeVoteGate(const GatePtr& gate) noexcept;
/// Propagates complements of argument gates down to leafs
/// according to the De Morgan's law
/// in order to remove any negative logic from the graph's gates.
/// The resulting graph will contain only positive gates, OR and AND types.
/// After this function, the PDAG is in negation normal form.
///
/// @param[in,out] gate The starting gate to traverse the graph.
/// This is for recursive purposes.
/// @param[in] keep_modules A flag to NOT propagate complements to modules.
/// @param[in,out] complements The processed complements of shared gates.
///
/// @note The graph must be normalized.
/// It must contain only OR and AND gates.
///
/// @warning Gate marks must be clear.
/// @warning If the root gate has a negative sign,
/// it must be handled before calling this function.
/// The arguments and type of the gate
/// must be inverted according to the logic of the root gate.
void
PropagateComplements(const GatePtr& gate, bool keep_modules,
std::unordered_map* complements) noexcept;
/// Runs gate coalescence on the whole PDAG.
///
/// @param[in] common A flag to also coalesce common/shared gates.
/// These gates may be important for other algorithms.
///
/// @returns true if the graph has been changed.
///
/// @note Module gates are omitted from coalescing to preserve them.
///
/// @warning Gate marks are used.
bool CoalesceGates(bool common) noexcept;
/// Coalesces positive argument gates
/// with the same OR or AND logic as parents.
/// This function merges similar logic gates of NAND and NOR as well.
///
/// @param[in,out] gate The starting gate to traverse the graph.
/// This is for recursive purposes.
/// @param[in] common A flag to also join common gates.
/// These gates may be important for other algorithms.
///
/// @returns true if the given graph has been changed by this function.
/// @returns false if no change has been made.
///
/// @note Constant state gates may be generated upon joining.
/// These gates are registered for future processing.
/// @note It is impossible that this function generates NULL type gates.
/// @note Module gates are omitted from coalescing to preserve them.
///
/// @warning Gate marks are used.
bool CoalesceGates(const GatePtr& gate, bool common) noexcept;
/// Detects and replaces multiple definitions of gates.
/// Gates with the same logic and inputs
/// but different indices are considered redundant.
///
/// @returns true if multiple definitions are found and replaced.
///
/// @note This function does not recursively detect multiple definitions
/// due to replaced redundant arguments of gates.
/// The replaced gates are considered a new graph,
/// and this function must be called again
/// to verify that the new graph does not have multiple definitions.
bool ProcessMultipleDefinitions() noexcept;
/// Traverses the PDAG to collect multiple definitions of gates.
///
/// @param[in] gate The gate to traverse the sub-graph.
/// @param[in,out] multi_def Detected multiple definitions.
/// @param[in,out] unique_gates A set of semantically unique gates.
///
/// @warning Gate marks must be clear.
void DetectMultipleDefinitions(
const GatePtr& gate,
std::unordered_map>* multi_def,
GateSet* unique_gates) noexcept;
/// Traverses the PDAG to detect modules.
/// Modules are independent sub-graphs
/// without common nodes with the rest of the graph.
void DetectModules() noexcept;
/// Traverses the given gate
/// and assigns time of visit to nodes.
///
/// @param[in] time The current time.
/// @param[in,out] gate The gate to traverse and assign time to.
///
/// @returns The final time of traversing.
int AssignTiming(int time, const GatePtr& gate) noexcept;
/// Determines modules from original gates
/// that have been already timed.
/// This function can also create new modules from the existing graph.
///
/// @param[in,out] gate The gate to test for modularity.
void FindModules(const GatePtr& gate) noexcept;
/// Processes gate arguments found during the module detection.
///
/// @param[in,out] gate The gate with the arguments.
/// @param[in] non_shared_args Args that belong only to this gate.
/// @param[in,out] modular_args Args that may be grouped into new modules.
/// @param[in,out] non_modular_args Args that cannot be grouped into modules.
void ProcessModularArgs(
const GatePtr& gate,
const std::vector>& non_shared_args,
std::vector>* modular_args,
std::vector>* non_modular_args) noexcept;
/// Creates a new module
/// as an argument of an existing gate
/// if the logic of the existing parent gate allows a sub-module.
/// The existing arguments of the original gate
/// are used to create the new module.
/// If the new module must contain all the arguments,
/// the original gate is asserted to be a module,
/// and no operation is performed.
///
/// @param[in,out] gate The parent gate for a module.
/// @param[in] args Modular arguments to be added into the new module.
///
/// @returns Pointer to the new module if it is created.
GatePtr
CreateNewModule(const GatePtr& gate,
const std::vector>& args) noexcept;
/// Checks if a group of modular arguments share
/// anything with non-modular arguments.
/// If so, then the modular arguments are not actually modular,
/// and those arguments are removed from modular containers.
/// This is due to chain of nodes
/// that are shared between modular and non-modular arguments.
///
/// @param[in,out] modular_args Candidates for modular grouping.
/// @param[in,out] non_modular_args Non modular arguments.
void FilterModularArgs(
std::vector>* modular_args,
std::vector>* non_modular_args) noexcept;
/// Groups modular arguments by their common elements.
/// The gates created with these modular arguments
/// are guaranteed to be independent modules.
///
/// @param[in,out] modular_args Candidates for modular grouping.
/// @param[out] groups Grouped modular arguments.
void GroupModularArgs(
std::vector>* modular_args,
std::vector>>* groups) noexcept;
/// Creates new module gates
/// from groups of modular arguments
/// if the logic of the parent gate allows sub-modules.
/// The existing arguments of the original gate
/// are used to create the new modules.
/// If all the parent gate arguments are modular and within one group,
/// the parent gate is asserted to be a module gate,
/// and no operation is performed.
///
/// @param[in,out] gate The parent gate for a module.
/// @param[in] modular_args All the modular arguments.
/// @param[in] groups Grouped modular arguments.
void CreateNewModules(
const GatePtr& gate,
const std::vector>& modular_args,
const std::vector>>& groups) noexcept;
/// Gathers all modules in the PDAG.
///
/// @returns Unique modules encountered breadth-first.
///
/// @pre Module detection and marking has already been performed.
///
/// @warning Gate marks are used.
std::vector GatherModules() noexcept;
/// Identifies common arguments of gates,
/// and merges the common arguments into new gates.
/// This technique helps uncover the common structure
/// within gates that are not modules.
///
/// @returns true if the graph structure is changed by this technique.
///
/// @note This technique works only with OR/AND gates.
/// Partial or full normalization may make
/// this technique more effective.
/// @note Constant arguments are not expected.
///
/// @warning Gate marks are used for traversal.
/// @warning Node counts are used for common node detection.
bool MergeCommonArgs() noexcept;
/// Merges common arguments for a specific group of gates.
/// The gates are grouped by their operators.
/// This is a helper function
/// that divides the main merging technique by the gate types.
///
/// @param[in] op The operator that defines the group.
///
/// @returns true if common args are merged into gates.
///
/// @note The operator or logic of the gates must allow merging.
/// OR/AND operators are expected.
///
/// @warning Gate marks are used for traversal.
/// @warning Node counts are used for common node detection.
bool MergeCommonArgs(Operator op) noexcept;
/// Marks common arguments of gates with a specific operator.
///
/// @param[in] gate The gate to start the traversal.
/// @param[in] op The operator of gates
/// which arguments must be marked.
///
/// @note Node count information is used to mark the common arguments.
///
/// @warning Gate marks are used for linear traversal.
void MarkCommonArgs(const GatePtr& gate, Operator op) noexcept;
/// Helper struct for algorithms
/// that must make an optimal decision
/// how to merge or factor out
/// common arguments of gates into new gates.
struct MergeTable {
using CommonArgs = std::vector; ///< Unique, sorted common arguments.
using CommonParents = std::set; ///< Unique common parent gates.
using Option = std::pair; ///< One possibility.
using OptionGroup = std::vector