Validation

BubbleFinder's snarl, superbubble, and ultrabubble algorithms are validated against a brute-force implementation on randomly generated graphs. This page describes how to run these tests.

---

Brute-force implementation

A brute-force program is built together with BubbleFinder from source and resides in the build directory after compilation. It can compute snarls and, in a different mode, superbubbles on a given GFA file. In the examples below this binary is referred to as ./build/snarls_bf.

To run the brute-force program on snarls:

cd build
./snarls_bf gfaGraphPath

The brute-force program outputs results consumed by src/bruteforce.py, which compares them with BubbleFinder's output. The same engine handles superbubble validation via the --superbubbles mode.

---

Random testing with src/bruteforce.py

The script src/bruteforce.py generates random graphs and compares the brute-force implementation against BubbleFinder. It operates in three modes: Snarls, Superbubbles, and Ultrabubbles.

Snarls

python3 src/bruteforce.py \
  --bruteforce-bin ./build/snarls_bf \
  --bubblefinder-bin ./BubbleFinder \
  --n-graphs 100

This generates random GFA graphs, runs both finders, compares their outputs (missing / extra pairs / segfaults), and optionally checks consistency across different thread counts (pass multiple values to --threads).

Ultrabubbles

Since oriented mode requires at least one tip or cut vertex per connected component, restrict generated graphs with:

python3 src/bruteforce.py \
  --bruteforce-bin ./build/ultrabubbles_bf \
  --bubblefinder-bin ./BubbleFinder \
  --n-graphs 100 \
  --min-tips-per-cc 1

Superbubbles

python3 src/bruteforce.py \
  --superbubbles \
  --bruteforce-bin ./build/superbubbles_bf \
  --bubblefinder-bin ./BubbleFinder \
  --n-graphs 100

To additionally check result consistency across thread counts:

python3 src/bruteforce.py \
  --superbubbles \
  --bruteforce-bin ./build/superbubbles_bf \
  --bubblefinder-bin ./BubbleFinder \
  --n-graphs 100 \
  --threads 1 4 8

Any divergence or error is reported. Pass --keep-failing to save the corresponding GFA and BubbleFinder outputs in /tmp for manual inspection.