Opened 4 years ago
Closed 4 years ago
#18418 closed enhancement (fixed)
Clean Hyperbolicity Module
Reported by:  borassi  Owned by:  borassi 

Priority:  major  Milestone:  sage6.7 
Component:  graph theory  Keywords:  Hyperbolicity 
Cc:  ncohen, dcoudert  Merged in:  
Authors:  Michele Borassi  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  0ce5420 (Commits)  Commit:  0ce54207bc9085c3128d407867e428e797d8a49c 
Dependencies:  Stopgaps: 
Description (last modified by )
Improve the hyperbolicity module by performing the following cleanings:
 rename "cuts" > "CCL", "cuts+" > "CCL+" or "CCL+FA";
 set "CCL+" as default (it is faster);
 include approximation algorithms using "cuts+" (already included, but an error is raised at the moment);
 put counting sort of pairs in a separate routine;
 use uint_32 and not uint_16 for pairs (graphs can have more than
2^16
vertices);  rename algorithm "basic+" to "basic".
Change History (24)
comment:1 Changed 4 years ago by
 Cc ncohen dcoudert added
 Description modified (diff)
 Keywords Hyperbolicity added
 Owner changed from (none) to borassi
comment:2 Changed 4 years ago by
 Description modified (diff)
comment:3 Changed 4 years ago by
 Component changed from PLEASE CHANGE to graph theory
 Description modified (diff)
 Type changed from PLEASE CHANGE to enhancement
comment:4 Changed 4 years ago by
in the hyperbolicity method, we are not using qsort but something similar to counting sort. You can certainly clean that part and put it in a specific method so that it can be reused
comment:5 Changed 4 years ago by
 Branch set to u/borassi/clean_hyperbolicity_module
comment:6 Changed 4 years ago by
 Commit set to b7cecc1b4e41eb973d517668e2d26522af94474d
 Description modified (diff)
 Status changed from new to needs_review
David, is there any particular reason why you use variable "triples", instead of simply iterating twice over the array "pairs_of_length"? If not, I could clean this, too.
comment:7 followup: ↓ 9 Changed 4 years ago by
Hello,
 editing remark : comments must be formatted in 80 columns format. Don't ask why ;)
 in the sort_pairs method, you are not using quick sort but counting sort
 there is a recent and useful method for malloc. See file
generic_graph_pyx.pyx
for examplefrom sage.ext.memory cimport check_allocarray, sage_malloc, sage_free elist = <int*>check_allocarray(2 * len(G.edges()) + 2, sizeof(int))
 I agree to remove
basic+
, although I would have prefer to renamebasic+
intobasic
and remove the oldbasic
which is slower. The basic method is useful only for comparison purpose.  the purpose of the
triples
list is to avoid computing many times the sum S1. It adds a loop but reduces the number of operations. Do you have a better solution in mind ?
David.
comment:8 Changed 4 years ago by
 Commit changed from b7cecc1b4e41eb973d517668e2d26522af94474d to 8a7ffe1d55e5efee710c4a50a6ae406674737e68
comment:9 in reply to: ↑ 7 Changed 4 years ago by
Hello!
 editing remark : comments must be formatted in 80 columns format. Don't ask why ;)
Done
 in the sort_pairs method, you are not using quick sort but counting sort
Yeah, sorry, wrong comment. Corrected.
 there is a recent and useful method for malloc. See file
generic_graph_pyx.pyx
for examplefrom sage.ext.memory cimport check_allocarray, sage_malloc, sage_free elist = <int*>check_allocarray(2 * len(G.edges()) + 2, sizeof(int))
Done
 I agree to remove
basic+
, although I would have prefer to renamebasic+
intobasic
and remove the oldbasic
which is slower. The basic method is useful only for comparison purpose.
I replaced the code of basic
with the old cose of basic+
.
 the purpose of the
triples
list is to avoid computing many times the sum S1. It adds a loop but reduces the number of operations. Do you have a better solution in mind ?
I see your point: very nice solution! My solution was simply to recompute S1
every time.
comment:10 followup: ↓ 13 Changed 4 years ago by
Hello,
Be careful with global name replacements
 performs very well in practice since it cuts the search space. This + performs very well in practice since it CCL the search space. This
In method sort_pairs
, you should
 Add a first comment line like
Return a list of pairs sorted in decreasing order of values
. Almost all methods have such a one line description.  declare the types of local variables i,j,k
In method __hyperbolicity__
, you should
 Replace
cdef uint32_t *nb_p = <uint32_t>check...
withcdef uint32_t nb_p
and then callsort_pairs
with&nb_p
and usenb_p
rather thannb_p[0]
You could also rename some methods
__hyperbolicity_basic_algorithm__
>hyperbolicity_basic_algorithm
__hyperbolicity__
>hyperbolicity_CCL
These methods are cdef, they are not visible at Python level.
comment:11 Changed 4 years ago by
 Commit changed from 8a7ffe1d55e5efee710c4a50a6ae406674737e68 to 4280fce704003ff53b80000e9d918c01b2a4e23b
Branch pushed to git repo; I updated commit sha1. New commits:
4280fce  After second correction.

comment:12 Changed 4 years ago by
 Commit changed from 4280fce704003ff53b80000e9d918c01b2a4e23b to 4c55f5eeadc7539a443bdcec0797eff28e99da35
Branch pushed to git repo; I updated commit sha1. New commits:
4c55f5e  After second correction (2)

comment:13 in reply to: ↑ 10 Changed 4 years ago by
Done everything!
comment:14 followup: ↓ 15 Changed 4 years ago by
list pairs {i,j} in increasing order
> decreasing order ?
comment:15 in reply to: ↑ 14 Changed 4 years ago by
I think in increasing order, because at line 569 I find:
# ==> Defines pairs_of_length[d] for all d for i from 1 <= i <= D: pairs_of_length[i] = pairs_of_length[i1] + nb_pairs_of_length[i1]
where pairs_of_length[i] is where the list of pairs at distance i starts.
comment:16 Changed 4 years ago by
 Description modified (diff)
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
You are perfectly right!
For me this patch is now good to go.
David.
comment:17 Changed 4 years ago by
 Status changed from positive_review to needs_work
Author name should be the full name, not trac username
comment:18 Changed 4 years ago by
 Status changed from needs_work to positive_review
Sorry, I have forgotten to check that.
comment:19 Changed 4 years ago by
 Status changed from positive_review to needs_work
Documentation doesnt' build:
[graphs ] docstring of sage.graphs.hyperbolicity:10: WARNING: Block quote ends without a blank line; unexpected unindent.
comment:20 Changed 4 years ago by
Michele, line 10 of the file, there is a Z
that should be removed.
comment:21 Changed 4 years ago by
 Commit changed from 4c55f5eeadc7539a443bdcec0797eff28e99da35 to 0ce54207bc9085c3128d407867e428e797d8a49c
Branch pushed to git repo; I updated commit sha1. New commits:
0ce5420  After correction of 'Z'

comment:23 Changed 4 years ago by
 Status changed from needs_review to positive_review
With the last commit, I can compile, run tests, do some other trials, build the doc and the result looks good. So it should be ok this time.
comment:24 Changed 4 years ago by
 Branch changed from u/borassi/clean_hyperbolicity_module to 0ce54207bc9085c3128d407867e428e797d8a49c
 Resolution set to fixed
 Status changed from positive_review to closed
I will perform the modifications in the description as soon as possible. Since this is my first ticket, please let me know if I make any mistake in my work.