#26428 closed enhancement (fixed)
improve is_weakly_chordal
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  66a1ed9 (Commits)  Commit:  66a1ed9a6521c26e3354b53ca5aaa9bb2f1e4c59 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket do:
 Remove recursion in methods
is_long_hole_free
andis_long_antihole_free
 Avoid modifying the input graph
 Cythonize parts of the code
Change History (8)
comment:1 Changed 2 years ago by
 Branch set to public/26428_weakly_chordal
 Commit set to f3fc0614c1311e4437d83766156ff077d89a2ac3
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 2 years ago by
 Commit changed from f3fc0614c1311e4437d83766156ff077d89a2ac3 to 1537dfd70f0aab5fbc2a8a34c99325e5aa2a1581
Branch pushed to git repo; I updated commit sha1. New commits:
1537dfd  trac #26428: remove useless imports

comment:3 Changed 2 years ago by
I think you should move process
out as a separate cdef inline
function and pass the data you need. It is likely equivalent to a Python function call, and since it is in the heart of the algorithm, it should be made to be called quickly (the inline hopefully will make it avoid the function call altogether).
I was going to say the same thing for the dist
, but since that is processing on the way out, it is only done once and should not contribute much time.
A few quick notes on style. For pointers, the *
is better next to the type, e.g., int*
as it makes it look less like multiplication. Also lambda X : foo
> lambda X: foo
.
Otherwise LGTM. Have you run some timings?
comment:4 Changed 2 years ago by
 Commit changed from 1537dfd70f0aab5fbc2a8a34c99325e5aa2a1581 to 66a1ed9a6521c26e3354b53ca5aaa9bb2f1e4c59
Branch pushed to git repo; I updated commit sha1. New commits:
66a1ed9  trac #26428: cdef methods process

comment:5 followup: ↓ 6 Changed 2 years ago by
I have cdef the methods process
and perform other suggestions.
I have not done clear timings. It is now faster on large cliques for instance, but very similar for graphs like the Petersen graph. My main motivation was not timing but 1) no sorting on original vertex labels, 2) no modification of the input graph (very bad), and 3) avoid recursive calls.
I also tried to use the has_edge
method of short_digraph
to avoid copying the graph in a n^2
length bitset (dense_graph
), but it was slightly slower. This is certainly something to consider if we have very large sparse graphs (i.e., when memory matters).
comment:6 in reply to: ↑ 5 Changed 2 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Replying to dcoudert:
I have cdef the methods
process
and perform other suggestions.
Thank you for doing that. I didn't realize process
needed so many of the local variables.
I have not done clear timings. It is now faster on large cliques for instance, but very similar for graphs like the Petersen graph. My main motivation was not timing but 1) no sorting on original vertex labels, 2) no modification of the input graph (very bad), and 3) avoid recursive calls.
Speed gains is a consequence of all of those things. ^{_}
I also tried to use the
has_edge
method ofshort_digraph
to avoid copying the graph in an^2
length bitset (dense_graph
), but it was slightly slower. This is certainly something to consider if we have very large sparse graphs (i.e., when memory matters).
It is good to care about these things as well. Sometimes we do have to sacrifice speed so that sparse graphs will work well too. We can also potentially try to do things differently for each those cases, but I think what you have done here is more than enough.
comment:7 Changed 2 years ago by
 Branch changed from public/26428_weakly_chordal to 66a1ed9a6521c26e3354b53ca5aaa9bb2f1e4c59
 Resolution set to fixed
 Status changed from positive_review to closed
comment:8 Changed 2 years ago by
 Milestone changed from sage8.4 to sage8.5
This should be retargeted for 8.5.
New commits:
trac #26428: multiple improvements