substructure

Substructure matching using the VF2++ algorithm.

Provides subgraph isomorphism detection for finding molecular substructures without requiring external dependencies like graph_tool.

VF2++ improves on VF2 with: - Optimal matching order based on node rarity and connectivity - Improved feasibility rules with better lookahead - More aggressive pruning

count_substructures(target, query, match_element=True)

Count occurrences of a query substructure in a target graph.

Parameters:

Name	Type	Description	Default
target	MolecularGraph	The target molecular graph to search in.	required
query	MolecularGraph	The query pattern to search for.	required
match_element	bool	If True, only match atoms with same atomic number.	True

Returns:

Type	Description
int	Number of times the query appears in the target.

Source code in chmpy/graph/substructure.py

def count_substructures(
    target: "MolecularGraph",
    query: "MolecularGraph",
    match_element: bool = True,
) -> int:
    """
    Count occurrences of a query substructure in a target graph.

    Args:
        target: The target molecular graph to search in.
        query: The query pattern to search for.
        match_element: If True, only match atoms with same atomic number.

    Returns:
        Number of times the query appears in the target.
    """
    return len(find_substructure(target, query, match_element))

find_functional_groups(target, group_name)

Find instances of a named functional group in a molecule.

Parameters:

Name	Type	Description	Default
target	MolecularGraph	The target molecular graph.	required
group_name	str	Name of the functional group (e.g., "hydroxyl", "carbonyl").	required

Returns:

Type	Description
list[dict[int, int]]	List of mappings from pattern indices to target indices.

Raises:

Type	Description
KeyError	If group_name is not recognized.

Source code in chmpy/graph/substructure.py

def find_functional_groups(
    target: "MolecularGraph",
    group_name: str,
) -> list[dict[int, int]]:
    """
    Find instances of a named functional group in a molecule.

    Args:
        target: The target molecular graph.
        group_name: Name of the functional group (e.g., "hydroxyl", "carbonyl").

    Returns:
        List of mappings from pattern indices to target indices.

    Raises:
        KeyError: If group_name is not recognized.
    """
    if group_name not in FUNCTIONAL_GROUPS:
        raise KeyError(f"Unknown functional group: {group_name}")

    atoms, bonds = FUNCTIONAL_GROUPS[group_name]
    return functional_group_matches(target, atoms, bonds)

find_substructure(target, query, match_element=True)

Find all occurrences of a query substructure in a target graph.

Uses the VF2++ algorithm for subgraph isomorphism.

Parameters:

Name	Type	Description	Default
target	MolecularGraph	The target molecular graph to search in.	required
query	MolecularGraph	The query pattern to search for.	required
match_element	bool	If True, only match atoms with same atomic number.	True

Returns:

Type	Description
list[dict[int, int]]	List of mappings from query atom indices to target atom indices.
list[dict[int, int]]	Each mapping is a dict {query_idx: target_idx}.

Source code in chmpy/graph/substructure.py

def find_substructure(
    target: "MolecularGraph",
    query: "MolecularGraph",
    match_element: bool = True,
) -> list[dict[int, int]]:
    """
    Find all occurrences of a query substructure in a target graph.

    Uses the VF2++ algorithm for subgraph isomorphism.

    Args:
        target: The target molecular graph to search in.
        query: The query pattern to search for.
        match_element: If True, only match atoms with same atomic number.

    Returns:
        List of mappings from query atom indices to target atom indices.
        Each mapping is a dict {query_idx: target_idx}.
    """
    if query.n_atoms == 0:
        return [{}]

    if query.n_atoms > target.n_atoms:
        return []

    matcher = _VF2PlusPlusMatcher(target, query, match_element)
    return matcher.find_all()

functional_group_matches(target, pattern_atoms, pattern_bonds, match_element=True)

Find matches of a functional group pattern in a target molecule.

Convenience function for matching simple patterns specified as atom lists and bond lists.

Parameters:

Name	Type	Description	Default
target	MolecularGraph	The target molecular graph.	required
pattern_atoms	list[int]	List of atomic numbers for pattern atoms.	required
pattern_bonds	list[tuple[int, int]]	List of (i, j) tuples for pattern bonds.	required
match_element	bool	If True, match atomic numbers.	True

Returns:

Type	Description
list[dict[int, int]]	List of mappings from pattern indices to target indices.

Source code in chmpy/graph/substructure.py

def functional_group_matches(
    target: "MolecularGraph",
    pattern_atoms: list[int],
    pattern_bonds: list[tuple[int, int]],
    match_element: bool = True,
) -> list[dict[int, int]]:
    """
    Find matches of a functional group pattern in a target molecule.

    Convenience function for matching simple patterns specified as atom
    lists and bond lists.

    Args:
        target: The target molecular graph.
        pattern_atoms: List of atomic numbers for pattern atoms.
        pattern_bonds: List of (i, j) tuples for pattern bonds.
        match_element: If True, match atomic numbers.

    Returns:
        List of mappings from pattern indices to target indices.
    """
    from .adjacency import MolecularGraph

    # Create pattern graph
    n = len(pattern_atoms)
    atomic_numbers = np.array(pattern_atoms, dtype=np.int32)
    positions = np.zeros((n, 3))  # Positions don't matter for matching
    pattern = MolecularGraph.from_edge_list(atomic_numbers, positions, pattern_bonds)

    return find_substructure(target, pattern, match_element)

has_substructure(target, query, match_element=True)

Check if a target graph contains a query substructure.

More efficient than find_substructure when only existence is needed.

Parameters:

Name	Type	Description	Default
target	MolecularGraph	The target molecular graph to search in.	required
query	MolecularGraph	The query pattern to search for.	required
match_element	bool	If True, only match atoms with same atomic number.	True

Returns:

Type	Description
bool	True if the query is found in the target.

Source code in chmpy/graph/substructure.py

def has_substructure(
    target: "MolecularGraph",
    query: "MolecularGraph",
    match_element: bool = True,
) -> bool:
    """
    Check if a target graph contains a query substructure.

    More efficient than find_substructure when only existence is needed.

    Args:
        target: The target molecular graph to search in.
        query: The query pattern to search for.
        match_element: If True, only match atoms with same atomic number.

    Returns:
        True if the query is found in the target.
    """
    if query.n_atoms == 0:
        return True

    if query.n_atoms > target.n_atoms:
        return False

    matcher = _VF2PlusPlusMatcher(target, query, match_element)
    return matcher.find_one() is not None

list_functional_groups()

List available functional group names.

Source code in chmpy/graph/substructure.py

def list_functional_groups() -> list[str]:
    """List available functional group names."""
    return list(FUNCTIONAL_GROUPS.keys())