#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 | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------+-------------------------------------------
Description changed by azi:
Old description:
> 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
> }}}
New description:
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
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14529#comment:3>
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.
