Sage: Ticket #8781: Overfull graph (and a bug in edge_coloring)
https://trac.sagemath.org/ticket/8781
<p>
This patch defines the (very short) function is_overfull (<a class="ext-link" href="http://en.wikipedia.org/wiki/Overfull_graph"><span class="icon"></span>http://en.wikipedia.org/wiki/Overfull_graph</a>), and updates the edge_coloring function to support it.
</p>
<p>
I also fixed a mistake in this code : I had mixed g.order() with max(g.degree()) for complete graphs <sup></sup>;
</p>
<p>
This is a prerequisite for <a class="closed ticket" href="https://trac.sagemath.org/ticket/9230" title="defect: Broken docstrings in Travelling Salesman Problem (closed: fixed)">#9230</a>.
</p>
<p>
<strong>Apply:</strong>
</p>
<ol><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/8166" title="enhancement: Expose max_weight_matching from NetworkX (closed: fixed)">#8166</a>
</li><li><a class="ext-link" href="http://trac.sagemath.org/sage_trac/attachment/ticket/8781/trac_8781.patch"><span class="icon"></span>trac_8781.patch</a>
</li><li><a class="ext-link" href="http://trac.sagemath.org/sage_trac/attachment/ticket/8781/trac_8781-reviewer.patch"><span class="icon"></span>trac_8781-reviewer.patch</a>
</li><li><a class="ext-link" href="http://trac.sagemath.org/sage_trac/attachment/ticket/8781/trac_8781-fix2.patch"><span class="icon"></span>trac_8781-fix2.patch</a>
</li></ol>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8781
Trac 1.1.6ncohenTue, 27 Apr 2010 12:15:49 GMTattachment set
https://trac.sagemath.org/ticket/8781
https://trac.sagemath.org/ticket/8781
<ul>
<li><strong>attachment</strong>
set to <em>trac_8781.patch</em>
</li>
</ul>
TicketncohenTue, 27 Apr 2010 12:15:56 GMTstatus changed
https://trac.sagemath.org/ticket/8781#comment:1
https://trac.sagemath.org/ticket/8781#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketmvnguMon, 10 May 2010 07:32:30 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/8781#comment:2
https://trac.sagemath.org/ticket/8781#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
<li><strong>reviewer</strong>
set to <em>Minh Van Nguyen</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
For the patch <a class="ext-link" href="http://trac.sagemath.org/sage_trac/attachment/ticket/8781/trac_8781.patch"><span class="icon"></span>trac_8781.patch</a>, I'm OK with the part dealing with defining the new method <code>is_overfull()</code>. 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 />
</p>
<p>
Now to the part I don't like about <a class="ext-link" href="http://trac.sagemath.org/sage_trac/attachment/ticket/8781/trac_8781.patch"><span class="icon"></span>trac_8781.patch</a>. It's the part of that patch that deals with the module <code>sage/graphs/graph_coloring.py</code>. While testing that part of ncohen's patch, I came across this failure:
</p>
<div class="wiki-code"><div class="code"><pre>sage: from sage.graphs.graph_coloring import edge_coloring
sage: <span class="nv">g</span> <span class="o">=</span> graphs.ClawGraph<span class="o">()</span>
sage: edge_coloring<span class="o">(</span>g, <span class="nv">value_only</span><span class="o">=</span>True<span class="o">)</span>
---------------------------------------------------------------------------
TypeError Traceback <span class="o">(</span>most recent call last<span class="o">)</span>
/dev/shm/mvngu/sandbox/sage-4.4.2.alpha0-8781-overfull/<ipython console> in <module><span class="o">()</span>
/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<span class="o">(</span>g, value_only, vizing, hex_colors, log<span class="o">)</span>
564 sum<span class="o">([</span>color<span class="o">[</span>R<span class="o">(</span>e<span class="o">)][</span>i<span class="o">]</span> <span class="k">for </span>e in g.edges_incident<span class="o">(</span>v<span class="o">)])</span>, <span class="nv">max</span><span class="o">=</span>1<span class="o">)</span>
565 <span class="k">for </span>v in g.vertex_iterator<span class="o">()</span>
--> 566 <span class="k">for </span>i in xrange<span class="o">(</span>k<span class="o">)]</span>
567 <span class="c"># an edge must have a color
</span>
568 <span class="o">[</span>p.add_constraint<span class="o">(</span>sum<span class="o">([</span>color<span class="o">[</span>R<span class="o">(</span>e<span class="o">)][</span>i<span class="o">]</span> <span class="k">for </span>i in xrange<span class="o">(</span>k<span class="o">)])</span>, <span class="nv">max</span><span class="o">=</span>1, <span class="nv">min</span><span class="o">=</span>1<span class="o">)</span>
/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__ <span class="o">(</span>sage/numerical/mip.c:9202<span class="o">)()</span>
TypeError: unhashable <span class="nb">type</span>: <span class="s1">'dict'</span>
</pre></div></div><p>
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.
</p>
TicketncohenMon, 10 May 2010 17:35:02 GMTstatus, description changed
https://trac.sagemath.org/ticket/8781#comment:3
https://trac.sagemath.org/ticket/8781#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8781?action=diff&version=3">diff</a>)
</li>
</ul>
<p>
Oops.... That's totally unrelated, and is caused by the recent upgrade of NetworkX. The default graphs from NetworkX (of which <a class="missing wiki">ClawGraph?</a>() 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 ;-)
</p>
<p>
There was already a patch waiting for review to fix it, which is <a class="closed ticket" href="https://trac.sagemath.org/ticket/8892" title="defect: Many doctests fails since the update of NetworkX ! (closed: fixed)">#8892</a>, 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.
</p>
<p>
Thank you very much Minh, and sorry again for that :-)
</p>
<p>
Nathann
</p>
TicketmvnguFri, 21 May 2010 16:54:36 GMTdescription changed
https://trac.sagemath.org/ticket/8781#comment:4
https://trac.sagemath.org/ticket/8781#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8781?action=diff&version=4">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8781#comment:3" title="Comment 3">ncohen</a>:
</p>
<blockquote class="citation">
<p>
There was already a patch waiting for review to fix it, which is <a class="closed ticket" href="https://trac.sagemath.org/ticket/8892" title="defect: Many doctests fails since the update of NetworkX ! (closed: fixed)">#8892</a>, but I had forgotten this file and only fixed generic_graph and graph...
</p>
</blockquote>
<p>
I have updated my reviewer patch to include the doctest that resulted in the failure I reported above. We better make sure it doesn't happen again. Anyone for a final review of the whole ticket?
</p>
TicketncohenMon, 24 May 2010 17:45:24 GMT
https://trac.sagemath.org/ticket/8781#comment:5
https://trac.sagemath.org/ticket/8781#comment:5
<p>
It's ok for me !! I thought for a time it also needed to be rebased, but I has just forgotten to apply my patch before yours ;-)
</p>
<p>
I noticed an error in the docstrings though... so positive review to your patch, and this ticket is still waiting for review because of mine.
</p>
<p>
and by the way... It's a bit odd that I did not notice this problem before, and I'm afraid tis may come from the fact I used CPLEX as a default solver before, while only GLPK is installed on my current copy of Sage O_o
</p>
<p>
Nathann
</p>
TicketncohenMon, 24 May 2010 17:45:40 GMTattachment set
https://trac.sagemath.org/ticket/8781
https://trac.sagemath.org/ticket/8781
<ul>
<li><strong>attachment</strong>
set to <em>trac_8781-fix.patch</em>
</li>
</ul>
TicketmvnguTue, 25 May 2010 01:09:00 GMTattachment set
https://trac.sagemath.org/ticket/8781
https://trac.sagemath.org/ticket/8781
<ul>
<li><strong>attachment</strong>
set to <em>trac_8781-reviewer.patch</em>
</li>
</ul>
TicketmvnguTue, 25 May 2010 01:14:45 GMT
https://trac.sagemath.org/ticket/8781#comment:6
https://trac.sagemath.org/ticket/8781#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8781#comment:5" title="Comment 5">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I noticed an error in the docstrings though... so positive review to your patch, and this ticket is still waiting for review because of mine.
</p>
</blockquote>
<p>
Your fix is OK by me. However, note that it requires GLPK or CBC. (I have only tested with those two spkg's.) Without any of those packages installed, I got the following failure:
</p>
<div class="wiki-code"><div class="code"><pre>sage -t -long <span class="s2">"devel/sage-main/sage/graphs/generic_graph.py"</span>
**********************************************************************
File <span class="s2">"/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/devel/sage-main/sage/graphs/generic_graph.py"</span>, line 1845:
sage: edge_coloring<span class="o">(</span>g, <span class="nv">value_only</span><span class="o">=</span>True<span class="o">)</span>
Expected:
3
Got:
4
**********************************************************************
File <span class="s2">"/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/devel/sage-main/sage/graphs/generic_graph.py"</span>, line 4027:
sage: g.matching<span class="o">(</span><span class="nv">algorithm</span><span class="o">=</span><span class="s2">"LP"</span>, <span class="nv">value_only</span><span class="o">=</span>True<span class="o">)</span>
Exception raised:
Traceback <span class="o">(</span>most recent call last<span class="o">)</span>:
File <span class="s2">"/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/bin/ncadoctest.py"</span>, line 1231, in run_one_test
self.run_one_example<span class="o">(</span><span class="nb">test</span>, example, filename, compileflags<span class="o">)</span>
File <span class="s2">"/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/bin/sagedoctest.py"</span>, line 38, in run_one_example
OrigDocTestRunner.run_one_example<span class="o">(</span>self, <span class="nb">test</span>, example, filename, compileflags<span class="o">)</span>
File <span class="s2">"/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/bin/ncadoctest.py"</span>, line 1172, in run_one_example
compileflags, 1<span class="o">)</span> in test.globs
File <span class="s2">"<doctest __main__.example_69[5]>"</span>, line 1, in <module>
g.matching<span class="o">(</span><span class="nv">algorithm</span><span class="o">=</span><span class="s2">"LP"</span>, <span class="nv">value_only</span><span class="o">=</span>True<span class="o">)</span><span class="c">###line 4027:
</span> sage: g.matching<span class="o">(</span><span class="nv">algorithm</span><span class="o">=</span><span class="s2">"LP"</span>, <span class="nv">value_only</span><span class="o">=</span>True<span class="o">)</span>
File <span class="s2">"/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/lib/python/site-packages/sage/graphs/generic_graph.py"</span>, line 4078, in matching
<span class="k">return </span>p.solve<span class="o">(</span><span class="nv">objective_only</span><span class="o">=</span>True, <span class="nv">solver</span><span class="o">=</span>solver, <span class="nv">log</span><span class="o">=</span>verbose<span class="o">)</span>
File <span class="s2">"mip.pyx"</span>, line 1051, in sage.numerical.mip.MixedIntegerLinearProgram.solve <span class="o">(</span>sage/numerical/mip.c:7884<span class="o">)</span>
ValueError: There does not seem to be any <span class="o">(</span>Mixed<span class="o">)</span> Integer Linear Program solver installed. Please visit http://www.sagemath.org/doc/constructions/linear_programming.html to learn more about the solvers available.
**********************************************************************
</pre></div></div><p>
So I have made the doctest optional. And as I said before: Anyone for a final review of the whole ticket? :-) See the ticket description for instructions on how to apply patches.
</p>
TicketncohenTue, 25 May 2010 17:11:00 GMT
https://trac.sagemath.org/ticket/8781#comment:7
https://trac.sagemath.org/ticket/8781#comment:7
<p>
Hem... So in the end, with your "optional" keyword and the 3 instead of 4, there is no error returned from the doctests when no solver is installed. The problem is that when a user who does not have any solver installed uses the edge_coloring method, he gets wrong results because the function, when noticing that the solve command raises an exception (because no solver is installed) incorrectly deduces that the problem has no solution, and answers Delta+1. This is just because I wrote except: instead of except MIPSolverException:, and it is (I hope) my last mistake. :-)
</p>
<p>
With this other 1-line patch, this should be fixed.... God I'm eager to see all those dependencies merged into Sage, I'm getting tired of applying them all each time I want to test something !!
</p>
<p>
Nathann
</p>
TicketncohenTue, 25 May 2010 17:11:15 GMTattachment set
https://trac.sagemath.org/ticket/8781
https://trac.sagemath.org/ticket/8781
<ul>
<li><strong>attachment</strong>
set to <em>trac_8781-fix2.patch</em>
</li>
</ul>
TicketmvnguSat, 12 Jun 2010 08:10:39 GMTdescription changed
https://trac.sagemath.org/ticket/8781#comment:8
https://trac.sagemath.org/ticket/8781#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8781?action=diff&version=8">diff</a>)
</li>
</ul>
<p>
I'm OK with <code>trac_8781.patch</code> and <code>trac_8781-fix2.patch</code>. We now need final approval for my reviewer patch <code>trac_8781-reviewer.patch</code>.
</p>
TicketncohenSat, 12 Jun 2010 22:04:29 GMTstatus changed
https://trac.sagemath.org/ticket/8781#comment:9
https://trac.sagemath.org/ticket/8781#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Fine without any LP solver, fine with GLPK, fine with CPLEX :-)
</p>
<p>
Positive review... But I noticed lots of failures because of the travelling_salesman_problem, still due to default {} labels... This function was under review when the patch fixing it was merged, so I'll create another one for this :-/
</p>
<p>
Nathann
</p>
TicketmvnguSun, 13 Jun 2010 09:28:53 GMTdescription changed
https://trac.sagemath.org/ticket/8781#comment:10
https://trac.sagemath.org/ticket/8781#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8781?action=diff&version=10">diff</a>)
</li>
</ul>
TicketrlmTue, 29 Jun 2010 16:44:50 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/8781#comment:11
https://trac.sagemath.org/ticket/8781#comment:11
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.5.alpha1</em>
</li>
</ul>
Ticket