Leo He

Tiptap is a headless, framework-agnostic rich text editor built on top of ProseMirror. One of its most powerful features is the ability to create custom nodes—content types that go beyond simple paragraphs and headings. In this post, we'll build a complete Mermaid diagram node from scratch, covering the schema definition, NodeView implementation, commands, and rendering logic.

By the end, you'll understand not just how to build a Mermaid node, but the underlying concepts that let you build any custom node.

Table of Contents

1. Understanding the ProseMirror Node Model
2. Setting Up the Node Schema
3. Building the NodeView
4. Rendering Mermaid Diagrams
5. Adding Commands and Input Rules
6. Handling Node Updates
7. Full Working Example
8. Common Pitfalls

1. Understanding the ProseMirror Node Model

Before writing code, it's important to understand three core concepts:

• Schema: Defines what kinds of nodes/marks exist in the document, their attributes, and how they can be nested. This is the "grammar" of your document.
• NodeView: A bridge between ProseMirror's abstract document model and actual DOM rendering. It gives you full control over how a node is rendered and how it responds to updates.
• Commands: Functions that describe transactions—ways to modify the document (insert, delete, update attributes, etc.).

Tiptap wraps these concepts in a friendlier API via Node.create(), but under the hood, it's all ProseMirror.

For our Mermaid node, we want:

• A block-level, atomic node (users edit it as a single unit, not character-by-character)
• An attribute to store the raw Mermaid syntax (e.g., graph TD; A-->B;)
• A NodeView that renders the diagram using the mermaid library
• The ability to click to edit the raw text and see it re-render

2. Setting Up the Node Schema

Let's start with the basic schema definition using Tiptap's Node.create():

import { Node, mergeAttributes } from '@tiptap/core'

export interface MermaidOptions {
  HTMLAttributes: Record<string, any>
}

declare module '@tiptap/core' {
  interface Commands<ReturnType> {
    mermaid: {
      setMermaid: (content: string) => ReturnType
    }
  }
}

export const Mermaid = Node.create<MermaidOptions>({
  name: 'mermaid',

  group: 'block',

  atom: true, // treat as a single, non-editable-by-default unit

  addOptions() {
    return {
      HTMLAttributes: {},
    }
  },

  addAttributes() {
    return {
      content: {
        default: 'graph TD;\n  A-->B;',
        parseHTML: (element) => element.getAttribute('data-content'),
        renderHTML: (attributes) => {
          return {
            'data-content': attributes.content,
          }
        },
      },
    }
  },

  parseHTML() {
    return [
      {
        tag: 'div[data-type="mermaid"]',
      },
    ]
  },

  renderHTML({ HTMLAttributes }) {
    return [
      'div',
      mergeAttributes(this.options.HTMLAttributes, HTMLAttributes, {
        'data-type': 'mermaid',
      }),
    ]
  },
})

Key Points

• group: 'block': This tells the schema that our node behaves like a paragraph or heading—it takes up a block-level slot in the document.
• atom: true: This is crucial. It tells ProseMirror to treat the entire node as a single, indivisible unit for cursor movement and selection. Users can't place a cursor inside the rendered diagram the way they would inside a paragraph.
• addAttributes(): We store the raw Mermaid syntax as a content attribute, which gets serialized to data-content in the HTML.
• parseHTML/renderHTML: These define the (de)serialization to/from HTML, important for copy-paste and for the initial document import.

At this point, we have a valid schema, but nothing renders as an actual diagram—we're just outputting a <div> with a data attribute. That's where NodeViews come in.

3. Building the NodeView

A NodeView gives us imperative control over the DOM for a specific node type. Tiptap exposes this through addNodeView(), which typically wraps @tiptap/vue-3's VueNodeViewRenderer, @tiptap/react's ReactNodeViewRenderer, or a plain vanilla NodeView.

Let's build this with the vanilla JS approach first, since it best exposes what's happening under the hood, and then show the React version.

Vanilla NodeView

import { Node, mergeAttributes } from '@tiptap/core'
import { NodeViewRenderer } from '@tiptap/pm/view'
import mermaid from 'mermaid'

mermaid.initialize({ startOnLoad: false })

export const Mermaid = Node.create<MermaidOptions>({
  // ... schema definition from before ...

  addNodeView() {
    return ({ node, editor, getPos }) => {
      const container = document.createElement('div')
      container.classList.add('mermaid-wrapper')

      const preview = document.createElement('div')
      preview.classList.add('mermaid-preview')

      const textarea = document.createElement('textarea')
      textarea.classList.add('mermaid-source')
      textarea.style.display = 'none'
      textarea.value = node.attrs.content

      container.append(preview, textarea)

      const renderDiagram = async (source: string) => {
        try {
          const id = `mermaid-${Math.random().toString(36).slice(2)}`
          const { svg } = await mermaid.render(id, source)
          preview.innerHTML = svg
        } catch (err) {
          preview.innerHTML = `<pre class="mermaid-error">${String(err)}</pre>`
        }
      }

      renderDiagram(node.attrs.content)

      // Click to toggle edit mode
      preview.addEventListener('dblclick', () => {
        preview.style.display = 'none'
        textarea.style.display = 'block'
        textarea.focus()
      })

      textarea.addEventListener('blur', () => {
        const newContent = textarea.value
        if (typeof getPos === 'function') {
          editor.view.dispatch(
            editor.view.state.tr.setNodeMarkup(getPos(), undefined, {
              ...node.attrs,
              content: newContent,
            })
          )
        }
        textarea.style.display = 'none'
        preview.style.display = 'block'
      })

      return {
        dom: container,
        update: (updatedNode) => {
          if (updatedNode.type.name !== 'mermaid') return false
          if (updatedNode.attrs.content !== node.attrs.content) {
            renderDiagram(updatedNode.attrs.content)
            textarea.value = updatedNode.attrs.content
          }
          node = updatedNode
          return true
        },
      }
    }
  },
})

What's happening here?

1. getPos: A function that returns the current position of this node in the document. We need this to dispatch transactions that update this specific node's attributes.
2. editor.view.dispatch(...): This is how we commit changes back to the ProseMirror state. setNodeMarkup is the standard way to update a node's attributes without replacing the whole node.
3. The update method: This is called whenever ProseMirror decides the node might need to re-render (e.g., due to collaborative editing or undo/redo). Returning true tells ProseMirror "I've handled the update myself, don't tear down and rebuild the DOM." Returning false forces ProseMirror to destroy and recreate the NodeView.
4. Toggling between preview and edit mode: We use a simple double-click-to-edit pattern, since directly editing SVG content isn't meaningful—we want to edit the source.

4. Rendering Mermaid Diagrams

The core rendering logic uses the mermaid npm package:

npm install mermaid

import mermaid from 'mermaid'

mermaid.initialize({
  startOnLoad: false,
  theme: 'default',
  securityLevel: 'loose', // needed if you allow click events inside diagrams
})

async function renderMermaidToSVG(source: string): Promise<string> {
  const id = `mermaid-svg-${Date.now()}`
  const { svg } = await mermaid.render(id, source)
  return svg
}

A few gotchas worth knowing:

• mermaid.render is async and returns a Promise, so your NodeView update logic must handle asynchronous rendering gracefully (e.g., avoid race conditions if the user types quickly).
• Unique IDs matter. Mermaid uses the id internally to generate SVG element IDs. If you reuse IDs across multiple diagrams, you'll get rendering conflicts.
• Error handling is essential. Invalid Mermaid syntax throws, and you don't want that error to crash your whole editor—catch it and display a friendly error state instead.

5. Adding Commands and Input Rules

Now let's make it easy to insert a Mermaid node. We add a command:

addCommands() {
  return {
    setMermaid:
      (content: string) =>
      ({ commands }) => {
        return commands.insertContent({
          type: this.name,
          attrs: { content },
        })
      },
  }
},

Usage in your editor:

editor.commands.setMermaid('graph TD;\n  A-->B;\n  B-->C;')

You could also add an input rule so that typing a shortcut like ```mermaidon its own line auto-inserts a diagram node:

import { textblockTypeInputRule } from '@tiptap/core'

addInputRules() {
  return [
    textblockTypeInputRule({
      find: /^```mermaid[\s\n]$/,
      type: this.type,
    }),
  ]
},

Note: for atom nodes, you'll typically want a custom InputRule rather than textblockTypeInputRule, since the latter is designed for textblock-type nodes with editable content. For an atomic node, a simpler approach is to use a Plugin with a regex-based text match that replaces the trigger text with insertContent.

6. Handling Node Updates

One subtlety with NodeViews for atomic/complex nodes is understanding when ProseMirror calls update() vs. when it destroys and recreates the view.

Key rules:

• If the node's type changes, ProseMirror always recreates the view.
• If only attrs change (like our content attribute), ProseMirror calls update(node, decorations) on the existing view, giving you a chance to patch the DOM instead of a full re-render.
• Returning false from update() forces a full teardown/rebuild—useful if the update is too complex to patch incrementally, but generally more expensive.

For our Mermaid node, since re-rendering the SVG is relatively cheap, we always return true from update() and let our internal renderDiagram() function handle applying the new SVG string.

If you're using React or Vue node views, this update-diffing is handled somewhat automatically via component re-renders when props/attrs change, which simplifies things considerably.

React Version (using @tiptap/react)

import { NodeViewWrapper, ReactNodeViewRenderer } from '@tiptap/react'
import { useEffect, useRef, useState } from 'react'
import mermaid from 'mermaid'

const MermaidComponent = ({ node, updateAttributes }: any) => {
  const [editing, setEditing] = useState(false)
  const [svg, setSvg] = useState('')
  const [error, setError] = useState<string | null>(null)

  useEffect(() => {
    let cancelled = false
    mermaid
      .render(`mermaid-${Math.random().toString(36).slice(2)}`, node.attrs.content)
      .then(({ svg }) => {
        if (!cancelled) {
          setSvg(svg)
          setError(null)
        }
      })
      .catch((err) => !cancelled && setError(String(err)))
    return () => {
      cancelled = true
    }
  }, [node.attrs.content])

  if (editing) {
    return (
      <NodeViewWrapper>
        <textarea
          autoFocus
          defaultValue={node.attrs.content}
          onBlur={(e) => {
            updateAttributes({ content: e.target.value })
            setEditing(false)
          }}
        />
      </NodeViewWrapper>
    )
  }

  return (
    <NodeViewWrapper>
      {error ? (
        <pre className="mermaid-error">{error}</pre>
      ) : (
        <div onDoubleClick={() => setEditing(true)} dangerouslySetInnerHTML={{ __html: svg }} />
      )}
    </NodeViewWrapper>
  )
}

// In your Node.create({...}):
addNodeView() {
  return ReactNodeViewRenderer(MermaidComponent)
},

Notice how much simpler this is: updateAttributes is provided directly by Tiptap's React integration, abstracting away the manual getPos + dispatch dance.

7. Full Working Example (Vanilla)

Putting it all together:

import { Node, mergeAttributes } from '@tiptap/core'
import mermaid from 'mermaid'

mermaid.initialize({ startOnLoad: false })

export const Mermaid = Node.create({
  name: 'mermaid',
  group: 'block',
  atom: true,

  addAttributes() {
    return {
      content: {
        default: 'graph TD;\nA-->B;',
        parseHTML: (el) => el.getAttribute('data-content'),
        renderHTML: (attrs) => ({ 'data-content': attrs.content }),
      },
    }
  },

  parseHTML() {
    return [{ tag: 'div[data-type="mermaid"]' }]
  },

  renderHTML({ HTMLAttributes }) {
    return ['div', mergeAttributes(HTMLAttributes, { 'data-type': 'mermaid' })]
  },

  addCommands() {
    return {
      setMermaid:
        (content: string) =>
        ({ commands }) =>
          commands.insertContent({ type: this.name, attrs: { content } }),
    }
  },

  addNodeView() {
    return ({ node, editor, getPos }) => {
      const dom = document.createElement('div')
      dom.className = 'mermaid-node'
      const preview = document.createElement('div')
      const textarea = document.createElement('textarea')
      textarea.style.display = 'none'
      dom.append(preview, textarea)

      const render = async (src: string) => {
        try {
          const { svg } = await mermaid.render(`m-${Date.now()}`, src)
          preview.innerHTML = svg
        } catch (e) {
          preview.innerHTML = `<pre>${e}</pre>`
        }
      }
      render(node.attrs.content)
      textarea.value = node.attrs.content

      preview.ondblclick = () => {
        preview.style.display = 'none'
        textarea.style.display = 'block'
        textarea.focus()
      }
      textarea.onblur = () => {
        if (typeof getPos === 'function') {
          editor.view.dispatch(
            editor.view.state.tr.setNodeMarkup(getPos(), undefined, {
              content: textarea.value,
            })
          )
        }
        preview.style.display = 'block'
        textarea.style.display = 'none'
      }

      return {
        dom,
        update: (updated) => {
          if (updated.type.name !== 'mermaid') return false
          render(updated.attrs.content)
          textarea.value = updated.attrs.content
          node = updated
          return true
        },
      }
    }
  },
})

Register it with your editor:

import { Editor } from '@tiptap/core'
import StarterKit from '@tiptap/starter-kit'
import { Mermaid } from './mermaid-extension'

const editor = new Editor({
  extensions: [StarterKit, Mermaid],
  content: '<p>Hello world</p>',
})

editor.commands.setMermaid('graph TD;\nA-->B;\nB-->C;')

8. Common Pitfalls

1. Forgetting atom: true for non-text content. Without it, ProseMirror expects the node to have editable text content matching its content schema expression, which conflicts with rendering an SVG diagram.

2. Not handling async rendering races. If a user rapidly edits the Mermaid source, multiple mermaid.render() calls can resolve out of order. Use a request ID or cancellation flag to ensure only the latest result is applied.

3. Missing getPos in newer Tiptap versions. In Tiptap 2.x, getPos is a function you must call (getPos()), not a static value—forgetting the parentheses is a very common bug.

4. SSR/hydration issues. If you use Tiptap with server-side rendering (e.g., Next.js), calling mermaid.render on the server will fail since it depends on browser DOM APIs. Guard NodeView rendering logic to only run client-side.

5. Copy-paste losing your diagram. Make sure your parseHTML/renderHTML (or parseDOM in raw ProseMirror) correctly round-trips the content attribute, otherwise copy-pasting Mermaid blocks between documents will silently drop the diagram source.

Conclusion

Custom nodes are where Tiptap and ProseMirror really shine, letting you embed arbitrarily rich, interactive content—diagrams, code sandboxes, polls, embeds—directly into a structured document model. The Mermaid node we built here demonstrates the essential pattern:

1. Define a schema with the attributes you need.
2. Use a NodeView to bridge the abstract node to real DOM/rendering logic.
3. Provide commands for programmatic insertion.
4. Handle updates gracefully to keep the editor responsive.

Once you understand this pattern, you can apply it to virtually any embeddable content type—it's just a matter of swapping out the rendering library (Mermaid, KaTeX, D3, a video player, etc.) while reusing the same schema/NodeView/command scaffolding.

Happy building! 🎨

Introduction

If you've ever worked with molecular structures in cheminformatics, you've likely encountered the concept of rings — cyclic substructures that are fundamental to understanding molecular topology. Benzene has one ring. Naphthalene has two. But what about complex fused ring systems like steroids or fullerenes? How do we systematically identify the "basic" set of rings in a molecule?

This is where the Minimum Cycle Basis (MCB) comes in — known in the chemistry world as the Smallest Set of Smallest Rings (SSSR). In this post, we'll explore what MCB is, how it's computed, why it matters in chemistry, and some of the subtleties that make it both powerful and occasionally controversial.

What Is a Cycle Basis?

Let's start with some graph theory fundamentals.

A graph \(G = (V, E)\) consists of vertices \(V\) and edges \(E\). A cycle (or circuit) in a graph is a closed path where no vertex is repeated except the starting/ending vertex.

The cycle space of a graph is a vector space over \(GF(2)\) (the field with two elements, \(\{0, 1\}\)), where each cycle is represented as a binary vector indicating which edges are included. Two cycles can be "added" by taking the symmetric difference (XOR) of their edge sets — the result is another element of the cycle space.

A cycle basis is a minimal set of linearly independent cycles that can generate all other cycles through symmetric difference (XOR) operations. The dimension of the cycle space is:

\(\nu = |E| - |V| + c\)

where \(c\) is the number of connected components. This number \(\nu\) is called the circuit rank (or cyclomatic number). Any cycle basis contains exactly \(\nu\) cycles.

A Minimum Cycle Basis (MCB) is a cycle basis where the total weight (sum of cycle lengths, or sum of edge weights) is minimized. In unweighted graphs, this means we want the set of \(\nu\) independent cycles whose total number of edges is as small as possible.

From Graph Theory to Chemistry: The SSSR

In cheminformatics, molecules are naturally represented as graphs: atoms are vertices, and bonds are edges. Ring perception — the identification of cyclic substructures — is one of the oldest and most fundamental problems in chemical information processing.

The Smallest Set of Smallest Rings (SSSR) is the chemistry community's name for the minimum cycle basis. The term was popularized in the 1960s and has been a cornerstone concept ever since.

Why Do Chemists Care About Rings?

1. Aromaticity: Determining whether a ring is aromatic (e.g., benzene, pyridine) requires first identifying the ring.
2. Molecular descriptors: Ring count, ring size distribution, and ring composition are widely used descriptors in QSAR/QSPR.
3. Substructure searching: Many pharmacophore patterns and functional groups involve ring systems.
4. Nomenclature: IUPAC nomenclature rules for polycyclic compounds depend on ring identification.
5. Force fields: Molecular mechanics force fields treat ring atoms differently (e.g., sp2 carbon in a 5-membered ring vs. a 6-membered ring).

A Simple Example

Consider naphthalene (two fused six-membered rings):

The molecular graph has 10 atoms (vertices) and 11 bonds (edges), with 1 connected component. The circuit rank is:

\(\nu = 11 - 10 + 1 = 2\)

So the SSSR contains exactly 2 rings. These are the two individual six-membered rings. Note that the 10-membered peripheral ring (the outer boundary) is not in the SSSR — it can be obtained by XOR-ing the two six-membered rings.

Algorithms for Computing the Minimum Cycle Basis

Several algorithms have been developed over the decades. Let's walk through the major approaches.

1. Horton's Algorithm (1987)

Horton's algorithm was one of the first polynomial-time algorithms for finding an MCB. It works in two phases:

Phase 1: Generate candidate cycles

For every vertex \(v\) and every edge \((u, w)\), Horton considers the cycle formed by the shortest path from \(v\) to \(u\), the edge \((u, w)\), and the shortest path from \(w\) back to \(v\). This generates \(O(|V| \cdot |E|)\) candidate cycles.

Phase 2: Extract a minimum basis

From the candidate set, select \(\nu\) linearly independent cycles with minimum total weight using Gaussian elimination over \(GF(2)\).

Time complexity: \(O(|E|^3 \cdot |V|)\) with naive implementation, though this can be improved.

Pseudocode:

function Horton_MCB(G):
    candidates = []
    
    // Phase 1: Generate candidate cycles
    for each vertex v in V:
        Compute shortest path tree T_v from v (using BFS for unweighted)
        for each edge (u, w) in E:
            if (u, w) not in T_v:
                cycle = shortest_path(v, u) + edge(u, w) + shortest_path(w, v)
                if cycle is a simple cycle:
                    candidates.append(cycle)
    
    // Phase 2: Gaussian elimination
    Sort candidates by weight (length)
    basis = []
    for each cycle C in candidates (ascending weight):
        if C is linearly independent from cycles in basis:
            basis.append(C)
        if |basis| == ν:
            break
    
    return basis

2. De Pina's Algorithm (1995)

De Pina introduced a more elegant approach based on the idea of maintaining a set of "witness" vectors. The algorithm iteratively finds the shortest cycle that is orthogonal to a growing set of support vectors.

Key idea: Maintain vectors \(S_1, S_2, \ldots\) in the edge space. At step \(i\), find the shortest cycle \(C_i\) such that \(\langle C_i, S_i \rangle \neq 0\) (non-zero inner product over \(GF(2)\)). Then update the remaining support vectors to ensure orthogonality.

Time complexity: \(O(\nu \cdot |E|^2)\) or better with efficient shortest-path subroutines.

3. Kavitha et al.'s Algorithm (2009)

This improved de Pina's approach to achieve a time complexity of \(O(|E|^2 |V| / \log |V|)\) for general weighted graphs, and even faster for sparse graphs. This is currently among the fastest known algorithms for MCB.

4. Vismara's Algorithm (1997) — Relevant Cycles

While not strictly an MCB algorithm, Vismara's approach is worth mentioning because it computes the union of all minimum cycle bases — the set of relevant cycles. This is important in chemistry because the MCB is not unique (more on this below), and chemists often want all "chemically meaningful" rings.

5. Classical Chemistry Approaches

In cheminformatics, several simpler (though sometimes less rigorous) algorithms have been widely used:

• Figueras' Algorithm (1996): Based on successive removal of nodes and edges.
• Zamora's Algorithm (1976): An early approach used in chemical databases.
• Fan, Panaye, Doucet, and Barber's Algorithm (1993): Ring perception using path-included distance matrix.

Most modern cheminformatics toolkits (RDKit, OpenBabel, CDK) implement some variant of the above algorithms, often with optimizations specific to molecular graphs (which are typically sparse and have small maximum degree).

A Worked Example

Let's trace through a simple example. Consider cubane (\(C_8H_8\)), whose carbon skeleton forms a cube:

• Vertices (V): 8
• Edges (E): 12
• Circuit rank: \(\nu = 12 - 8 + 1 = 5\)

So the SSSR has 5 rings, each of length 4 (the six faces of the cube give six 4-membered rings, but only five are linearly independent).

The six faces are:

• \(\{1,2,3,4\}\) (top)
• \(\{5,6,7,8\}\) (bottom)
• \(\{1,2,6,5\}\) (front)
• \(\{4,3,7,8\}\) (back)
• \(\{1,4,8,5\}\) (left)
• \(\{2,3,7,6\}\) (right)

Any five of these six 4-membered rings form an MCB. The sixth can always be obtained as the XOR of the other five. This immediately illustrates the non-uniqueness problem.

The Non-Uniqueness Problem

This is perhaps the most important caveat about the SSSR/MCB, and it has caused considerable debate in the cheminformatics community.

The Problem

The minimum cycle basis is not unique. For the cubane example above, there are six different valid SSSR, each containing five of the six faces. Which five should we choose? The choice is arbitrary, and different algorithms may return different results.

This non-uniqueness can lead to problems:

1. Missing chemically intuitive rings: A valid SSSR might omit a ring that a chemist would consider "obvious."
2. Non-reproducibility: Different software packages might give different SSSR for the same molecule.
3. Counterintuitive results: In some pathological cases, the SSSR can omit rings that are "more important" than the ones it includes.

A Notorious Example: Bridged Bicyclics

Consider bicyclo[2.2.1]heptane (norbornane):

The molecule has three rings (two 5-membered and one 6-membered), but \(\nu = 2\). So the SSSR only contains two rings, and which two you get depends on the algorithm. A chemist might want all three.

Solutions

Several approaches have been proposed to deal with non-uniqueness:

1. Relevant Cycles (Vismara): Compute the union of all possible MCBs. This gives all rings that could appear in some minimum cycle basis.
2. Essential Cycles: Cycles that appear in every MCB. These are unambiguously part of the SSSR.
3. ESSR (Extended SSSR): Supplements the SSSR with additional rings to capture all "chemically meaningful" cycles.
4. All Rings: Simply enumerate all cycles (though this can be exponential).

Most modern cheminformatics applications use a combination: compute the SSSR as a basis, then augment it with relevant or essential cycles as needed.

Implementation in Modern Cheminformatics Toolkits

RDKit (Python)

from rdkit import Chem
from rdkit.Chem import rdmolops

mol = Chem.MolFromSmiles('c1ccc2ccccc2c1')  # naphthalene
ring_info = mol.GetRingInfo()

# Get SSSR
sssr = Chem.GetSymmSSSR(mol)
print(f"Number of rings in SSSR: {len(sssr)}")
for ring in sssr:
    print(list(ring))

Output:

Number of rings in SSSR: 2
[0, 1, 2, 3, 4, 9]
[4, 5, 6, 7, 8, 9]

OpenBabel (C++)

OpenBabel uses a modified version of Figueras' algorithm for ring perception:

#include <openbabel/mol.h>
#include <openbabel/obconversion.h>

OpenBabel::OBMol mol;
// ... read molecule ...
std::vector<OpenBabel::OBRing*>& sssr = mol.GetSSSR();
for (auto ring : sssr) {
    std::cout << "Ring size: " << ring->Size() << std::endl;
}

CDK (Java)

import org.openscience.cdk.ringsearch.SSSRFinder;
import org.openscience.cdk.interfaces.IRingSet;

SSSRFinder sssrFinder = new SSSRFinder(molecule);
IRingSet sssr = sssrFinder.findSSSR();
System.out.println("Number of SSSR rings: " + sssr.getAtomContainerCount());

Beyond SSSR: Other Ring Sets in Chemistry

For most practical applications in drug discovery and materials science, the relevant rings or a carefully augmented SSSR provides the best balance between completeness and computational tractability.

Complexity and Performance

For molecular graphs specifically, the situation is much better than for general graphs:

• Molecular graphs are sparse (maximum degree \(\le 4\) for organic molecules, rarely \(> 6\)).
• The circuit rank \(\nu\) is typically small (proportional to the number of atoms).
• Ring sizes are bounded in practice (3-membered to ~30-membered for macrocycles).

This means that even naive SSSR algorithms run efficiently on molecules. For a typical drug-like molecule (20–50 heavy atoms), SSSR computation takes microseconds. Even for large natural products or polymers, it rarely becomes a bottleneck.

However, for graph databases containing millions of molecules, the constant factors matter. Efficient implementations using Horton's algorithm with BFS-based shortest paths (since molecular graphs are unweighted) are preferred.

Mathematical Details: Linear Algebra over GF(2)

For those who want to understand the linear algebra underpinning, here's a deeper look.

Edge Space Representation

Each cycle \(C\) is represented as a vector in \(\{0,1\}^{|E|}\):

\(C = (c_1, c_2, \ldots, c_{|E|}), \quad c_i = \begin{cases} 1 & \text{if edge } e_i \in C \\ 0 & \text{otherwise} \end{cases}\)

XOR Operation

The sum of two cycles over \(GF(2)\) corresponds to the symmetric difference:

\(C_1 \oplus C_2 = C_1 \triangle C_2 = (C_1 \cup C_2) \setminus (C_1 \cap C_2)\)

The result is always a union of edge-disjoint cycles (or the empty set).

Independence Check

During Gaussian elimination, we maintain a matrix where each row is a cycle vector. A new cycle \(C\) is linearly independent from the existing set if it cannot be expressed as an XOR combination of the current basis vectors.

In practice, this is implemented as:

def is_independent(cycle_vector, basis_matrix):
    """Check if cycle_vector is linearly independent from rows of basis_matrix over GF(2)."""
    v = cycle_vector.copy()
    for row in basis_matrix:
        # Find the leading 1 in this basis row
        lead = leading_one(row)
        if v[lead] == 1:
            v = v ^ row  # XOR
    return any(v)  # Independent if v is non-zero

Greedy Selection

The MCB can be found by a greedy algorithm: sort all candidate cycles by weight, then greedily select cycles that are linearly independent from those already chosen. This greedy approach works because the cycle matroid satisfies the matroid property — but note that the set of all cycles does not form a matroid. Horton's insight was identifying a polynomial-size candidate set that is guaranteed to contain an MCB.

Common Pitfalls and FAQs

Q: Is the SSSR always what a chemist expects?

No. The classic counterexample is the envelope of fused rings. In biphenylene (two benzene rings fused with a cyclobutadiene), the SSSR contains two 6-membered rings and one 4-membered ring (\(\nu = 3\)). But a chemist might also consider the 8-membered ring formed by the two six-membered rings sharing the four-membered bridge. This ring is not in the SSSR.

Q: Should I use SSSR or "all rings"?

It depends on your application. For most descriptor calculations and substructure searching, the SSSR is sufficient. For comprehensive ring analysis (e.g., in natural product chemistry), you might want relevant cycles or all small rings up to a size limit.

Q: What about macrocycles?

Macrocycles (rings with \(> 12\) atoms) are correctly identified by SSSR algorithms, but they can be computationally expensive if you're searching for all rings. Most implementations handle them fine for individual molecules.

Q: How does SSSR handle disconnected molecules?

The formula \(\nu = |E| - |V| + c\) accounts for multiple connected components. Each component contributes independently to the SSSR.

Conclusion

The Minimum Cycle Basis — or SSSR as chemists call it — sits at a beautiful intersection of graph theory and chemistry. While the underlying mathematics is elegant (linear algebra over \(GF(2)\), matroid theory, shortest-path algorithms), the practical application to chemical ring perception has driven decades of algorithmic development.

The key takeaways:

1. MCB = SSSR: They're the same concept viewed from different disciplines.
2. The circuit rank \(\nu = |E| - |V| + c\) tells you exactly how many rings are in the basis.
3. Non-uniqueness is the main challenge — be aware that different algorithms may give different (but equally valid) results.
4. For chemistry applications, consider using relevant cycles or augmented SSSR when completeness matters.
5. Modern toolkits (RDKit, OpenBabel, CDK) handle SSSR computation efficiently for typical molecules.

Understanding ring perception is fundamental to almost every area of cheminformatics. Whether you're computing molecular descriptors, searching chemical databases, or designing retrosynthetic routes, the SSSR is working behind the scenes to make sense of molecular topology.

References

1. Horton, J. D. (1987). "A polynomial-time algorithm to find the shortest cycle basis of a graph." SIAM Journal on Computing, 16(2), 358–366.
2. De Pina, J. C. (1995). "Applications of shortest path methods." PhD thesis, University of Amsterdam.
3. Kavitha, T., et al. (2009). "An \(\tilde{O}(m^2n)\) algorithm for minimum cycle basis of graphs." Algorithmica, 52(3), 333–349.
4. Vismara, P. (1997). "Union of all the minimum cycle bases of a graph." Electronic Journal of Combinatorics, 4(1), R9.
5. Downs, G. M., et al. (1989). "Review of ring perception algorithms for chemical graphs." Journal of Chemical Information and Computer Sciences, 29(3), 172–187.
6. Berger, F., Gritzmann, P., & de Vries, S. (2004). "Minimum cycle bases for network graphs." Algorithmica, 40(1), 51–62.
7. Plotkin, M. (1971). "Mathematical basis of ring-finding algorithms in CIDS." Journal of Chemical Documentation, 11(2), 94–98.
8. Figueras, J. (1996). "Ring perception using breadth-first search." Journal of Chemical Information and Computer Sciences, 36(5), 986–991.