ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 22 Sep 2012 03:36:42 -0500Minor improvement to chromatic numberhttp://ask.sagemath.org/question/9330/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)
Start with random graph of order 11
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
Tue, 18 Sep 2012 10:20:48 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/Comment by kcrisman for <p>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</p>
<p>if len(G.edges()) == 0:</p>
<p>to</p>
<p>if G.size() == 0:</p>
<pre><code>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
</code></pre>
<p>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.</p>
<pre><code>g=graphs.RandomGNP(11,0.6)
</code></pre>
<p>Start with random graph of order 11</p>
<pre><code>timeit('len(g.edges())')
</code></pre>
<p>625 loops, best of 3: 72.9 µs per loop</p>
<pre><code>timeit('g.size()')
</code></pre>
<p>625 loops, best of 3: 1.12 µs per loop</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19045#post-id-19045Do you have any timings for comparing?Tue, 18 Sep 2012 14:21:59 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19045#post-id-19045Comment by G-Sage for <p>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</p>
<p>if len(G.edges()) == 0:</p>
<p>to</p>
<p>if G.size() == 0:</p>
<pre><code>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
</code></pre>
<p>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.</p>
<pre><code>g=graphs.RandomGNP(11,0.6)
</code></pre>
<p>Start with random graph of order 11</p>
<pre><code>timeit('len(g.edges())')
</code></pre>
<p>625 loops, best of 3: 72.9 µs per loop</p>
<pre><code>timeit('g.size()')
</code></pre>
<p>625 loops, best of 3: 1.12 µs per loop</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19030#post-id-19030@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.Sat, 22 Sep 2012 03:36:42 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19030#post-id-19030Comment by kcrisman for <p>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</p>
<p>if len(G.edges()) == 0:</p>
<p>to</p>
<p>if G.size() == 0:</p>
<pre><code>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
</code></pre>
<p>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.</p>
<pre><code>g=graphs.RandomGNP(11,0.6)
</code></pre>
<p>Start with random graph of order 11</p>
<pre><code>timeit('len(g.edges())')
</code></pre>
<p>625 loops, best of 3: 72.9 µs per loop</p>
<pre><code>timeit('g.size()')
</code></pre>
<p>625 loops, best of 3: 1.12 µs per loop</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19044#post-id-19044By 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 ;-)Tue, 18 Sep 2012 14:22:22 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19044#post-id-19044Comment by kcrisman for <p>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</p>
<p>if len(G.edges()) == 0:</p>
<p>to</p>
<p>if G.size() == 0:</p>
<pre><code>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
</code></pre>
<p>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.</p>
<pre><code>g=graphs.RandomGNP(11,0.6)
</code></pre>
<p>Start with random graph of order 11</p>
<pre><code>timeit('len(g.edges())')
</code></pre>
<p>625 loops, best of 3: 72.9 µs per loop</p>
<pre><code>timeit('g.size()')
</code></pre>
<p>625 loops, best of 3: 1.12 µs per loop</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19031#post-id-19031Thanks for the timing info! That's cool.Fri, 21 Sep 2012 16:46:25 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19031#post-id-19031Answer by Nathann for <p>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</p>
<p>if len(G.edges()) == 0:</p>
<p>to</p>
<p>if G.size() == 0:</p>
<pre><code>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
</code></pre>
<p>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.</p>
<pre><code>g=graphs.RandomGNP(11,0.6)
</code></pre>
<p>Start with random graph of order 11</p>
<pre><code>timeit('len(g.edges())')
</code></pre>
<p>625 loops, best of 3: 72.9 µs per loop</p>
<pre><code>timeit('g.size()')
</code></pre>
<p>625 loops, best of 3: 1.12 µs per loop</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?answer=14047#post-id-14047Heeeeeeeeeeeeeere it is !
http://trac.sagemath.org/sage_trac/ticket/13510
NathannWed, 19 Sep 2012 12:35:51 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?answer=14047#post-id-14047Comment by Jason Grout for <p>Heeeeeeeeeeeeeere it is !</p>
<p><a href="http://trac.sagemath.org/sage_trac/ticket/13510">http://trac.sagemath.org/sage_trac/ti...</a></p>
<p>Nathann</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19038#post-id-19038Isn't your change the last thing listed in the patch? http://trac.sagemath.org/sage_trac/attachment/ticket/13510/trac_13510.patchWed, 19 Sep 2012 16:02:25 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19038#post-id-19038Comment by G-Sage for <p>Heeeeeeeeeeeeeere it is !</p>
<p><a href="http://trac.sagemath.org/sage_trac/ticket/13510">http://trac.sagemath.org/sage_trac/ti...</a></p>
<p>Nathann</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19035#post-id-19035@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!Thu, 20 Sep 2012 10:56:51 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19035#post-id-19035Comment by G-Sage for <p>Heeeeeeeeeeeeeere it is !</p>
<p><a href="http://trac.sagemath.org/sage_trac/ticket/13510">http://trac.sagemath.org/sage_trac/ti...</a></p>
<p>Nathann</p>
http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19039#post-id-19039Oh, 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???Wed, 19 Sep 2012 15:17:03 -0500http://ask.sagemath.org/question/9330/minor-improvement-to-chromatic-number/?comment=19039#post-id-19039