Ask Your Question
2

Minor improvement to chromatic number

asked 2012-09-18 17:20:48 +0200

G-Sage gravatar image

updated 2012-09-21 14:19:11 +0200

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

edit retag flag offensive close merge delete

Comments

Do you have any timings for comparing?

kcrisman gravatar imagekcrisman ( 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 ;-)

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

Thanks for the timing info! That's cool.

kcrisman gravatar imagekcrisman ( 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.

G-Sage gravatar imageG-Sage ( 2012-09-22 10:36:42 +0200 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2012-09-19 19:35:51 +0200

Nathann gravatar image

Heeeeeeeeeeeeeere it is !

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

Nathann

edit flag offensive delete link more

Comments

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

G-Sage gravatar imageG-Sage ( 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

Jason Grout gravatar imageJason Grout ( 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!

G-Sage gravatar imageG-Sage ( 2012-09-20 17:56:51 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-09-18 17:20:48 +0200

Seen: 384 times

Last updated: Sep 21 '12