On Jul 30, 2009, at 5:41 AM, Nathann Cohen wrote:
>
> 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.
Do you have the "bad" graph somewhere? We should file a ticket for
this. As for the rest of the email, I'm not really qualified to
answer, but it sounds like something that would be good to get in.
> 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
-~----------~----~----~----~------~----~------~--~---
