Opened 7 years ago
Closed 7 years ago
#11735 closed defect (fixed)
Bug in is_chordal
Reported by: | ncohen | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-4.8 |
Component: | graph theory | Keywords: | |
Cc: | lsampaio, ddestrada, dcoudert | Merged in: | sage-4.8.alpha4 |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
As reported by Jan on sage-devel [1], the current implementation of is_chordal is incorrect. Given a vertex v adjacent to x and y (x and y being non-adjacent), a shortest path between x and y in G-v does not necessarily avoid the neighbors of v. Clearly. Well, with this patch the shortest path is computed in the graph G with v and all its neighbors removed with the exception of x and y, so that it can not happen again.
Besides, as it is almost free to check that the certificate is indeed a hole, this patch adds a test just in case :-)
Nathann
Requires :
Apply:
[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion
Attachments (1)
Change History (12)
comment:1 Changed 7 years ago by
- Component changed from PLEASE CHANGE to graph theory
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Cc ddestrada added
- Description modified (diff)
Changed 7 years ago by
comment:3 Changed 7 years ago by
- Cc dcoudert added
(I was told that from this ticket's content, one could not really know whether the ticket really needed a review. The answer is : yes it does, the present ticket has to be merged into Sage to fix the bug, and is followd by #11961. I thought of updating the discussion, but forgot about the ticket itself ^^;
)
Nathann
comment:4 Changed 7 years ago by
Are we lucky enough that these patches fix #10899 en passant?
comment:5 Changed 7 years ago by
No it should not :-)
Nathann
comment:6 Changed 7 years ago by
- Reviewers set to David Coudert
Either I don't understand the definition of chordal graphs, or the current implementation is still incorrect. I did the test with sage-4.8alpha3, so I assume I don't need to add patch 11738.
sage: N = 50 sage: NN = 3*N sage: L = [(3*i, (3*i+1) % NN) for i in xrange(N)] + [(3*i, (3*i+2)%NN) for i in xrange(N)] + [((3*i+1)%NN, (3*i+2)%NN) for i in xrange(N)] sage: G=Graph() sage: G.add_edges(L) sage: G.is_chordal() True sage: G.add_edge(0,15) sage: G.is_chordal() True sage: G.add_edge(0,25) sage: G.is_chordal() True
So, what's wrong ?
David.
comment:7 Changed 7 years ago by
OK, the previous example is not correct (long day). But that one should be correct. I want to create a cycle of triangles. This should be chordal...
sage: N = 50 sage: NN = 2*N sage: L = [(2*i, (2*i+1) % NN) for i in xrange(N)] + [(2*i, (2*i+2)%NN) for i in xrange(N)] + [((2*i+1)%NN, (2*i+2)%NN) for i in xrange(N)] sage: G = Graph() sage: G.add_edges(L) sage: G.is_chordal() False
Nathann, am I right this time ? D.
comment:8 Changed 7 years ago by
Well, this graph clearly contains a long hole (induced cycle). Sage can find it too, with the "certificate" flag :
sage: G.is_chordal(certificate = True) (False, Subgraph of (): Graph on 50 vertices) sage: G.is_chordal(certificate = True)[1].show()
I mean, a graph is chordal if it contains an induced long cycle, and if you build a cycle of triangles it will of course contain a large induced cycle : the triangles offer no protection against that (just take two vertices that are very far away from each other, and compute a shortest path between them. As any shortest path, this path is induced, and the same way you can obtain an induced cycle).
Nathann
comment:9 follow-up: ↓ 10 Changed 7 years ago by
- Status changed from needs_review to positive_review
You're right Nathann. I should not try a patch after a long day of work...
I did new tests this morning and the algorithm works fine. I have no compilation error. The doc is OK and includes the test of the patch (I don't if it's usual to let the patch number in the doc, but it has no consequences).
So I'm positive with this patch.
Thank you Nathann.
I hope someone will later be able to improve the running time of the algorithm. Current implementation is quite slow for an O(m) algorithm compared to other (nicely impleted) algorithms with higher complexity
sage: G = graphs.RandomInterval(1000) sage: G.num_edges() 319501 sage: %time G.is_chordal() CPU times: user 24.83 s, sys: 0.05 s, total: 24.87 s Wall time: 24.95 s True sage: %time G.diameter() CPU times: user 1.59 s, sys: 0.00 s, total: 1.59 s Wall time: 1.59 s 2
comment:10 in reply to: ↑ 9 Changed 7 years ago by
I hope someone will later be able to improve the running time of the algorithm. Current implementation is quite slow for an O(m) algorithm compared to other (nicely impleted) algorithms with higher complexity
Yep :-/
Thanks for the review, though ! ;-)
Nathann
comment:11 Changed 7 years ago by
- Merged in set to sage-4.8.alpha4
- Resolution set to fixed
- Status changed from positive_review to closed
As this patch is already written (and readily updated to be applied on top of #11738), I think it best to merge it into Sage as soon as possible. It (apparently) fixes the bug reported by Jan, but most importantly ensures that the answer returned is indeed *valid*, so that no erroneous answer could be returned as previously.
Of course, this version of the implementation will have to be patched as soon as possible using Jan's code, in order to match a proven algorithm (or until I can come up with a proof that the current implementation is correct, or find a paper that does if I actually found it somewhere).
I'll do that *asap*, but I still think it better to merge this patch in the meantime, if only to be sure no bad answer is ever returned (God I hate that).
Nathann