rings

Ring detection algorithms for molecular graphs.

Implements SSSR (Smallest Set of Smallest Rings) using a modified version of Horton's algorithm, and all-rings enumeration.

find_all_rings(graph, max_size=12)

Find all rings in a molecular graph up to a maximum size.

Uses depth-limited DFS to enumerate all cycles.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required
max_size	int	Maximum ring size to consider (default 12).	12

Returns:

Type	Description
list[tuple[int, ...]]	List of tuples, each containing atom indices forming a ring.

Source code in chmpy/graph/rings.py

def find_all_rings(
    graph: "MolecularGraph", max_size: int = 12
) -> list[tuple[int, ...]]:
    """
    Find all rings in a molecular graph up to a maximum size.

    Uses depth-limited DFS to enumerate all cycles.

    Args:
        graph: A MolecularGraph instance.
        max_size: Maximum ring size to consider (default 12).

    Returns:
        List of tuples, each containing atom indices forming a ring.
    """
    n = graph.n_atoms
    neighbors = graph.all_neighbors()
    all_rings = set()

    def dfs(start: int, current: int, path: list[int], visited: set[int]):
        """DFS to find rings starting from 'start'."""
        if len(path) > max_size:
            return

        for neighbor in neighbors[current]:
            if neighbor == start and len(path) >= 3:
                # Found a ring
                ring = _canonicalize_ring(path)
                all_rings.add(ring)
            elif neighbor not in visited and neighbor > start:
                # Continue searching (neighbor > start avoids duplicates)
                visited.add(neighbor)
                path.append(neighbor)
                dfs(start, neighbor, path, visited)
                path.pop()
                visited.remove(neighbor)

    for start in range(n):
        visited = {start}
        for neighbor in neighbors[start]:
            if neighbor > start:
                visited.add(neighbor)
                dfs(start, neighbor, [start, neighbor], visited)
                visited.remove(neighbor)

    return list(all_rings)

find_sssr(graph)

Find the Smallest Set of Smallest Rings (SSSR) in a molecular graph.

Uses a modified Horton's algorithm: 1. Find all fundamental cycles from shortest path trees 2. Select a minimal linearly independent set

The SSSR size equals M - N + C where: - M = number of edges (bonds) - N = number of vertices (atoms) - C = number of connected components

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
list[tuple[int, ...]]	List of tuples, each containing atom indices forming a ring.

Source code in chmpy/graph/rings.py

def find_sssr(graph: "MolecularGraph") -> list[tuple[int, ...]]:
    """
    Find the Smallest Set of Smallest Rings (SSSR) in a molecular graph.

    Uses a modified Horton's algorithm:
    1. Find all fundamental cycles from shortest path trees
    2. Select a minimal linearly independent set

    The SSSR size equals M - N + C where:
    - M = number of edges (bonds)
    - N = number of vertices (atoms)
    - C = number of connected components

    Args:
        graph: A MolecularGraph instance.

    Returns:
        List of tuples, each containing atom indices forming a ring.
    """
    n = graph.n_atoms
    m = graph.n_bonds
    n_components, _ = graph.connected_components()

    # Calculate expected SSSR size (cyclomatic number)
    sssr_size = m - n + n_components

    if sssr_size <= 0:
        return []

    # Find all candidate rings using BFS from each atom
    candidate_rings = _find_candidate_rings(graph)

    if not candidate_rings:
        return []

    # Sort by ring size
    candidate_rings.sort(key=len)

    # Select linearly independent rings
    sssr = _select_independent_rings(candidate_rings, m, sssr_size, graph)

    return sssr

fused_ring_systems(graph)

Find fused ring systems (groups of rings sharing bonds).

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
list[set[int]]	List of sets, each set containing atom indices of a fused ring system.

Source code in chmpy/graph/rings.py

def fused_ring_systems(graph: "MolecularGraph") -> list[set[int]]:
    """
    Find fused ring systems (groups of rings sharing bonds).

    Args:
        graph: A MolecularGraph instance.

    Returns:
        List of sets, each set containing atom indices of a fused ring system.
    """
    rings = find_sssr(graph)

    if not rings:
        return []

    # Build ring adjacency (rings that share atoms)
    n_rings = len(rings)
    ring_sets = [set(ring) for ring in rings]

    # Union-find to group connected rings
    parent = list(range(n_rings))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py

    # Connect rings that share at least 2 atoms (fused)
    for i in range(n_rings):
        for j in range(i + 1, n_rings):
            if len(ring_sets[i] & ring_sets[j]) >= 2:
                union(i, j)

    # Group rings by their root
    groups = {}
    for i in range(n_rings):
        root = find(i)
        if root not in groups:
            groups[root] = set()
        groups[root].update(ring_sets[i])

    return list(groups.values())

is_in_ring(graph, atom_idx)

Check if an atom is part of any ring.

Parameters:

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

Returns:

Type	Description
bool	True if the atom is in at least one ring.

Source code in chmpy/graph/rings.py

def is_in_ring(graph: "MolecularGraph", atom_idx: int) -> bool:
    """
    Check if an atom is part of any ring.

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

    Returns:
        True if the atom is in at least one ring.
    """
    rings = find_sssr(graph)
    return any(atom_idx in ring for ring in rings)

is_ring_bond(graph, atom_i, atom_j)

Check if a bond is part of any ring.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required
atom_i	int	First atom index.	required
atom_j	int	Second atom index.	required

Returns:

Type	Description
bool	True if the bond is part of at least one ring.

Source code in chmpy/graph/rings.py

def is_ring_bond(graph: "MolecularGraph", atom_i: int, atom_j: int) -> bool:
    """
    Check if a bond is part of any ring.

    Args:
        graph: A MolecularGraph instance.
        atom_i: First atom index.
        atom_j: Second atom index.

    Returns:
        True if the bond is part of at least one ring.
    """
    if not graph.has_bond(atom_i, atom_j):
        return False

    rings = find_sssr(graph)
    for ring in rings:
        ring_size = len(ring)
        for i in range(ring_size):
            a, b = ring[i], ring[(i + 1) % ring_size]
            if (a == atom_i and b == atom_j) or (a == atom_j and b == atom_i):
                return True
    return False

ring_membership(graph)

Count ring membership for each atom.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
ndarray	Array of shape (n_atoms,) with count of SSSR rings each atom belongs to.

Source code in chmpy/graph/rings.py

def ring_membership(graph: "MolecularGraph") -> np.ndarray:
    """
    Count ring membership for each atom.

    Args:
        graph: A MolecularGraph instance.

    Returns:
        Array of shape (n_atoms,) with count of SSSR rings each atom belongs to.
    """
    rings = find_sssr(graph)
    counts = np.zeros(graph.n_atoms, dtype=np.int32)

    for ring in rings:
        for atom_idx in ring:
            counts[atom_idx] += 1

    return counts

ring_sizes(graph)

Get the sizes of all rings in the SSSR.

Parameters:

Name	Type	Description	Default
graph	MolecularGraph	A MolecularGraph instance.	required

Returns:

Type	Description
list[int]	Sorted list of ring sizes.

Source code in chmpy/graph/rings.py

def ring_sizes(graph: "MolecularGraph") -> list[int]:
    """
    Get the sizes of all rings in the SSSR.

    Args:
        graph: A MolecularGraph instance.

    Returns:
        Sorted list of ring sizes.
    """
    rings = find_sssr(graph)
    return sorted(len(ring) for ring in rings)

smallest_ring_containing_atom(graph, atom_idx)

Find the smallest ring containing a given atom.

Parameters:

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

Returns:

Type	Description
tuple[int, ...] | None	Tuple of atom indices forming the smallest ring, or None if not in any ring.

Source code in chmpy/graph/rings.py

def smallest_ring_containing_atom(
    graph: "MolecularGraph", atom_idx: int
) -> tuple[int, ...] | None:
    """
    Find the smallest ring containing a given atom.

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

    Returns:
        Tuple of atom indices forming the smallest ring, or None if not in any ring.
    """
    rings = find_sssr(graph)
    containing = [ring for ring in rings if atom_idx in ring]

    if not containing:
        return None

    return min(containing, key=len)