scram::core::Preprocessor

The class provides main preprocessing operations over a PDAG to simplify the fault tree and to help analysis run more efficiently.

#include <preprocessor.h>

Inherits from boost::noncopyable

Inherited by scram::core::CustomPreprocessor< Bdd >, scram::core::CustomPreprocessor< Zbdd >

Public Classes

	Name
class	GateSet <br>Container of unique gates.

Protected Classes

	Name
class	DecompositionProcessor <br>Functor for processing of decomposition setups with common nodes.
struct	MergeTable <br>Helper struct for algorithms that must make an optimal decision how to merge or factor out common arguments of gates into new gates.

Public Functions

	Name
	Preprocessor(Pdag * graph)<br>Constructs a preprocessor of a PDAG representing a fault tree.
virtual	~Preprocessor() =default
void	operator()()<br>Runs the graph preprocessing.

Protected Functions

	Name
virtual void	Run() =0<br>Container of unique gates by semantics.
void	RunPhaseOne()<br>The initial phase of preprocessing.
void	RunPhaseTwo()<br>Preprocessing phase of the original structure of the graph.
void	RunPhaseThree()<br>Application of gate normalization.
void	RunPhaseFour()<br>Propagation of complements.
void	RunPhaseFive()<br>The final phase that cleans up the graph, and puts the structure of the graph ready for analysis.
void	NormalizeGates(bool full)<br>Normalizes the gates of the whole PDAG into OR, AND gates.
void	NotifyParentsOfNegativeGates(const GatePtr & gate)<br>Notifies all parents of negative gates, such as NOT, NOR, and NAND, before transforming these gates into basic gates of OR and AND.
void	NormalizeGate(const GatePtr & gate, bool full)<br>Normalizes complex gates into OR, AND gates.
void	NormalizeXorGate(const GatePtr & gate)<br>Normalizes a gate with XOR logic.
void	NormalizeAtleastGate(const GatePtr & gate)<br>Normalizes a ATLEAST gate with a atleast number.
void	PropagateComplements(const GatePtr & gate, bool keep_modules, std::unordered_map< int, GatePtr > * complements)<br>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.
bool	CoalesceGates(bool common)<br>Runs gate coalescence on the whole PDAG.
bool	CoalesceGates(const GatePtr & gate, bool common)<br>Coalesces positive argument gates with the same OR or AND logic as parents.
bool	ProcessMultipleDefinitions()<br>Detects and replaces multiple definitions of gates.
void	DetectMultipleDefinitions(const GatePtr & gate, std::unordered_map< GatePtr, std::vector< GateWeakPtr > > * multi_def, GateSet * unique_gates)<br>Traverses the PDAG to collect multiple definitions of gates.
void	DetectModules()<br>Traverses the PDAG to detect modules.
int	AssignTiming(int time, const GatePtr & gate)<br>Traverses the given gate and assigns time of visit to nodes.
void	FindModules(const GatePtr & gate)<br>Determines modules from original gates that have been already timed.
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)<br>Processes gate arguments found during the module detection.
GatePtr	CreateNewModule(const GatePtr & gate, const std::vector< std::pair< int, NodePtr > > & args)<br>Creates a new module as an argument of an existing gate if the logic of the existing parent gate allows a sub-module.
void	FilterModularArgs(std::vector< std::pair< int, NodePtr > > * modular_args, std::vector< std::pair< int, NodePtr > > * non_modular_args)<br>Checks if a group of modular arguments share anything with non-modular arguments.
void	GroupModularArgs(std::vector< std::pair< int, NodePtr > > * modular_args, std::vector< std::vector< std::pair< int, NodePtr > > > * groups)<br>Groups modular arguments by their common elements.
void	CreateNewModules(const GatePtr & gate, const std::vector< std::pair< int, NodePtr > > & modular_args, const std::vector< std::vector< std::pair< int, NodePtr > > > & groups)<br>Creates new module gates from groups of modular arguments if the logic of the parent gate allows sub-modules.
std::vector< GateWeakPtr >	GatherModules()<br>Gathers all modules in the PDAG.
bool	MergeCommonArgs()<br>Identifies common arguments of gates, and merges the common arguments into new gates.
bool	MergeCommonArgs(Connective op)<br>Merges common arguments for a specific group of gates.
void	MarkCommonArgs(const GatePtr & gate, Connective op)<br>Marks common arguments of gates with a specific connective.
void	GatherCommonArgs(const GatePtr & gate, Connective op, MergeTable::Candidates * group)<br>Gathers common arguments of the gates in the group of a specific connective.
void	FilterMergeCandidates(MergeTable::Candidates * candidates)<br>Filters merge candidates and their shared arguments to detect opportunities for simplifications like gate substitutions.
void	GroupCandidatesByArgs(MergeTable::Candidates * candidates, std::vector< MergeTable::Candidates > * groups)<br>Groups candidates with common arguments.
void	GroupCommonParents(int num_common_args, const MergeTable::Candidates & group, MergeTable::Collection * parents)<br>Finds intersections of common arguments of gates.
void	GroupCommonArgs(const MergeTable::Collection & options, MergeTable * table)<br>Groups common args for merging.
void	FindOptionGroup(MergeTable::MergeGroup * all_options, MergeTable::OptionGroup * best_group)<br>Finds an optimal way of grouping options.
void	FindBaseOption(MergeTable::MergeGroup * all_options, MergeTable::MergeGroup::iterator * best_option)<br>Finds the starting option for group formation.
void	TransformCommonArgs(MergeTable::MergeGroup * group)<br>Transforms common arguments of gates into new gates.
bool	DetectDistributivity()<br>Detects and manipulates AND and OR gate distributivity for the whole graph.
bool	DetectDistributivity(const GatePtr & gate)<br>Detects and manipulates AND and OR gate distributivity.
bool	HandleDistributiveArgs(const GatePtr & gate, Connective distr_type, std::vector< GatePtr > * candidates)<br>Manipulates gates with distributive arguments.
bool	FilterDistributiveArgs(const GatePtr & gate, std::vector< GatePtr > * candidates)<br>Detects relationships between the gate and its distributive arguments to remove unnecessary candidates.
void	GroupDistributiveArgs(const MergeTable::Collection & options, MergeTable * table)<br>Groups distributive gate arguments for future factorization.
void	TransformDistributiveArgs(const GatePtr & gate, Connective distr_type, MergeTable::MergeGroup * group)<br>Transforms distributive of arguments gates into a new subgraph.
void	BooleanOptimization()<br>Propagates failures of common nodes to detect redundancy.
void	GatherCommonNodes(std::vector< GateWeakPtr > * common_gates, std::vector< std::weak_ptr< Variable > > * common_variables)<br>Traverses the graph to find nodes that have more than one parent.
template <class N > <br>void	ProcessCommonNode(const std::weak_ptr< N > & common_node)<br>Tries to simplify the graph by removing redundancies generated by a common node.
void	MarkAncestors(const NodePtr & node, GatePtr * module)<br>Marks ancestor gates true.
int	PropagateState(const GatePtr & gate, const NodePtr & node)<br>Propagates failure or success of a common node by setting its ancestors' optimization values to 1 or -1 if they fail or succeed according to their Boolean logic.
void	DetermineGateState(const GatePtr & gate, int num_failure, int num_success)<br>Determines if a gate fails or succeeds due to failed/succeeded arguments.
int	CollectStateDestinations(const GatePtr & gate, int index, std::unordered_map< int, GateWeakPtr > * destinations)<br>Collects failure or success destinations and marks non-redundant nodes.
void	CollectRedundantParents(const NodePtr & node, std::unordered_map< int, GateWeakPtr > * destinations, std::vector< GateWeakPtr > * redundant_parents)<br>Detects if parents of a node are redundant.
void	ProcessRedundantParents(const NodePtr & node, const std::vector< GateWeakPtr > & redundant_parents)<br>Detects if parents of a node are redundant.
template <class N > <br>void	ProcessStateDestinations(const std::shared_ptr< N > & node, const std::unordered_map< int, GateWeakPtr > & destinations)<br>Transforms failure or success destination according to the logic and the common node.
void	ClearStateMarks(const GatePtr & gate)<br>Clears all the ancestor marks used in Boolean optimization steps.
bool	DecomposeCommonNodes()<br>The Shannon decomposition for common nodes in the PDAG.
void	ReplaceGate(const GatePtr & gate, const GatePtr & replacement)<br>Replaces one gate in the graph with another.
bool	RegisterToClear(const GatePtr & gate)<br>Registers mutated gates for potential deletion later.
void	GatherNodes(std::vector< GatePtr > * gates, std::vector< VariablePtr > * variables)<br>Gathers all nodes in the PDAG.
void	GatherNodes(const GatePtr & gate, std::vector< GatePtr > * gates, std::vector< VariablePtr > * variables)<br>Gathers nodes in the sub-graph.

Protected Attributes

	Name
Pdag *	graph_ <br>The PDAG to preprocess.

Public Functions Documentation

function Preprocessor

cpp

explicit Preprocessor(
    Pdag * graph
)

Constructs a preprocessor of a PDAG representing a fault tree.

Parameters:

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.

function ~Preprocessor

cpp

virtual ~Preprocessor() =default

function operator()

cpp

void operator()()

Runs the graph preprocessing.

Protected Functions Documentation

function Run

cpp

virtual void Run() =0

Container of unique gates by semantics.

Reimplemented by: scram::core::CustomPreprocessor< Bdd >::Run, scram::core::CustomPreprocessor< Zbdd >::Run, scram::core::CustomPreprocessor< Mocus >::Run

Runs the default preprocessing that achieves the graph in a normal form.

function RunPhaseOne

cpp

void RunPhaseOne()

The initial phase of preprocessing.

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.
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.

The most basic cleanup algorithms are applied. The cleanup should benefit all other phases and algorithms.

function RunPhaseTwo

cpp

void RunPhaseTwo()

Preprocessing phase of the original structure of the graph.

Note:

Multiple definitions of gates are detected and processed.
Modules are detected and created.
Non-module and non-multiple gates are coalesced.
Boolean optimization is applied.

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.

function RunPhaseThree

cpp

void RunPhaseThree()

Application of gate normalization.

Note: Gate normalization is conducted.

After this phase, the graph is in normal form.

function RunPhaseFour

cpp

void RunPhaseFour()

Propagation of complements.

Note: Complements are propagated to the variables of the graph.

Complements are propagated down to the variables in the graph. After this phase, the graph is in negation normal form.

function RunPhaseFive

cpp

void RunPhaseFive()

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.

function NormalizeGates

cpp

void NormalizeGates(
    bool full
)

Normalizes the gates of the whole PDAG into OR, AND gates.

Parameters:

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.
New gates are created only upon full normalization of complex gates like XOR and K/N.
The full normalization is meant to be called only once.

Warning:

The root get may still be NULL type.
Gate marks are used.
Node ordering may be used for full normalization.
Node visit information is used.

function NotifyParentsOfNegativeGates

cpp

void NotifyParentsOfNegativeGates(
    const GatePtr & gate
)

Notifies all parents of negative gates, such as NOT, NOR, and NAND, before transforming these gates into basic gates of OR and AND.

Parameters:

gate The gate to start processing.

Note: This function is a helper function for NormalizeGates().

Warning:

Gate marks must be clear.
This function does not change the types of gates.
The root gate does not have parents, so it is not handled here.

The argument gates are swapped with a negative sign.

function NormalizeGate

cpp

void NormalizeGate(
    const GatePtr & gate,
    bool full
)

Normalizes complex gates into OR, AND gates.

Parameters:

gate The gate to be processed.
full A flag to handle complex gates like XOR and K/N.

Note:

This is a helper function for NormalizeGates().
This function registers NULL type gates for future removal.

Warning:

Gate marks must be clear.
The parents of negative gates are assumed to be notified about the change of their arguments' types.

function NormalizeXorGate

cpp

void NormalizeXorGate(
    const GatePtr & gate
)

Normalizes a gate with XOR logic.

Parameters:

gate The gate to normalize.

Note: This is a helper function for NormalizeGate.

This is a helper function for the main gate normalization function.

function NormalizeAtleastGate

cpp

void NormalizeAtleastGate(
    const GatePtr & gate
)

Normalizes a ATLEAST gate with a atleast number.

Parameters:

gate The ATLEAST gate to normalize.

Precondition:

Variable ordering is assigned to arguments.
This helper function is called from NormalizeGate.

The gate is turned into an OR gate of recursively normalized ATLEAST 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.

function PropagateComplements

cpp

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

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.

Parameters:

gate The starting gate to traverse the graph. This is for recursive purposes.
keep_modules A flag to NOT propagate complements to modules.
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.
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.

The resulting graph will contain only positive gates, OR and AND types. After this function, the PDAG is in negation normal form.

function CoalesceGates

cpp

bool CoalesceGates(
    bool common
)

Runs gate coalescence on the whole PDAG.

Parameters:

common A flag to also coalesce common/shared gates. These gates may be important for other algorithms.

Return: true if the graph has been changed.

Note: Module gates are omitted from coalescing to preserve them.

Warning: Gate marks are used.

function CoalesceGates

cpp

bool CoalesceGates(
    const GatePtr & gate,
    bool common
)

Coalesces positive argument gates with the same OR or AND logic as parents.

Parameters:

gate The starting gate to traverse the graph. This is for recursive purposes.
common A flag to also join common gates. These gates may be important for other algorithms.

Return:

true if the given graph has been changed by this function.
false if no change has been made.

Note:

Constant state gates may be generated upon joining. These gates are registered for future processing.
It is impossible that this function generates NULL type gates.
Module gates are omitted from coalescing to preserve them.

Warning: Gate marks are used.

This function merges similar logic gates of NAND and NOR as well.

function ProcessMultipleDefinitions

cpp

bool ProcessMultipleDefinitions()

Detects and replaces multiple definitions of gates.

Return: 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.

Gates with the same logic and inputs but different indices are considered redundant.

function DetectMultipleDefinitions

cpp

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

Traverses the PDAG to collect multiple definitions of gates.

Parameters:

gate The gate to traverse the sub-graph.
multi_def Detected multiple definitions.
unique_gates A set of semantically unique gates.

Warning: Gate marks must be clear.

function DetectModules

cpp

void DetectModules()

Traverses the PDAG to detect modules.

Modules are independent sub-graphs without common nodes with the rest of the graph.

function AssignTiming

cpp

int AssignTiming(
    int time,
    const GatePtr & gate
)

Traverses the given gate and assigns time of visit to nodes.

Parameters:

time The current time.
gate The gate to traverse and assign time to.

Return: The final time of traversing.

function FindModules

cpp

void FindModules(
    const GatePtr & gate
)

Determines modules from original gates that have been already timed.

Parameters:

gate The gate to test for modularity.

This function can also create new modules from the existing graph.

function ProcessModularArgs

cpp

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
)

Processes gate arguments found during the module detection.

Parameters:

gate The gate with the arguments.
non_shared_args Args that belong only to this gate.
modular_args Args that may be grouped into new modules.
non_modular_args Args that cannot be grouped into modules.

function CreateNewModule

cpp

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

Creates a new module as an argument of an existing gate if the logic of the existing parent gate allows a sub-module.

Parameters:

gate The parent gate for a module.
args Modular arguments to be added into the new module.

Return: Pointer to the new module if it is created.

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.

function FilterModularArgs

cpp

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

Checks if a group of modular arguments share anything with non-modular arguments.

Parameters:

modular_args Candidates for modular grouping.
non_modular_args 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.

function GroupModularArgs

cpp

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

Groups modular arguments by their common elements.

Parameters:

modular_args Candidates for modular grouping.
groups Grouped modular arguments.

The gates created with these modular arguments are guaranteed to be independent modules.

function CreateNewModules

cpp

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

Creates new module gates from groups of modular arguments if the logic of the parent gate allows sub-modules.

Parameters:

gate The parent gate for a module.
modular_args All the modular arguments.
groups Grouped modular arguments.

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.

function GatherModules

cpp

std::vector< GateWeakPtr > GatherModules()

Gathers all modules in the PDAG.

Return: Unique modules encountered breadth-first.

Warning: Gate marks are used.

Precondition: Module detection and marking has already been performed.

function MergeCommonArgs

cpp

bool MergeCommonArgs()

Identifies common arguments of gates, and merges the common arguments into new gates.

Return: 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.
Constant arguments are not expected.

Warning:

Gate marks are used for traversal.
Node counts are used for common node detection.

This technique helps uncover the common structure within gates that are not modules.

function MergeCommonArgs

cpp

bool MergeCommonArgs(
    Connective op
)

Merges common arguments for a specific group of gates.

Parameters:

op The connective that defines the group.

Return: true if common args are merged into gates.

Note: The connective or logic of the gates must allow merging. OR/AND connectives are expected.

Warning:

Gate marks are used for traversal.
Node counts are used for common node detection.

The gates are grouped by their connectives. This is a helper function that divides the main merging technique by the gate types.

function MarkCommonArgs

cpp

void MarkCommonArgs(
    const GatePtr & gate,
    Connective op
)

Marks common arguments of gates with a specific connective.

Parameters:

gate The gate to start the traversal.
op The connective 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.

function GatherCommonArgs

cpp

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

Gathers common arguments of the gates in the group of a specific connective.

Parameters:

gate The gate to start the traversal.
op The connective of gates in the group.
group The group of the gates with their common arguments.

Note:

The common arguments are sorted.
The gathering is limited by modules. That is, no search is performed in submodules because they don't have common args with the supermodule.

Warning: Gate marks are used for linear traversal.

The common arguments must be marked by the second visit exit time.

function FilterMergeCandidates

cpp

void FilterMergeCandidates(
    MergeTable::Candidates * candidates
)

Filters merge candidates and their shared arguments to detect opportunities for simplifications like gate substitutions.

Parameters:

candidates The group of merge candidate gates

Note: The simplifications are based on optimistic heuristics, and the end result may not be the most optimal.

Warning: May produce NULL type and constant gates.

function GroupCandidatesByArgs

cpp

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

Groups candidates with common arguments.

Parameters:

candidates The group of the gates with their common args.
groups Non-intersecting collection of groups of candidates.

Note: Groups with only one member are discarded.

The groups do not intersect either by candidates or common arguments.

function GroupCommonParents

cpp

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

Finds intersections of common arguments of gates.

Parameters:

num_common_args The least number common arguments to consider.
group The group of the gates with their common arguments.
parents Grouped common parent gates for the sets of common arguments.

Note: The common arguments are sorted.

Gates with the same common arguments are grouped to represent common parents for the arguments.

function GroupCommonArgs

cpp

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

Groups common args for merging.

Parameters:

options Combinations of common args and distributive gates.
table Groups of distributive gates for separate manipulation.

The common parents of arguments are isolated into groups so that other groups are not affected by the merging operations.

function FindOptionGroup

cpp

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

Finds an optimal way of grouping options.

Parameters:

all_options The sorted set of options. The options must be sorted in ascending size of common arguments.
best_group The optimal group of options.

Note: The all_options parameter is not passed by const reference because the best group must store non const pointers to options. It is expected that the chosen options will be manipulated by the user of this function through these pointers. However, this function guarantees not to manipulate or change the set of all options.

The goal of this function is to maximize the effect of gate merging or common argument factorization.

After common arguments and parents are grouped, the merging technique must find the most optimal strategy to create new gates that will represent the common arguments. The strategy may favor modularity, size, or other parameters of the new structure of the final graph. The common elements within the groups of common parents and common arguments create the biggest challenge for finding the optimal solution. For example, { (a, b) : (p1, p2), (b, c) : (p2, p3) } The strategy has to make the most optimal choice between two mutually exclusive options.

function FindBaseOption

cpp

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

Finds the starting option for group formation.

Parameters:

all_options The sorted set of options. The options must be sorted in ascending size of common arguments.
best_option The optimal starting option if any. If not found, iterator at the end of the group.

function TransformCommonArgs

cpp

void TransformCommonArgs(
    MergeTable::MergeGroup * group
)

Transforms common arguments of gates into new gates.

Parameters:

group Group of merge options for manipulation.

function DetectDistributivity

cpp

bool DetectDistributivity()

Detects and manipulates AND and OR gate distributivity for the whole graph.

Return: true if the graph is changed.

function DetectDistributivity

cpp

bool DetectDistributivity(
    const GatePtr & gate
)

Detects and manipulates AND and OR gate distributivity.

Parameters:

gate The gate which arguments and subgraph must be tested.

Return: true if transformations are performed.

Note:

This algorithm does not produce constant gates.
NULL type gates are registered if produced.

Warning: Gate marks must be clear.

For example, (a | b) & (a | c) = a | b & c.

function HandleDistributiveArgs

cpp

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

Manipulates gates with distributive arguments.

Parameters:

gate The gate which arguments must be manipulated.
distr_type The type of distributive arguments.
candidates Candidates for distributivity check.

Return: true if transformations are performed.

Designed to work with distributivity detection and manipulation logic.

function FilterDistributiveArgs

cpp

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

Detects relationships between the gate and its distributive arguments to remove unnecessary candidates.

Parameters:

gate The gate which arguments must be filtered.
candidates Candidates for distributivity check.

Return: true if the candidates and the gate are manipulated.

Note: The redundant candidates are also removed from the gate.

The determination of redundant candidates follow the Boolean logic. For example, if any argument is superset of another argument, it can be removed from the gate.

function GroupDistributiveArgs

cpp

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

Groups distributive gate arguments for future factorization.

Parameters:

options Combinations of common args and distributive gates.
table Groups of distributive gates for separate manipulation.

The function tries to maximize the return from the gate manipulations.

function TransformDistributiveArgs

cpp

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

Transforms distributive of arguments gates into a new subgraph.

Parameters:

gate The parent gate of all the distributive arguments.
distr_type The type of distributive arguments.
group Group of distributive args options for manipulation.

function BooleanOptimization

cpp

void BooleanOptimization()

Propagates failures of common nodes to detect redundancy.

Warning:

Boolean optimization may replace the root gate of the graph.
Node visit information is manipulated.
Gate marks are manipulated.
Node optimization values are manipulated.

The graph structure is optimized by removing the redundancies if possible. This optimization helps reduce the number of common nodes.

function GatherCommonNodes

cpp

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

Traverses the graph to find nodes that have more than one parent.

Parameters:

common_gates Gates with more than one parent.
common_variables Common variables.

Note: Constant nodes are not expected to be operated.

Warning: Node visit information is manipulated.

Common nodes are encountered breadth-first, and they are unique.

function ProcessCommonNode

cpp

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

Tries to simplify the graph by removing redundancies generated by a common node.

Parameters:

common_node A node with more than one parent.

Template Parameters:

N Non-Node, concrete (i.e. Gate, etc.) type.

function MarkAncestors

cpp

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

Marks ancestor gates true.

Parameters:

node The child node.
module The root module gate ancestor.

Warning: Since very specific branches are marked 'true', cleanup must be performed after/with the use of the ancestors. If the cleanup is done improperly or not at all, the default global contract of clean marks will be broken.

Precondition: Gate marks are clear.

The marking stops at the root of an independent subgraph for algorithmic efficiency.

function PropagateState

cpp

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

Propagates failure or success of a common node by setting its ancestors' optimization values to 1 or -1 if they fail or succeed according to their Boolean logic.

Parameters:

gate The root gate under consideration.
node The node that is the source of failure.

Return: Total multiplicity of the node.

Precondition:

The optimization value of the main common node is 1 or -1.
The marks of ancestor gates are 'true'.

Postcondition:

The marks of all ancestor gates are reset to 'false'.
All ancestor gates are marked with the descendant index.

The failure of an argument is similar to propagating constant TRUE/1. The success of an argument is similar to propagating constant FALSE/-1.

function DetermineGateState

cpp

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

Determines if a gate fails or succeeds due to failed/succeeded arguments.

Parameters:

gate The gate with the arguments.
num_failure The number of failure (TRUE/1) arguments.
num_success The number of success (FALSE/-1) arguments.

If gates fails, its optimization value is set to 1. If it succeeds, its optimization value is -1. If the state is indeterminate, the optimization value is 0.

function CollectStateDestinations

cpp

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

Collects failure or success destinations and marks non-redundant nodes.

Parameters:

gate The non-failed gate which sub-graph is to be traversed.
index The index of the main state-source common node.
destinations Destinations of the state.

Return: The number of encounters with the destinations.

The optimization value for non-redundant gates are set to 2.

function CollectRedundantParents

cpp

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

Detects if parents of a node are redundant.

Parameters:

node The common node.
destinations Destinations of the state.
redundant_parents A set of redundant parents.

Precondition:

Destinations have valid state (Success or Failure).
Non-redundant parents have optimization value 2.

Postcondition: Destinations that are also redundant parents are removed if the semantics of the transformations is equivalent.

function ProcessRedundantParents

cpp

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

Detects if parents of a node are redundant.

Parameters:

node The common node.
redundant_parents A set of redundant parents.

Note:

Constant gates are registered for removal.
Null type gates are registered for removal.

If there are redundant parents, depending on the logic of the parent, the node is removed from the parent unless it is also in the destination set with specific logic. In the latter case, the parent is removed from the destinations.

function ProcessStateDestinations

cpp

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

Transforms failure or success destination according to the logic and the common node.

Parameters:

node The common node.
destinations Destination gates for the state.

Template Parameters:

N Non-Node, concrete (i.e. Gate, etc.) type.

Warning: This function will replace the root gate of the graph if it is the destination.

function ClearStateMarks

cpp

void ClearStateMarks(
    const GatePtr & gate
)

Clears all the ancestor marks used in Boolean optimization steps.

Parameters:

gate The top ancestor of the common node.

Warning: The common node must be cleaned separately.

Precondition:

All ancestor gates are marked with the descendant index.
The common node itself is not the ancestor.

function DecomposeCommonNodes

cpp

bool DecomposeCommonNodes()

The Shannon decomposition for common nodes in the PDAG.

Return: true if the setups are found and processed.

Note: This preprocessing algorithm may introduce clones of existing shared gates, which may increase the size of the graph and complicate application and performance of other algorithms.

Warning:

Gate descendant marks are used.
Gate ancestor marks are used.
Node visit information is used.
Gate marks are used.

This procedure is also called "Constant Propagation", but it is confusing with the actual propagation of house events and constant gates.

The main two operations are performed according to the Shannon decomposition of particular setups:

x & f(x, y) = x & f(1, y) x | f(x, y) = x | f(0, y)

function ReplaceGate

cpp

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

Replaces one gate in the graph with another.

Parameters:

gate An existing gate to be replaced.
replacement A gate that will replace the old gate.

Postcondition:

The sign of the existing gate as an argument is transferred to the replacement gate.
If any parent becomes constant or NULL type, the parent is registered for removal.

function RegisterToClear

cpp

bool RegisterToClear(
    const GatePtr & gate
)

Registers mutated gates for potential deletion later.

Parameters:

gate The mutated gate under examination.

Return: true if the gate is registered for clearance.

Precondition: The caller will later call the appropriate cleanup functions.

function GatherNodes

cpp

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

Gathers all nodes in the PDAG.

Parameters:

gates A set of gates.
variables A set of variables.

Warning: Node visit information is manipulated.

function GatherNodes

cpp

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

Gathers nodes in the sub-graph.

Parameters:

gate The root gate to traverse.
gates A set of gates.
variables A set of variables.

Precondition: Visited nodes are marked.

Protected Attributes Documentation

variable graph_

cpp

Pdag * graph_;

The PDAG to preprocess.

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

scram::core::Preprocessor ​

Public Classes ​

Protected Classes ​

Public Functions ​

Protected Functions ​

Protected Attributes ​

Public Functions Documentation ​

function Preprocessor ​

function ~Preprocessor ​

function operator() ​

Protected Functions Documentation ​

function Run ​

function RunPhaseOne ​

function RunPhaseTwo ​

function RunPhaseThree ​

function RunPhaseFour ​

function RunPhaseFive ​

function NormalizeGates ​

function NotifyParentsOfNegativeGates ​

function NormalizeGate ​

function NormalizeXorGate ​

function NormalizeAtleastGate ​

function PropagateComplements ​

function CoalesceGates ​

function CoalesceGates ​

function ProcessMultipleDefinitions ​

function DetectMultipleDefinitions ​

function DetectModules ​

function AssignTiming ​

function FindModules ​

function ProcessModularArgs ​

function CreateNewModule ​

function FilterModularArgs ​

function GroupModularArgs ​

function CreateNewModules ​

function GatherModules ​

function MergeCommonArgs ​

function MergeCommonArgs ​

function MarkCommonArgs ​

function GatherCommonArgs ​

function FilterMergeCandidates ​

function GroupCandidatesByArgs ​

function GroupCommonParents ​

function GroupCommonArgs ​

function FindOptionGroup ​

function FindBaseOption ​

function TransformCommonArgs ​

function DetectDistributivity ​

function DetectDistributivity ​

function HandleDistributiveArgs ​

function FilterDistributiveArgs ​

function GroupDistributiveArgs ​

function TransformDistributiveArgs ​

function BooleanOptimization ​

function GatherCommonNodes ​

function ProcessCommonNode ​

function MarkAncestors ​

function PropagateState ​

function DetermineGateState ​

function CollectStateDestinations ​

function CollectRedundantParents ​

function ProcessRedundantParents ​

function ProcessStateDestinations ​

function ClearStateMarks ​

function DecomposeCommonNodes ​

function ReplaceGate ​

function RegisterToClear ​

function GatherNodes ​

function GatherNodes ​

Protected Attributes Documentation ​

variable graph_ ​

scram::core::Preprocessor

Public Classes

Protected Classes

Public Functions

Protected Functions

Protected Attributes

Public Functions Documentation

function Preprocessor

function ~Preprocessor

function operator()

Protected Functions Documentation

function Run

function RunPhaseOne

function RunPhaseTwo

function RunPhaseThree

function RunPhaseFour

function RunPhaseFive

function NormalizeGates

function NotifyParentsOfNegativeGates

function NormalizeGate

function NormalizeXorGate

function NormalizeAtleastGate

function PropagateComplements

function CoalesceGates

function CoalesceGates

function ProcessMultipleDefinitions

function DetectMultipleDefinitions

function DetectModules

function AssignTiming

function FindModules

function ProcessModularArgs

function CreateNewModule

function FilterModularArgs

function GroupModularArgs

function CreateNewModules

function GatherModules

function MergeCommonArgs

function MergeCommonArgs

function MarkCommonArgs

function GatherCommonArgs

function FilterMergeCandidates

function GroupCandidatesByArgs

function GroupCommonParents

function GroupCommonArgs

function FindOptionGroup

function FindBaseOption

function TransformCommonArgs

function DetectDistributivity

function DetectDistributivity

function HandleDistributiveArgs

function FilterDistributiveArgs

function GroupDistributiveArgs

function TransformDistributiveArgs

function BooleanOptimization

function GatherCommonNodes

function ProcessCommonNode

function MarkAncestors

function PropagateState

function DetermineGateState

function CollectStateDestinations

function CollectRedundantParents

function ProcessRedundantParents

function ProcessStateDestinations

function ClearStateMarks

function DecomposeCommonNodes

function ReplaceGate

function RegisterToClear

function GatherNodes

function GatherNodes

Protected Attributes Documentation

variable graph_