#12743: Addition of reduction rules as pre-processing of the vertex cover
function
---------------------------------+------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Comment (by ncohen):
Hellooooooooo David !!
Well, the patch seems good to go, but there is one thing that should be
changed : one of the two tests deals with randomGNP graphs, and tests the
algorithms on instances of ``graphs.RandomGNP(20,.3)``.
Now the problem is that this actually does not test the reductions rules :
{{{
sage: all(min(graphs.RandomGNP(50,.3).degree())>2 for i in range(100))
True
}}}
Could you change the .3 to something like 4/50 ? It looks better this way
:
{{{
sage: graphs.RandomGNP(50,4/50).cores(k=2)
([33, 0, 1, 18, 28, 42, 43], [23, 27, 38, 40, 44, 2, 4, 7, 15, 22, 24, 29,
35, 5, 8, 9, 10, 12, 16, 17, 19, 26, 30, 31, 39, 48, 3, 20, 37, 41, 45,
47, 6, 46, 32, 21, 14, 49, 36, 34, 13, 11, 25])
sage: graphs.RandomGNP(50,4/50).cores(k=2)
([16, 30, 0, 2, 4, 38, 6], [5, 32, 37, 41, 31, 49, 10, 13, 14, 17, 19, 21,
25, 28, 7, 33, 35, 36, 42, 45, 9, 20, 3, 11, 15, 1, 23, 26, 27, 39, 46, 8,
12, 29, 34, 44, 47, 48, 43, 18, 24, 40, 22])
sage: graphs.RandomGNP(50,4/50).cores(k=2)
([18, 42, 4, 31, 32], [5, 11, 12, 22, 24, 37, 14, 13, 3, 27, 28, 34, 35,
36, 39, 1, 8, 10, 15, 17, 23, 25, 38, 41, 46, 49, 6, 21, 29, 33, 40, 45,
47, 30, 2, 26, 0, 43, 7, 9, 16, 19, 20, 44, 48])
sage: graphs.RandomGNP(50,4/50).cores(k=2)
([0, 11, 22, 32, 3, 15, 49, 45, 29], [18, 26, 28, 35, 40, 43, 44, 5, 13,
27, 20, 24, 25, 8, 2, 30, 34, 36, 39, 41, 46, 47, 9, 7, 10, 12, 17, 19,
21, 42, 48, 1, 16, 23, 31, 37, 14, 33, 4, 6, 38])
}}}
So the rules are actually being tested `:-)`
You can set the ticket to "positive review" afterwards, for the ticket is
good to go `:-)`
Thank for this patch !
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743#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.
