Macaulay2 / Macaulay2/M2

SuffixTree misses overlaps on small pattern sets and leaves expected suffix links unset

Open
#4,701 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Engine
Dominant language
Macaulay2
Stars
435
Forks
297
Avg merge
4d 20h
Merged PRs (30d)
11

Description

Restoring the existing suffix-tree unit tests exposes missing overlaps on small pattern sets. The same Sklyanin overlap case passes through `WordTable`.

### Minimal overlap reproduction

Add this case to `M2/Macaulay2/e/unit-tests/NCGroebnerTest.cpp`, which already includes the required headers:

```cpp
TEST(SuffixTree, initialSklyaninOverlaps)
{
const std::vector patterns {{2, 0}, {2, 1}, {2, 2}};
SuffixTree tree;
std::vector overlaps;
for (const auto& pattern : patterns)
tree.insert(Word(pattern), overlaps);
const std::vector expected {
std::make_tuple(2, 1, 0, true),
std::make_tuple(2, 1, 1, true),
std::make_tuple(2, 1, 2, true)};
std::sort(overlaps.begin(), overlaps.end());
EXPECT_EQ(expected, overlaps);
}
```

For `ZX`, `ZY`, `ZZ`, the final word has one-letter right overlaps with all three words. Expected:

```text
{ (2, 1, 0, true), (2, 1, 1, true), (2, 1, 2, true) }
```

Actual:

```text
{ (2, 1, 2, true) }
```

Replacing `SuffixTree` with `WordTable` yields all three expected overlaps.

### Another existing pattern set

Inserting `{{2,2}, {2,0,1}, {1,0,1,0}}` (`cc`, `cab`, `baba`) should report the self-overlaps of `cc` and `baba`:

```text
Expected: { (0, 1, 0, true), (2, 2, 2, true) }
Actual: { (0, 1, 0, true) }
```

In that same case, the existing test expects the nodes located by `extendedLocus(root, ...)` for `a`, `b`, and `c` to have suffix links to the root, and the `ba` node to link to the `a` node. All four observed suffix links are null.

These are the initial failed invariants in the restored `SuffixTree.suffixtree1` and `SuffixTree.suffixtree2` tests. The tests stop at the overlap failures before proceeding to the longer pattern sets, so those later paths are not validated by the current run. Re-enable the tests once the intended overlap and suffix-link invariants hold.

### Verification

Reproduced with CMake Debug and Autotools on Apple Silicon/macOS, using the engine at `abbcf9b3b35df37fb6aa33fd5c05e9928ab9281a` on the `retroactive` branch, with the test-only working-tree changes being prepared for [MichaelABurr/M2#82](https://github.com/MichaelABurr/M2/pull/82). Both restored tests also fail in the shuffled run with seed 915 and the coverage build. No production fix is included.

Searched open and closed issues for `SuffixTree` and `"suffix tree"`; no matching report was found.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the restored SuffixTree.suffixtree1 and SuffixTree.suffixtree2 tests in M2/Macaulay2/e/unit-tests/NCGroebnerTest.cpp, then inspect the SuffixTree behavior alongside WordTable for the reported pattern sets. Re-enable the tests and verify that all expected overlaps are found and that the nodes for a, b, c, and ba have the specified suffix links, including in shuffled and coverage runs.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend, testing-qa
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.