allow subdomains to have multiple parents

[dave-doty]

It was only for convenience that subdomains have a single parent, but nothing logically prevents them from having multiple parents, we just have to implement it. Currently it isn't even checked whether two different domains use the same subdomain as children, so it just silently replaces the _parent field with the second one, and this leads to bugs where the first domain doesn't get assigned (if the parents are the dependent ones and the children are the independents domains).

Generalize to allow an arbitrary DAG, rather than a tree, describing subdomains.

[dave-doty]

We had talked about enforcing the constraint that either exactly one, or at most one, domain is independent on any path from a source to a sink.

Suppose we enforce that it is exactly one. In the case of a tree, this makes every domain "uniquely assignable". But this is not true for an arbitrary DAG. Suppose we have two domains d1 and d2 with a shared subdomain s. They could overlap like this:

d1 -------------------------------->
d2                       ---------------------------------->
s                        ---------->

Then if we declare s is dependent and d1, d2 are independent, this obeys the constraint that there is exactly one independent domain on any source-to-sink path. However, s is not "uniquely assignable", it could be changed by assigning to either d1 or d2. Worse yet, if we assign to d1, we have to change d2 also since they overlap.

Now, maybe this is not a big deal to allow this non-unique assignability. However, we probably want to change how we represent domain sequences. In particular, going through the entire DAG each time one is updated and updating the other sequences might be hard to do efficiently.

A better approach might be to traverse the DAG once before the search and create a single long mutable string. This string won't necessarily be the sequence of any domain or strand in the system. Above, it would be the "union" d1 and d2. Then each domain would store intervals, start and end indices into this long string, and when one is updated, we just update that substring. This would then immediately reflect the changes in every other domain.

One way to do this is to use a bytearray to store the long sequence, and use memoryview to maintain subarrays, where changes to either the big array or its subarrays will be reflected in the others.

We would still have to somehow track which domains changed, so that we know which constraints need to be reevaluated. This is currently done here:

nuad/nuad/search.py

Line 96 in bd65b5c

domains_in_tree = domain.all_domains_in_tree()

where all domains in the same tree are considered changed. That will have to be rewritten to search in the DAG, and should also be optimized since not every domain in the DAG necessarily changed. For instance, if the subdomains are

p1     --------------------------------------------> 
                                         p2 ---------------------------------->
                    d1  ------------>    d2 ------->

Above, if d1 changes, then p1 also changes, but not d2 or p2.