Detect multiple possible solutions

[yngvem]

We should detect whenever there are multiple possible alignments

To do this, we can modify the alignment code in https://github.com/yngvem/stringalign/blob/59e6c59b57759ecd8d94bab6453ba694a33f4318/python/stringalign/align.py#L134

ALIGNMENT_DIRECTIONS = {
    Keep: (-1, -1),
    Replace: (-1, -1),
    Insert: (-1, 0),
    Delete: (0, -1)
}
# [...]
multiple_alignments = False
while row > 0 or col > 0:
    num_alignments = 0
    to_append: AlignmentOperation | None = None

    if row > 0 and col > 0 and reference_clusters[row - 1] == predicted_clusters[col - 1]:
        num_alignments = 1
        to_append = Keep(reference_clusters[row - 1])
    if row > 0 and (col == 0 or cost_matrix[row, col] == cost_matrix[row - 1, col] + 1):
        num_alignments += 1
        to_append  = to_append  or Insert(reference_clusters[row - 1])
    if col > 0 and (row == 0 or cost_matrix[row, col] == cost_matrix[row, col - 1] + 1):
        num_alignments += 1
        to_append  = to_append  or Delete(predicted_clusters[col - 1])
    if row > 0 and col > 0 and cost_matrix[row, col] == cost_matrix[row, col] + 1:
        num_alignments += 1
        to_append  = to_append  or Replace(predicted_clusters[col - 1], reference_clusters[row - 1])
    assert num_alignments
    assert to_append is not None

    is_unique = is_unique and (not num_alignments > 1)
    alignment.append(to_append)

[yngvem]

Some test cases:

• a, a, True
• b, a, True
• a, b, True
• aa, ab, True
• abc, adc, True
• aa, a, False
• ab, ba, False