Opened 7 years ago

Closed 7 years ago

#12389 closed defect (fixed)

Rounding error in graph coloring

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: Merged in: sage-5.0.beta3
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Geoff Tims reported the following bug :

sage: sub = graphs.PetersenGraph()
sage: sub.complement().chromatic_number(algorithm="MILP")
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/ncohen/<ipython console> in <module>()

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in chromatic_number(self, algorithm)
   2487         elif algorithm == "MILP":
   2488             from sage.graphs.graph_coloring import vertex_coloring
-> 2489             return vertex_coloring(self, value_only=True)
   2490         # another algorithm with bad performance; only good for small graphs
   2491         elif algorithm == "CP":

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph_coloring.pyc in vertex_coloring(g, k, value_only, hex_colors, solver, verbose)
    342             # tries to color the graph, increasing k each time it fails.
    343             tmp = vertex_coloring(g, k=k, value_only=value_only,
--> 344                                   hex_colors=hex_colors, verbose=verbose)
    345             if tmp is not False:
    346                 if value_only:

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph_coloring.pyc in vertex_coloring(g, k, value_only, hex_colors, solver, verbose)
    431         # a vertex has exactly one color
    432         [p.add_constraint(Sum([color[v][i] for i in xrange(k)]), min=1, max=1)
--> 433              for v in g.vertices()]
    434         # adjacent vertices have different colors
    435         [p.add_constraint(color[u][i] + color[v][i], max=1)

TypeError: integer argument expected, got float

Attachments (1)

trac_12389.patch (805 bytes) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (4)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review
  • Summary changed from Bug in graph coloring to Rounding error in graph coloring

Here is the one-line patch needed !

Nathann

Changed 7 years ago by ncohen

comment:2 Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

Without the patch, I observe the same error than the reported one.

With the patch:

sage: sub = graphs.PetersenGraph()
sage: sub.complement().chromatic_number(algorithm="MILP")
5

So I give a positive review.

D.

comment:3 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.