#1314: graphs: calculate tutte polynomial
-------------------------------------+-------------------------------------
Reporter: jason | Owner: rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-6.1
Component: graph theory | Resolution:
Keywords: tutte, graph | Merged in:
Authors: Mike Hansen, | Reviewers: Jernej Azarija,
Frédéric Chapoton, Jernej Azarija | Nathann Cohen
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/tscrim/tutte_polynomial-1314 | b02b9395dad4d69508a2897832b42892ce89e564
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
Replying to [comment:77 ncohen]:
> Ahahahah. So you will not do without a "local cache" and a "global
cache". You want to use the global cache to speedup the results, and you
want to clear the local cache only. And merge the two if the user wants to
keep it.
What we should probably do, if we do keep a global cache, is during the
computation check if the key is in the global cache as well. However I'm
thinking we should not have a global cache because we get a memory leak.
Create a graph `G`, compute it's Tutte polynomial, then delete `G`. The
polynomial is now stuck in the global cache (that we don't want to have to
manually clear). I'm thinking the better way to do things is only have a
local cache and make `tutte_polynomial()` a cached method of the graphs.
That way when we delete the graph (along with the local cache), the
resulting polynomial can be garbage collected. It's probably better to
call the local cache the computation cache.
> And what happens if the local cache generates values that exist in the
global cache too ? `:-P` What do you cache then ? `:-P`
In effect what I'm proposing is we keep them completely separate, I think
that would create the least amount of problems. One other thing we could
do is keep a small fixed-size permanent cache.
That gives me an idea about something else to do: have an option for the
max size of a truly local cache when doing the computations. A priority
queue up to some fixed size which keeps track of computed Tutte
polynomials (with the priority being most often computed or some other
heuristic) from that in the local cache. However the above, which turns it
into a paging problem, might be an over-thought approach.
How big of a concern is it for recomputing Tutte polynomials for
isomorphic-but-not-identical graphs?
Simon, I was trying to convert it to use the usual `@cached_function`
instead of the custom cache.
--
Ticket URL: <http://trac.sagemath.org/ticket/1314#comment:79>
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/groups/opt_out.
