#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 !!!
> 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.
Totally right `:-)`
> I'm now using the cores.
+1
> 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.
Oh right, you also remove neighbors... Well, at least for trees everything
is removed in only one run `:-D`
But actually, that was the whole point of my first remark --copy/paste the
code from "cores" and modify it so that this problem is solved. Its
principle is actually very simple : "first compute the degree of all the
vertices in your graph and keep them in a table for quick access. For as
long as there is a vertex of degree 1, remove it and update the degree of
its neighbors in the table."
You would only have to say instead "for as long as there is a vertex of
degree 1, delete both vertices and update the degree of its distance-2
neighbors."
This "cores" function is not "so very smart", but it is very small and
efficient with memory.
By the way there is a set method to remove an element regardless of
whether it is already inside or not : set.discard
> I have also updated the tests in the tsp function, translating sentences
from french to english ;-)
Oh my god, some tests were written in french ? `:-D`
> Thanks for your help Nathann, and congratulation for the CNRS ranking
!!!
Thaaaaaaaaaaaaaaaaaaaaaaaaaanks ! `:-D`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743#comment:8>
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.
