is_directed_acyclic(certificate=True) doesn't always give an ordering back

[koffie]

Currently we have:

sage: m=Matrix(3,[0, 1, 1, 0, 0, 0, 0, 1, 0])
sage: g=DiGraph(m)
sage: g.is_directed_acyclic(certificate=True)
(True, [0, 1, 2, 1])

Component: combinatorics

Keywords: sd35

Work Issues: rebase to 11950

Author: Maarten Derickx, David Harvey

Issue created by migration from https://trac.sagemath.org/ticket/12180

[koffie]

Description changed:

--- 
+++ 
@@ -3,6 +3,6 @@

sage: m=Matrix(3,[0, 1, 1, 0, 0, 0, 0, 1, 0]) sage: g=DiGraph(m) -sage: g.is_directed_acyclic(certificate=True)[1] -[0, 1, 2, 1] +sage: g.is_directed_acyclic(certificate=True) +(True, [0, 1, 2, 1])

[koffie]

Changed keywords from none to sd35

[koffie]

comment:3

Attachment: 12180-fix_is_directed_acyclic.patch.gz

It is working now. There is also a more extensive randomized test because the old test didn't find the bug because the dags it generated where already ordered, and ordering something already ordened is significantly easier. Also the randomized testing did not test non dags. Ps. David harvey wrote most of the test code.

[koffie]

Author: Maarten Derickx, David Harvey

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

Helloooooooo !!!

I think I fixed it already :-)

It must beeeee....... #11950 !

Currently, in Sage 5.0-beta2 :

sage: m=Matrix(3,[0, 1, 1, 0, 0, 0, 0, 1, 0])
sage: g=DiGraph(m)
sage: g.is_directed_acyclic(certificate=True)
(True, [0, 2, 1])

Nathann

[koffie]

comment:6

Ok, I didn't find that one when creating this ticket, because it didn't mention the is_directed_acyclic anywhere. I'm putting this to needs work again because I think at least some parts of the patch here are superior with respect 11950. The two things being the addition of a more rigid randomized doctest and the removal of inserting stuff at the beginning of the list (see line 2806 after applying 11950, or line 2796 before applying it). This stupid inserting at the front of a list basically changes an algorithm whose run time is linear in the number of vertices to something wich is quadratic in the number of vertices!

[koffie]

Work Issues: rebase to 11950

[rwst]

comment:7

Better revert milestone then too.

[vbraun]

comment:9

Reviewer name, work issues?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:10

No idea... I just saw a ticket in wontfix, so I changed it to positive_review O_o

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:11

Arg, I am an idiot. It was changed FROM wontfix to 6.3 T_T

[dcoudert]

comment:14

Note that since #30479 we have digraphs.RandomDirectedAcyclicGraph. It might be helpful if you plan to add tests to is_directed_acyclic.

Also, I think this ticket should be in graph theory and not combinatorics.