Opened 11 years ago
Last modified 11 years ago
#8781 closed enhancement
Overfull graph (and a bug in edge_coloring) — at Version 4
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: |
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 ^{};
Apply:
Change History (5)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Reviewers set to Minh Van Nguyen
- Status changed from needs_review to needs_info
comment:3 follow-up: ↓ 4 Changed 11 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 11 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?
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.