Comment 4 for bug 567214

Status update:

Transpositions that occur between the witnesses cause cycles in the VariantGraph.
The challenge is how to deal with these cycles.

I got cycle detection to work on the VariantGraph implementation. Problem is that one transposition can cause multiple cycles. It is not easy to transform cycles intro transpositions and decycle them. The damage has already occured.

I recently changed tactics. Instead of working on cycle detection, I am now working on cycle prevention.
The focus of development has shifted to cycle prevention while building the VariantGraph.

In my 'old' alignment code from the bootcamp of april 2010 there already is transposition detection code.
I need to combine the new VariantGraph based alignment code with the old transposition detection code.

pseudo code looks as follows:

buildVariantGraph:
for each witness {
  match tokens of new witness with existing variant graph
  determine sequences in matches
  determine transpositions
  for each transposition {
    determine which vertices in the variant graph need to be duplicated to prevent cycles
    add vertices
  }
  add edges for matches, add vertices for variants.
}

The new implementation is in the VariantGraph2 class in the experimental package in the 1.0development tree of the source code. The implementation has just started, the code will be in a state of flux for a while.
When its done it will replace the current VariantGraph and DAVariantGraph classes.