#13073: recognition of weakly chordal graphs
--------------------------------------------------+-------------------------
Reporter: eisermbi | Owner: jason,
ncohen, rlm
Type: enhancement | Status:
needs_review
Priority: major | Milestone: sage-5.1
Component: graph theory | Resolution:
Keywords: weakly chordal, hole, antihole | Work issues:
Report Upstream: N/A | Reviewers: Nathann
Cohen
Authors: Birk Eisermann | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Changes (by {'newvalue': u'Birk Eisermann', 'oldvalue': ''}):
* reviewer: => Nathann Cohen
* author: => Birk Eisermann
Old description:
> Adding functionality to recognize weakly chordal graphs;
> as part of that, procedures for finding holes (= induced cycle of length
> >=5) and antiholes (complements of holes) in graphs are included.
New description:
Adding functionality to recognize weakly chordal graphs;
as part of that, procedures for finding holes (= induced cycle of length
>=5) and antiholes (complements of holes) in graphs are included.
Apply:
* [attachment:trac_13073_weaklychordal-module.patch]
* [attachment:trac_13073_weaklychordal-review.patch]
--
Comment:
Hellooooooooo Birk !!!
Here is the promised reviewer's patch ! I originally intended to do a bit
more, but some of the optimizations I had in mind were actually worsening
the situation on random graphs, and I got stuck with *another*
optimization because some things are possible in Python files that are not
in Cython ones... *sigh* `:-)`
Anyway I changed the code a little since the previous version :
* Added the new module to the documentation
* Added a copyright header for the new file (and for an old file which
had none)
* Added some documentation at the module's head
* Edited the doc where it mentionned the "P_4-structure" of the graph.
The algorithm actually is not very complicated, so it's better to give its
main idea in this short description `:-)`
* Added a link toward the pdf, and edited some trivial things too
* I really could not make sense of the way you built the induced cycle
back, at the end of the algorithm. It did not appear to be very efficient
either (you enumerated many edges, then checked that you had to consider
them)... I wrote a new version of it, which also works for antiholes
(though I have to call a .complement() on a (hopefully small) subgraph),
and I hope that it is clearer this way. There are some explanations around
in the code.
Well, that's more or less all I did. Please tell me what you think of it !
The usual procedure in these situations is that I review your changes
while you review mine, and we can set the ticket to positive_review when
we are both confident that the other made no catastrophic blunder `:-)`
Thank you again !!
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13073#comment:5>
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.
