Revision history [back]

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.