Revision history [back]

A perfect matching (if the graph has one) is a spanning elementary subgraph according your definition. You can get all the perfect matchings (only 1 in your graph) using

sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]

Now if you want all spanning elementary subgraphs, you have to design a specific algorithm.

A perfect matching (if the graph has one) is a spanning elementary subgraph according your definition. You can get all the perfect matchings (only 1 in your graph) using

sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]

Now if you want all spanning elementary subgraphs, you have to design a specific algorithm.

def elementary_subgraphs(G, nmin=0):
    r"""
    Iterator over the elementary subgraphs of `G`.

    A subgraph `H` of a graph `G` is *elementary* if each of its connected
    components is either an edge or a cycle.

    INPUT:

    - ``G`` -- a Graph

    - ``nmin`` -- integer (default: ``0``); lower bound on the number of
      vertices involved in the elementary subgraphs of any returned
      solution. When set to ``G.order()``, the subgraphs must be spanning.
    """
    G._scream_if_not_simple()

    def rec(H, low):
        if not H.size():
            yield {'cycles': [], 'edges': []}, 0
            return
        if H.order() < low:
            # no solution
            return

        # We select an edge e = (u, v) of H and remove it
        u, v = next(H.edge_iterator(labels=False))
        H.delete_edge((u, v))

        # Case 1: return solutions without e
        for sol, n in rec(H, low):
            if n >= low:
                yield sol, n

        # Case 2: select e as an isolated edge
        I = H.edges_incident([u, v])
        H.delete_vertices([u, v])
        for sol, n in rec(H, low - 2):
            if n + 2 >= low:
                sol['edges'].append((u, v))
                yield sol, n + 2
        H.add_vertices([u, v])
        H.add_edges(I)

        # Case 3: select e as part of a cycle
        for P in H.all_paths(u, v):
            C = [(P[i], P[i + 1]) for i in range(len(P) - 1)]
            C.append((u, v))
            K = H.copy()
            K.delete_vertices(P)
            nP = len(P)
            for sol, n in rec(K, low - nP):
                if n + nP >= low:
                    sol['cycles'].append(C)
                    yield sol, n + nP

        # Finally restore edge e
        H.add_edge(u, v)

    for sol, n in rec(G.copy(), nmin):
        if n >= nmin:
            yield sol

sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])
sage: for s in elementary_subgraphs(G, G.order()):
....:     print(s)
{'cycles': [], 'edges': [(8, 9), (7, 10), (5, 6), (3, 4), (1, 2), (11, 12)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(7, 9), (6, 8)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(8, 9), (6, 7)]}
{'cycles': [[(6, 8), (8, 9), (9, 7), (6, 7)], [(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': []}

sage: len(list(elementary_subgraphs(G, G.order()-1)))
32

sage: len(list(elementary_subgraphs(G, 0)))
647

A perfect matching (if the graph has one) is a spanning elementary subgraph according your definition. You can get all the perfect matchings (only 1 in your graph) using

sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]

Now if you want all spanning elementary subgraphs, you have to design a specific algorithm.

EDIT:

A solution is to enumerate all elementary subgraphs and to prune subgraphs without enough vertices.

def elementary_subgraphs(G, nmin=0):
    r"""
    Iterator over the elementary subgraphs of `G`.

    A subgraph `H` of a graph `G` is *elementary* if each of its connected
    components is either an edge or a cycle.

    INPUT:

    - ``G`` -- a Graph

    - ``nmin`` -- integer (default: ``0``); lower bound on the number of
      vertices involved in the elementary subgraphs of any returned
      solution. When set to ``G.order()``, the subgraphs must be spanning.
    """
    G._scream_if_not_simple()

    def rec(H, low):
        if not H.size():
            yield {'cycles': [], 'edges': []}, 0
            return
        if H.order() < low:
            # no solution
            return

        # We select an edge e = (u, v) of H and remove it
        u, v = next(H.edge_iterator(labels=False))
        H.delete_edge((u, v))

        # Case 1: return solutions without e
        for sol, n in rec(H, low):
            if n >= low:
                yield sol, n

        # Case 2: select e as an isolated edge
        I = H.edges_incident([u, v])
        H.delete_vertices([u, v])
        for sol, n in rec(H, low - 2):
            if n + 2 >= low:
                sol['edges'].append((u, v))
                yield sol, n + 2
        H.add_vertices([u, v])
        H.add_edges(I)

        # Case 3: select e as part of a cycle
        for P in H.all_paths(u, v):
            C = [(P[i], P[i + 1]) for i in range(len(P) - 1)]
            C.append((u, v))
            K = H.copy()
            K.delete_vertices(P)
            nP = len(P)
            for sol, n in rec(K, low - nP):
                if n + nP >= low:
                    sol['cycles'].append(C)
                    yield sol, n + nP

        # Finally restore edge e
        H.add_edge(u, v)

    for sol, n in rec(G.copy(), nmin):
        if n >= nmin:
            yield sol

The idea behind the algorithm is, given any edge e=(u,v), to

1. either search for solutions without edge e. We return all elementary subgraphs of G-e.
2. or e is in the solution and is a connected component. We remove the end vertices of e from the graph, search for all elementary subgraphs of the remaining graph, and add e to each found subgraph before returning it
3. or e is part of a cycle. We enumerate all paths between the end vertices of e. Each path combined with e forms a cycle. For each of these cycles, we search for all elementary subgraphs of the graph G without the vertices of the cycle.

We get the spanning elementary subgraphs as follows:

sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])
sage: for s in elementary_subgraphs(G, G.order()):
....:     print(s)
{'cycles': [], 'edges': [(8, 9), (7, 10), (5, 6), (3, 4), (1, 2), (11, 12)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(7, 9), (6, 8)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(8, 9), (6, 7)]}
{'cycles': [[(6, 8), (8, 9), (9, 7), (6, 7)], [(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': []}

We can also get the elementary subgraphs with at least G.order() - 1 vertices:

sage: len(list(elementary_subgraphs(G, G.order()-1)))
32

or all elementary subgraphs (including the empty graph):

sage: len(list(elementary_subgraphs(G, 0)))
647

sage: %timeit list(spanning_elementary_subgraphs(G))
16.2 s ± 3.41 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit list(elementary_subgraphs(G, G.order()))
14.3 ms ± 459 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)