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)

Tuttepolynomial.sage (4.9 KB) - added by lkeough 22 months ago.
You also need the patches from #13242
tutte.sage (13.3 KB) - added by mhansen 22 months ago.
trac_1314_tuttePoly.patch (14.6 KB) - added by azi 10 months ago.
trac_1314_addon_fc.patch (24.1 KB) - added by chapoton 7 months ago.

Download all attachments as: .zip

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: Changed 5 years ago by ncohen

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:

"(C) Copyright David James Pearce and Gary Haggard, 2007.

Permission to copy, use, modify, sell and distribute this software is granted provided this copyright notice appears in all copies. This software is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.

Email: david.pearce@…"

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):

"Copyright (1984-2004) Brendan McKay?. All rights reserved. Permission

is hereby given for use and/or distribution with the exception of sale for profit or application with nontrivial military significance. You must not remove this copyright notice, and you must document any changes that you make to this program. This software is subject to this copyright only, irrespective of any copyright attached to any package of which this is a part.

This program is only provided "as is". No responsibility will be taken by the author, his employer or his pet rabbit for any misfortune which befalls you because of its use. I don't think it will delete all your files, burn down your computer room or turn your children against you, but if it does: stiff cheddar. On the other hand, I very much welcome bug reports, or at least I would if there were any bugs.

RIP, 1989


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...

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:5 Changed 5 years ago by mvngu

  • Cc mvngu added

CC myself.

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: 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

x2*y2 + x*y3 + x3 + x2*y + x*y2 + x2 + x*y

The actual Tutte polynomial of K4 is x3 + 3*x2 + y3 + 4*x*y + 3*y2 + 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*x4 + 22*(x + y)2*x + 8*(x + y)*((x + y)*x + y2 + x + y)*x + (x4 + x3 + (x + y)*(x2 + x + y) + x2 + x + y)*x2 + ((x + y)2*x + (x + y)2 + y3 + ((x + y)*x2 + (x + y)*x + y2 + x + y)*x + y2 + x + y)*x2 + 22*(x + y)2 + 13*(y2 + x + y)2 + 14*x3 + 22*y3 + 14*(x + y)*(x2 + x + y) + 4*(y2 + x + y)*((x + y)2 + y3 + y2 + x + y) + 5*((x + y)*x + (x2 + x + y)*x + y2 + x + y)*y + 9*((x + y)*x2 + (x + y)*x + y2 + x + y)*x + 9*(x4 + x3 + x2 + x + y)*x + ((x + y)2*x + (x + y)2 + y3 + ((x + y)*x2 + (x + y)*x + y2 + x + y)*x + y2 + x + y)*x + (x4 + (x4 + x3 + x2 + x + y)*x2 + x3 + (x + y)*(x2 + x + y) + (x4 + x3 + x2 + x + y)*x + x2 + x + y)*x + 4*(x4 + (x + y)2*x + (x + y)2 + x3 + y3 + (x + y)*(x2 + x + y) + ((x + y)*x2 + (x + y)*x + y2 + x + y)*x + (x4 + x3 + x2 + x + y)*x + x2 + y2 + 2*x + 2*y)*x + 2*(x4 + (x + y)2*x + (x + y)2 + x3 + y3 + (x + y)*(x2 + x + y) + ((x + y)*x2 + (x + y)*x + y2 + x + y)*x + (x4 + x3 + x2 + x + y)*x + (x4 + x3 + (x + y)*(x2 + x + y) + (x4 + x3 + x2 + x + y)*x + x2 + x + y)*x + x2 + y2 + 2*x + 2*y)*x + 2*(x4 + 2*(x +....

And this is the output of Jeremy's: x9 + 6*x8 + 21*x7 + 56*x6 + 12*x5*y + 114*x5 + y6 + 70*x4*y + 30*x3*y2 + 15*x2*y3 + 10*x*y4 + 170*x4 + 180*x3 + 120*x2 + 9*y5 + 170*x3*y + 105*x2*y2 + 65*x*y3 + 35*y4 + 240*x2*y + 171*x*y2 + 75*y3 + 168*x*y + 84*y2 + 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?

Changed 22 months ago by lkeough

You also need the patches from #13242

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: 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 22 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: 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!

Last edited 9 months ago by azi (previous) (diff)

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: 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

  • Authors set to Mike Hansen

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

New commits:

34735d6trac #1314 cleanup of tutte patch + 100 % doc
e411f6b# Sat Jun 22 12:10:02 2013 +0200

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

  • Authors changed from Mike Hansen to Mike Hansen, Frédéric Chapoton, Jernej Azarija
  • 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

Branch pushed to git repo; I updated commit sha1. New commits:

e411f6b# Sat Jun 22 12:10:02 2013 +0200
34735d6trac #1314 cleanup of tutte patch + 100 % doc
f515a6etrac #1314: Rebase ono 6.1.beta4
6ef434etrac #1314: cleaning the cache before leaving

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

Branch pushed to git repo; I updated commit sha1. New commits:

e896d88Reworked the internal structure.
63b0487Added doctest to the internal function.

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...

Last edited 4 months ago by tscrim (previous) (diff)

comment:71 follow-up: 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:

7a55cf6Tweaked 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:

5450ef2Some 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:

e896d88Reworked the internal structure.
63b0487Added doctest to the internal function.
466cec6Moved the cache.
da55de3Moved @_cached to its proper place.
7515b6bAdded the variables back.
91a3696pyflakes cleanup.
b02b939Cached the output of tutte_polynomial.

comment:77 follow-ups: 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: 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: 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
Note: See TracTickets for help on using tickets.