[darcs-devel] conflict resolution: an efficient algorithm

[Ben Franksen]

I made a small mistake in the description of the algorithm: I have
written C0(s,q) where it should be C1(s,q). I have marked the error below.

Am 14.05.2018 um 15:30 schrieb Ben Franksen:
> Pick any element s of C(q) (s is a sequence of prim patches). Try to
> merge it with all other elements of C(q). The result is two new sets:
> C0(s,q) contains all elements of C(q)\{s} that conflict with s, while
> C1(s,q) contains the result of the merge for those that do not conflict
> with s. If C1(s,q) is empty, then {s} is already maximal and we are done
> with C1(s,q). If it has only one element, then this element is maximal
> and we are also done with C1(s,q). Otherwise any maximal non-conflicting
> subset of C(q) that contains s must also contain at least one of the
> elements of C1(s,q) and none of the elements of C0(s,q). Suppose we have
> u and v in C(q)\{s} that both do not conflict with s, let su and sv be
> the result of the merges with s, then su and sv conflict if and only if
> u and v conflict. Thus any maximal non-conflicting subset that contains
> s must be among the results of solving the sub-problem for C0(s,q). On
                                                             ^^^^^^^
                                                  should be: C1(s,q)
> the other hand, any maximal non-conflicting subset of C(q) that does
> /not/ contain s must be a subset of C0(s,q). So we can recursively solve
> the sub-problems for both C0(s,q) and C1(s,q) and the result is the
> (disjoint) union of the two sub-results.

Cheers
Ben