Opened 9 years ago

Closed 9 years ago

#14527 closed enhancement (fixed)

chromatic_polynomial - fixed memory leak and added new test cases

Reported by: azi Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.10
Component: graph theory Keywords:
Cc: ncohen stefan slani Merged in: sage-5.10.beta2
Authors: Jernej Azarija Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ncohen)

This patch fixes a minor memory leak in the chromatic polynomial code. It appears to me that the mpz variables should be freed at the end of the function.

I have also added additional tests.

The code appears not to be practical for graphs of order +15. I am wondering if we could gain some speed by using memoization. It would complicate the code quite a bit but it might be a drastic improvement!

Attachments (2)

trac_14527_chrompoly2.patch (518 bytes) - added by azi 9 years ago.
trac_14527_chrompoly.patch (1.6 KB) - added by azi 9 years ago.

Download all attachments as: .zip

Change History (24)

comment:1 follow-up: Changed 9 years ago by azi

  • Status changed from new to needs_review

comment:2 in reply to: ↑ 1 Changed 9 years ago by ncohen

Looks right ! Is there any reason why every coeffs[i] and m should not be cleared too ?

Nathann

comment:3 follow-up: Changed 9 years ago by azi

m is a single mpz_t variable and is correctly freed in this patch. As for coeffs[i] you're right - nice catch. That should be freed as well IMO.

I've attached a patch fixing this remark as well. Can you check if it makes sense to stack patches like that?

PS. What is the status of the edge contraction code? I would like to test this memonization thing that I talk about..

Changed 9 years ago by azi

comment:4 in reply to: ↑ 3 ; follow-up: Changed 9 years ago by ncohen

I've attached a patch fixing this remark as well. Can you check if it makes sense to stack patches like that?

Yeah it does. We do it often when we use Mercurial Queue, but if you don't perhaps it is not worth trying it... considering that we will switch to git soon (wheeeeeeeeeen ??)

PS. What is the status of the edge contraction code? I would like to test this memonization thing that I talk about..

The status ? Well, it has been there for years and never touched again :

~/sage/graphs$ hg log -r 13627
changeset:   13627:50d1cb107fc3
user:        Robert Miller <rlm@rlmiller.org>
date:        Thu Jan 14 00:38:41 2010 -0800
summary:     Added tag 4.3.1.alpha3 for changeset 79eb28e13210

~/sage/graphs$ hg log -r 8924
changeset:   8924:ec7c9745bc66
user:        Robert L. Miller <rlm@rlmiller.org>
date:        Tue Mar 11 16:41:10 2008 -0700
summary:     chromatic polynomial revisited

Nathann

comment:5 follow-up: Changed 9 years ago by ncohen

To me this test on a random graph is too long, too :-/

sage: %time G.chromatic_polynomial()
CPU times: user 9.76 s, sys: 0.00 s, total: 9.76 s
Wall time: 9.81 s
x^13 - 57*x^12 + 1486*x^11 - 23364*x^10 + 245983*x^9 - 1820644*x^8 + 9675792*x^7 - 37032141*x^6 + 100750221*x^5 - 188744964*x^4 + 229141077*x^3 - 160012790*x^2 + 47819400*x

I understand what you want to do with these long tests, but I really think that people around will not like the side-effects if we keep on like that :-/

Nathann

comment:6 in reply to: ↑ 4 ; follow-up: Changed 9 years ago by azi

Replying to ncohen:

I've attached a patch fixing this remark as well. Can you check if it makes sense to stack patches like that?

Yeah it does. We do it often when we use Mercurial Queue, but if you don't perhaps it is not worth trying it... considering that we will switch to git soon (wheeeeeeeeeen ??)

Interesting. What is the reason for switching to Git? Its because Linus uses it right???

PS. What is the status of the edge contraction code? I would like to test this memonization thing that I talk about..

Nonono not this! I was asking about the code that you guys were doing that allows *contracting* an edge of a graph. I am not sure this thing was accepted yet?

The status ? Well, it has been there for years and never touched again :

~/sage/graphs$ hg log -r 13627
changeset:   13627:50d1cb107fc3
user:        Robert Miller <rlm@rlmiller.org>
date:        Thu Jan 14 00:38:41 2010 -0800
summary:     Added tag 4.3.1.alpha3 for changeset 79eb28e13210

~/sage/graphs$ hg log -r 8924
changeset:   8924:ec7c9745bc66
user:        Robert L. Miller <rlm@rlmiller.org>
date:        Tue Mar 11 16:41:10 2008 -0700
summary:     chromatic polynomial revisited

Nathann

comment:7 in reply to: ↑ 5 Changed 9 years ago by azi

Replying to ncohen:

To me this test on a random graph is too long, too :-/

sage: %time G.chromatic_polynomial()
CPU times: user 9.76 s, sys: 0.00 s, total: 9.76 s
Wall time: 9.81 s
x^13 - 57*x^12 + 1486*x^11 - 23364*x^10 + 245983*x^9 - 1820644*x^8 + 9675792*x^7 - 37032141*x^6 + 100750221*x^5 - 188744964*x^4 + 229141077*x^3 - 160012790*x^2 + 47819400*x

I understand what you want to do with these long tests, but I really think that people around will not like the side-effects if we keep on like that :-/

Nathann

I understand yes. Somehow I was thought to always extensively and insanely test software. The fact that i use this for research made me exaggerate even more.

I still think that's the way to go but I completely agree with you that in the current setting this might not be the best way to go :-)

comment:8 in reply to: ↑ 6 ; follow-up: Changed 9 years ago by ncohen

Interesting. What is the reason for switching to Git? Its because Linus uses it right???

From my point of view, it is because some Sage developpers think that it is great. And I've been contaminated by their enthusiasm, even though I barely used it :-P

Nonono not this! I was asking about the code that you guys were doing that allows *contracting* an edge of a graph. I am not sure this thing was accepted yet?

Oh. I don't know where it stands. I hate that patch. But honestly, if you want efficient code, rewrite your own. It is not a long code anyway.

Nathann

comment:9 in reply to: ↑ 8 Changed 9 years ago by azi

Replying to ncohen:

Interesting. What is the reason for switching to Git? Its because Linus uses it right???

From my point of view, it is because some Sage developpers think that it is great. And I've been contaminated by their enthusiasm, even though I barely used it :-P

Nonono not this! I was asking about the code that you guys were doing that allows *contracting* an edge of a graph. I am not sure this thing was accepted yet?

Oh. I don't know where it stands. I hate that patch. But honestly, if you want efficient code, rewrite your own. It is not a long code anyway.

Yes but I just wanted to quickly test something and not bother writing an edge contraction routine :-/ Do you happen to be able to extract that quickly from the patch or something? I just need to be able to contract an edge of a graph (ignoring loops & multiple edges)

Nathann

comment:10 Changed 9 years ago by ncohen

Quickly contract an edge uv ? What about that ?

g.add_edges([(u,x) for x in g.neighbors(v)])
g.delete_vertex(v)

comment:11 Changed 9 years ago by ncohen

Oh. I mean, in a graph that does not allow multiple edges :-P

Nathann

comment:12 Changed 9 years ago by ncohen

So, what do you decide with this patch ? If you make this 13 a 10 I agree with it, otherwise I will let somebody else give it a review. You tell me !

Nathann

comment:13 Changed 9 years ago by azi

10 it is!

comment:14 Changed 9 years ago by ncohen

  • Description modified (diff)

Okayyyyy, thanks ! :-)

By the way, when there are several patches on a ticket, Jeroen likes to have a message in the trac's description saying how they are to be applied. Like the one I just added.

Have fuuuuuuuuuuuuuuun !

Nathann

comment:15 Changed 9 years ago by ncohen

And the following message is there to tell the patchbot (the circle that you see at the top of each ticket's page) how to apply the patches.

comment:16 Changed 9 years ago by ncohen

Apply trac_14527_chrompoly.patch, trac_14527_chrompoly2.patch

comment:17 Changed 9 years ago by ncohen

Oh O_o

Looks like your new example is missing a ::

Nathann

Changed 9 years ago by azi

comment:18 Changed 9 years ago by azi

Fixed.

comment:19 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

Good to go !

Nathann

comment:20 Changed 9 years ago by azi

  • Authors set to Jernej Azarija

comment:21 Changed 9 years ago by jdemeyer

  • Reviewers set to Nathann Cohen

comment:22 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.10.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.