Graph orientations output convention inconsistent

[Gordon]

This is not exactly a bug, but definitely a "gotcha" which will catch many people unawares but could easily be fixed.

It is related to the two functions "orientations" and "acyclic_orientations" which are meant to return iterators to all orientations and to the acyclic orientations respectively.

The confusion arises from the fact that these two functions return their results in different ways, one of which is intuitive, but the other very counterintuitive. 

One way of viewing an "orientation" is as an undirected graph with some indication on each edge (u,v) as to whether it is directed from u to v, or v to u.

Another way of viewing an "orientation" is that it is a directed graph, where each edge has been replaced either with the arc u->v or v->u.

The command "g.orientations()" returns an iterator which produces a sequence of directed graphs, each being a different orientation of the original graph. This is natural and unambiguous.

The command "g.acyclic_orientations()" also returns an iterator that produces a sequence of directed graphs, but it just produces the SAME directed graph multiple times. The information about the orientation is hidden in labels on the edges, so that (u,v,0) means an arc from u to v and (u,v,1) means an arc from v to u. 

So "acyclic_orientations" is mixing up the two representations  - it is returning digraphs, but also labelling the edges.  

My suggestion is that the output from "acyclic_orientations" should be changed so that it returns digraphs with unlabelled edges. 

In this fashion, the orientation information is contained directly in the digraph and the output is then consistent with "orientations()".

Thanks

Gordon

[Emmanuel Charpentier]

Illustration in this ask.sagemath.org question.

HTH,

​

[Dima Pasechnik]

Hi Gordon,

Indeed, it's inconsistent design. However,

From efficiency point of view, returning a sequence of graphs is much
slower than returning edge labels only.
I.e., mathematically, for a graph (V,E) I'd define orientation
(acyclic or not) as a function E -> VxV
and return an iterator giving all such functions.
The default should be this most efficient representation - which is
trivial to convert to a sequence of digraphs, if needed.

acyclic_orientation() does this sort of optimisation, not creating new
digraphs. Might lead to "interesting" side effects,
as it returns a digraph, just one for all the orientations, as far as I can see.


I've opened https://github.com/sagemath/sage/issues/38758 to deal with this.

Dima




>Thanks
>
>Gordon
>
>
>
>