#11735: Bug in is_chordal
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: tbd
Type: defect | Status: positive_review
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: David Coudert | Author: Nathann Cohen
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by dcoudert):
* status: needs_review => positive_review
Comment:
You're right Nathann. I should not try a patch after a long day of work...
I did new tests this morning and the algorithm works fine.
I have no compilation error.
The doc is OK and includes the test of the patch (I don't if it's usual to
let the patch number in the doc, but it has no consequences).
So I'm positive with this patch.
Thank you Nathann.
I hope someone will later be able to improve the running time of the
algorithm. Current implementation is quite slow for an O(m) algorithm
compared to other (nicely impleted) algorithms with higher complexity
{{{
sage: G = graphs.RandomInterval(1000)
sage: G.num_edges()
319501
sage: %time G.is_chordal()
CPU times: user 24.83 s, sys: 0.05 s, total: 24.87 s
Wall time: 24.95 s
True
sage: %time G.diameter()
CPU times: user 1.59 s, sys: 0.00 s, total: 1.59 s
Wall time: 1.59 s
2
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11735#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
