#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:
--------------------------------------------------+-------------------------
Comment (by eisermbi):
Hello Nathann!
I agree with most of the patch set. Especially the removal of the variable
ActivePath is nice and the hole/antihole extraction is easier to
understand (and does not need to be highly effficient). The techniques in
the optim patch are kind of what I could imagine. Since I am new to sage
and python it could not do that. So you did good work and the speed is
much better!
On the other side, I want to point out that the algorithm became less
readable to an outsider. Now it uses some kind of 'low level' programming.
If one looks at `bitset_in(dense_graph,u*n+v)` it takes time to realize
that it stands for `g.has_edge(u,v)`. I think this should be somehow
hidden in the graph class instead of showing up in a 'high level'
algorithm... (Of course, my statement about hidden is very blurry. I will
write something about that and the graphs class hierarchy in general on
sage-devel soon.) For the moment, I added a small modification
(trac_13073-optim-review.patch) with which I could live. :-)
Finally some what- and why-questions:
- What is the difference between '`del InPath[c]`' and
'`InPath.pop(c)`' ? You changed the former to the latter but only in some
places...
- I find the change
`for u in g.vertices()`
to
`for u in g`
makes the code harder to read for an outsider. Why making it more
cryptic?
- Why is the reference deleted in is_longanti_hole_free (but not in
is_long_hole_free)?
- There is an upwards shift arrow appended at the end of the line
# C[i]...C[j] is necessarily an induced cycle.⇧
in process() of is_long_hole_free(). Similar for
is_long_antihole_free(). What is the use of that symbol?
Thank you!
Birk
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13073#comment:13>
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.
