#17712: Adds memoization to the branch and bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_work
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | 6e39f78fbdfcf22ca89ba23ac96ce88431feaa6e
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17112 |
Dependencies: |
#17711 |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hello again,
This commit does what was said above, and also rephrases the short
description of the caching mechanism in the module's doc. I hope that it
is clearer.
As you just removed a keyword I also wondered about the use of "is_on".
Two remarks:
1) Right now you 'store' the size of the dictionary in an integer
variable. To do this, every time you add a new element in the dictionary,
you check whether the element is there already. Thus, each of the `+1`
costs you a lookup, theoretically a `log(n)` operation. I have not run any
timings, but I would be a bit troubled if calling `len(the_dict)` was not
faster.
2) I still do not understand the point of the dictionary: what are "False"
values useful for ? Why isn't it just a set of frozensets ?
3)
{{{
~/sage/graphs/graph_decompositions$ sage -coverage vertex_separation.pyx
------------------------------------------------------------------------
SCORE vertex_separation.pyx: 88.9% (8 of 9)
Missing doctests:
* line 1663: def __init__(self, int max_prefix_length=20, int
max_prefix_number=10**6)
------------------------------------------------------------------------
}}}
Nathann
P.S. : About removing this `PrefixStorage`: let us first see what happens
with this dict/set question. My intuition is that if this thing becomes a
set you can already remove `cost/upper_bound/is_improved` from `update()`
(and only call 'update' when appropriate) which may already simplify
matters.
--
Ticket URL: <http://trac.sagemath.org/ticket/17712#comment:13>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
