# Revision history [back]

### acyclic subdigraph

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[0]] < p[e[1]]:

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


Any ideas would be greatly appreciated.

### acyclic subdigraphIterate 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[0]] < p[e[1]]:
-1)

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


Any ideas would be greatly appreciated.

 3 retagged FrédéricC 3790 ●3 ●36 ●75

### 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[0]] < p[e[1]]:

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


Any ideas would be greatly appreciated.

 4 retagged FrédéricC 3790 ●3 ●36 ●75

### 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()