#12743: Addition of reduction rules as pre-processing of the vertex cover
function
---------------------------------+------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
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 ncohen):
* status: needs_review => needs_work
Comment:
Hellooooooooooo !!!
A few comments about this patch :
* 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 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`
* Gosh your docstrings are now totally spotless.. This, or we make the
same mistakes, but they look totally clean to me `:-)`
* Variable ``rules_are_used`` initialized to True. What about using
reduction_rules instead, as it alrady exists ?
* 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. I think that
{{{
V = [ u for u in g.vertices() if g.degree(u) == 1 ]
}}}
Should become
{{{
V = self.cores(2)[0]
}}}
The advantage is that this core decomposition is recursive, so after
the for loop there can be no vertex of degree 1 left in the graph
{{{
sage: g = graphs.RandomTree(50)
sage: g.cores(2)
([0, 1, 6, 14, 16, 17, 20, 23, 24, 25, 26, 29, 31, 32, 33, 34, 36,
42, 44, 46, 49, 43, 48, 5, 38, 22, 3, 7, 12, 8, 21, 10, 18, 39, 47, 19,
11, 45, 28, 35, 15, 9, 13, 30, 27, 2, 40, 41, 37, 4], [])
}}}
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...).
* ``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`
* 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.
All in all, a good patch `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743#comment:6>
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.
