Opened 6 years ago

Last modified 5 years ago

#14529 needs_info enhancement

Drastic performance improvement of computing the chromatic polynomial

Reported by: azi Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-6.4
Component: graph theory Keywords:
Cc: ncohen, stefan, slani, rbeezer Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by azi)

Hello!

I am not sure I have the energy to do that at the moment but its a nice task that we might want to address at some point. Hence I am leaving some stuff here for further reference.

The current implementation of the chromatic_polynomial uses the deletion-contraction recurrence directly. This gives us an exponential branching tree. The neat thing is that at some point some of the branches compute the chromatic polynomial for the same graphs (multiple - exponential) times!

A very dumb implementation in Python (see below) that is faster than the C code. It takes 700us to compute the chromatic polynomial of a random dense graph of order 15 and 74 minutes (!) with the C code currently used by Sage.

Of course this code needs more work and can be optimized even further (perhaps by calling the C implementation under a threshold) but for now here it is.

global cache
cache = {}
def chrompoly(G):
    
    global cache 

    s = tuple(G.canonical_label().edges(labels=False))

    if s in cache:
        return cache[s]
    if not G.is_connected():
        return prod([chrompoly(C) for C in G.connected_components_subgraphs()])

    R = ZZ['x']
    x = R.gen()
    
    n = G.order()
    m = G.size()

    #  Since we know that G is connected it is enough to check the number of edges
    #  to test if it is a tree
    if m == n-1:
        return x*(x-1)**(n-1)

    u,v = G.edge_iterator(labels=False).next()

    G.delete_edge(u,v)
    p = chrompoly(G)
    G.add_edge(u,v)

    G2 = G.copy()
    G2.add_edges(((u,x) for x in G.neighbor_iterator(v)))
    G2.delete_vertex(v)

    ret = p - chrompoly(G2)
    
    cache[s] = ret 

    return ret 

Attachments (2)

trac_14592_chrompoly.patch (17.1 KB) - added by azi 6 years ago.
trac_14592_chrompoly2.patch (1.1 KB) - added by azi 6 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 6 years ago by azi

Hm... Maybe I am being too fast with the time results. I should really check what happens if I delete the cache after each run

comment:2 Changed 6 years ago by azi

Looks fine!!

sage: G = graphs.RandomGNP(14,0.8)
sage: %timeit G.chromatic_polynomial()
1 loops, best of 3: 50.7 s per loop

sage: %timeit chrompoly(G)
1 loops, best of 3: 790 us per loop

comment:3 Changed 6 years ago by azi

  • Description modified (diff)

comment:4 Changed 6 years ago by azi

Does anyone of you guys sees a reason not to remove the current Cython implementation and adding this code

comment:5 Changed 6 years ago by ncohen

Yep : the authors of the Cython code may be so impressed by your caching that they may want to adapt their code to it. Worth sending an email. Otherwise, if the results are better and the code clearer.... :-P

Nathann

comment:6 follow-up: Changed 6 years ago by azi

Good!

How do you think we should handle the global cache if this is to be made into a proper patch?

What I would like to do is have a global ____sage_very_very_private__cache__chrompoly___dict = {} variable outside the function and delete the cache each time the computation is over. In addition I would have a parameter keep_cache that keeps the cache alive (convenient when you're computing the polynomial in a loop)

What do you think?

Also whom would you send an email to?

comment:7 in reply to: ↑ 6 Changed 6 years ago by ncohen

Helloooooooo !

How do you think we should handle the global cache if this is to be made into a proper patch?

Hmmm... Well, there is the @cached_method decorator, that automatically manages the cache of any function. But you can't empty it automatically when the computations are done though.

Technically, what you can do is write a function A (without the decorator) which call function B (the real one, with the cached_method decorator). Before returning B's result, A would clear the cache of B.

I wouldn't go to such lengths before there is a real need, actually... If somebody computes one chromatic polynomial perhaps he will compute two, and ... well. It's up to you. To me caching the method with the cached_method decorator would do the job. and you can add in its documentation an explanation of how the cache can be cleared manually, with the clear_cache method.

http://www.sagemath.org/doc/reference/misc/sage/misc/cachefunc.html

Also whom would you send an email to?

The file seems to have been written by Robert Miller and Gordon Royle (just reading the copyright in the file itself). Robert Miller does not work on Sage anymore but should be interested (he's the one who initially wrote all the graph-related stuff in Sage. Backends included). And Gordon Royle may be interested too, though I probably never wrote to him :-)

Nathann

comment:8 Changed 6 years ago by azi

Great thanks for the info! I'll read through that stuff and produce a proper patch.

As for the "compute one or two,.." I would for example like to test the Birkhoff-Lewis conjecture for all planar graphs of some order and having such a cache alive through all the computation would be very nice.

comment:9 Changed 6 years ago by mhansen

There is some similar code for caching, etc. in "tutte.sage" at #1314 .

comment:10 Changed 6 years ago by jdemeyer

  • Cc ncohen stefan slani rbeezer added; ncohen stefan slani rbeezer removed
  • Milestone changed from sage-5.11 to sage-5.12

Changed 6 years ago by azi

comment:11 Changed 6 years ago by azi

Attached it is a proposed patch for the chromatic polynomial.

The new code is short, self-explanatory and incorrect. Due to the nature of the incorrectness I suspect that the edge contraction part of the code may not be correct.

Anyone happens to see the issue?

comment:12 Changed 6 years ago by ncohen

How do you know that the graph is connected, recursively ? O_o

Nathann

Changed 6 years ago by azi

comment:13 Changed 6 years ago by azi

I don't.. It looks like I removed that check (which is present in the above code) when merging the patches.. FML... TNX for the spot on!

The code now works correctly!

comment:14 Changed 6 years ago by azi

  • Status changed from new to needs_review

comment:15 Changed 6 years ago by darij

Needs some adjustments:

darij@travis-virtualbox:~/sage-5.11.beta3/devel/sage-main$ hg qpush
applying trac_14592_chrompoly.patch
patching file sage/graphs/chrompoly.pyx
Hunk #1 FAILED at 0
1 out of 1 hunks FAILED -- saving rejects to file sage/graphs/chrompoly.pyx.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_14592_chrompoly.patch

It looks like undeleting the deleted pyx file does the trick.

Last edited 6 years ago by darij (previous) (diff)

comment:16 Changed 6 years ago by darij

The chromatic polynomial of the empty graph should be 1, not x as your code returns (nor should it throw a LookupError? as the original code did). While you might want to wait until the is_connected() method correctly recognizes the empty graph as disconnected, please make sure that the returned value is actually the polynomial 1, not the integer 1 (so use ZZ['x'].prod instead of prod).

Nice speedup, though it would be better to take the best of both worlds and redo it in Cython. I'm getting slowdowns on small graphs (up to 6 vertices), which might be an issue with the combinatorics I'm doing (combinatorial Hopf algebras have me work with many many little graphs rather than few large ones); but I think the added speedup of Cython will get rid of these slowdowns easily.

Last edited 6 years ago by darij (previous) (diff)

comment:17 Changed 6 years ago by darij

is_connected() is probably not going to handle the empty graph nicely, so it is best if you check for the empty graph explicitly.

comment:18 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_info

Helloooooooooooooooo Jernej !

Would it be possible to keep the old implementation too, and have the two reachable through the same function ? Something like g.chromatic_polynomial(implementation="Python/C") ?

We would be able to check correction of each of them with the other, and if we ever notice that we can do better by caching inside of the C function.

Nathann

comment:19 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:20 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:21 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.