instagram.py

def form_preference_list(image, edge, others):
    def g():
        for other_edge in others:
            yield (other_edge, image.row_dist(edge, other_edge))
    return [x[0] for x in sorted(g(), key=operator.itemgetter(1))]


def stable_matching(image, lefts, rights):
    free_left = set(lefts)
    right_edges = set(rights)

    result = []

    def _match(edge):
        for pair in result:
            if edge in pair:
                return pair

    while free_left:
        left = free_left.pop()
        print 'Lefts %d' % len(free_left)
        for preferred in form_preference_list(image, left, right_edges):
            if not _match(preferred):
                result.append((preferred, left))
                break
            else:
                right_pref = form_preference_list(image, preferred, lefts)
                pair = _match(preferred)
                if right_pref.index(pair[1]) > right_pref.index(left):
                    free_left.add(pair[1])
                    result.remove(pair)
                    result.append((preferred, left))
                    break
    return result