# Iterate over acyclic subdigraphs I have a graph D, and would like to iterate over its (maximal) acyclic subdigraphs (not necessarily induced).

My current best bet is to iterate over all permutations of the vertex set of D and, for each one, create an acyclic digraph A by going through each edge of D in turn and adding to A only those edges ij where i is less than j in the current permutation.

But this seems awfully inefficient.

More precisely:

D = DiGraph()
n = D.num_verts()

for p in Permutations(n):
A = DiGraph()
for e in D.edges():
if p[e] < p[e]:

# Here A is a maximal acyclic subdigraph of D
do_stuff(A)


Any ideas would be greatly appreciated.

edit retag close merge delete

Sort by » oldest newest most voted

This is certainly not an easy question and I have no better algorithm in mind.

I recommend to use Permutations(D.vertices()) instead. This is safer for instance if you remove vertex 0.

Furthermore, with your code you may generate multiple times the same acyclic orientation.

sage: D = DiGraph(graphs.PathGraph(3))
sage: print D.edges(labels=0)
[(0, 1), (1, 0), (1, 2), (2, 1)]
sage: for p in Permutations(D.vertices()):
....:     A = DiGraph([(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]])
....:     print A.edges(labels=0)
....:
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]
[(0, 1), (1, 2)]


One solution is to keep track of previous sets of edges, but this is certainly not scalable. I'm using type Set since it is hashable.

sage: D = DiGraph(graphs.PathGraph(3))
sage: orientations = set()
sage: for p in Permutations(D.vertices()):
....:     E = [(p[u],p[v]) for u,v in D.edges(labels=0) if p[u]<p[v]]
....:     SE = Set(E)
....:     if SE in orientations:
....:         continue
....:     A = DiGraph(E)
....:     print A.edges(labels=0)
....:
[(0, 1), (1, 2)]
[(0, 2), (1, 2)]
[(0, 1), (0, 2)]


For the example you gave, your code generates 5040 graphs while my code generates only 4055 graphs.

more