The acyclic orientations function behaves unexpectedly

asked 2024-10-02 11:17:20 +0100

Gordon
197 ●3 ●8 ●19

updated 2024-10-06 11:40:56 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

I need all of the acyclic orientations of an input graph.

There is a handy function

acyclic_orientations()

which is meant to return an iterator for the acyclic orientations which, when asked, will return a digraph representing the "next" acyclic orientation.

But I am not sure what it is actually doing because it seems to be producing the same acyclic orientation multiple times.

g = Graph([(0,1),(1,2),(2,3),(3,0),(0,2)])
for d in g.acyclic_orientations():
    print(d.edges(labels=false))

[(1, 0), (1, 2), (2, 0), (3, 0), (3, 2)]
[(1, 0), (1, 2), (2, 0), (3, 0), (3, 2)]
[(1, 0), (1, 2), (2, 0), (3, 0), (3, 2)]
...
...
[(1, 0), (1, 2), (2, 0), (3, 0), (3, 2)]

It produces 18 identical lines. There are actually 18 acyclic orientations of this graph, and so the number is at least correct, but I would like to it actually return the correct orientations.

For very small graphs, I can avoid this problem by using the function

orientations()

which produces every orientation and then extract the acyclic ones.

g = Graph([(0,1),(1,2),(2,3),(3,0),(0,2)])
for d in g.orientations():
    if d.all_simple_cycles() == []:
        print(d.edges(labels=false))

[(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)]
[(0, 1), (0, 2), (0, 3), (1, 2), (3, 2)]
[(0, 1), (0, 2), (0, 3), (2, 1), (2, 3)]
...
...
[(1, 0), (2, 0), (2, 1), (3, 0), (3, 2)]

edit retag flag offensive close merge delete

Comments

Just a side note: instead of d.all_simple_cycles() == [], it's more efficient to check d.is_directed_acyclic().

Max Alekseyev ( 2024-10-02 12:49:08 +0100 )edit

Thanks Max, I quickly looked to see if there was an is_acyclic() function but mostly wanted something just to illustrate the question.

Gordon ( 2024-10-02 14:47:17 +0100 )edit

add a comment

answered 2024-10-02 13:19:33 +0100

Emmanuel Charpentier
7764 ●6 ●50 ●153

updated 2024-10-02 13:56:31 +0100

Well... the problem seems to arise from the label=False option. Without it :

sage: [u.edges() for u in g.acyclic_orientations()]
[[(1, 0, 0), (1, 2, 0), (2, 0, 1), (3, 0, 0), (3, 2, 0)],
 [(1, 0, 0), (1, 2, 0), (2, 0, 1), (3, 0, 1), (3, 2, 0)],
 [(1, 0, 1), (1, 2, 0), (2, 0, 1), (3, 0, 0), (3, 2, 0)],
 [(1, 0, 0), (1, 2, 0), (2, 0, 1), (3, 0, 1), (3, 2, 1)],
 [(1, 0, 1), (1, 2, 1), (2, 0, 1), (3, 0, 0), (3, 2, 0)],
 [(1, 0, 1), (1, 2, 0), (2, 0, 1), (3, 0, 1), (3, 2, 0)],
 [(1, 0, 1), (1, 2, 0), (2, 0, 1), (3, 0, 1), (3, 2, 1)],
 [(1, 0, 1), (1, 2, 1), (2, 0, 1), (3, 0, 1), (3, 2, 0)],
 [(1, 0, 1), (1, 2, 1), (2, 0, 1), (3, 0, 1), (3, 2, 1)],
 [(1, 0, 0), (1, 2, 0), (2, 0, 0), (3, 0, 0), (3, 2, 0)],
 [(1, 0, 0), (1, 2, 0), (2, 0, 0), (3, 0, 0), (3, 2, 1)],
 [(1, 0, 0), (1, 2, 1), (2, 0, 0), (3, 0, 0), (3, 2, 0)],
 [(1, 0, 0), (1, 2, 1), (2, 0, 0), (3, 0, 0), (3, 2, 1)],
 [(1, 0, 0), (1, 2, 0), (2, 0, 0), (3, 0, 1), (3, 2, 1)],
 [(1, 0, 1), (1, 2, 1), (2, 0, 0), (3, 0, 0), (3, 2, 0)],
 [(1, 0, 0), (1, 2, 1), (2, 0, 0), (3, 0, 1), (3, 2, 1)],
 [(1, 0, 1), (1, 2, 1), (2, 0, 0), (3, 0, 0), (3, 2, 1)],
 [(1, 0, 1), (1, 2, 1), (2, 0, 0), (3, 0, 1), (3, 2, 1)]]

The label carries the orientation of an edge. Quick check of the unicity :

sage: len([u.edges() for u in g.acyclic_orientations()])
18
sage: Set(([u.edges() for u in g.acyclic_orientations()])).cardinality()
18

The problem is therefore that print( an edge , label=False) merely suppresses the label. In this special case, it might be pertinent to reverse the order of the edges if the label is 1 ; however, the pertinence of this change in the more general cases of graph printing is to be checked...

EDIT : The problem may be more extensive that it seems :

sage: graphics_array([plot(u) for u in g.acyclic_orientations()], nrows=6, ncols
....: =3)
Launched png viewer for Graphics Array of size 6 x 3

image description

which is eighteen copies of the same directed graph.

Workaround :

sage: def fix(e):return tuple([e[1], e[0]]) if e[2] else tuple([e[0], e[1]])
sage: graphics_array([plot(DiGraph([fix(u) for u in v.edges()])) for v in g.acyc
....: lic_orientations()], nrows=6, ncols=3)
Launched png viewer for Graphics Array of size 6 x 3

image description

which seems correct.

This is probably worth of a Github ticket (by someone more versed in graph theory and its Sage implementation(s) than I am...).

HTH,

edit flag offensive delete link

Comments

Do acyclic_orientations() return labeled but still undirected graphs? This is weird. I would assume those should be unlabeled directed graphs.

Max Alekseyev ( 2024-10-02 13:34:54 +0100 )edit

So I deduce the following: there are two incompatible ways of representing an oriented graph and the function is trying to use both. The first way is to assign an orientation to each edge, thereby "labelling" the edges of an otherwise undirected graph, for example using $(u,v,0)$ to represent $u \to v$ and $(u,v,1)$ to represent $v \to u$. The second way is to replace each edge of the undirected graph with a single directed arc, and then return one digraph for each orientation. The problem here is that the function does return a digraph, but it also labels the edges of the digraph. It just returns the same digraph for every orientation and only alters the edge labels. So it pretends to use the "digraph representation" but actually uses the "labelled edges" option. Confusion follows.

Gordon ( 2024-10-02 15:08:26 +0100 )edit

@Gordon, could you report your analysis to sage-support and/or file an issue on Github ?

Emmanuel Charpentier ( 2024-10-02 17:12:38 +0100 )edit

You are right, the output of the method is incorrect. The step using the edge label to orient the arcs is missing. I pushed a possible fix in https://github.com/sagemath/sage/pull...

David Coudert ( 2024-10-03 11:03:50 +0100 )edit

Wow, that is very fast. I had not even finished typing the description of the problem into sage-support and it has already been fixed.

Gordon ( 2024-10-03 13:08:38 +0100 )edit

add a comment

The acyclic orientations function behaves unexpectedly

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

The acyclic orientations function behaves unexpectedly edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

The acyclic orientations function behaves unexpectedly