Opened 6 years ago
Closed 3 months ago
#1314 closed enhancement (fixed)
graphs: calculate tutte polynomial
Reported by: | jason | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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_polynomial-1314 (Commits) | Commit: | b279c3363f2e06dab8332c8ce8f470480ccf966d |
Dependencies: | Stopgaps: |
Description (last modified by ncohen)
Implements a Graph.tutte_polynomial method
Attachments (4)
Change History (93)
comment:1 Changed 6 years ago by jason
- Summary changed from [graphs] calculate tutte polynomial to graphs: calculate tutte polynomial
comment:2 Changed 6 years ago by rlm
- Component changed from combinatorics to graph theory
- Keywords graphs removed
- Owner changed from mhansen to rlm
comment:3 follow-up: ↓ 4 Changed 5 years ago by ncohen
comment:4 in reply to: ↑ 3 Changed 5 years ago by rlm
Replying to ncohen:
So in the end it reads like the license is at least as GPL-uncompatible 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 4 years ago by timmcmillen
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 22 months ago by jeremy.l.martin
- 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 22 months ago by sdenton
- Cc lkeough sdenton added
comment:9 Changed 22 months ago by ddrake
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 22 months ago by mhampton
- Cc ncohen added
comment:11 Changed 22 months ago by lkeough
Tutte polynomial also needs code to determine whether an edge is a cut edge. You can find this at ticket #13242.
comment:12 follow-up: ↓ 13 Changed 22 months ago by 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).
comment:13 in reply to: ↑ 12 Changed 22 months ago by jeremy.l.martin
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 22 months ago by mhansen
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 22 months ago by lkeough
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 22 months ago by lkeough
I attached Jeremy's code as Tuttepolynomial.sage in case anyone else wants to timeit.
comment:17 follow-up: ↓ 18 Changed 22 months ago by mhansen
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 22 months ago by lkeough
Replying to mhansen:
x and y 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 the cache_key method in my patch.
Will do!
comment:19 Changed 22 months ago by mhansen
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 22 months ago by mhansen
comment:20 Changed 21 months ago by Stefan
- Cc Stefan added
comment:21 Changed 12 months ago by azi
What is the current status of this code?
comment:22 Changed 12 months ago by azi
- Cc azi added
comment:23 Changed 12 months ago by mhansen
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 follow-up: ↓ 25 Changed 12 months ago by azi
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 12 months ago by mhansen
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 12 months ago by azi
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 12 months ago by mhansen
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 12 months ago by azi
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 12 months ago by mhansen
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 12 months ago by azi
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 10 months ago by azi
comment:31 Changed 10 months ago by azi
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 10 months ago by azi
- Status changed from new to needs_review
comment:33 Changed 10 months ago by azi
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 10 months ago by ncohen
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 Python3-ready, and prefer ValueError("something").
This contextmanager decorator really is a funny thing :-)
Nathann
comment:35 Changed 10 months ago by ncohen
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 10 months ago by ncohen
- Status changed from needs_review to needs_work
comment:37 Changed 10 months ago by ncohen
- Description modified (diff)
comment:38 Changed 9 months ago by chapoton
- Description modified (diff)
- Work issues set to documentation
here is small clean-up 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 9 months ago by chapoton
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 9 months ago by azi
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 9 months ago by chapoton
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 9 months ago by azi
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 8 months ago by chapoton
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 8 months ago by chapoton
more doc, doctest coverage is now 65%
comment:45 Changed 7 months ago by chapoton
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 7 months ago by ncohen
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 7 months ago by chapoton
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 7 months ago by mhansen
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 7 months ago by chapoton
comment:49 follow-up: ↓ 52 Changed 7 months ago by chapoton
- 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 months ago by chapoton
- Keywords tutte graph added
- Milestone changed from sage-wishlist to sage-5.13
- Work issues changed from documentation to memory cleanup ?
comment:51 Changed 6 months ago by chapoton
comment:52 in reply to: ↑ 49 Changed 6 months ago by ncohen
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 months ago by mhansen
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 months ago by chapoton
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 4 months ago by chapoton
- Branch set to u/chapoton/1314
- Commit set to 34735d6ff56394bbbaedd3a778e1d2fc1bae14ea
comment:56 Changed 4 months ago by ncohen
Ping ?
comment:57 Changed 4 months ago by chapoton
This is now available via matroids.
comment:58 Changed 4 months ago by ncohen
What does that mean ? O_o
comment:59 Changed 4 months ago by chapoton
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 4 months ago by ncohen
Oh. Right. They enumerate all spanning trees, though. They would probably be glad to have another implementation :-P`
Nathann
comment:61 Changed 4 months ago by ncohen
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 4 months ago by Stefan
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 4 months ago by ncohen
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 4 months ago by Stefan
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 4 months ago by ncohen
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 4 months ago by ncohen
- 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 non-mathematical 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 4 months ago by git
- Commit set to 6ef434eb8b91c3c1e3587ee3acbd08f7c0158e3d
comment:68 Changed 4 months ago by ncohen
- Work issues memory cleanup ? deleted
comment:69 Changed 4 months ago by git
- Commit changed from 6ef434eb8b91c3c1e3587ee3acbd08f7c0158e3d to 63b04872bc064f46b2856b63e9fc2d4a4e1b2839
comment:70 Changed 4 months ago by tscrim
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 follow-up: ↓ 78 Changed 4 months ago by tscrim
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 4 months ago by git
- 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 4 months ago by git
- 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 4 months ago by git
- 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 4 months ago by tscrim
I put my changes in the branch u/tscrim/tutte_polynomial-1314 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 hyper-sensitive.
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 non-keyword arguments. I also made some other micro-optimizations by moving the if edge_selector is None: into the initial_call block and moved the x,y = R.gens().
comment:76 Changed 4 months ago by tscrim
- Branch changed from public/1314 to u/tscrim/tutte_polynomial-1314
- 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 cc-ed 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 follow-ups: ↓ 79 ↓ 80 Changed 4 months ago by 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.
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 4 months ago by SimonKing
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 ; follow-up: ↓ 81 Changed 4 months ago by tscrim
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 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.
comment:80 in reply to: ↑ 77 Changed 4 months ago by SimonKing
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 4 months ago by SimonKing
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 4 months ago by tscrim
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 4 months ago by mhansen
- Branch changed from u/tscrim/tutte_polynomial-1314 to u/mhansen/tutte_polynomial-1314
comment:84 Changed 4 months ago by mhansen
- Commit changed from b02b9395dad4d69508a2897832b42892ce89e564 to b279c3363f2e06dab8332c8ce8f470480ccf966d
I pushed a change which just makes the cache an optional keyword argument. All of the sub-calls to tutte_polynomial use the same cache as the top-level 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 follow-up: ↓ 87 Changed 3 months ago by tscrim
I like the elegance of it; so positive review from me. Nathann and anyone else, any objections?
comment:86 Changed 3 months ago by tscrim
- Status changed from needs_info to needs_review
comment:87 in reply to: ↑ 85 Changed 3 months ago by ncohen
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 3 months ago by tscrim
- 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 3 months ago by vbraun
- 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 GPL-uncompatible as Nauty's, and will then have to be included as an external software...