#9584: Weird timeouts in doctesting generic_graph with 4.5.2.alpha0 on some
systems
-----------------------+----------------------------------------------------
Reporter: mpatel | Owner: mvngu
Type: defect | Status: new
Priority: blocker | Milestone: sage-4.5.2
Component: doctest | Keywords: generic_graph, generic graph, time-out,
time out
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------+----------------------------------------------------
Comment(by ncohen):
Hmmmm.... :-/
Then perhaps setting the number of vertices to 20 instead of 30 ? With
CPLEX as a solver, this test is actually much faster, this may be why I
originally put a 30 there, which may be too big for GLPK.
{{{
sage: T = lambda x: x.edge_disjoint_spanning_trees(x.edge_connectivity())
sage: %timeit T(digraphs.RandomDirectedGNP(30,.3))
5 loops, best of 3: 6.03 s per loop
}}}
{{{
sage: T = lambda x: x.edge_disjoint_spanning_trees(x.edge_connectivity(),
solver= "CPLEX")
sage: %timeit T(digraphs.RandomDirectedGNP(30,.3))
5 loops, best of 3: 668 ms per loop
}}}
In this case, though, we should increase the probability, lest we find
non-strongly-connected graphs, but this still takes a lot of time
{{{
sage: T = lambda x: x.edge_disjoint_spanning_trees(x.edge_connectivity())
sage: %timeit T(digraphs.RandomDirectedGNP(20,.5))
5 loops, best of 3: 4.52 s per loop
}}}
As I still haven't found a way to write #7303, perhaps the following would
be a good alternative :
We build a directed circulant graph on n vertices by linking the i th
vertex to i+1, i+2, ... , i+k, thus ensuring our graph is k-connected.
Then, by Edmond's theorem, we know this graph has `k` edge-disjoint
spanning arborescences
{{{
sage: n = 20
sage: k = 3
sage: g = DiGraph()
sage: g.add_edges( (Integer(i),Integer(Mod(i+j,n))) for i in range(n) for
j in range(1,k+1) )
sage: k == g.edge_connectivity()
True
sage: arborescences = g.edge_disjoint_spanning_trees(k)
sage: all([a.is_directed_acyclic() for a in arborescences])
True
sage: all([a.is_connected() for a in arborescences])
True
}}}
It is nicer now :
{{{
sage: %timeit g.edge_disjoint_spanning_trees(k)
5 loops, best of 3: 283 ms per loop
}}}
Plus it is a bit "cleaner" without the random graphs in this case,
methinks :-)
Sorry for the trouble !!!!!!!!!!!!!!!!!!
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9584#comment:31>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
