Fixes a bug in is_chordal -- two algorithms

[nathanncohen]

This ticket follows #11735, which fixes the bug reported by Jan on sage-devel [1]. It makes his alternative algorithm available in the function, so that we now have two different versions available, and still double-check the values it returns :-)

Requires : #11735

Apply : attachment: trac_11961.patch

[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion

Component: graph theory

Author: Nathann Cohen, Jan Elffers

Reviewer: David Coudert

Merged: sage-4.8.alpha5

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

[jdemeyer]

Milestone sage-4.7.3 deleted

[nathanncohen]

Attachment: trac_11961.patch.gz

[dcoudert]

comment:3

I had no problem when installing the patch. The doc is also correctly generated.

All tests I have performed are consistent: both algorithms return the same boolean value. The certificate are not the same when several certificates are possible.

Algorithm B is a bit slower than algorithm A.

As I already said for patch #11735, significant running time improvements are possible for these linear time algorithms, but at least we have some algorithms ;)

Thank you Nathann.

[dcoudert]

Reviewer: David Coudert

[nathanncohen]

comment:4

Thank you for the review ! :-)

Algorithm B is a bit slower than algorithm A.

Yep. That's why it is good to have both :-)

As I already said for patch #11735, significant running time improvements are possible for these linear time algorithms, but at least we have some algorithms ;)

These codes are really standard. It would really be a shame not to implement them properly in C/C++ at some point.

Nathann

[jdemeyer]

Merged: sage-4.8.alpha5