Iterate over acyclic subdigraphs

asked 2017-05-17 17:40:16 +0100

tassio
5 ●1 ●2

updated 2017-07-31 22:07:59 +0100

FrédéricC

5251 ●3 ●44 ●116

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()
D.add_edges([[0,1],[0,2],[1,2],[1,3],[2,3],[3,4],[4,5],[4,6],[5,6],[5,0],[6,0]])
n = D.num_verts()

for p in Permutations(n):
    A = DiGraph()
    for e in D.edges():
        if p[e[0]] < p[e[1]]:
            A.add_edge(p[e[0]] -1,p[e[1]] -1)

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

Any ideas would be greatly appreciated.

answered 2017-05-19 14:40:07 +0100

David Coudert
766 ●12 ●20 http://www-sop.inria.f...

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
....:     orientations.add(SE)
....:     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.

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Iterate over acyclic subdigraphs

1 Answer

Your Answer

Question Tools

Stats

Related questions

Iterate over acyclic subdigraphs edit

1 Answer

Your Answer

Question Tools

Stats

Related questions

Iterate over acyclic subdigraphs