Opened 12 years ago
Closed 6 years ago
#1314 closed enhancement (fixed)
graphs: calculate tutte polynomial
Reported by:  jason  Owned by:  rlm 

Priority:  major  Milestone:  sage6.1 
Component:  graph theory  Keywords:  tutte, graph 
Cc:  mvngu, lkeough, sdenton, ncohen, Stefan, azi, SimonKing, nbruin  Merged in:  
Authors:  Mike Hansen, Frédéric Chapoton, Jernej Azarija  Reviewers:  Jernej Azarija, Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  u/mhansen/tutte_polynomial1314 (Commits)  Commit:  b279c3363f2e06dab8332c8ce8f470480ccf966d 
Dependencies:  Stopgaps: 
Description (last modified by )
Implements a Graph.tutte_polynomial
method
Attachments (4)
Change History (93)
comment:1 Changed 12 years ago by
 Summary changed from [graphs] calculate tutte polynomial to graphs: calculate tutte polynomial
comment:2 Changed 12 years ago by
 Component changed from combinatorics to graph theory
 Keywords graphs removed
 Owner changed from mhansen to rlm
comment:3 followup: ↓ 4 Changed 11 years ago by
comment:4 in reply to: ↑ 3 Changed 11 years ago by
Replying to ncohen:
So in the end it reads like the license is at least as GPLuncompatible as Nauty's, and will then have to be included as an external software...
Not really. Sage includes software which could be used to replace this functionality. We just need to get the *rest* of the software relicensed, if this is possible.
comment:6 Changed 10 years ago by
Per discussion in Ticket http://trac.sagemath.org/sage_trac/ticket/7052 Pearce and Haggard's code could be included but nauty's license is incompatible. nauty could however be included as a separate optional spkg and the isomorphism function that it is used for replaced with Sage library calls. Then nauty could be used if available or called.
Since Pearce and Haggard's code is extremely efficient at computing the chromatic polynomial as well (between two and three orders of magnitude faster than the current Sage function) it could offer benefit there too.
comment:7 Changed 7 years ago by
 Report Upstream set to N/A
I have written code from scratch to compute the Tutte polynomial of a graph. I think it is at least correct and maybe even sort of efficient. Along the way I have written a couple of other routines for the Graph class that might be useful. I am planning to submit a patch once I figure out how do that (I am brand new at Sage developing....)
comment:8 Changed 7 years ago by
 Cc lkeough sdenton added
comment:9 Changed 7 years ago by
This ticket requires an edge contraction method; the existing merge_vertices
method doesn't work properly for the computation of Tutte polynomials. A working method is available at ticket #13239.
comment:10 Changed 7 years ago by
 Cc ncohen added
comment:11 Changed 7 years ago by
Tutte polynomial also needs code to determine whether an edge is a cut edge. You can find this at ticket #13242.
comment:12 followup: ↓ 13 Changed 7 years ago by
I had some old code from awhile back for computing this which I've attached, along with some commented out possible optimizations. I think I remember when doing this in practice, avoiding copying the graph saved quite a bit of time (hence the unmerge function).
comment:13 in reply to: ↑ 12 Changed 7 years ago by
Replying to mhansen:
I had some old code from awhile back for computing this which I've attached, along with some commented out possible optimizations. I think I remember when doing this in practice, avoiding copying the graph saved quite a bit of time (hence the unmerge function).
mhansen, thanks for sharing this code. Unfortunately, it does not seem to give the right answer for K_4:
sage: G = graphs.CompleteGraph?(4); G.allow_loops(true); G.allow_multiple_edges(true); tp = tutte_polynomial(G,x,y); tp
x^{2}*y^{2} + x*y^{3} + x^{3} + x^{2}*y + x*y^{2} + x^{2} + x*y
The actual Tutte polynomial of K4 is x^{3} + 3*x^{2} + y^{3} + 4*x*y + 3*y^{2} + 2*x + 2*y.
I currently do not see a way to implement the Tutte polynomial without making lots of copies of graphs, but maybe someone else can.
comment:14 Changed 7 years ago by
Sorry  there was a typo in that one. I've uploaded a new version which works and implements caching which should save quite a bit of time.
comment:15 Changed 7 years ago by
I timed both Jeremy's code and mhansen's code and it seems that mhansen's is much faster.
The two codes give two different looking (but potentially the same) answers on the Petersen graph.
This is about a third of the tutte.sage output 14*x^{4 + 22*(x + y)}2*x + 8*(x + y)*((x + y)*x + y^{2 + x + y)*x + (x}4 + x^{3 + (x + y)*(x}2 + x + y) + x^{2 + x + y)*x}2 + ((x + y)^{2*x + (x + y)}2 + y^{3 + ((x + y)*x}2 + (x + y)*x + y^{2 + x + y)*x + y}2 + x + y)*x^{2 + 22*(x + y)}2 + 13*(y^{2 + x + y)}2 + 14*x^{3 + 22*y}3 + 14*(x + y)*(x^{2 + x + y) + 4*(y}2 + x + y)*((x + y)^{2 + y}3 + y^{2 + x + y) + 5*((x + y)*x + (x}2 + x + y)*x + y^{2 + x + y)*y + 9*((x + y)*x}2 + (x + y)*x + y^{2 + x + y)*x + 9*(x}4 + x^{3 + x}2 + x + y)*x + ((x + y)^{2*x + (x + y)}2 + y^{3 + ((x + y)*x}2 + (x + y)*x + y^{2 + x + y)*x + y}2 + x + y)*x + (x^{4 + (x}4 + x^{3 + x}2 + x + y)*x^{2 + x}3 + (x + y)*(x^{2 + x + y) + (x}4 + x^{3 + x}2 + x + y)*x + x^{2 + x + y)*x + 4*(x}4 + (x + y)^{2*x + (x + y)}2 + x^{3 + y}3 + (x + y)*(x^{2 + x + y) + ((x + y)*x}2 + (x + y)*x + y^{2 + x + y)*x + (x}4 + x^{3 + x}2 + x + y)*x + x^{2 + y}2 + 2*x + 2*y)*x + 2*(x^{4 + (x + y)}2*x + (x + y)^{2 + x}3 + y^{3 + (x + y)*(x}2 + x + y) + ((x + y)*x^{2 + (x + y)*x + y}2 + x + y)*x + (x^{4 + x}3 + x^{2 + x + y)*x + (x}4 + x^{3 + (x + y)*(x}2 + x + y) + (x^{4 + x}3 + x^{2 + x + y)*x + x}2 + x + y)*x + x^{2 + y}2 + 2*x + 2*y)*x + 2*(x^{4 + 2*(x +.... }
And this is the output of Jeremy's: x^{9 + 6*x}8 + 21*x^{7 + 56*x}6 + 12*x^{5*y + 114*x}5 + y^{6 + 70*x}4*y + 30*x^{3*y}2 + 15*x^{2*y}3 + 10*x*y^{4 + 170*x}4 + 180*x^{3 + 120*x}2 + 9*y^{5 + 170*x}3*y + 105*x^{2*y}2 + 65*x*y^{3 + 35*y}4 + 240*x^{2*y + 171*x*y}2 + 75*y^{3 + 168*x*y + 84*y}2 + 36*x + 36*y
Although they are both showing up funny looking here...
Is there an easy way to multiply out and gather like terms in sage?
comment:16 Changed 7 years ago by
I attached Jeremy's code as Tuttepolynomial.sage in case anyone else wants to timeit.
comment:17 followup: ↓ 18 Changed 7 years ago by
x
and y
should ideally be integer polynomials (i.e., R.<x,y> = ZZ[]
)  then you don't have to deal with manually "expanding".
Additionally, in the tuttepolynomial.sage
code, you should probably be caching a canonical label of the graph  see the cache_key
method in my patch.
comment:18 in reply to: ↑ 17 Changed 7 years ago by
Replying to mhansen:
x
andy
should ideally be integer polynomials (i.e.,R.<x,y> = ZZ[]
)  then you don't have to deal with manually "expanding".
I see now! This makes it much better. If we put R.<x,y> = ZZ[] as the first line in the Tutte polynomial code it does this for us. Doing that shouldn't mess anything up, right?
Additionally, in the
tuttepolynomial.sage
code, you should probably be caching a canonical label of the graph  see thecache_key
method in my patch.
Will do!
comment:19 Changed 7 years ago by
I was curious and went ahead an implemented the optimizations at http://homepages.ecs.vuw.ac.nz/~djp/files/TOMS10.pdf . It seems our primary bottleneck is computing the canonical label of the graphs.
Changed 7 years ago by
comment:20 Changed 7 years ago by
 Cc Stefan added
comment:21 Changed 7 years ago by
What is the current status of this code?
comment:22 Changed 7 years ago by
 Cc azi added
comment:23 Changed 7 years ago by
tutte.sage works  it just needs to be added as a patch, documented, etc. I haven't had time to do this myself.
comment:24 followup: ↓ 25 Changed 7 years ago by
Nice, perhaps I'll do that one time if you wish.
Btw, there is a minor bug in tutte.sage. In the corner case
257 if G.num_edges() == 0: 258 return 1
we should actually still return a polynomial since otherwise:
tutte_polynomial(graphs.CompleteGraph(10).complement())(0,3)
would break.
comment:25 in reply to: ↑ 24 Changed 7 years ago by
Replying to azi:
Btw, there is a minor bug in tutte.sage. In the corner case
257 if G.num_edges() == 0: 258 return 1
Yep. One of the things that helps a lot is being able to avoid copying the graph. For the Tutte polynomial code, we just make one copy of the graph on the initial call, but never copy it afterward. I found context managers useful to manage mutating the graph and restoring it.
Also, I think the edge selection strategy has a bit of an effect on the speed of the chromatic polynomial computation as well.
comment:26 Changed 7 years ago by
I am in the process of integrating this code into Sage. There appears to be a memory issue when calculating the Tutte polynomial of a number of small graphs sequentially. Namely, Sage gets killed by the OS after exhausting all the physical memory.
Do you happen to have an idea where the fault for this could be?
comment:27 Changed 7 years ago by
Can you give some code to reproduce this? I've been running code like
for g in graphs.nauty_geng("7"): print tutte_polynomial(g, x, y)
but haven't been able to reproduce this.
comment:28 Changed 7 years ago by
Sure here is an example.
load tutte.sage c = 0 for G in graphs.nauty_geng("13 39:39"): if sorted(G.degree_sequence()) != sorted(G.complement().degree_sequence()): c+=1 if tutte_polynomial(G,x,y) == tutte_polynomial(G.complement(),x,y): print G.graph6_string() from time import sleep sleep(24*60*60) if c % 1000 == 0: print c
The motivation of this code stems from an open problem that I am now working on.
comment:29 Changed 7 years ago by
My guess is just that the cache in that version isn't reset after each run. If you add tutte_polynomial.cache.clear()
before the if tutte_polynomial(G,x,y) == tutte_polynomial(G.complement(),x,y):
line, you won't have that problem.
comment:30 Changed 7 years ago by
Good! I'll play with that and see what happens.
BTW, could you add yourself to the main TRAC page at the bottom so that I know what to write in the code under as the author ?
Changed 6 years ago by
comment:31 Changed 6 years ago by
Okay !
Attached is the nhansen's code factored into Sage. Before having any changes of being positively reviewed I we need to figure out how can we allow the users to use the edge selectors in the code and document that.
Let me know if you have any other comments and of course don't be shy to modify this yourself as well.
comment:32 Changed 6 years ago by
 Status changed from new to needs_review
comment:33 Changed 6 years ago by
Just a quick remark! The code computing the Tutte polynomial is correct (I reviewed that) so I only need someone to check if this patch is integrated correctly into Sage.
comment:34 Changed 6 years ago by
Hellooooooooo !!
If you just want comments on the integration into Sage, it would be nice if you could add it to the reference manual, perhaps rename the file to tutte_polynomial.py
, and add documentation to the new functions until sage coverage yourfile.py
says that everything is filled. In particular it would be nice if you could be more verbose about what VertexOrder
and MinimizeDegree
actually do :)
Oh, and people around do not like the raise ValueError, "something"
. They say it's not pep8 or not Python3ready, and prefer ValueError("something")
.
This contextmanager decorator really is a funny thing :)
Nathann
comment:35 Changed 6 years ago by
By the way, could you define what an "ear" is somewhere ? You say that it is a "sequence of vertices" which is a tad vague, and your code seems to imply somewhere that a vertex of degree 2 adjacent to two vertices of degree 3 is not an ear, while I thought that it was.
Well, .. :)
Nathann
comment:36 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:37 Changed 6 years ago by
 Description modified (diff)
comment:38 Changed 6 years ago by
 Description modified (diff)
 Work issues set to documentation
here is small cleanup patch. There remains to write doc for all functions.
for the bot:
apply trac_1314_tuttePoly.patch trac_1314_addon_fc.patch
comment:39 Changed 6 years ago by
Here is a new patch, that includes
 renaming of the file tutte_poly.py into tutte_polynomial.py
 inclusion into the reference manual
There still remains work to be done to have 100% doctesting and clean documentation
comment:40 Changed 6 years ago by
Hello!
What exactly is still required to be done? Also, is there a reason for renaming it to tutte_polynomial? I am wondering whether we should name it tuttepoly to be consistent with chrompoly?
comment:41 Changed 6 years ago by
There is nothing like chrompoly, the function is called
G.chromatic_polynomial
What remains to be done: add explanations, and document every function. See the previous comments (see comments 34 and 35 in particular)
comment:42 Changed 6 years ago by
Yes! But the file is called chrompoly.py. And so is the file for the matching polynomial called matchpoly.
OK I'll look into Nathann's comments!
comment:43 Changed 6 years ago by
I have started adding the doc, but there remains several functions with no doc.
In particular, it is necessary to explain more precisely what is an ear.
comment:44 Changed 6 years ago by
more doc, doctest coverage is now 65%
comment:45 Changed 6 years ago by
more doc, doctest coverage is now 95%
There remains only one function to doctest, but this is a decorator and I do not know what to do ! Could anybody please help ?
comment:46 Changed 6 years ago by
You could just call a function which is decorated with it, and add a #indirect doctest
flag to the corresponding doctest line.
Nathann
comment:47 Changed 6 years ago by
100 % doctested and almost ready for review !
But the doc of tutte_polynomial
does not appear, because it is cached (in a custom way, not by the usual cached_function
) !
comment:48 Changed 6 years ago by
Yep, I think this was before cached_function existed. Anyway, you can add "@sage_wraps(func)" before "def wrapper" to make things nicer on that front. I also feel that at the end of the tutte_polynomial function, we should add something like
if initial_call is True: tutte_polynomial.cache.clear()
so that the cache is valid for only the computation of one "tree". This does play bad with threads (which aren't used much). It might be better to just manually pass the cache along as a default argument throughout the call tree. I think that's probably best.
Changed 6 years ago by
comment:49 followup: ↓ 52 Changed 6 years ago by
 Status changed from needs_work to needs_review
The docs seems to be ok now, thanks Mike !
I have not taken care of the cache cleaning, as I do not know where to put the lines you suggested.
Still I think it deserves to be "need review"
comment:50 Changed 6 years ago by
 Keywords tutte graph added
 Milestone changed from sagewishlist to sage5.13
 Work issues changed from documentation to memory cleanup ?
comment:51 Changed 6 years ago by
comment:52 in reply to: ↑ 49 Changed 6 years ago by
I have not taken care of the cache cleaning, as I do not know where to put the lines you suggested.
At the end of the block if initial_call is True
, you can add the following :
ans = tutte_polynomial(G, initial_call=False, edge_selector=edge_selector) tutte_polynomial.cache.clear() return ans
Nathann
comment:53 Changed 6 years ago by
I think it's better to just have a cache=None default keyword. On the initial call, this can be detected and a new cache can be created or the user could pass in their own to use across multiple runs.
comment:54 Changed 6 years ago by
Mike, could you please add a review patch implementing what you suggest ? I do not feel able to guess and try to do it myself.
comment:55 Changed 6 years ago by
 Branch set to u/chapoton/1314
 Commit set to 34735d6ff56394bbbaedd3a778e1d2fc1bae14ea
comment:56 Changed 6 years ago by
Ping ?
comment:57 Changed 6 years ago by
This is now available via matroids.
comment:58 Changed 6 years ago by
What does that mean ? O_o
comment:59 Changed 6 years ago by
This mean that somebody else has done the job for matroids.
sage: Matroid(graphs.PetersenGraph()).tutte_polynomial() x^9 + 6*x^8 + 21*x^7 + 56*x^6 + 12*x^5*y + y^6 + 114*x^5 + 70*x^4*y + 30*x^3*y^2 + 15*x^2*y^3 + 10*x*y^4 + 9*y^5 + 170*x^4 + 170*x^3*y + 105*x^2*y^2 + 65*x*y^3 + 35*y^4 + 180*x^3 + 240*x^2*y + 171*x*y^2 + 75*y^3 + 120*x^2 + 168*x*y + 84*y^2 + 36*x + 36*y
comment:60 Changed 6 years ago by
Oh. Right. They enumerate all spanning trees, though. They would probably be glad to have another implementation :P
`
Nathann
comment:61 Changed 6 years ago by
Anyway Frederic, is this patch in needs_review
or in needs_work
(cf the caching thing above), and what is left to be reviewed ? Jernej said some time ago that the mathematical part of the algorithm was correct, but as it seems he wrote the code himself that does not count :P
Nathann
comment:62 Changed 6 years ago by
The Matroid implementation is hopelessly slow, and an optimized implementation as in this ticket would be most welcome for matroids too. Until that day, there is definitely a use for the implementation on this ticket!
comment:63 Changed 6 years ago by
Stefan : how should this method be exposed in the matroid code ? It only works for graph, and I guess matroids need something more general ?
Nathann
comment:64 Changed 6 years ago by
Yeah. The main idea (caching small graphs) generalizes to matroids, but the code needs to be changed properly, and probably tweaked a lot to get good speeds.
comment:65 Changed 6 years ago by
Okay. Does it mean that the function that this patch implements is of no direct use for Matroids, and that there is no need to expose it anywhere right now ?
Nathann
comment:66 Changed 6 years ago by
 Branch changed from u/chapoton/1314 to public/1314
 Commit 34735d6ff56394bbbaedd3a778e1d2fc1bae14ea deleted
 Description modified (diff)
 Reviewers set to Jernej Azarija, Nathann Cohen
Okayyyyyyy... Let's sum it up : Mike Hansen wrote the initial code, Jernej checked the math and cleaned bits of it, and Frédéric cleaned it again and add some documentation.
Cool. I just changed the branch as I have a couple of commits to add
 Rebase on 6.1.beta4
 An option to clean the cache, as mentionned earlier
I agree with the nonmathematical part of what was above. Soooooo we just need somebody to review my two commits and we are done.
Have fuuuuuuuuun !
Nathann
comment:67 Changed 6 years ago by
 Commit set to 6ef434eb8b91c3c1e3587ee3acbd08f7c0158e3d
comment:68 Changed 6 years ago by
 Work issues memory cleanup ? deleted
comment:69 Changed 6 years ago by
 Commit changed from 6ef434eb8b91c3c1e3587ee3acbd08f7c0158e3d to 63b04872bc064f46b2856b63e9fc2d4a4e1b2839
comment:70 Changed 6 years ago by
I've removed the initial_call
argument since it was prone to be abused (especially since it was the first one), and doing it this way should give some (marginal) speedup. I'm going to run some timings now. I'm also going to now try it by converting to use cached_function
.
Edit  I just realized I forgot to move the @_cache
to the internal function...
comment:71 followup: ↓ 78 Changed 6 years ago by
Okay, @cached_function
doesn't work because we can't pass a key function to it... (aside: I think such a feature would be quite useful) Back to the custom @_cache
.
With my changes (including some other optimizations):
sage: P = graphs.PetersenGraph() sage: %timeit P.tutte_polynomial() 1 loops, best of 3: 256 ms per loop
Before:
sage: P = graphs.PetersenGraph() sage: %timeit P.tutte_polynomial() 1000 loops, best of 3: 1.08 ms per loop
Now I'm currently perplexed...currently the best involves extra if statements, creation of parents, and unused arguments being passed. So we might just want to merge 6ef434e
instead. Still testing stuff...
comment:72 Changed 6 years ago by
 Commit changed from 63b04872bc064f46b2856b63e9fc2d4a4e1b2839 to 6ef434eb8b91c3c1e3587ee3acbd08f7c0158e3d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:73 Changed 6 years ago by
 Commit changed from 6ef434eb8b91c3c1e3587ee3acbd08f7c0158e3d to 7a55cf6c7f53c6d32a33907641b1a0db9bd4cb98
Branch pushed to git repo; I updated commit sha1. New commits:
7a55cf6  Tweaked the cache and set initial_call to last argument.

comment:74 Changed 6 years ago by
 Commit changed from 7a55cf6c7f53c6d32a33907641b1a0db9bd4cb98 to 5450ef20b36892ccbe3f6c3d5c9f049fad03cbb8
Branch pushed to git repo; I updated commit sha1. New commits:
5450ef2  Some other micro optimizations.

comment:75 Changed 6 years ago by
I put my changes in the branch u/tscrim/tutte_polynomial1314
and reverted back the public branch. It seems like I'm making a whole bunch of extra function calls that I have NO idea why...stuff it getting put into the cache as it should, everything is calling the internal function... IMO this is a better way of doing things, but something is being hypersensitive.
Anyways, I did make a few tweaks. I put initial_call
as the last argument to make the user less likely to touch it. I also allowed the cache to take nonkeyword arguments. I also made some other microoptimizations by moving the if edge_selector is None:
into the initial_call
block and moved the x,y = R.gens()
.
comment:76 Changed 6 years ago by
 Branch changed from public/1314 to u/tscrim/tutte_polynomial1314
 Cc SimonKing nbruin added
 Commit changed from 5450ef20b36892ccbe3f6c3d5c9f049fad03cbb8 to b02b9395dad4d69508a2897832b42892ce89e564
 Status changed from needs_review to needs_info
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 cced you here because we might need a good weak cache solution here and I'd like your thoughts and expertise.
New commits:
e896d88  Reworked the internal structure.

63b0487  Added doctest to the internal function.

466cec6  Moved the cache.

da55de3  Moved @_cached to its proper place.

7515b6b  Added the variables back.

91a3696  pyflakes cleanup.

b02b939  Cached the output of tutte_polynomial.

comment:77 followups: ↓ 79 ↓ 80 Changed 6 years ago by
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.
And what happens if the local cache generates values that exist in the global cache too ? :P
What do you cache then ? :P
I think you are overthinking very simple needs :)
Nathann
comment:78 in reply to: ↑ 71 Changed 6 years ago by
Replying to tscrim:
Okay,
@cached_function
doesn't work because we can't pass a key function to it...
I don't understand what you mean with this. Note that in the @_cached decorator you are not passing an arbitrary key function either: You have _cache_key hardcoded.
comment:79 in reply to: ↑ 77 ; followup: ↓ 81 Changed 6 years ago by
Replying to 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 fixedsize 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 overthought approach.
How big of a concern is it for recomputing Tutte polynomials for isomorphicbutnotidentical graphs?
Simon, I was trying to convert it to use the usual @cached_function
instead of the custom cache.
comment:80 in reply to: ↑ 77 Changed 6 years ago by
Replying to 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.
Where are the two merged? I can't see it in the code.
And what happens if the local cache generates values that exist in the global cache too ?
What should happen? You have two caches caching the same value. You clear the first cache. The value is still in the second cache.
comment:81 in reply to: ↑ 79 Changed 6 years ago by
Replying to tscrim:
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.
Sounds reasonable.
Simon, I was trying to convert it to use the usual
@cached_function
instead of the custom cache.
Can you use immutable graphs? See #15278, #15603, #15619 and #15622. These can be used as dictionary key and are thus acceptable input for a cached function.
comment:82 Changed 6 years ago by
The problem is we can't currently do any preprocessing on the arguments for @cached_function
(like we do for UniqueRepresentation
), or at least that I'm aware of. So if we pass in a mutable graph, we can't convert it into something immutable and @cached_function
returns an error (or do any other form of standardization).
comment:83 Changed 6 years ago by
 Branch changed from u/tscrim/tutte_polynomial1314 to u/mhansen/tutte_polynomial1314
comment:84 Changed 6 years ago by
 Commit changed from b02b9395dad4d69508a2897832b42892ce89e564 to b279c3363f2e06dab8332c8ce8f470480ccf966d
I pushed a change which just makes the cache an optional keyword argument. All of the subcalls to tutte_polynomial use the same cache as the toplevel one. Additionally, if the use does not want the cache destroyed at the end of the computation, they just provide their own dictionary to the method.
New commits:
b279c33  #1314: Make the cache an argument instead of storing it on the decorator

comment:85 followup: ↓ 87 Changed 6 years ago by
I like the elegance of it; so positive review from me. Nathann and anyone else, any objections?
comment:86 Changed 6 years ago by
 Status changed from needs_info to needs_review
comment:87 in reply to: ↑ 85 Changed 6 years ago by
I like the elegance of it; so positive review from me. Nathann and anyone else, any objections?
Nono, it's fine :)
Nathann
comment:88 Changed 6 years ago by
 Status changed from needs_review to positive_review
For a future ticket with #15657  make Graph.tutte_polynomial
a @cached_method
once @cached_method
can ignore the cache argument.
comment:89 Changed 6 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
http://homepages.mcs.vuw.ac.nz/~djp/tutte/
This software could be pretty useful.... But I know nothing about license matters :
The majority of files are currently under the following simple and quite unrestrictive license:
This license may not be removed from any of the files in question.
This software makes use of Brendan McKay?'s excellent "Nauty" program for determining (amongst other things) whether two graphs are isomorphic or not. You can find more information about this program here: http://cs.anu.edu.au/~bdm/nauty
All files from the Nauty program are located in the nauty/ subdirectory. The following license applies to all files in the nauty/ directory (see nauty.h for more details):
So in the end it reads like the license is at least as GPLuncompatible as Nauty's, and will then have to be included as an external software...