Hello !!
Trying to write a Linear Program version of the coloring problem, I
found a graph ( pure luck, it was a RandomGNP ) for which the
functions chromatic_number() and coloring() return a wrong value.
sage: h=Graph(":I`ASWCaG`WaJC{afP")
sage: h.chromatic_number()
4
sage: h.coloring()
[[6, 8], [9], [0, 4, 7, 3], [1, 2, 5]]
with my version of the coloring() function I found a coloring using
only 3 classes. As a proof, you can type which checks that each class
is actually an independent set.
for c in [[3, 9, 1], [9, 4, 0, 3], [3, 8, 5]]:
print h.subgraph(c).connected_components_number()==len(c)
This means that there is an error in the two functions named, but
which means the all_graph_colorings() function, as all the others use
it. I do not know how to fix this function, even though it may be a
minor mistake in the code.
The thing is that the patches and SPKG for LP features in SAGE are
currently in review ( cf http://trac.sagemath.org/sage_trac/ticket/6502
), and that I have written several graph functions that I will post on
TRAC as soon as LP has become part of Sage, all of them using LP.
Among them is a LP version of the coloring function that I wrote to
compare its performances against the current one. I tested it with the
following code :
for i in range(20):
g=graphs.RandomGNP(10,.5)
print "Sage's coloring function"
timeit("g.coloring()",number=1)
print "LP formulation"
timeit("coloring(g)",number=1)
which outputs :
Sage's coloring function
1 loops, best of 3: 6.31 s per loop
LP formulation
1 loops, best of 3: 402 ms per loop
Sage's coloring function
1 loops, best of 3: 33.8 s per loop
LP formulation
1 loops, best of 3: 115 ms per loop
Sage's coloring function
1 loops, best of 3: 6.85 s per loop
LP formulation
1 loops, best of 3: 38.9 ms per loop
Sage's coloring function
1 loops, best of 3: 25.5 s per loop
LP formulation
1 loops, best of 3: 1.33 s per loop
Sage's coloring function
1 loops, best of 3: 27.8 s per loop
LP formulation
1 loops, best of 3: 52.3 ms per loop
Sage's coloring function
1 loops, best of 3: 1.08 s per loop
LP formulation
1 loops, best of 3: 46.6 ms per loop
Showing that the LP version is faster in this case. However, ( please
excuse my english if necessary ), the LP has a overhead time which is
apparent when coloring smaller graphs. When I change the probability
from 0.5 ( previously ) to 0.3, here are the results :
Sage's coloring function
1 loops, best of 3: 1.21 ms per loop
LP formulation
1 loops, best of 3: 5.48 ms per loop
Sage's coloring function
1 loops, best of 3: 1.45 ms per loop
LP formulation
1 loops, best of 3: 12.2 ms per loop
Sage's coloring function
1 loops, best of 3: 1.75 ms per loop
LP formulation
1 loops, best of 3: 4.85 ms per loop
Sage's coloring function
1 loops, best of 3: 1.14 ms per loop
LP formulation
1 loops, best of 3: 4.83 ms per loop
Sage's coloring function
1 loops, best of 3: 2.1 ms per loop
LP formulation
1 loops, best of 3: 3.55 ms per loop
Sage's coloring function
1 loops, best of 3: 1.25 ms per loop
LP formulation
1 loops, best of 3: 6.32 ms per loop
Sage's coloring function
1 loops, best of 3: 2.15 ms per loop
LP formulation
1 loops, best of 3: 10.7 ms per loop
Sage's coloring function
1 loops, best of 3: 2.07 ms per loop
LP formulation
1 loops, best of 3: 4.13 ms per loop
In the end, if the current coloring() function can be fixed, it may be
interesting to keep it for small graphs even if the LP version is
available. Besides, I do not know yet how to enumerate in a LP all the
solutions of a problem, and so I cannot for the moment say that it
could be possible to replace functions like all_graph_colorings() by a
LP formulation. This may be a good reason to spend some time on this
function if the timeit() on small instances was not so convincing.
Nathann
P.S. : Trac ticket -> http://trac.sagemath.org/sage_trac/ticket/6660
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
