Opened 10 years ago
Closed 10 years ago
#8781 closed enhancement (fixed)
Overfull graph (and a bug in edge_coloring)
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.5 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.5.alpha1 | |
Authors: | Nathann Cohen | Reviewers: | Minh Van Nguyen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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 ^{};
This is a prerequisite for #9230.
Apply:
Attachments (4)
Change History (15)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Reviewers set to Minh Van Nguyen
- Status changed from needs_review to needs_info
comment:3 follow-up: ↓ 4 Changed 10 years ago by
- 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
comment:4 in reply to: ↑ 3 Changed 10 years ago by
- Description modified (diff)
Replying to ncohen:
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...
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?
comment:5 follow-up: ↓ 6 Changed 10 years ago by
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 ;-)
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.
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
Nathann
Changed 10 years ago by
Changed 10 years ago by
comment:6 in reply to: ↑ 5 Changed 10 years ago by
Replying to ncohen:
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.
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:
sage -t -long "devel/sage-main/sage/graphs/generic_graph.py" ********************************************************************** File "/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/devel/sage-main/sage/graphs/generic_graph.py", line 1845: sage: edge_coloring(g, value_only=True) Expected: 3 Got: 4 ********************************************************************** File "/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/devel/sage-main/sage/graphs/generic_graph.py", line 4027: sage: g.matching(algorithm="LP", value_only=True) Exception raised: Traceback (most recent call last): File "/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_69[5]>", line 1, in <module> g.matching(algorithm="LP", value_only=True)###line 4027: sage: g.matching(algorithm="LP", value_only=True) File "/dev/shm/mvngu/sandbox/sage-4.4.2.sandbox.6/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4078, in matching return p.solve(objective_only=True, solver=solver, log=verbose) File "mip.pyx", line 1051, in sage.numerical.mip.MixedIntegerLinearProgram.solve (sage/numerical/mip.c:7884) ValueError: There does not seem to be any (Mixed) Integer Linear Program solver installed. Please visit http://www.sagemath.org/doc/constructions/linear_programming.html to learn more about the solvers available. **********************************************************************
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.
comment:7 Changed 10 years ago by
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. :-)
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 !!
Nathann
Changed 10 years ago by
comment:8 Changed 10 years ago by
- Description modified (diff)
I'm OK with trac_8781.patch
and trac_8781-fix2.patch
. We now need final approval for my reviewer patch trac_8781-reviewer.patch
.
comment:9 Changed 10 years ago by
- Status changed from needs_review to positive_review
Fine without any LP solver, fine with GLPK, fine with CPLEX :-)
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 :-/
Nathann
comment:10 Changed 10 years ago by
- Description modified (diff)
comment:11 Changed 10 years ago by
- Merged in set to sage-4.5.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
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: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.