[darcs-devel] conflict resolution: an efficient algorithm

Benjamin Franksen ben.franksen at online.de
Tue May 22 17:15:05 UTC 2018


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.

At the moment I think this means that for the general case we have to
fall back to calculating maximal cliques with the Bron-Kerbosch
algorithm, which has worst-case running time of O(3^(n/3)).

On 05/18/2018 08:37 PM, Guillaume Hoffmann wrote:
> Hi Ben,
> 
> I'm attaching the article you mentionned.
> 
> I cannot bring myself up to speed with your current research right now, but
> I suspect there indeed exists a better (compatible) algorithm for darcs-2
> conflict resolution. Keep on the good work!
> 
> Guillaume
> El jue., 17 may. 2018 a las 10:46, Benjamin Franksen (<
> ben.franksen at online.de>) escribió:
> 
>> The algorithm I presented is incorrect and the conclusions drawn
>> therefore obsolete. The problem is that C0(s,q) is /not/ a superset of
>> all solutions that don't contain s because neither "conflicts with" nor
>> "does not conflict with" are transitive relations. Thus solving the
>> subproblem for C0(s,q) is not enough to determine all maximal
>> non-conflicting subsets that do not contain s.
> 
>> In fact, the problem of finding maximal non-conflicting subsets is
>> equivalent to a well-known problem in graph theory, namely that of
>> finding the maximal cliques of a simple graph. The vertices of the graph
>> are the elements of C(q) and an edge means "does not conflict with".
> 
>> This problem is NP-complete in general (according to wikipedia).
> 
>> There are a number of graph classes for which it is solvable in
>> polynomial time and I think our concrete problem should be in one of
>> those classes. A good candidate are comparability graphs since our main
>> target are hunk patches: a set of transitively conflicting hunks must be
>> in the same file and thus all pairs among them that are not in conflict
>> can be strictly ordered. Another way to see this is that the complement
>> graph (where an edge means "conflict") is an interval graph, where the
>> interval is the the set of lines modified by the hunk.
> 
>> Wikipedia tells me that there is a quadratic time algorithm for finding
>> the maximal cliques of a comparability graph but unfortunately the
>> article is behind a paywall. Here is the citation: Even, S.; Pnueli, A.;
>> Lempel, A. (1972), "Permutation graphs and transitive graphs", Journal
>> of the ACM, 19 (3): 400–410). If someone has access to a copy...
> 
>> BTW, given some strict order between non-conflicting pairs of patches
>> (which is the definiton of a comparability graph) it seems that maximal
>> cliques must actually be paths.
> 
>> Cheers
>> Ben
> 
> 
>> _______________________________________________
>> darcs-devel mailing list
>> darcs-devel at osuosl.org
>> https://lists.osuosl.org/mailman/listinfo/darcs-devel
>>
>>
>> _______________________________________________
>> darcs-devel mailing list
>> darcs-devel at osuosl.org
>> https://lists.osuosl.org/mailman/listinfo/darcs-devel




More information about the darcs-devel mailing list