1 | initial version |
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.