#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 ncohen):
Helloooooo Birk !!!
> 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. :-)
Oh ! Nice. And you are right of course. We really need low-level backends
for such things.. Could you change your patch a little bit though ? You
define the _has_edge function inside of the other functions, and as you
are in your own module I guess nobody would mind if you define a has_edge
method. The other thing is that you could define it as a C method,
something like that :
{{{
cdef inline int has_edge(bitset_t bs, int u, int v, int n):
return bitset_in(bs, u*n+v)
}}}
This way you avoid a function call... But that's not very costly anyway
`:-)`
> 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...
Hmmmm... I believed that that the following code would also destroy the
content of ``a``, though it still exists.
{{{
sage: a = set([1,2,3])
sage: a
set([1, 2, 3])
sage: d = {8:a}
sage: d
{8: set([1, 2, 3])}
sage: del d[8]
sage: a
set([1, 2, 3])
}}}
I believed that a call to "del" was a direct order to destroy the given
object, but it only removes the value from the dictionary. Looks good :
sorry for this (partial!) modification, please update the code however you
like `:-)`
> - 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?
`O_o`
Well, there is a small difference between the two lines, but I only
changed it to make the code more... readable. You think "for u in g" is
worse that "for u in g.vertices()" ?
We can write `\forall u \in G` in papers, and I usually write "for u in g"
because the line is shorter, and (to me) easier to read.
The difference between the two lines is that g.vertices() returns the
*sorted* list of vertices, while "for i in g" returns the list of vertices
in any order -- hence there is no call to *sort* and is *theoretically*
faster, though I do not think that there is any significant difference in
practice. It's up to you too if you don't like it !
> - Why is the reference deleted in is_longanti_hole_free (but not in
is_long_hole_free)?
Oh. I believe Sage complained when I built the documentation (``sage
-docbuild reference html``) because of the double entry (with the same
reference code). The link works when you click on them in the HTML
documentation though.
> - 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?
It expresses my right to make typos in patches, but I understand from your
comment that you believe I do not deserve that right `:-P`
Sorry about that, it is just a tyo `^^;`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13073#comment:14>
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.
