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 shortest paths.
On topic: I think this does not make the procedure correct.
Also, it seems function lex_BFS does something else than what is
specified in the comments: the predecessor tree returns the _last_
discoverer for each vertex, instead of the first.
But in function is_chordal the code reads:
if t_peo.out_degree(v)>0 and g.neighbors(v) not in
neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]:
it seems here we expect that the discoverer recorded is indeed the
last.
If we change the lex_BFS function to return the first discoverers,
graph({1:[2,3,4,5],2:[3,5],4:[3,5]}) is a counterexample.
I don't know whether the current impl. is correct, but i.m.o. it is
quite different from what is proposed in the paper so it might be
better to change it to something which has been proven correct.
I tried to implement the method from the paper myself, the resulting
diff is below.
Regards,
Jan
==========
9498c9498,9500
<
---
>
> pos_in_peo = dict(zip(peo, range(self.order())))
>
9500c9502
< for v in peo:
---
> for v in reversed(peo):
9502,9504c9504
< if t_peo.out_degree(v)>0 and g.neighbors(v) not in
neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]:
<
< x = t_peo.neighbor_out_iterator(v).next()
---
> if t_peo.out_degree(v)>0 and [v1 for v1 in g.neighbors(v) if
> pos_in_peo[v1] > pos_in_peo[v]] not in
> neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]:
9508d9507
<
9513,9519c9512,9519
<
< S = neighbors_subsets[x]
<
< for y in g.neighbors(v):
< if [y] not in S:
< break
<
---
> max_tup = (-1, 0)
> for xi in g.neighbors(v):
> for yi in g.vertices():
> if not [yi] in neighbors_subsets[xi] and
> pos_in_peo[xi] > pos_in_peo[v] and pos_in_peo[yi] > pos_in_peo[v]:
> new_tup = (pos_in_peo[xi], pos_in_peo[yi])
> if max_tup < new_tup:
> max_tup = new_tup
> x, y = xi, yi
9538,9539d9537
< g.delete_vertex(v)
<
==========
On Aug 24, 11:02 am, Nathann Cohen <nathann.co...@gmail.com> wrote:
> 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 waiting for a review. I also added a small test in the
> code, so that the certificate is checked for correctness before being
> returned. It takes absolutely no time to check, so... :-)
>
> Oh, and thank you very much for this bug report ! Could I know what you are
> doing with chordal graphs ?
>
> Nathann
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
