#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:
---------------------------------+------------------------------------------
Changes (by dcoudert):
* status: needs_work => needs_review
Comment:
Replying to [comment:6 ncohen]:
> * Why do you check in independent_set whether the value given by
"algorithm" is good ? vertex_cover is already dealing with that, so if you
forward something else the function already raises an exception
I have removed the test.
> * I hesitated myself between returning lists or sets but now that all
graph functions return lists I guess it is best to stick with it..
Wrapping the return value with a list() looks best `:-p`
Changed to list
> * Variable rules_are_used initialized to True. What about using
reduction_rules instead, as it alrady exists ?
I don't like the idea since in future improvements of the function one may
need the original value of !`reduction_rules` later in the algorithm.
> * As it is, if the given graph is a tree you compute n/2 times the list
of vertices of degree 1. That's a bit too much. ...... Then, instead of
removing only one vertex from V you could write "for v n V" and apply you
rule on each of them iteratively (after checking that they have not been
removed already, or that their neighbor has. With a bit of luck it should
also be faster (though perhaps this difference is actually hard to
measure...).
I'm now using the cores.
Note however that what you said is not exact. When removing the neighbor
of a degree one vertex from the graph, it is possible reduce the degree of
some vertices to 0 or 1. These vertices are not identified by the cores
function. They will thus be considered only at next iteration of the main
while loop.
> * if v in g.neighbors(w): . This is True mathematically speaking, but
a sin from the programming point of view. You are actually building the
list of neighbors of w, then checking whether v belongs to the list when
you mean "g.has_edge(v,w)" `:-p`
I was not sure of the best solution to choose when writing the function
because I don't know how the neighbors function is written. I did proposed
modification.
> * Could you also add in a "TESTS::" section a small "for" loop ensuring
that that the algorithms outputs the same cardinalities when
reduction_rules is enabled or not ? Something like what appears at the
bottom of GenericGraph .traveling_salesman_problem.
Done. I have also move some test from independent_set to vertex_cover.
I have also updated the tests in the tsp function, translating sentences
from french to english ;-)
Thanks for your help Nathann, and congratulation for the CNRS ranking !!!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743#comment:7>
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.
