mutually_avoiding.py

"""
this files contains the function related to the notion of mutually avoiding decomposition tree
(for now it need to be copy-paste to main)
"""
def mutually_avoiding_algorithm():
    geom = draw_geom()[0]
    chirot = chiro(geom)

    def BadAlgo(X, e):
        E = set(X) - {e}
        set_ = set()
        for x in E - {e}:
            for y in E - {x, e}:
                tup = tuple((e, x, y))
                sorted_tup = tuple(list(sorted(tup)))
                if sign_perm(tup) * chirot[sorted_tup] == +1:
                    bool_ = True
                    A = {x, y}
                    for f in E - {x, y, e}:
                        tupx = tuple((e, f, x))
                        tupy = tuple((e, f, y))
                        sortedx = tuple(list(sorted(tupx)))
                        sortedy = tuple(list(sorted(tupy)))
                        if sign_perm(tupx) * chirot[sortedx] != sign_perm(tupy) * chirot[sortedy]:
                            tupx2 = tuple((e, x, f))
                            sortedx2 = tuple(list(sorted(tupx2)))
                            if sign_perm(tupx2) * chirot[sortedx2] == +1:
                                A = A.union({f})
                            else:
                                bool_ = False
                                break
                    if bool_:
                        # print(A)
                        set_ = set_.union({tuple(list(sorted(A)))})
                        compA = set(X) - A
                        set_ = set_.union({tuple(list(sorted(compA)))})
        print(set_)
        return set_

    def GoodAlgo():
        pass

    E = chirot.get_ground_set()
    e = E[0]
    family = BadAlgo(E, e)
    for i in range(1, len(E)):
        e = E[i]
        # print(family)
        family = family.intersection(BadAlgo(E, e))
    print("AVEC ALGO")
    print(list(sorted(family)))
    print("EXHAUSTIF")
    family2 = set()
    circuits = cocirc(chirot)
    for A in powerset(E):
        if MA(circuits, A):
            family2 = family2.union({tuple(list(sorted(A)))})
    print({elem for elem in family2 if 2 <= len(elem) <= len(E) - 2})

def ma_example():
    """
    Program used to make example of the article on Mutually avoiding decompositions.
    :return:
    """
    # First we calculate the oriented matroid M on the set described in Figure ??
    # We also compute its sets of circuits and its chirotopes. M has to be uniform.
    geom = read("files/geometric_model/exMA2.txt")
    # latex(geom)
    print(geom)
    chirot = chiro(geom)
    circuits = circ(geom)
    print(circuits.is_uniform())

    # THis algo is sligthly differnt as the one described in the article but uses the same principle
    # for each e \in E we compute the sets of interval f_e of \sigma_e
    def BadAlgo(X, e):
        E = set(X) - {e}
        set_ = set()
        for x in E - {e}:
            for y in E - {x, e}:
                tup = tuple((e, x, y))
                sorted_tup = tuple(list(sorted(tup)))
                if sign_perm(tup) * chirot[sorted_tup] == +1:
                    bool_ = True
                    A = {x, y}
                    for f in E - {x, y, e}:
                        tupx = tuple((e, f, x))
                        tupy = tuple((e, f, y))
                        sortedx = tuple(list(sorted(tupx)))
                        sortedy = tuple(list(sorted(tupy)))
                        if sign_perm(tupx) * chirot[sortedx] != sign_perm(tupy) * chirot[sortedy]:
                            tupx2 = tuple((e, x, f))
                            sortedx2 = tuple(list(sorted(tupx2)))
                            if sign_perm(tupx2) * chirot[sortedx2] == +1:
                                A = A.union({f})
                            else:
                                bool_ = False
                                break
                    if bool_:
                        # print(A)
                        set_ = set_.union({tuple(list(sorted(A)))})
                        compA = set(X) - A
                        set_ = set_.union({tuple(list(sorted(compA)))})
        print(set_)
        return set_


    E = chirot.get_ground_set()
    e = E[0]
    # we calculates the intersection of all the f_e. In this algorithm, we do not take into acocunt the singletons.
    family = BadAlgo(E, e)

    for i in range(1, len(E)):
        e = E[i]
        # print(family)
        family = family.intersection(BadAlgo(E, e))
    # we print the list of mutually avoiding sets computed by the aglorithm
    print("AVEC ALGO")
    L = list(sorted(family))
    print(L)
    # we compare it with an exhaustive algorihtm
    print("EXHAUSTIF")
    family2 = set()
    circuits = cocirc(chirot)
    for A in powerset(E):
        if MA(circuits, A):
            family2 = family2.union({tuple(list(sorted(A)))})
    family2 = {elem for elem in family2 if 2 <= len(elem) <= len(E) - 2}
    print(family2)
    print(family.symmetric_difference(family2))

    # Now we compute the sets of strong elements (i;e: edges of the tree decomposition)
    def crossing_free(L: list, E):
        C = []
        set_E = set(E)
        for i in range(0, len(L)):
            bool_ = True
            set_i = set(L[i])
            for j in range(0, len(L)):
                if i != j:
                    set_j = set(L[j])
                    if set_i.intersection(set_j) != set() and set_i.difference(set_j) != set() and set_j.difference(
                            set_i) != set():
                        print(L[i], L[j])
                        if set_i.union(set_j) != set_E:
                            print(L[i], L[j])
                            bool_ = False
                            break
            if bool_:
                C.append(L[i])
        return C

    crossfree = crossing_free(L, E)
    print("crossing-free:", crossfree)

    L2 = [elem for elem in crossfree if 0 not in elem]

    print(L2)