chromatic_polynomial - fixed memory leak and added new test cases #14527

sagetrac-azi · 2013-05-04T08:34:19Z

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!

CC: ncohen stefan slani

Component: graph theory

Author: Jernej Azarija

Reviewer: Nathann Cohen

Merged: sage-5.10.beta2

Issue created by migration from https://trac.sagemath.org/ticket/14527

nathanncohen · 2013-05-04T08:51:44Z

comment:2

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

Nathann

sagetrac-azi · 2013-05-04T09:24:14Z

comment:3

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

nathanncohen · 2013-05-04T09:32:57Z

comment:4

Attachment: trac_14527_chrompoly2.patch.gz

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

nathanncohen · 2013-05-04T09:43:37Z

comment:5

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

sagetrac-azi · 2013-05-04T10:17:35Z

comment:6

Replying to @nathanncohen:

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

sagetrac-azi · 2013-05-04T10:19:44Z

comment:7

Replying to @nathanncohen:

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

nathanncohen · 2013-05-04T10:20:59Z

comment:8

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

sagetrac-azi · 2013-05-04T10:27:54Z

comment:9

Replying to @nathanncohen:

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

nathanncohen · 2013-05-04T10:30:57Z

comment:10

Quickly contract an edge uv ? What about that ?

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

nathanncohen · 2013-05-04T10:31:43Z

comment:11

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

Nathann

nathanncohen · 2013-05-04T10:46:27Z

comment:12

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

sagetrac-azi · 2013-05-04T10:53:28Z

comment:13

10 it is!

nathanncohen · 2013-05-04T10:56:56Z

comment:14

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

nathanncohen · 2013-05-04T10:57:41Z

comment:15

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.

nathanncohen · 2013-05-04T10:57:57Z

comment:16

Apply trac_14527_chrompoly.patch, trac_14527_chrompoly2.patch

nathanncohen · 2013-05-04T10:58:48Z

comment:17

Oh O_o

Looks like your new example is missing a ::

Nathann

sagetrac-azi · 2013-05-04T11:02:43Z

comment:18

Attachment: trac_14527_chrompoly.patch.gz

Fixed.

nathanncohen · 2013-05-04T11:04:04Z

comment:19

Good to go !

Nathann

sagetrac-azi · 2013-05-04T11:31:01Z

Author: Jernej Azarija

jdemeyer · 2013-05-04T12:44:15Z

Reviewer: Nathann Cohen

jdemeyer · 2013-05-07T09:07:47Z

Merged: sage-5.10.beta2

sagetrac-azi mannequin added this to the sage-5.10 milestone May 4, 2013

sagetrac-azi mannequin added c: graph theory labels May 4, 2013

sagetrac-azi mannequin assigned jasongrout, nathanncohen and rlmill May 4, 2013

sagetrac-azi mannequin added the s: needs review label May 4, 2013

This comment has been minimized.

Sign in to view

nathanncohen mannequin added s: positive review and removed s: needs review labels May 4, 2013

jdemeyer removed the s: positive review label May 7, 2013

jdemeyer closed this as completed May 7, 2013

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

chromatic_polynomial - fixed memory leak and added new test cases #14527

chromatic_polynomial - fixed memory leak and added new test cases #14527

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

This comment has been minimized.

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

jdemeyer commented May 4, 2013

jdemeyer commented May 7, 2013

chromatic_polynomial - fixed memory leak and added new test cases #14527

chromatic_polynomial - fixed memory leak and added new test cases #14527

Comments

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

This comment has been minimized.

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

nathanncohen mannequin commented May 4, 2013

sagetrac-azi mannequin commented May 4, 2013

jdemeyer commented May 4, 2013

jdemeyer commented May 7, 2013