GadgetSearch

find_maximal_independent_sets(g::SimpleGraph{Int})::Tuple{AbstractMatrix{Int}, Int}

Finds all maximal independent sets (MIS) of a given simple graph g and returns them in a matrix format along with the count of such sets.

Arguments

• g::SimpleGraph{Int}: The input graph represented as a SimpleGraph object with integer vertex labels.

Returns

• A tuple containing:
  1. AbstractMatrix{Int}: A matrix where each row represents a maximal independent set (MIS) in bitvector format. Each column corresponds to a vertex, and a value of 1 indicates the vertex is part of the MIS.
  2. Int: The total number of maximal independent sets found.

Details

The function computes the maximal independent sets of the input graph by leveraging the equivalence between finding the maximal independent set of a graph and finding the maximal clique of its complement graph. Internally, it uses Graphs.maximal_cliques to compute the maximal cliques of the complement graph and then converts the result into a matrix format.

format_grstate_output(ground_states::Vector{Int}, bit_length::Int)::Vector{String}

Format the a vector of integers in to a vector of binary strings with a fixed bit length, which is easy to store in a JSON file.

Arguments

• ground_states::Vector{Int}: a vector of decimal integers representing the ground states.

format_truth_table(truth_table::AbstractMatrix)::Vector{Int}

Format the truth table into a vector of integers, row by row. The truth table is a matrix where each row represents a binary number.

Arguments

• truth_table::AbstractMatrix: a matrix where each row represents a binary number, which can be a Matrix{Int} or a BitMatrix.

genericrule(ruleid::Int, bits::Int; show_info::Bool=false)::Vector{Int}

Generate the decimal vector ground_states of a generic bits-state-constraint with the given rule_id.

Note

State constraints allow for more flexible conditions that determine which states are permitted.

generic_rule(rule_id::Int, bit_num::Vector{Int}; show_info::Bool=false)
            ::Vector{Int}

Generate the decimal vector ground_states of a generic input_bits-in-output_bits-out gate with the given rule_id.

Arguments

• rule_id::Int: the ID of the gate.
• bit_num::Vector{Int}: a length-2-vector of two integers representing the number of input and output bits.

Keyword Arguments

• show_info::Bool=false: whether to show the truth table of the gate.

Returns

The decimal vector of the ground_states.

reconstruct_rule_id(ground_states::Vector{Int}, bit_num::Vector{Int}) -> Int

Reconstructs a unique gate identifier (rule_id) based on the provided ground_states, the number of input_bits, and output_bits.

Arguments

• ground_states::Vector{Int}: A vector of integers representing the ground state constraints.
• bit_num::Vector{Int}: A length-2 vector of two integers representing the number of input and output bits.

Returns

• Int: A unique integer identifier (rule_id) that encodes the mapping of inputs to outputs based on the provided ground states.

Details

• Each constraint in ground_states is assumed to encode both input and output bits.
• The input is extracted by shifting the constraint right by output_bits and applying a mask to isolate the input_bits.
• The output is extracted by masking the lower output_bits of the constraint.
• The rule_id is constructed by combining the outputs, shifted into positions determined by their corresponding inputs.

search_single_rule(graph_dict::Dict{String, SimpleGraph{Int}}, bit_num::Union{Int, Vector{Int}}; ground_states::Vector{Int}, truth_table::AbstractMatrix=Matrix{Int}(undef, 0, 0), rule_id::Int=0, pin_set::Vector{Int}=Int[], split_idx::Int=0, split_size::Int=0, start_idx::Int=0, end_idx::Int=0, greedy::Bool=false, threshold::Int=0, max_samples::Int=0)

Searches for a single rule that satisfies given constraints for a single graph.

This particular function is designed for generic constraint search.

Arguments

• graph_dict::Dict{String, SimpleGraph{Int}}: The input graph dictionary, where the key is the graph name like "graph100" and the value is a Graphs.SimpleGraph object.

Keyword Arguments

• split_idx::Int = 0(optional): The index of the split file to process. Defaults to 0.
• split_size::Int = 0(optional): The maximum number of rows (graphs) in each split file. Defaults to 0. If one wants to process split files manually, please ensure that all dictionaries have the same length split_size except for the last one.

search_single_rule(graph::SimpleGraph{Int}, bit_num::Union{Int, Vector{Int}}; ground_states::Vector{Int}, truth_table::AbstractMatrix=Matrix{Int}(undef, 0, 0), rule_id::Int=0, pin_set::Vector{Int}=Int[], greedy::Bool=false, threshold::Int=0, max_samples::Int=0)

Searches for a single rule that satisfies given constraints for a single graph.

This particular function is designed for generic constraint search.

Arguments

• graph::SimpleGraph{Int}: The input graph, represented as a Graphs.SimpleGraph object.

search_single_rule(graph_path::String, bit_num::Union{Int, Vector{Int}};        ground_states::Vector{Int}=Int[], truth_table::AbstractMatrix=Matrix{Int}(undef, 0, 0), rule_id::Int=0, max_file_size_mb::Int=30, greedy::Bool=false, threshold::Int=0, max_samples::Int=0)
::Union{gadget, Nothing}

For a series of ground states, search for a single rule that can satisfy all of them. This particular function is designed for generic constraint search.

Arguments

• graph_path::String: the path of the graph *.g6 file.
• bit_num::Union{Int, Vector{Int}}: the number of pins, which also shows the kind of the rule to search for, e.g. 2 for a 2-bit state constraint, [2, 1] for a 2-in-1-out logic gate.

Keyword Arguments

• ground_states::Vector{Int} = Int[]: the truth table of ground states to satisfy. Note: the default value of the ground states is a vector of decimal numbers, e.g. [0, 1, 2, 3] for binary numbers [00, 01, 10, 11] if we have 2-bit constraint.
• truth_table::AbstractMatrix{Int} = Matrix{Int}(undef, 0, 0): the truth table of the logic gate to search for.
• rule_id::Int = -1: the ID of the logic gate to search for. This is a reserved parameter for the logic gate search.
• pin_set::Vector{Int} = Int[]: the set of pins to search for. If not provided, the function will search for all possible pins.
• max_file_size_mb::Int = 30: the maximum file size (unit: Mb) to process. If the file size exceeds this value, the function will split the file and process each part separately.
• split_size::Int = 700_000: the maximum number of rows (graphs) in each split file.
• start_idx::Int = 0: the starting index of the graph to search.
• end_idx::Int = 0: the ending index of the graph to search.
• greedy::Bool = false: a flag indicating whether to use a greedy approach. Defaults to false.
• threshold::Int = 0: the maximum number of MIS combinations to consider for sampling. Defaults to no sampling.
• max_samples::Int = 0: the maximum number of samples to generate. Defaults to no sampling.

Returns

Returns an instance of gadget if a valid solution is found; otherwise, returns nothing.

Notes

• Either ground_states or truth_table must be provided unless the rule_id of the target logic gate is known, in which case this function can be called directly.
• The function ensures that the graph is connected before proceeding.
• The function iterates over all possible pin vectors and checks if they satisfy the given ground states within the maximal independent sets of the graph.
• If a valid candidate and weight are found, they are returned immediately.

show_rule_info(rule_id::Int, bits::Int)

Show the truth table of a generic bits-state-constarint with the given rule_id.

show_rule_info(rule_id::Int, input_bits::Int, output_bits::Int)

Show the truth table of a generic input_bits-in-output_bits-out gate with the given rule_id.

Arguments

• rule_id::Int: the ID of the gate.
• input_bits::Int: the number of input bits.
• output_bits::Int: the number of output bits.