#14529: Drastic performance improvement of computing the chromatic polynomial
----------------------------+-----------------------------------------------
Reporter: azi | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.10
Component: graph theory | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
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) is already faster on
graphs of order 13 than the C code. It takes 2ms to compute the chromatic
polynomial with this code and 1 minute with the one we have now!
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 = G.canonical_label().sparse6_string()
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()
if G.is_tree():
return x*(x-1)**(G.order()-1)
u,v = G.edges(labels=False)[0]
G.delete_edge(u,v)
p1 = chrompoly(G)
G.add_edge(u,v)
ret = p1 - chrompoly(contract_edge(G, u,v))
cache[s] = ret
return ret
def contract_edge(G, u,v):
Gret = G.copy()
Gret.add_edges([(u,x) for x in G.neighbors(v)])
Gret.delete_vertex(v)
return Gret
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14529>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
