#13073: recognition of weakly chordal graphs
--------------------------------------------------+-------------------------
Reporter: eisermbi | Owner: jason,
ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.1
Component: graph theory | Resolution:
Keywords: weakly chordal, hole, antihole | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Comment (by ncohen):
Helloooooo Birk !!!
I do not know whether you want this patch to be reviewed already but I
could not help giving it a look anyway, and I should make some remarks
before I forget them `:-)`
* The first one is *thank you very much* for adding this kind of
features, I added some recognition algorithms to Sage recently and I had
no idea that there was a nice way to recognize these graphs !
* Your patch modifies the file generic_graph.py, which means that the
patch would add methods to BOTH Graph and DiGraph objects. As I guess that
the algorithm does not answer anything sensible when given a DiGraph as an
input, I guess the best would be to add the methods to graph.py instead.
BUT
* Your patch adds quite long functions. Hence perhaps the best is
to write them inside of another file, while still exposing your functions
in the Graph class.
* I do not understand why you have both a isHoleFree and
isAntiholeFree method. Aren't they doing the same job ? You only use the
first one yourself in is_weakly_chordal, so why write both in the patch ?
At the very least the second one should call the first one on the graph's
complement ?.. Did I say something wrong ?
* If this isAntiHoleFree function can be removed, perhaps the code
will be short enough so that it will become possible to add it direcly
inside of graph.py without writing it in a diffrent file first...
* We already have a is_even_hole_free method, as well as an
is_odd_hole_free method. You can see by looking at their code that they
are quite straightforward functions -- they immediately call the
subgraph_search method. While it is algorithmically a very bad way to
solve the problem, the search for subgraph is implemented in C and can be
expected to be quite fast. Is such a method totally left behind by your
specific code ? I expect that it is but I just wondered..
* Oh, and also... Could you add some comments to our code ? As it is,
it is pretty hard for somebody who is not you to understand what it does
`:-)`
Thank you again !!!
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13073#comment:1>
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.
