Opened 10 years ago
Closed 10 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)
Change History (4)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
- Summary changed from Bug in graph coloring to Rounding error in graph coloring
Changed 10 years ago by
comment:2 Changed 10 years ago by
- 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 10 years ago by
- 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.
Here is the one-line patch needed !
Nathann