netlist_carpentry.core.graph.pattern ¶

Module for graph pattern handling, used to find and/or replace patterns within a circuit.

Classes:

Pattern –

The Pattern class represents a subgraph pattern in a digital circuit graph.

Pattern ¶

Pattern(
    graph: ModuleGraph,
    replacement_graph: ModuleGraph = EMPTY_GRAPH,
    ignore_port_names: bool = True,
    matching_constraints: List[Constraint] = [],
    mapping: Dict[Tuple[str, str, int], Tuple[str, str, int]] = {},
    ignore_boundary_conditions: bool = False,
)

The Pattern class represents a subgraph pattern in a digital circuit graph.

It is used to match specific patterns within the graph, allowing for efficient identification and manipulation of components or subcircuits. This class is essential for tasks such as optimization, verification, and synthesis of digital circuits.

In a graph representing a digital circuit, this class can be used to identify common patterns like cascading logic gates (e.g., AND, OR, NOT), or more complex components like redundant multiplexers. These patterns help in searching for and analyzing specific parts of the circuit, facilitating tasks (e. g. debugging, testing and refinement).

Additionally, this class can also be used to specify a replacement graph that will replace the matched pattern in the original graph. This allows for the simplification or transformation of digital circuits by replacing complex patterns with simpler ones.

To use this class, create an instance by providing a subgraph that represents the desired pattern and optionally a replacement graph. Then, utilize the provided methods to match this pattern within a larger graph representing the digital circuit. If a replacement graph is given, it can be used to replace all (or certain) occurrences.

replacement_graph (ModuleGraph): The graph representing the replacement structure to replace pattern matches with.
ignore_port_names (bool): Whether to check if the port names of the pattern match the port names of the circuit. Defaults to True.
matching_constraints (List): A list of constraints for the matching algorithm. Currently unused.
mapping (Dict[Tuple[str, str, int], Tuple[str, str, int]]): A dictionary that maps the original nodes and edges to their new counterparts.
ignore_boundary_conditions (bool): Whether to ignore any boundary conditions when matching the pattern to a given circuit. Defaults to False.

Methods:

get_mapping –

This method generates a mapping between the ports of a pattern module and its corresponding replacement module.
find_matches –

Attempts to find matches for this pattern in the given circuit graph.
count_matches –

Counts the number of matches of this pattern in the given circuit graph.
interesting_edges –

Returns a set of edges connected to the given node that have not been processed yet.
replace –

Replaces occurrences of a pattern in the given module.

Attributes:

graph (ModuleGraph) –

Returns the pattern graph.
replacement_graph (ModuleGraph) –

Retrieves the replacement graph associated with this pattern.
matching_constraints (List[Constraint]) –

Returns the list of matching constraints associated with this pattern.

graph `property` ¶

graph: ModuleGraph

Returns the pattern graph.

This property provides read-only access to the internal pattern graph. The pattern graph is a MultiDiGraph representing the structure of the pattern to be matched in the target graph.

Returns:

ModuleGraph ( ModuleGraph ) –

The pattern graph.

replacement_graph `property` ¶

replacement_graph: ModuleGraph

Retrieves the replacement graph associated with this pattern.

The replacement graph is used to specify the structure that should replace occurrences of the original graph (the pattern graph) in a larger network. This property allows for the inspection and modification of the replacement graph.

Returns:

ModuleGraph ( ModuleGraph ) –

The replacement graph.

matching_constraints `property` ¶

matching_constraints: List[Constraint]

Returns the list of matching constraints associated with this pattern.

get_mapping `classmethod` ¶

get_mapping(
    pattern_module: Module, replacement_module: Module
) -> Dict[Tuple[str, str, int], Tuple[str, str, int]]

This method generates a mapping between the ports of a pattern module and its corresponding replacement module.

The generated mapping can be used to replace instances of the pattern module with the replacement module in a larger circuit graph, ensuring that all port connections are correctly maintained.

Parameters:

pattern_module ¶
(Module) –

The module representing the pattern to be replaced.
replacement_module ¶
(Module) –

The module representing the replacement for the pattern.

Returns:

Dict[Tuple[str, str, int], Tuple[str, str, int]] –

Dict[Tuple[str, str, int], Tuple[str, str, int]]: A dictionary where each key is a tuple containing the name of the instance currently being processed,
Dict[Tuple[str, str, int], Tuple[str, str, int]] –

the name of the current port of the instance, and the current segment of the port (is -1, if the port consists only of one segment, or if all segments are equal).
Dict[Tuple[str, str, int], Tuple[str, str, int]] –

Each corresponding value is a tuple with the same information for the equivalent port in the replacement module.

Raises:

ValueError –

If the ports of the pattern and replacement modules do not match.

find_matches ¶

find_matches(
    circuit_graph: ModuleGraph, max_match_count: Optional[PositiveInt] = None
) -> Match

Attempts to find matches for this pattern in the given circuit graph.

Parameters:

circuit_graph ¶
(ModuleGraph) –

The circuit graph to search for matches.
max_match_count ¶
(Optional[PositiveInt], default: None ) –

The maximum number of matches to find. If set to None, no limit is applied. Defaults to None.

Returns:

Match ( Match ) –

A Match object containing the found matches. If no matches were found, the Match object is empty.

Notes

This method checks if the pattern is not empty before attempting to find matches. It uses a random node from the pattern as a starting point for the search.

count_matches ¶

count_matches(circuit_graph: ModuleGraph) -> int

Counts the number of matches of this pattern in the given circuit graph.

This method checks if the pattern is not empty and then finds possible start nodes in the circuit graph. It uses a helper function to recursively explore all possible matches starting from each node in the circuit graph that could potentially match the first node in the pattern.

Parameters:

circuit_graph ¶
(ModuleGraph) –

The graph to search for matches in.

Returns:

int ( int ) –

The number of matches found.

interesting_edges ¶

interesting_edges(
    graph: ModuleGraph, curr_node: str, processed_nodes: List[str]
) -> Set[Tuple[str, str, str]]

Returns a set of edges connected to the given node that have not been processed yet.

An edge is considered unprocessed if either node is not in the given processed_nodes list. If both end points are in the processed_nodes list, the edges is considered processed.

Parameters:

graph ¶
(ModuleGraph) –

The graph to process.
curr_node ¶
(str) –

The current node to consider.
processed_nodes ¶
(List[str]) –

A list of nodes that have already been processed, in processing order.

Returns:

Set[Tuple[str, str, str]] –

Set[Tuple[str, str, str]]: A set of edges connected to the given node that have not been processed yet.
Set[Tuple[str, str, str]] –

The first tuple element is the start of the edge, the second element is the end of the edge, and the third element is the key (for multi-edge connections).

replace ¶

replace(
    module: Module,
    iterations: Optional[PositiveInt] = None,
    replace_all_parallel: bool = False,
) -> int

Replaces occurrences of a pattern in the given module.

This method takes a module and a mapping as input. The mapping is used to determine how the pattern should be replaced. It returns the number of replacements made.

The replacement process involves finding all occurrences of the pattern in the module, and then replacing them according to the provided mapping. If the module is marked as locked, no replacements are made and a warning message is logged.

Parameters:

module ¶
(Module) –

The module in which to replace the pattern.
iterations ¶
(Optional[PositiveInt], default: None ) –

The number of replacement iterations to perform. If set to None, executes replacements until none are left. Defaults to None.
replace_all_parallel ¶
(bool, default: False ) –

If set to True, all occurrences of the pattern will be replaced in parallel (i.e. in the same iteration). Otherwise, only one occurrence per iteration will be replaced. If set to True, it may result in issues for overlapping occurrences.

Returns:

int ( int ) –

The number of replacements made.

Notes

This method modifies the input module. If you want to preserve the original module, create a copy before calling this method.

netlist_carpentry.core.graph.pattern ¶

Pattern ¶

graph `property` ¶

replacement_graph `property` ¶

matching_constraints `property` ¶

get_mapping `classmethod` ¶

`pattern_module` ¶

`replacement_module` ¶

find_matches ¶

`circuit_graph` ¶

`max_match_count` ¶

count_matches ¶

`circuit_graph` ¶

interesting_edges ¶

`graph` ¶

`curr_node` ¶

`processed_nodes` ¶

replace ¶

`module` ¶

`iterations` ¶

`replace_all_parallel` ¶

netlist_carpentry.core.graph.pattern ¶

Pattern ¶

graph property ¶

replacement_graph property ¶

matching_constraints property ¶

get_mapping classmethod ¶

pattern_module ¶

replacement_module ¶

find_matches ¶

circuit_graph ¶

max_match_count ¶

count_matches ¶

circuit_graph ¶

interesting_edges ¶

graph ¶

curr_node ¶

processed_nodes ¶

replace ¶

module ¶

iterations ¶

replace_all_parallel ¶

graph `property` ¶

replacement_graph `property` ¶

matching_constraints `property` ¶

get_mapping `classmethod` ¶

`pattern_module` ¶

`replacement_module` ¶

`circuit_graph` ¶

`max_match_count` ¶

`circuit_graph` ¶

`graph` ¶

`curr_node` ¶

`processed_nodes` ¶

`module` ¶

`iterations` ¶

`replace_all_parallel` ¶