# Minor improvement to chromatic number

If any one wants to, here is a very minor change you could make in the calculation of chromatic number that would make it faster! The change is to take the line that says

if len(G.edges()) == 0:

to

if G.size() == 0:

def chromatic_number(G):
r"""
Returns the minimal number of colors needed to color the
vertices of the graph G.

EXAMPLES::

sage: from sage.graphs.graph_coloring import chromatic_number
sage: G = Graph({0:[1,2,3],1:[2]})
sage: chromatic_number(G)
3

sage: G = graphs.PetersenGraph()
sage: G.chromatic_number()
3
"""
o = G.order()
if o == 0:
return 0
if len(G.edges()) == 0:
return 1
elif G.is_bipartite(): #can we do it in linear time?
return 2
else: #counting cliques is faster than our brute-force method...
m = G.clique_number()
if m >= o-1: #marginal improvement... if there's an o-1 clique and not an o clique, don't waste our time coloring.
return m
for n in range(m,o+1):
for C in all_graph_colorings(G,n):
return n


Update: Nathann has already implemented this help so thanks! I thought I would give a quick update just on the timing since kcrisman asked. In fact, g.size() is much faster than len(g.edges), relatively, though the magnitudes are so small that it probably doesn't affect the chromatic number much. However, if you wanted to find the chromatic number on all graphs of order 11, over 1 billion, which I did recently, if the average time savings is 70 microseconds, that's a total savings of 70000 seconds, which is nearly 20 hours. And, since Nathann also made a similar change on all_graph_colorings, which is used in chromatic_number, the savings could be in the neighborhood of 40 hours. By the way, the time savings from len(g.vertices()) to g.order() is 8 microseconds on the graph I randomly generated.

g=graphs.RandomGNP(11,0.6)


timeit('len(g.edges())')


625 loops, best of 3: 72.9 µs per loop

timeit('g.size()')


625 loops, best of 3: 1.12 µs per loop

edit retag close merge delete

Do you have any timings for comparing?

( 2012-09-18 21:21:59 +0200 )edit
2

By the way, this is an ideal thing to post on sage-devel or even to just open a new Trac ticket - it's easy to get an account ;-)

( 2012-09-18 21:22:22 +0200 )edit

Thanks for the timing info! That's cool.

( 2012-09-21 23:46:25 +0200 )edit

@kcrisman I also did a bigger graph, something like 25 vertices. In that case, the g.size() was still at about 1.12 microseconds, but the len(g.edges()) was up to 330 microseconds, or something like that.

( 2012-09-22 10:36:42 +0200 )edit

Sort by » oldest newest most voted

Heeeeeeeeeeeeeere it is !

http://trac.sagemath.org/sage_trac/ti...

Nathann

more

Oh, I see, you just included this little bit in that patch too. But, you actually fixed a similar problem like the one I mentioned, but NOT the one I mentioned. Right???

( 2012-09-19 22:17:03 +0200 )edit

Isn't your change the last thing listed in the patch? http://trac.sagemath.org/sage_trac/attachment/ticket/13510/trac_13510.patch

( 2012-09-19 23:02:25 +0200 )edit

@jasonGrout Alright, you are correct. I was confused because he also fixed other similar problems and I didn't notice the gray line in between. Thanks Nathann!

( 2012-09-20 17:56:51 +0200 )edit