Hi Gordon, On 3 October 2024 12:06:03 BST, Gordon <gordonfro...@gmail.com> wrote: >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()". > 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 > > > > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/CAAWYfq0RSvD0azxWvZ6oP1dx9ZjJsjCrTFg7jR65gDCdhWWgYA%40mail.gmail.com.
