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