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.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.