#19049: New Hyperbolicity Algorithm
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: Hyperbolicity | Merged in:
Authors: Michele Borassi | Reviewers: David Coudert
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/borassi/new_hyperbolicity_algorithm|
9c97e2812e1aa2e34cefebaec06b335a6b4632f7
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by vbraun):
* status: positive_review => needs_work
Comment:
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]
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/19049#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
