Opened 4 years ago

Closed 4 years ago

#18418 closed enhancement (fixed)

Clean Hyperbolicity Module

Reported by: borassi Owned by: borassi
Priority: major Milestone: sage-6.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 dcoudert)

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 borassi

  • Authors set to borassi
  • Cc ncohen dcoudert added
  • Description modified (diff)
  • Keywords Hyperbolicity added
  • Owner changed from (none) to borassi

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.

comment:2 Changed 4 years ago by borassi

  • Description modified (diff)

comment:3 Changed 4 years ago by borassi

  • 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 dcoudert

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 borassi

  • Branch set to u/borassi/clean_hyperbolicity_module

comment:6 Changed 4 years ago by borassi

  • 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 follow-up: Changed 4 years ago by dcoudert

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.

comment:8 Changed 4 years ago by git

  • Commit changed from b7cecc1b4e41eb973d517668e2d26522af94474d to 8a7ffe1d55e5efee710c4a50a6ae406674737e68

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

3e16a6fCleaned hyperbolicity (2)
66099f5Temp
49ce531Revert
177c42eAfter David's suggestions
8a7ffe1After David's suggestions

comment:9 in reply to: ↑ 7 Changed 4 years ago by borassi

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.

comment:10 follow-up: Changed 4 years ago by dcoudert

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.

comment:11 Changed 4 years ago by git

  • Commit changed from 8a7ffe1d55e5efee710c4a50a6ae406674737e68 to 4280fce704003ff53b80000e9d918c01b2a4e23b

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

4280fceAfter second correction.

comment:12 Changed 4 years ago by git

  • Commit changed from 4280fce704003ff53b80000e9d918c01b2a4e23b to 4c55f5eeadc7539a443bdcec0797eff28e99da35

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

4c55f5eAfter second correction (2)

comment:13 in reply to: ↑ 10 Changed 4 years ago by borassi

Done everything!

comment:14 follow-up: Changed 4 years ago by dcoudert

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

comment:15 in reply to: ↑ 14 Changed 4 years ago by borassi

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.

comment:16 Changed 4 years ago by dcoudert

  • 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 vbraun

  • 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 dcoudert

  • Authors changed from borassi to Michele Borassi
  • Status changed from needs_work to positive_review

Sorry, I have forgotten to check that.

comment:19 Changed 4 years ago by vbraun

  • 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 dcoudert

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

comment:21 Changed 4 years ago by git

  • Commit changed from 4c55f5eeadc7539a443bdcec0797eff28e99da35 to 0ce54207bc9085c3128d407867e428e797d8a49c

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

0ce5420After correction of 'Z'

comment:22 Changed 4 years ago by borassi

  • Status changed from needs_work to needs_review

Done!

comment:23 Changed 4 years ago by dcoudert

  • 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 vbraun

  • Branch changed from u/borassi/clean_hyperbolicity_module to 0ce54207bc9085c3128d407867e428e797d8a49c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.