Hi Nathann,
Thanks for fixing it! :) I forgot the issue so my reply is late.
I looked at the patch you produced.
I think it's fine except for that I would prefer the algorithm
keyword-argument to be placed at the end of the argument list for
backward compatibility.
Best regards,
Jan
On Oct 29,
Hello !!
Thanks for fixing it! :) I forgot the issue so my reply is late.
Well, it took me a month to write it ;-)
I looked at the patch you produced.
I think it's fine except for that I would prefer the algorithm
keyword-argument to be placed at the end of the argument list for
backward
Hellooo again !!!
I finally wrote this patch, available there :
http://trac.sagemath.org/sage_trac/ticket/11961
Though the two algorithms are very similar, I thought it better to
split it into two different parts, so that one can understand better
how each of them works without having
Hi Nathann,
I extracted the modified is_chordal function, it is shown below.
Regards, Jan
==
def is_chordal(self, certificate = False):
r
Tests whether the given graph is chordal.
A Graph `G` is said to be chordal if it contains no induced hole
(a
cycle of length at
Hello Jan !
I am trying to write the patch corresponding to your modifications,
but the file has changed much since and I have some trouble dealing
with your diff file... Could you copy/paste the totality of the code ?
:-)
Thaanks !
Nathann
--
To post to this group, send email to
Hello Jan !
Quick update :
I just reviewed #11738 which touched some code related to chordality.
http://trac.sagemath.org/sage_trac/ticket/11738
I also updated my patch at #11735 that implements my (still unproved)
version of the algorithm, because it is formally better than the current
one, and
Hi Nathann,
For a time I thought I would be able to patch my proof, but in the end I
don't get how this recognition algorithm works... Which is a pity because I
am sure I had found a clear explanation in a paper when I implemented all
that stuff. What I need right now is some sleep though.
Hi Nathann,
after this line (line 9520 in
http://trac.sagemath.org/sage_trac/attachment/ticket/11735/trac_11735.patch):
g.delete_vertices([vv for vv in g.neighbors(v) if vv != y and vv !=
x])
How can one be sure that x and y are still connected? (otherwise no
path x -- y exists)
I don't know
Hellooo Jan !
It is 20:20, it is almost dark outside and I am getting home by bike.
Worst of all, I am being assaulted by hungry mosquitoes. I re-read it
the following enough times to be sure that if I miswrote v instead
of x somewhere, reading it again wouldn't have changed anything.
When v
Hi Nathann,
First, thank you for taking time to give a very detailed reply.
I'm sorry but I'm not yet done bothering you :-]
I think this is wrong:
When v is considered for removal, it is a leaf of the lex-BFS tree.
Its father (and first discoverer) is named x, and we suppose that
there is a
Consider: g = graph({1:[2,3,4,5],2:[3,5],4:[3,5]}).
Hahahahhahaaha ! Dead right :-)
And the code works anyway because the tree it returns actually is *NOT* a
BFS tree :-)
sage: g.lex_BFS(tree = True)[1].edges()
[(2, 1, None), (3, 2, None), (4, 5, None), (5, 2, None)]
Two (obvious) black
Hello !
I'm finally back to the civilisation if you want us to deal with this patch :-)
Nathann
On 29 August 2011 15:46, Nathann Cohen nathann.co...@gmail.com wrote:
Hello Jan !!!
I am sorry for my vry slow answers, I am on vacation right now, with
very very bad WiFi connections when I
Hello Jan !!!
I am sorry for my vry slow answers, I am on vacation right now, with
very very bad WiFi connections when I get some. If you think you would sleep
better with copying the implementation given in the paper, then the best is
probably to write a patch for this. I like mine better,
Your code, after the patch, seems to work (I tested it on all graphs
with 8 vertices, and it doesn't fail), but I think it differs from
what the paper does.
The first difference is that, after LexBFS, the current code processes
the vertices in the PEO order, and chooses the first violating vertex.
Hello Jan !
I just wrote a patch for that. What they do in this paper is exactly the
same, except that of course they compute the shortest path in the graph
without the neighbors of v, short of the two we are interested in :-)
http://trac.sagemath.org/sage_trac/ticket/11735
The patch is now
Hi Nathann,
Thanks for the reply. As for my interest in the subject, I am an
undergrad. CS student at TU Delft and have been following a research
track there, focusing on planning/scheduling problems. We use chordal
graphs to maintain certain information related to constraints,
especially about
16 matches
Mail list logo
