#!/usr/bin/env python3

#####################################################
### Function that returns all matchings for a list
### of vertices.

def matchings(l):
    """
    Returns all matchings of elements of list l
    """
    if len(l) <= 1:
        return [[]]
    else:
        m = matchings(l[1:])
        for i in l[1:]:
            l1 = l[1:]
            l1.remove(i)
            m += [m1 + [(l[0],i)] for m1 in matchings(l1)]
        return m

#####################################################
### Node class for union-find structure

class Node:
    def __init__(self, value):
        self.value = value
        self.parent = self

#####################################################
### Main class for union-find structure

class UnionFind:
    def __init__(self):
        self.nodes = {}

    def find(self, value):
        if value not in self.nodes:
            self.nodes[value] = Node(value)
            return value
        
        current_node = self.nodes[value]
        while current_node.parent != current_node:
            current_node = current_node.parent
        
        return current_node.value

    ### This is a special form of the union operation.
    ### It returns 1 if the arguments already belong
    ### to the same component, and 0 otherwise.
    ### In the context of two matchings, returning 1
    ### means closing a cycle.
    
    def union(self, value1, value2):
        root1 = self.find(value1)
        root2 = self.find(value2)
        
        if root1 != root2:
            self.nodes[root2].parent = self.nodes[root1]
            return 0
        else:
            return 1

#####################################################
### Distance computation using union-find structure to determine
### the connected components of the union of two matchings.

def dist(x, y):
    """
    Compute distance between matchings.

    Method: use union-find structire to record the connected
    components of the union of two matchings.
    For each edge in either matching, add 1 to distance.
    For each cycle closed (union returns 1), subtract 2
    from distance.
    """
    d = 0
    uf = UnionFind()
    for u, v in x:
        d += 1
        uf.union(u, v)
    for u, v in y:
        d += 1
        d -= 2 * uf.union(u, v)
    return d

def score(m, a, b, c):
    """
    Computes the score d(m; a, b, c).
    """
    return dist(m, a) + dist(m, b) + dist(m, c)

def medians(a, b, c, candidates):
    """
    Returns all medians of the first three parameters
    among all matchings given by the fourth parameter.
    """
    minimum = -1
    for m in candidates:
        sc = score(m, a, b, c)
        if minimum == -1 or sc < minimum:
            minimum = sc
            medians = [m]
        elif sc == minimum:
            medians.append(m)
    return medians

def occur(edges, lists):
    """
    Returns true when at least one of the edges
    belongs to at least one of the medians.
    """
    for e in edges:
        for l in lists:
            if e in l:
                return True
    return False

#####################################################
### Tests whether there is always an edge that is a
### partial median in a 4-cycle involving A and
### B in a graph with 8 vertices.

def main():
    ## Edges making up the 4-cycle
    ## It is important that all edges are increasing
    ### e.g., write (1,2), not (2,1)
    initial_a = [(0,1), (2,3)]
    initial_b = [(1,2), (0,3)]

    ## Complement: possible matchings on the
    ## vertices not involved in the initial edges
    compl = matchings(list(range(4,8)))

    ## All 8-vertex matchings: to loop over for
    ## the C matching and for median candidates
    all = matchings(list(range(8)))

    for ca in compl:
        ## ca is the complement for A
        a = initial_a + ca
        print("A", a)
        for cb in compl:
            ## cb is the complement for A
            b = initial_b + cb
            print("B", b)
            for c in all:
                print("C", c)
                ## Collects all medians, see if some edge belongs
                mds = medians(a, b, c, all)
                print("MS", mds)
                if not occur(initial_a + initial_b, mds):
                    print('problem', a, b, c, mds)

if __name__ == "__main__":
    main()