faster implementation of finding maximal simplices

[maximelucas]

This question https://stackoverflow.com/questions/14106121/efficient-algorithm-for-finding-all-maximal-subsets contains an answer with an efficient python-coded solution. We might want to incorporate this to replace ours.

[nwlandry]

This is a great idea! Especially since we've already built the forward and reverse maps.

[nwlandry]

This is a first pass at a faster version - from initial testing, this method is anywhere from 4x-40x faster than the current method. The naïve approach is first and then the method based on the thread you linked is second:

def maximal_faces(H):
    """Gets the maximal faces given a hypergraph

    Parameters
    ----------
    H : Hypergraph

    Returns
    -------
    dict of iterables
        The dict of maximal faces.
    """
    edges = H.edges.members(dtype=dict)
    max_faces = {}

    for i, e in edges.items():
        flag = True
        old_max_faces = dict(max_faces)
        for j, f in old_max_faces.items():
            if set(e).issubset(f):
                flag = False
                break
            elif set(f).issubset(e):
                del max_faces[j]
        if flag:
            max_faces[i] = e
    return max_faces

def fast_maximal_faces(H):
    """Gets the maximal faces given a hypergraph

    Parameters
    ----------
    H : Hypergraph

    Returns
    -------
    dict of iterables
        The dict of maximal faces.
    """
    edges = H.edges.members(dtype=dict)
    nodes = H.nodes.memberships()
    max_faces = {}

    intersection = lambda x, y: x & y

    for i, e in edges.items():
        in_common = reduce(intersection, [nodes[n] for n in e])

        if len(in_common) == 1:
            [elem] = in_common
            if elem == i:
                max_faces[i] = e
    return max_faces

[nwlandry]

Two more things:

1. The new method gets rid of multiples of maximal edges.
2. Finding maximal edges can be useful not just for simplicial complexes, but for hypergraphs too. I think we should extend the method to work for both. (The last I checked, it only worked for simplicial complexes)

[leotrs]

Code looks good. Yes to also implementing it on hypergraphs.