canonicalization

Graph canonicalization using the Morgan algorithm.

Provides unique atom ordering for canonical SMILES generation and Morgan/ECFP-style fingerprints.

atom_invariant(graph, atom_idx)

Compute the invariant for a single atom.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required
atom_idx	int	Index of the atom.	required

Returns:

Type	Description
int	Integer invariant encoding atom properties.

Source code in chmpy/graph/canonicalization.py

def atom_invariant(graph: "MolecularGraph", atom_idx: int) -> int:
    """
    Compute the invariant for a single atom.

    Args:
        graph: A MolecularGraph instance.
        atom_idx: Index of the atom.

    Returns:
        Integer invariant encoding atom properties.
    """
    invariants = _compute_initial_invariants(graph)
    return int(invariants[atom_idx])

canonical_atom_map(graph)

Get mapping from original atom indices to canonical indices.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
dict[int, int]	Dictionary mapping original index to canonical index.

Source code in chmpy/graph/canonicalization.py

def canonical_atom_map(graph: "MolecularGraph") -> dict[int, int]:
    """
    Get mapping from original atom indices to canonical indices.

    Args:
        graph: A MolecularGraph instance.

    Returns:
        Dictionary mapping original index to canonical index.
    """
    ordering = canonical_ordering(graph)
    return {i: int(ordering[i]) for i in range(len(ordering))}

canonical_ordering(graph)

Compute a canonical ordering of atoms in the molecular graph.

Uses an extended Morgan algorithm with symmetry breaking to produce a unique, deterministic ordering regardless of input atom order.

The algorithm: 1. Compute initial atom invariants (atomic number, degree, etc.) 2. Iteratively refine using neighbor information 3. Break ties using lexicographic ordering

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
ndarray	Array of shape (n_atoms,) containing the canonical index for each atom.
ndarray	To reorder atoms: new_order[canonical_ordering[i]] = i

Source code in chmpy/graph/canonicalization.py

def canonical_ordering(graph: "MolecularGraph") -> np.ndarray:
    """
    Compute a canonical ordering of atoms in the molecular graph.

    Uses an extended Morgan algorithm with symmetry breaking to produce
    a unique, deterministic ordering regardless of input atom order.

    The algorithm:
    1. Compute initial atom invariants (atomic number, degree, etc.)
    2. Iteratively refine using neighbor information
    3. Break ties using lexicographic ordering

    Args:
        graph: A MolecularGraph instance.

    Returns:
        Array of shape (n_atoms,) containing the canonical index for each atom.
        To reorder atoms: new_order[canonical_ordering[i]] = i
    """
    n = graph.n_atoms

    if n == 0:
        return np.array([], dtype=np.int32)

    if n == 1:
        return np.array([0], dtype=np.int32)

    # Step 1: Compute initial invariants
    invariants = _compute_initial_invariants(graph)

    # Step 2: Morgan iteration to propagate neighbor information
    invariants = _morgan_iteration(graph, invariants)

    # Step 3: Break ties and compute final ordering
    ordering = _compute_ordering(invariants)

    return ordering

equivalent_atoms(graph)

Find sets of equivalent (symmetric) atoms.

Two atoms are equivalent if they have the same Morgan invariant after convergence, meaning they are in symmetric positions.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
list[set[int]]	List of sets, each containing indices of equivalent atoms.

Source code in chmpy/graph/canonicalization.py

def equivalent_atoms(graph: "MolecularGraph") -> list[set[int]]:
    """
    Find sets of equivalent (symmetric) atoms.

    Two atoms are equivalent if they have the same Morgan invariant
    after convergence, meaning they are in symmetric positions.

    Args:
        graph: A MolecularGraph instance.

    Returns:
        List of sets, each containing indices of equivalent atoms.
    """
    invariants = _compute_initial_invariants(graph)
    invariants = _morgan_iteration(graph, invariants)

    # Group by invariant
    groups = {}
    for i, inv in enumerate(invariants):
        if inv not in groups:
            groups[inv] = set()
        groups[inv].add(i)

    return list(groups.values())

morgan_fingerprint(graph, radius=2, n_bits=2048)

Compute an ECFP-style Morgan fingerprint.

Generates circular fingerprints by hashing atom environments at different radii.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required
radius	int	Maximum radius for environment expansion.	2
n_bits	int	Size of the fingerprint bit vector.	2048

Returns:

Type	Description
ndarray	Boolean array of shape (n_bits,) representing the fingerprint.

Source code in chmpy/graph/canonicalization.py

def morgan_fingerprint(
    graph: "MolecularGraph", radius: int = 2, n_bits: int = 2048
) -> np.ndarray:
    """
    Compute an ECFP-style Morgan fingerprint.

    Generates circular fingerprints by hashing atom environments
    at different radii.

    Args:
        graph: A MolecularGraph instance.
        radius: Maximum radius for environment expansion.
        n_bits: Size of the fingerprint bit vector.

    Returns:
        Boolean array of shape (n_bits,) representing the fingerprint.
    """
    n = graph.n_atoms
    neighbors = graph.all_neighbors()
    fingerprint = np.zeros(n_bits, dtype=bool)

    # Initial atom invariants
    atom_features = _compute_initial_invariants(graph)

    # For each radius
    for r in range(radius + 1):
        if r == 0:
            # Radius 0: just the atom itself
            for i in range(n):
                bit = hash(atom_features[i]) % n_bits
                fingerprint[bit] = True
        else:
            # Radius r: include neighbor information
            new_features = np.zeros(n, dtype=np.int64)
            for i in range(n):
                # Include bond information
                neighbor_info = []
                for neighbor in neighbors[i]:
                    bond_order = get_bond_order(graph, i, neighbor)
                    neighbor_info.append((int(bond_order * 10), atom_features[neighbor]))
                neighbor_info.sort()

                combined = (atom_features[i],) + tuple(neighbor_info)
                new_features[i] = hash(combined) & 0x7FFFFFFFFFFFFFFF

                # Set bit
                bit = hash((r, new_features[i])) % n_bits
                fingerprint[bit] = True

            atom_features = new_features

    return fingerprint

morgan_fingerprint_bits(graph, radius=2)

Get the set of Morgan fingerprint bit indices (on bits).

Useful for Tanimoto similarity calculations.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required
radius	int	Maximum radius for environment expansion.	2

Returns:

Type	Description
set[int]	Set of bit indices that are on.

Source code in chmpy/graph/canonicalization.py

def morgan_fingerprint_bits(
    graph: "MolecularGraph", radius: int = 2
) -> set[int]:
    """
    Get the set of Morgan fingerprint bit indices (on bits).

    Useful for Tanimoto similarity calculations.

    Args:
        graph: A MolecularGraph instance.
        radius: Maximum radius for environment expansion.

    Returns:
        Set of bit indices that are on.
    """
    n = graph.n_atoms
    neighbors = graph.all_neighbors()
    bits = set()

    atom_features = _compute_initial_invariants(graph)

    for r in range(radius + 1):
        if r == 0:
            for i in range(n):
                bits.add(hash(atom_features[i]))
        else:
            new_features = np.zeros(n, dtype=np.int64)
            for i in range(n):
                neighbor_info = []
                for neighbor in neighbors[i]:
                    bond_order = get_bond_order(graph, i, neighbor)
                    neighbor_info.append((int(bond_order * 10), atom_features[neighbor]))
                neighbor_info.sort()

                combined = (atom_features[i],) + tuple(neighbor_info)
                new_features[i] = hash(combined) & 0x7FFFFFFFFFFFFFFF
                bits.add(hash((r, new_features[i])))

            atom_features = new_features

    return bits

reorder_graph(graph)

Create a new graph with atoms in canonical order.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
MolecularGraph	New MolecularGraph with atoms reordered canonically.

Source code in chmpy/graph/canonicalization.py

def reorder_graph(graph: "MolecularGraph") -> "MolecularGraph":
    """
    Create a new graph with atoms in canonical order.

    Args:
        graph: A MolecularGraph instance.

    Returns:
        New MolecularGraph with atoms reordered canonically.
    """
    from .adjacency import MolecularGraph as MG

    ordering = canonical_ordering(graph)
    n = graph.n_atoms

    # Create inverse mapping
    inverse = np.zeros(n, dtype=np.int32)
    for i, rank in enumerate(ordering):
        inverse[rank] = i

    # Reorder atoms
    new_atomic_numbers = graph.atomic_numbers[inverse]
    new_positions = graph.positions[inverse]

    # Reorder edges
    new_edges = []
    for i, j in graph.edges():
        new_i = ordering[i]
        new_j = ordering[j]
        new_edges.append((min(new_i, new_j), max(new_i, new_j)))

    return MG.from_edge_list(new_atomic_numbers, new_positions, new_edges)

tanimoto_similarity(fp1, fp2)

Compute Tanimoto similarity between two fingerprints.

Parameters:

Name	Type	Description	Default
fp1	ndarray	First fingerprint (boolean array).	required
fp2	ndarray	Second fingerprint (boolean array).	required

Returns:

Type	Description
float	Tanimoto similarity in [0, 1].

Source code in chmpy/graph/canonicalization.py

def tanimoto_similarity(fp1: np.ndarray, fp2: np.ndarray) -> float:
    """
    Compute Tanimoto similarity between two fingerprints.

    Args:
        fp1: First fingerprint (boolean array).
        fp2: Second fingerprint (boolean array).

    Returns:
        Tanimoto similarity in [0, 1].
    """
    intersection = np.sum(fp1 & fp2)
    union = np.sum(fp1 | fp2)

    if union == 0:
        return 1.0  # Both empty

    return intersection / union