[darcs-devel] conflict resolution: an efficient algorithm

[Ben Franksen]

Am 22.05.2018 um 19:15 schrieb Benjamin Franksen:
> Unfortunately, I have no idea how to order non-conflicting patches in
> general i.e. when patches other than hunks are involved. For instance, a
> hunk followed by a replace commute if the new token is present in
> neither source nor target interval of the hunk. Two replace patches
> commute if the tokenChars are identical and the {oldtoken,newtoken} sets
> are disjoint.

To clarify, what I mean is that I see no way to define an irreflexive
partial order < such that p does not conflict with q if and only if p <
q or q < p. Graphs with such a property are called comparability graphs
or transitively orientable and they have polynomial algorithms for
calculating the maximal cliques.

Apart from this principal problem, the situation for camp conflictors is
somewhat different than for darcs-2. This is because they do not store
the transitive set of conflicting patches, only those that directly
conflict. This means we cannot calculate the resolution using one
conflictor alone, as we can for darcs-2. Instead, we first need to
commute every conflictor in the repo (up to the latest clean tag) to the
end of the repo, if possible, and then build the conflict graph from all
of them at once. The good news is that this is going to be *much* faster
than for darcs-2 conflictors because the incidence list for each vertex
can be directly read off the representation of the conflictor (once it
has been commuted to the end of the repo) and does not need to be
(re-)calculated by trying to merge them. Once a suitable graph
representation has been built (using Int for vertices and an array of
[Int] for the edges), we must split it into connected components and
then for each component calculate the maximal independent sets (which
are the maximal cliques of the complementary graph). I have implemented
an algorithm (adapted from one of the papers I have read) and it
performs quite well on randomly generated graphs with up to 100 vertices.

Cheers
Ben