Skip to content

netlist_carpentry.core.graph.match

Wrapper module to handle found pattern occurrences in a circuit graph.

Classes:

Match 

Match(pattern_graph: ModuleGraph, matches: List[ModuleGraph])

Methods:

  • get_interfaces –

    Returns a dictionary of interfaces for each matched subgraph in the original circuit.

Attributes:

  • pattern_graph (ModuleGraph) –

    Returns a deep copy of the pattern graph.

  • matches (List[ModuleGraph]) –

    Returns a deep copy of the list of matched subgraphs found in the original circuit.

  • count (int) –

    Returns the number of matches found for the pattern graph.

  • pairings (Dict[str, Dict[int, str]]) –

    Returns a dictionary of pairings between nodes in the pattern graph and their corresponding matched nodes.

pattern_graph property 

pattern_graph: ModuleGraph

Returns a deep copy of the pattern graph.

The returned graph is a copy of the actual pattern graph to prevent external modifications.

Returns:

  • ModuleGraph ( ModuleGraph ) –

    A deep copy of the pattern graph.

matches property 

matches: List[ModuleGraph]

Returns a deep copy of the list of matched subgraphs found in the original circuit.

The returned list is a copy of the actual list to prevent external modifications to the internal state.

count property 

count: int

Returns the number of matches found for the pattern graph.

This property is useful to quickly determine how many subgraphs in the original circuit match the given pattern, without having to access the actual matched subgraphs (e. g. for filtering or statistical analysis).

Returns:

  • int ( int ) –

    The number of matches found for the pattern graph.

pairings property 

pairings: Dict[str, Dict[int, str]]

Returns a dictionary of pairings between nodes in the pattern graph and their corresponding matched nodes.

This property uses graph isomorphism to establish these pairings. Graph isomorphism is a powerful tool for identifying structurally identical subgraphs within larger graphs. By leveraging this concept, the parts of the original circuit matching the given pattern can be identified, even if they have different node labels or edge configurations. Since the found matches already are isomorph to the pattern, the isomorphism function is only used to get the mapping between all found matching subgraphs and the pattern.

One of the main advantages of using graph isomorphism is its Flexibility. It finds matches between subgraphs with varying node and edge attributes (but with correct instance types in the circuit). It can handle minor differences in the structure of the matched subgraphs (such as instance names, which are structurally irrelevant), making it more resilient to noise or variations in the data.

For example, a pattern graph with two nodes 'A' and 'B' connected by an edge. Both nodes are circuit instances of a certain type. If the original circuit contains two identical subgraphs with nodes 'X'-'Y' (where X has the same type as A, and Y the same as B) and 'P'-'Q' (P.type == A.type and Q.type == B.type), the pairings property would return a dictionary mapping 'A' to {'0': 'X', '1': 'P'} and 'B' to {'0': 'Y', '1': 'Q'}.

Returns:

  • Dict[str, Dict[int, str]] –

    Dict[str, Dict[int, str]]: A dictionary mapping pattern graph nodes to dictionaries of matched node IDs.

get_interfaces 

get_interfaces(
    circuit_graph: ModuleGraph,
) -> Dict[int, Dict[Tuple[str, str, int], Set[Tuple[str, str, int]]]]

Returns a dictionary of interfaces for each matched subgraph in the original circuit.

This method constructs an interface for each match by identifying the connections between the matched subgraph and the rest of the circuit. The returned dictionary maps each match index to its corresponding interface, which is represented as a nested dictionary.

The interface dictionary has the following structure: - The outermost key is the match index (an integer). - The next level of keys is a tuple following the schema (instance_name, port_name, segment_number), which represents the unique connection point of the current instance, i.e. a port of an instance of the pattern. - The values for each connection tuple is a set containing all other end points as tuples with with the given port segment is connected via the same wire. The tuple again follows the schema (opposing_instance_name, port_of_opposing_instance, segment_number).

If the key tuple references a driving port, the value set contains all load ports. If the key tuple references a load port, the value set conntains all driving ports (which should only be one). If the port is dangling (i.e. there is no opposing end point), the port is not listed.

This way, each connection (with at least one end point inside the pattern) is listed along with every opposing end point connected to this port. For example, if a match has two instances ('inst1' and 'inst2'), which are connected between each other (via the output port 'Y' of 'inst1' and 'A' of 'inst2'), the interface dictionary might look like this:

{
    0: {
        ('inst1', 'A', 0): {('inst3', 'Y', 0)},
        ('inst1', 'B', 0): {('inst4', 'Y', 0)},
        ('inst1', 'Y', 0): {('inst5', 'D', 0), ('inst2', 'A', 0)},
        ('inst2', 'A', 0): {('inst1', 'Y', 0)},
        ('inst2', 'Y', 0): {(None, 'out_port', 0), ('inst6', 'A', 0)},
    },
    1: {
        ('inst6', 'A', 0): {('inst2', 'Y', 0)},
        ('inst6', 'Y', 0): {('inst7', 'A', 0)},
        ('inst7', 'A', 0): {('inst6', 'Y', 0)},
    }
}

In this example, inst1 has three connections outside the pattern, one for each port A, B and Y. However, inst1 also has a connection inside the pattern to inst2 via its port Y (index 0) and the port A of inst2 (where the index is 0 again). If an instance is connected to a module port, then this connection does not have an instance. This can be seen for port Y of inst2, where the instance name is None, indicating that the referenced port out_port is a module port. If a port is missing in the returned dictionary, then this port is unconnected in the circuit. Thus there is no corresponding edge in the circuit graph. This can be indirectly seen at inst7, where only the port A is listed and no second port.

This method is useful for analyzing the interactions between matched subgraphs and their surroundings in the original circuit.

Parameters:

Returns: