#12362: Improvement of GNP generators for graphs and digraphs
-----------------------------+----------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-5.0
Component: graph theory | Keywords: directed graphs, generators
Work_issues: | Upstream: N/A
Reviewer: Nathann Cohen | Author: David Coudert
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Comment(by ncohen):
Hellooooooooooo !!!!
On my machine I was also getting a timeout when running the doctests with
the -long flag. It was caused by the edge_disjoint_spanning_trees method,
for which the "random digraph" returned by the new random graph generator
was a bad instance.
There actually was not any problem, short of the fact that GLPK was having
a hard time. The problem did not occur when CPLEX was installed which is
probably why it did not happen on your computer.
The small patch I add does the following :
1) changes the value of epsilon from 1/10*n to 1/3*n
2) adds a verification at the end of edge_disjoint_spanning_tree so that
we aresure the answers computed by the LP solver are correct.
Theoretically speaking, setting epsilon to 1/2*n is sufficient, but I
often set the value to something smaller "just to be sure". 1/10*n seems
to be a bit too low, and for this reason GLPK had a hard time finding the
solutions. It would have found it eventually, but with a low value of
epsilon it has more branches to explore.
So, with this small patch I am adding the value of epsilon goes to 1/3,
which is till more than necessary and should not cause any problem. And
"just to be sure", I also added a test at the end of the function, to
ensure that the results returned are indeed correct (that each graph is
connected).
It passes all long tests on my machine, is faster than before, and "if you
agree with those new modifications [...]" `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12362#comment:22>
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.
