The graph is defined in the previous message ! ;-)
sage: h=Graph(":I`ASWCaG`WaJC{afP")
You can obtain a string describing a graph by using the
Graph.graph6_string method. Pretty useful !
And this ticket you mentionned is there :
http://trac.sagemath.org/sage_trac/ticket/6660
;-)
Nathann
This weird thing is a
On Jul 30, 3:55 pm, Robert Bradshaw <rober...@math.washington.edu>
wrote:
> 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 ( cfhttp://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
-~----------~----~----~----~------~----~------~--~---
