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: |
Description (last modified by )
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)
Change History (24)
comment:1 follow-up: ↓ 2 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 in reply to: ↑ 1 Changed 9 years ago by
comment:3 follow-up: ↓ 4 Changed 9 years ago by
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
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 6 Changed 9 years ago by
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: ↓ 7 Changed 9 years ago by
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: ↓ 8 Changed 9 years ago by
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 revisitedNathann
comment:7 in reply to: ↑ 5 Changed 9 years ago by
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*xI 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: ↓ 9 Changed 9 years ago by
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
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
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
Oh. I mean, in a graph that does not allow multiple edges :-P
Nathann
comment:12 Changed 9 years ago by
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
10 it is!
comment:14 Changed 9 years ago by
- 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
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
Apply trac_14527_chrompoly.patch, trac_14527_chrompoly2.patch
comment:17 Changed 9 years ago by
Oh O_o
Looks like your new example is missing a ::
Nathann
Changed 9 years ago by
comment:18 Changed 9 years ago by
Fixed.
comment:19 Changed 9 years ago by
- Status changed from needs_review to positive_review
Good to go !
Nathann
comment:20 Changed 9 years ago by
comment:21 Changed 9 years ago by
- Reviewers set to Nathann Cohen
comment:22 Changed 9 years ago by
- Merged in set to sage-5.10.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
Looks right ! Is there any reason why every
coeffs[i]
andm
should not be cleared too ?Nathann