Opened 6 years ago

Closed 6 years ago

#19049 closed enhancement (fixed)

New Hyperbolicity Algorithm

Reported by: borassi Owned by:
Priority: major Milestone: sage-6.9
Component: graph theory Keywords: Hyperbolicity
Cc: ncohen, dcoudert Merged in:
Authors: Michele Borassi Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: bc34557 (Commits, GitHub, GitLab) Commit: bc34557c74be36de553b0b940d423f6fe35dd626
Dependencies: Stopgaps:

Status badges

Description (last modified by borassi)

Implement the hyperbolicity algorithm in ![1].

![1] Michele Borassi, David Coudert, Pierluigi Crescenzi and Andrea Marino. On Computing the Hyperbolicity of Real-World Graphs. In Proceedings of the 23rd European Symposium on Algorithms (ESA 2015)

Change History (17)

comment:1 Changed 6 years ago by borassi

  • Authors set to Michele Borassi
  • Cc ncohen dcoudert added
  • Component changed from PLEASE CHANGE to graph theory
  • Description modified (diff)
  • Keywords Hyperbolicity added
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 6 years ago by borassi

  • Branch set to u/borassi/new_hyperbolicity_algorithm

comment:3 Changed 6 years ago by borassi

  • Commit set to e2fe1c11dee8d5424927eb2a002c92687536b68e
  • Status changed from new to needs_review

New commits:

4720ef9New hyperbolicity algorithm (documentation to be improved)
e2fe1c1First draft

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

It's working very well. I have very few and minor comments

  • reduce the number of iterations of the test for i in range(100): # long time. 10 is enough.
  • replace reference [CCL12] with [CCL15]: N. Cohen, D. Coudert, A. Lancin. On computing the Gromov hyperbolicity. ACM Journal of Experimental Algorithmics, 20(1.6):1-18, 2015. [<http://dx.doi.org/10.1145/2780652>_] or [<https://hal.inria.fr/hal-01182890>_]
  • I think it is better to write for b in range(D-1,-1,-1): than for b from D > b >= 0: although the later is easier to read. see http://docs.cython.org/src/userguide/language_basics.html#integer-for-loops
  • Instead of c = a, a = b and b = c you can write directly a,b = b,a
  • When you # We reset acc_bool, it might be easier to use memset. This part has negligeable impact on the computation time anyway.

David.

comment:5 in reply to: ↑ 4 Changed 6 years ago by borassi

Hello!

Replying to dcoudert:

It's working very well. I have very few and minor comments

  • reduce the number of iterations of the test for i in range(100): # long time. 10 is enough.

Done!

  • replace reference [CCL12] with [CCL15]: N. Cohen, D. Coudert, A. Lancin. On computing the Gromov hyperbolicity. ACM Journal of Experimental Algorithmics, 20(1.6):1-18, 2015. [<http://dx.doi.org/10.1145/2780652>_] or [<https://hal.inria.fr/hal-01182890>_]

Done! I used the first link.

Done!

  • Instead of c = a, a = b and b = c you can write directly a,b = b,a

Done!

  • When you # We reset acc_bool, it might be easier to use memset. This part has negligeable impact on the computation time anyway.

Not done! In my opinion, it has impact on the computation time. Indeed, when we fix a pair (a,b), the algorithm does the following:

for c in decreasing order of ecc(c)-d(a,c):
    if ecc(c)-d(a,c) >= 3*(h+1)-2*d(a,b):
        ... other tests to check if v is acceptable and/or valuable
    else:
        break # All other vertices c are not acceptable and not valuable

for c in valuable:
    for (c,d) pair before (a,b), with d acceptable:
        h = max(h, delta(a,b,c,d))

for c in acceptable:
    acc_bool[c] = 0

Here, the first for loop is performed as many times as the number of vertices satisfying ecc(c)-d(a,c) >= 3*(h+1)-2*d(a,b) (let's say, 100, if the graph has with 10000 vertices). The second for loop needs time O(acceptable * valuable), where acceptable is, let's say, 10, and valuable is 5. The total time is 50.

The last loop takes time 10, as it is, while it takes time 10000 if we use memset (I know memset is very fast, but here we are talking about two orders of magnitude).

Did I convince you?

comment:6 Changed 6 years ago by git

  • Commit changed from e2fe1c11dee8d5424927eb2a002c92687536b68e to 4dba3d9a5fa98984198157a8a60ba06af84ca292

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

4dba3d9Reviewer's comments

comment:7 Changed 6 years ago by dcoudert

can you just fix the remainings ... -> ....:

       sage: for i in range(10): # long time
       ...       n = random.randint(2, 20)

comment:8 Changed 6 years ago by git

  • Commit changed from 4dba3d9a5fa98984198157a8a60ba06af84ca292 to 9c97e2812e1aa2e34cefebaec06b335a6b4632f7

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

9c97e28Fixed ...

comment:9 Changed 6 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

So then the patch is good to go! Thanks, David.

comment:10 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

32-bit linux:

sage -t --long src/sage/graphs/hyperbolicity.pyx
**********************************************************************
File "src/sage/graphs/hyperbolicity.pyx", line 1212, in sage.graphs.hyperbolicity.?
Failed example:
    for i in xrange(10): # long time
        G = graphs.RandomBarabasiAlbert(100,2)
        d1,_,_ = hyperbolicity(G,algorithm='basic')
        d2,_,_ = hyperbolicity(G,algorithm='CCL')
        d3,_,_ = hyperbolicity(G,algorithm='CCL+')
        d4,_,_ = hyperbolicity(G,algorithm='CCL+FA')
        d5,_,_ = hyperbolicity(G,algorithm='BCCM')
        l3,_,u3 = hyperbolicity(G,approximation_factor=2)
        if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1:
           print "That's not good!"
Expected nothing
Got:
    That's not good!
    That's not good!
    That's not good!
    That's not good!
    That's not good!
    That's not good!
    That's not good!
    That's not good!
    That's not good!
    That's not good!
**********************************************************************
File "src/sage/graphs/hyperbolicity.pyx", line 1226, in sage.graphs.hyperbolicity.?
Failed example:
    for i in range(10): # long time
        n = random.randint(2, 20)
        m = random.randint(0, n*(n-1) / 2)
        G = graphs.RandomGNM(n, m)
        for cc in G.connected_components_subgraphs():
            d1,_,_ = hyperbolicity(cc, algorithm='basic')
            d2,_,_ = hyperbolicity(cc, algorithm='CCL')
            d3,_,_ = hyperbolicity(cc, algorithm='CCL+')
            d4,_,_ = hyperbolicity(cc, algorithm='CCL+FA')
            d5,_,_ = hyperbolicity(cc, algorithm='BCCM')
            l3,_,u3 = hyperbolicity(cc, approximation_factor=2)
            if (not d1==d2==d3==d4==d5) or l3>d1 or u3<d1:
                print "Error in graph ", cc.edges()
Expected nothing
Got:
    Error in graph  [(0, 2, None), (0, 5, None), (0, 6, None), (0, 7, None), (1, 2, None), (1, 5, None), (2, 4, None), (2, 7, None), (2, 8, None), (3, 5, None), (3, 6, None), (3, 8, None)]
    Error in graph  [(0, 1, None), (0, 8, None), (0, 10, None), (0, 11, None), (1, 4, None), (2, 9, None), (2, 10, None), (3, 5, None), (3, 9, None), (3, 10, None), (3, 11, None), (4, 7, None), (4, 9, None), (4, 11, None), (5, 8, None), (6, 8, None), (7, 8, None), (7, 9, None), (7, 10, None)]
    Error in graph  [(0, 1, None), (0, 3, None), (0, 7, None), (0, 11, None), (1, 2, None), (1, 6, None), (1, 9, None), (1, 10, None), (2, 8, None), (3, 4, None), (3, 5, None), (3, 7, None), (3, 10, None), (4, 5, None), (4, 6, None), (4, 9, None), (4, 10, None), (4, 11, None), (5, 8, None), (5, 9, None), (5, 10, None), (6, 7, None), (8, 11, None)]
    Error in graph  [(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None), (0, 5, None), (0, 6, None), (0, 7, None), (0, 9, None), (0, 11, None), (1, 2, None), (1, 3, None), (1, 4, None), (1, 5, None), (1, 6, None), (1, 7, None), (1, 8, None), (1, 9, None), (1, 10, None), (1, 11, None), (2, 3, None), (2, 6, None), (2, 7, None), (2, 8, None), (2, 10, None), (2, 11, None), (3, 4, None), (3, 5, None), (3, 6, None), (3, 7, None), (3, 8, None), (3, 10, None), (3, 11, None), (4, 6, None), (4, 7, None), (4, 9, None), (4, 10, None), (4, 11, None), (5, 6, None), (5, 7, None), (5, 8, None), (5, 9, None), (5, 10, None), (5, 11, None), (6, 8, None), (6, 9, None), (6, 10, None), (6, 11, None), (7, 8, None), (7, 9, None), (7, 11, None), (8, 9, None), (8, 10, None), (8, 11, None), (9, 10, None), (9, 11, None)]
    Error in graph  [(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None), (0, 5, None), (0, 9, None), (0, 10, None), (0, 11, None), (0, 12, None), (0, 13, None), (1, 4, None), (1, 6, None), (1, 9, None), (1, 11, None), (1, 12, None), (1, 13, None), (2, 3, None), (2, 5, None), (2, 8, None), (2, 9, None), (2, 12, None), (3, 6, None), (3, 10, None), (3, 12, None), (4, 9, None), (4, 11, None), (4, 12, None), (4, 13, None), (5, 8, None), (5, 9, None), (5, 10, None), (5, 13, None), (6, 7, None), (6, 12, None), (7, 10, None), (7, 12, None), (8, 12, None), (9, 10, None), (9, 12, None), (11, 12, None), (11, 13, None)]
    Error in graph  [(0, 3, None), (0, 4, None), (0, 6, None), (0, 7, None), (0, 8, None), (1, 10, None), (1, 11, None), (1, 15, None), (2, 5, None), (2, 10, None), (2, 13, None), (2, 14, None), (3, 4, None), (3, 8, None), (3, 12, None), (3, 14, None), (4, 5, None), (4, 9, None), (4, 13, None), (4, 17, None), (5, 10, None), (5, 13, None), (5, 14, None), (5, 17, None), (6, 15, None), (8, 9, None), (9, 13, None), (9, 15, None), (10, 11, None), (10, 12, None), (10, 15, None), (11, 15, None), (11, 17, None), (15, 17, None)]
    Error in graph  [(0, 2, None), (0, 3, None), (0, 5, None), (0, 7, None), (0, 8, None), (0, 9, None), (0, 10, None), (0, 11, None), (0, 12, None), (0, 14, None), (1, 2, None), (1, 3, None), (1, 4, None), (1, 5, None), (1, 6, None), (1, 7, None), (1, 8, None), (1, 10, None), (1, 11, None), (2, 4, None), (2, 5, None), (2, 6, None), (2, 7, None), (2, 9, None), (2, 13, None), (3, 4, None), (3, 5, None), (3, 6, None), (3, 7, None), (3, 8, None), (3, 9, None), (3, 10, None), (3, 13, None), (4, 6, None), (4, 8, None), (4, 9, None), (4, 10, None), (4, 11, None), (4, 12, None), (4, 14, None), (5, 6, None), (5, 7, None), (5, 9, None), (5, 11, None), (5, 12, None), (5, 13, None), (6, 8, None), (6, 9, None), (6, 10, None), (6, 11, None), (7, 8, None), (7, 9, None), (7, 10, None), (7, 11, None), (7, 12, None), (7, 13, None), (7, 14, None), (8, 9, None), (8, 10, None), (8, 11, None), (8, 12, None), (8, 14, None), (9, 10, None), (9, 13, None), (9, 14, None), (10, 11, None), (10, 12, None), (10, 13, None), (10, 14, None), (11, 12, None), (11, 13, None), (11, 14, None), (12, 14, None), (13, 14, None)]
    Error in graph  [(0, 1, None), (0, 4, None), (0, 5, None), (0, 7, None), (0, 8, None), (1, 2, None), (1, 3, None), (1, 6, None), (1, 7, None), (1, 8, None), (2, 3, None), (2, 4, None), (2, 6, None), (2, 8, None), (2, 9, None), (3, 5, None), (3, 6, None), (3, 8, None), (3, 9, None), (4, 5, None), (4, 6, None), (4, 7, None), (4, 8, None), (4, 9, None), (5, 7, None), (6, 8, None), (6, 9, None), (7, 9, None), (8, 9, None)]
**********************************************************************
File "src/sage/graphs/hyperbolicity.pyx", line 1246, in sage.graphs.hyperbolicity.?
Failed example:
    hyperbolicity(G)
Expected:
    (1/2, [6, 7, 8, 9], 1/2)
Got:
    (0, [], 0)
**********************************************************************
1 item had failures:
   3 of  50 in sage.graphs.hyperbolicity.?
    [66 tests, 3 failures, 0.41 s]

comment:11 Changed 6 years ago by dcoudert

This is weird. I have tried both on a 64bits and a 32 bits computer all the graphs for which we have the list of edges and my computers reports no error. I cannot reproduce the failing example with BA graphs, but a long test on the ticket is successful on my computer. I have no clue where the problem may comes from :(

David.

comment:12 Changed 6 years ago by git

  • Commit changed from 9c97e2812e1aa2e34cefebaec06b335a6b4632f7 to 6cd507f5b6d9ee5b4d219f64585cca0c17024092

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

6cd507fSet h=0 at the beginning

comment:13 Changed 6 years ago by borassi

  • Status changed from needs_work to needs_review

Hello!

This problem was that I forgot to set h=0 at the beginning... Now it should work!

Michele

comment:14 Changed 6 years ago by dcoudert

The patch passes all tests on both my mac (64bits) and a 32bits linux PC. For me the patch is ok, but is is certainly better to rebase on 9.3. David.

comment:15 Changed 6 years ago by git

  • Commit changed from 6cd507f5b6d9ee5b4d219f64585cca0c17024092 to bc34557c74be36de553b0b940d423f6fe35dd626

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

bc34557Merged with 6.9 beta3

comment:16 Changed 6 years ago by dcoudert

  • Status changed from needs_review to positive_review

Good to go. David.

comment:17 Changed 6 years ago by vbraun

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