# 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.

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

# 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

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


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

# 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

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


This method is faster for this graph than the (nice) solution using linear programming:

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)