#8781: Overfull graph (and a bug in edge_coloring)
-------------------------------+--------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.4.2
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: Minh Van Nguyen | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by newvalueoldvalue):
* status: needs_review => needs_info
* reviewer: => Minh Van Nguyen
* author: => Nathann Cohen
Comment:
For the patch
[http://trac.sagemath.org/sage_trac/attachment/ticket/8781/trac_8781.patch
trac_8781.patch], I'm OK with the part dealing with defining the new
method `is_overfull()`. I have attached reviewer patch that adds some more
doctests to that method, fixes some formatting styles, and adds a comment
about optimizing that method for speed.
[[BR]]
Now to the part I don't like about
[http://trac.sagemath.org/sage_trac/attachment/ticket/8781/trac_8781.patch
trac_8781.patch]. It's the part of that patch that deals with the module
`sage/graphs/graph_coloring.py`. While testing that part of ncohen's
patch, I came across this failure:
{{{
#!sh
sage: from sage.graphs.graph_coloring import edge_coloring
sage: g = graphs.ClawGraph()
sage: edge_coloring(g, value_only=True)
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
/dev/shm/mvngu/sandbox/sage-4.4.2.alpha0-8781-overfull/<ipython console>
in <module>()
/dev/shm/mvngu/sandbox/sage-4.4.2.alpha0-8781-overfull/local/lib/python2.6
/site-packages/sage/graphs/graph_coloring.pyc in edge_coloring(g,
value_only, vizing, hex_colors, log)
564 sum([color[R(e)][i] for e in g.edges_incident(v)]),
max=1)
565 for v in g.vertex_iterator()
--> 566 for i in xrange(k)]
567 # an edge must have a color
568 [p.add_constraint(sum([color[R(e)][i] for i in xrange(k)]),
max=1, min=1)
/dev/shm/mvngu/sandbox/sage-4.4.2.alpha0-8781-overfull/local/lib/python2.6
/site-packages/sage/numerical/mip.so in
sage.numerical.mip.MIPVariable.__getitem__ (sage/numerical/mip.c:9202)()
TypeError: unhashable type: 'dict'
}}}
This also came up even though I had installed the optional GLPK spkg. One
possibility here is to split off the part of the patch that deals with
edge coloring and put that part in another ticket. That ticket could also
be about resolving the failure I reported above. Other possibility is to
resolve the above failure in the current ticket.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8781#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
