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: |
Description (last modified by )
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
- 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
- Branch set to u/borassi/new_hyperbolicity_algorithm
comment:3 Changed 6 years ago by
- Commit set to e2fe1c11dee8d5424927eb2a002c92687536b68e
- Status changed from new to needs_review
comment:4 follow-up: ↓ 5 Changed 6 years ago by
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):
thanfor 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
andb = c
you can write directlya,b = b,a
- When you
# We reset acc_bool
, it might be easier to usememset
. This part has negligeable impact on the computation time anyway.
David.
comment:5 in reply to: ↑ 4 Changed 6 years ago by
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):
thanfor 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
andb = c
you can write directlya,b = b,a
Done!
- When you
# We reset acc_bool
, it might be easier to usememset
. 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
- Commit changed from e2fe1c11dee8d5424927eb2a002c92687536b68e to 4dba3d9a5fa98984198157a8a60ba06af84ca292
Branch pushed to git repo; I updated commit sha1. New commits:
4dba3d9 | Reviewer's comments
|
comment:7 Changed 6 years ago by
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
- Commit changed from 4dba3d9a5fa98984198157a8a60ba06af84ca292 to 9c97e2812e1aa2e34cefebaec06b335a6b4632f7
Branch pushed to git repo; I updated commit sha1. New commits:
9c97e28 | Fixed ...
|
comment:9 Changed 6 years ago by
- 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
- 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
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
- Commit changed from 9c97e2812e1aa2e34cefebaec06b335a6b4632f7 to 6cd507f5b6d9ee5b4d219f64585cca0c17024092
Branch pushed to git repo; I updated commit sha1. New commits:
6cd507f | Set h=0 at the beginning
|
comment:13 Changed 6 years ago by
- 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
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
- Commit changed from 6cd507f5b6d9ee5b4d219f64585cca0c17024092 to bc34557c74be36de553b0b940d423f6fe35dd626
Branch pushed to git repo; I updated commit sha1. New commits:
bc34557 | Merged with 6.9 beta3
|
comment:16 Changed 6 years ago by
- Status changed from needs_review to positive_review
Good to go. David.
comment:17 Changed 6 years ago by
- Branch changed from u/borassi/new_hyperbolicity_algorithm to bc34557c74be36de553b0b940d423f6fe35dd626
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
New hyperbolicity algorithm (documentation to be improved)
First draft