Clean Hyperbolicity Module

[sagetrac-borassi]

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".

CC: @nathanncohen @dcoudert

Component: graph theory

Keywords: Hyperbolicity

Author: Michele Borassi

Branch/Commit: 0ce5420

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/18418

[sagetrac-borassi]

Author: borassi

[sagetrac-borassi]

comment:1

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.

[sagetrac-borassi]

Changed keywords from none to Hyperbolicity

[dcoudert]

comment:4

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

[sagetrac-borassi]

Branch: u/borassi/clean_hyperbolicity_module

[sagetrac-borassi]

Commit: b7cecc1

[sagetrac-borassi]

comment:6

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.

[dcoudert]

comment:7

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 example

from 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 rename basic+ into basic and remove the old basic 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.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3e16a6f	Cleaned hyperbolicity (2)
66099f5	Temp
49ce531	Revert
177c42e	After David's suggestions
8a7ffe1	After David's suggestions

[sagetrac-git]

Changed commit from b7cecc1 to 8a7ffe1

[sagetrac-borassi]

comment:9

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 example

from 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 rename basic+ into basic and remove the old basic 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.

[dcoudert]

comment:10

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... with cdef uint32_t nb_p and then call sort_pairs with &nb_p and use nb_p rather than nb_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.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4280fce

After second correction.

[sagetrac-git]

Changed commit from 8a7ffe1 to 4280fce

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4c55f5e

After second correction (2)

[sagetrac-git]

Changed commit from 4280fce to 4c55f5e

[sagetrac-borassi]

comment:13

Done everything!

[dcoudert]

comment:14

list pairs {i,j} in increasing order -> decreasing order ?

[sagetrac-borassi]

comment:15

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[i-1] + nb_pairs_of_length[i-1]

where pairs_of_length[i] is where the list of pairs at distance i starts.

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:16

You are perfectly right!

For me this patch is now good to go.

David.

[vbraun]

comment:17

Author name should be the full name, not trac username

[dcoudert]

Changed author from borassi to Michele Borassi

[dcoudert]

comment:18

Sorry, I have forgotten to check that.

[vbraun]

comment:19

Documentation doesnt' build:

[graphs   ] docstring of sage.graphs.hyperbolicity:10: WARNING: Block quote ends without a blank line; unexpected unindent.

[dcoudert]

comment:20

Michele, line 10 of the file, there is a Z that should be removed.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0ce5420

After correction of 'Z'

[sagetrac-git]

Changed commit from 4c55f5e to 0ce5420

[sagetrac-borassi]

comment:22

Done!

[dcoudert]

comment:23

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.

[vbraun]

Changed branch from u/borassi/clean_hyperbolicity_module to 0ce5420