New Hyperbolicity Algorithm

[sagetrac-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)

CC: @nathanncohen @dcoudert

Component: graph theory

Keywords: Hyperbolicity

Author: Michele Borassi

Branch/Commit: bc34557

Reviewer: David Coudert

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

[sagetrac-borassi]

Changed keywords from none to Hyperbolicity

[sagetrac-borassi]

Author: Michele Borassi

[sagetrac-borassi]

Branch: u/borassi/new_hyperbolicity_algorithm

[sagetrac-borassi]

Commit: e2fe1c1

[sagetrac-borassi]

New commits:

4720ef9	New hyperbolicity algorithm (documentation to be improved)
e2fe1c1	First draft

[dcoudert]

comment:4

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.

[sagetrac-borassi]

comment:5

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.

• 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

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?

[sagetrac-git]

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

4dba3d9

Reviewer's comments

[sagetrac-git]

Changed commit from e2fe1c1 to 4dba3d9

[dcoudert]

comment:7

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

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

[sagetrac-git]

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

9c97e28

Fixed ...

[sagetrac-git]

Changed commit from 4dba3d9 to 9c97e28

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:9

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

[vbraun]

comment:10

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]

[dcoudert]

comment:11

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.

[sagetrac-git]

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

6cd507f

Set h=0 at the beginning

[sagetrac-git]

Changed commit from 9c97e28 to 6cd507f

[sagetrac-borassi]

comment:13

Hello!

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

Michele

[dcoudert]

comment:14

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.

[sagetrac-git]

Changed commit from 6cd507f to bc34557

[sagetrac-git]

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

bc34557

Merged with 6.9 beta3

[dcoudert]

comment:16

Good to go.
David.

[vbraun]

Changed branch from u/borassi/new_hyperbolicity_algorithm to bc34557