#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:
-------------------------------------+-------------------------------------
Changes (by tscrim):
* status: needs_review => needs_info
* cc: SimonKing, nbruin (added)
* branch: public/1314 => u/tscrim/tutte_polynomial-1314
* commit: 5450ef20b36892ccbe3f6c3d5c9f049fad03cbb8 =>
b02b9395dad4d69508a2897832b42892ce89e564
Comment:
Okay, I figured out what was changing. I wasn't caching the final result
of the Tutte polynomial, and how it currently is done will overly clear
the cache. For example, say you compute the Tutte polynomial on some large
graph `G`, then you compute it on a very small graph `H` and ask it to
clear the cache. Now the cached data for `G` is gone. I think we should
always cache the final results, and with the current implementation, there
is the possibility we've already computed the Tutte polynomial of a small
graph. However I think this will be infrequent or you should not be
clearing the utility cache.
Although there is a problem, we get memory leaks. Now one can argue with
the previous behavior along with the default implementation, this is not a
leak. If the user was deciding to keep the cache, this would be the user
knowing what (s)he is doing. Yet I wouldn't want my small computation to
destroy the data of my big one, nor store it myself. So which way should
we go, and if we go with 2 caches, how usable would the weak caches be?
Feedback is needed.
Simon, Nils -- I cc-ed you here because we might need a good weak cache
solution here and I'd like your thoughts and expertise.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=e896d884fecc58ab18e75c546bd3c79b046cbd41
e896d88]||{{{Reworked the internal structure.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=63b04872bc064f46b2856b63e9fc2d4a4e1b2839
63b0487]||{{{Added doctest to the internal function.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=466cec64e495570548ad90a3923cffc43a2479cb
466cec6]||{{{Moved the cache.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=da55de3e37b727f474cf86706935a6486ec8f6c2
da55de3]||{{{Moved @_cached to its proper place.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=7515b6bceb2510b040cee5489e0e01a73c11d16a
7515b6b]||{{{Added the variables back.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=91a36960339d944a932a7db3177de1ce4614906c
91a3696]||{{{pyflakes cleanup.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=b02b9395dad4d69508a2897832b42892ce89e564
b02b939]||{{{Cached the output of tutte_polynomial.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/1314#comment:76>
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.
