Opened 11 years ago

Last modified 11 years ago

#8781 closed enhancement

Overfull graph (and a bug in edge_coloring) — at Version 3

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.5
Component: graph theory Keywords:
Cc: Merged in:
Authors: Nathann Cohen Reviewers: Minh Van Nguyen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ncohen)

This patch defines the (very short) function is_overfull (http://en.wikipedia.org/wiki/Overfull_graph), and updates the edge_coloring function to support it.

I also fixed a mistake in this code : I had mixed g.order() with max(g.degree()) for complete graphs ;

Requires #8892

Nathann

Change History (4)

Changed 11 years ago by ncohen

comment:1 Changed 11 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 11 years ago by mvngu

  • Authors set to Nathann Cohen
  • Reviewers set to Minh Van Nguyen
  • Status changed from needs_review to needs_info

For the 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.

Now to the part I don't like about 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:

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.

comment:3 Changed 11 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_info to needs_review

Oops.... That's totally unrelated, and is caused by the recent upgrade of NetworkX. The default graphs from NetworkX (of which ClawGraph?() is an example) now have {} instead of None as default edge labels... And as {} is not hashable, Sage does not like to find it as part of a dictionary key ;-)

There was already a patch waiting for review to fix it, which is #8892, but I had forgotten this file and only fixed generic_graph and graph... Well, I updated that patch, which is now a dependency of this very one, and fixes the bug you found.

Thank you very much Minh, and sorry again for that :-)

Nathann

Note: See TracTickets for help on using tickets.