A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in its role as a source vertex to a vertex $v$ of $D$ in its role as a target vertex.
Question:
what can be exploited to speed up the enumeration of all directed cycle-covers, in the above sense, of a given digraph $D$?
So far it appears to me that a recursive depth-first search is a good basic algorithm; here is an exemplary implementation in the python language:
def report_covers(G):
n = len(G)
covers = []
used = [False]*n
cover = [0]*len(G)
used = [False]*n
cover = [0]*n
def listing_covers(k):
if k < 0:
covers.append(cover.copy())
return
# iterate over the outedges of vertex k
for v in G[k]:
if not used[v]:
cover[k] = v
used[v] = True
listing_covers(k-1)
used[v] = False
listing_covers(n-1)
return covers
The optimization potentials I see for that algorithm are:
- choosing between iterating over the in-edges and iterating over the out-edges if the product of in-degrees is smaller than the product of out-degrees
- chosing between reordering the vertices according to increasing degree vs according to descending degree in favor of ascending degree
- if the outdegree of $u$ is one and $(u,v)\in D$, then all incoming edges of $v$, except $(u,v)$ can be removed from $D$ prior to the enumeration.
- what else?
