After discovering a bug (thanks windows buildbot!) in the application of label
reduction to label equivalence relation that would try to remove a label from a
group it wasn't part of, I ran another experiment comparing to the version
before this issues. Fortunately, nothing changed:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-base-current-comparison.html

I guess that gcc willingly removes an element from a doubly linked list even
from the "wrong" group, because the removing operation actually does not have to
look at the group and only has to update the pointers of the neighbouring
elements. The Visual Studio compiler failed however.

That change was already included. Merged and pushed.

If the change to use caches within the heuristics (done by Salomé a while back)
is already integrated in your branch, then I don't think it's necessary.
Everything else shouldn't change where and how many times heuristic values are
computed. But of course feel free to run experiments if you prefer.

Summarizing comparison (baseline vs v7):
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-base-v7-comparison.html

Performance increases for f-preserving shrinking configurations, and decreases
for bisimulation shrinking configurations. Considering that the code got much
cleaner (thanks for the feedback!), I think this can be merged.

However, there have been *lots* of changes in the default branch; should I
re-run experiments after merging the latest version?

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v7-rest-issue604-v6-issue604-v7-compare.html

All together, this doesn't look that bad. (Although I still don't understand why
there is so much change at all.)

In version 7, I changed the recomputation of label group costs in
LabelEquivalenceRelation to only recompute the cost of affected groups. To do
so, the method takes an unordered_set<int> pointer from TransitionSystem, which
computes this information anyway. Surprisingly for me, this does not have a
purely positive impact on performance. However, it is unclear to say that memory
or time increases or decreases, because it is different for different
configurations.

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v7-issue604-v6-issue604-v7-compare.html

I'll also run the remaining configurations of the regular ones.

Very nice.

And especially after seeing the results in version 6, where I basically changed
one line, namely to reserve memory for the new transitions when applying an
abstraction to a transition system
(new_transitions.reserve(old_transition.size())). Even if this is usually too
much, it apparently is a lot better than risking several resizes.

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v6-issue604-v5-issue604-v6-compare.html

I think we can live with it, especially as coverage still looks good.

In version 5, as discussed, we store a vector<Transitions> for later moving
instead of a set. This attenuates the increase of memory consumption compared to
the last version, but in comparison with version 3, there is still a notable
difference. For some configurations, the average memory score goes down by up to
0.75. Should we live with that?

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v3-v5-comparison.html

Version 4 changed the order of the method
TransitionSystem::apply_label_reduction as we discussed, but unfortunately, the
memory consumption increases a lot.
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v4-issue604-v3-issue604-v4-compare.html

I think that precomputing the transitions and keeping them around (and we still
need to the keep the old group ids in parallel) for *all* label reductions,
before assigning them to their new position, is too expensive.
(The changeset is here:
https://bitbucket.org/SilvanS/fd-dev/commits/a77dddbb03abbbb5f257ec5fab60e25b5952a1ae)

Results for version 3, which fixes the slow version 2, are fine (comparison
against v1):
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v1-v3-comparison.html

Following our discussion from the train this morning, I separated the single
loop into several pieces: unfortunately, it now requires 4 iterations over the
label mapping or its derived information to incorporate the label mapping:
1) collect the group ids which are affected for every "single" label reduction
2) update label equivalence relation: remove all labels from their group(s), add
a new group for the new label
3) compute the transitions for all new labels (more precisely, all new label
groups), and remember all label groups that became empty -- we cannot remove
their transitions yet however, as we still may need them for other label reductions
4) remove all transitions of label groups that became empty

The method in TransitionSystem did not become shorter, but at least the
interface of LabelEquivalenceRelation became smaller. I am still not sure
whether this change is really an improvement. It is small and has a nice
side-by-side diff. Maybe you could have a look at it?
https://bitbucket.org/SilvanS/fd-dev/commits/84ef1034f272245f923df93dc94ca9f19512d800?at=default

Version 2 includes some refactoring and documentation of TransitionSystem. Most
importantly, the class TSConstIterator now has a more typical iterator class
interface, with a *-operator that returns a simple class that wraps the label
group and its transitions. To avoid also having a non-const iterator,
TransitionSystems internally directly iterates over the group ids (only in once
place, namely computation of locally equivalent labels). In the second version,
this was done without skipping empty label groups, and hence caused a huge overhead.

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v2-issue604-v1-issue604-v2-compare.html

Version 3 fixes this, but results aren't ready yet.

In version 1, the three constructors of TransitionSystem have been replaced by a
single one-shot constructor, that moves in all necessary data, either provided
by the FTSFactory (atomic transition systems) or a new static merge method in
TransitionSystem.

Results:
http://ai.cs.unibas.ch/_tmp_files/sieverss/issue604-v1-issue604-base-issue604-v1-compare.html
There seems to be slight a increase in memory consumption, which I cannot
explain. The diff is somewhat small, maybe it is worth to have a look at it.
https://bitbucket.org/SilvanS/fd-dev/pull-requests/10/issue604/diff

This is part of meta issue567. 

We want to tackle item O.):
  - We currently have a two-stage initialization for the atomic
    transition systems. First, they are created in an incomplete state,
    and then the factory takes over the rest of the initialization. We
    should have a constructor that generates them in one shot.

More precisely, atomic transition systems are currently partly created by
FTSFactory, and party in an "atomic transition system" constructor. The goal is
to get rid of the three different constructors in TransitionSystem, and to have
only one constructor which moves in *all* data which make up a transition
system. This also requires the merge constructor to be moved to a separate
function, which will probably be used from FactoredTransitionSystem.