#23139 closed enhancement (fixed)
Graphic Matroid class
Reported by: | zgershkoff | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.1 |
Component: | matroid theory | Keywords: | days88, IMA coding sprints |
Cc: | Stefan, yomcat, tscrim | Merged in: | |
Authors: | Zach Gershkoff | Reviewers: | Stefan van Zwam, Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | b930927 (Commits) | Commit: | |
Dependencies: | #23300, #23290, #23382 | Stopgaps: |
Description (last modified by )
Implement a graphic matroid class, instances of which will be based on graphs. The class will have methods and algorithms specifically for graphs.
Change History (97)
comment:1 Changed 4 years ago by
- Cc Stefan yomcat tscrim added
- Component changed from PLEASE CHANGE to matroid theory
- Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 4 years ago by
- Branch set to u/zgershkoff/graphic_matroid_class
comment:3 Changed 4 years ago by
- Commit set to 33b0a831a47c28edf2a7fc1874f6d1f3be799f61
- Description modified (diff)
comment:4 Changed 4 years ago by
- Commit changed from 33b0a831a47c28edf2a7fc1874f6d1f3be799f61 to dd5ef4f6ac1aa9e2d07989a27bc8159b0f50322e
Branch pushed to git repo; I updated commit sha1. New commits:
dd5ef4f | Beginnings of _has_minor()
|
comment:5 Changed 4 years ago by
- Commit changed from dd5ef4f6ac1aa9e2d07989a27bc8159b0f50322e to 92b08317bf3f34a9c2ed438c4a31aec54daf3029
Branch pushed to git repo; I updated commit sha1. New commits:
92b0831 | Refinements to _minor()
|
comment:6 Changed 4 years ago by
- Commit changed from 92b08317bf3f34a9c2ed438c4a31aec54daf3029 to f47fdd36388353b20c1557eb2c76c2f85c3e09b8
Branch pushed to git repo; I updated commit sha1. New commits:
f47fdd3 | New methods + general tidiness
|
comment:7 Changed 4 years ago by
- Commit changed from f47fdd36388353b20c1557eb2c76c2f85c3e09b8 to fd54096f67e2dab1d98e0c680344ea12066999e5
comment:8 Changed 4 years ago by
- Commit changed from fd54096f67e2dab1d98e0c680344ea12066999e5 to 02f7d4aae8b60455e7b1bba995b63966f37793d5
comment:9 Changed 4 years ago by
- Commit changed from 02f7d4aae8b60455e7b1bba995b63966f37793d5 to a1f31cd328a9a74bdd1afc5f7ff0949e681b17ad
Branch pushed to git repo; I updated commit sha1. New commits:
deab177 | Forgot to save comment on _isomorphism()
|
a71ee90 | Added graphic_extension(), graphic_extensions(), graphic_coextension(). Still need to test them.
|
d2ff13c | Saving changes before I lose them
|
a1f31cd | Refined extension/coextension methods after testing
|
comment:10 Changed 4 years ago by
- Commit changed from a1f31cd328a9a74bdd1afc5f7ff0949e681b17ad to fb7f8e7a41884aff0d99e7694fbc0db90c3d0848
Branch pushed to git repo; I updated commit sha1. New commits:
fb7f8e7 | Moved contract_edge() to utilities; added _closure()
|
comment:11 Changed 4 years ago by
- Commit changed from fb7f8e7a41884aff0d99e7694fbc0db90c3d0848 to 7d854ebfe8f028d2bb2592cf5210c338f38bfb10
comment:12 Changed 4 years ago by
- Commit changed from 7d854ebfe8f028d2bb2592cf5210c338f38bfb10 to fc45f1fbd7a9bab356bd2bfc62c43df585c1a8f5
comment:13 Changed 4 years ago by
- Dependencies set to 23300, 7304, 23290
comment:14 Changed 4 years ago by
- Commit changed from fc45f1fbd7a9bab356bd2bfc62c43df585c1a8f5 to 81d47a3c2ce61fba3da2910ea4374294554b6c36
comment:15 Changed 4 years ago by
- Commit changed from 81d47a3c2ce61fba3da2910ea4374294554b6c36 to cb4e56e2d8c28b689908817f9f171a3599a3fc3c
Branch pushed to git repo; I updated commit sha1. New commits:
cb4e56e | Whitney twisting
|
comment:16 Changed 4 years ago by
- Commit changed from cb4e56e2d8c28b689908817f9f171a3599a3fc3c to 62e7658d83b2f5a2784a790bcaa4a85b82dcf4ce
Branch pushed to git repo; I updated commit sha1. New commits:
62e7658 | __init__ forces vertex labels to be integers
|
comment:17 Changed 4 years ago by
- Commit changed from 62e7658d83b2f5a2784a790bcaa4a85b82dcf4ce to e72b0ec4080ee8fc1cc1773f7f0857b301c33834
Branch pushed to git repo; I updated commit sha1. New commits:
eca714e | Merge branch 'develop' into t/23139/graphic_matroid_class
|
45a629a | Merge branch 'u/zgershkoff/graphic_matroid_class' of git://trac.sagemath.org/sage into t/23139/graphic_matroid_class
|
e72b0ec | GraphicMatroid in constructor + documentation
|
comment:18 Changed 4 years ago by
- Dependencies changed from 23300, 7304, 23290 to #23300, #7304, #23290
It looks like all the merging might have caused some isses. I'm going to try upgrading my SageMath installation and merging again. We'll see if that fixes it.
comment:19 Changed 4 years ago by
- Commit changed from e72b0ec4080ee8fc1cc1773f7f0857b301c33834 to c367dad1132f1defca49af1b066870f9b03626e5
Branch pushed to git repo; I updated commit sha1. New commits:
c367dad | typo in documentation
|
comment:20 Changed 4 years ago by
- Commit changed from c367dad1132f1defca49af1b066870f9b03626e5 to f20135075836319cc2fad5b50c36028b495b7e72
Branch pushed to git repo; I updated commit sha1. New commits:
f201350 | added a few examples
|
comment:21 Changed 4 years ago by
- Commit changed from f20135075836319cc2fad5b50c36028b495b7e72 to 49338d6f7d275b7fe3c430366becc740eef17cfe
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
35a7201 | Tabs instead of spaces. I blame the editor.
|
a77404f | Merge branch 't/23290/ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f' into t/7304/contract_edge_in_graph
|
29dd861 | efficiency improvements
|
a444488 | additional tests
|
4383814 | redundancy in tests
|
645c3e7 | Documentation fixes
|
50a884f | a bit of extra whitespace...
|
6f2a583 | proper demarcation of variables
|
000cb47 | Merge branch 't/7304/contract_edge_in_graph' into t/23139/graphic_matroid_class
|
49338d6 | Merge branch 'develop' into t/23139/graphic_matroid_class
|
comment:22 Changed 4 years ago by
- Commit changed from 49338d6f7d275b7fe3c430366becc740eef17cfe to f6886676362a77e529cec1382a392568df32a3b8
comment:23 Changed 4 years ago by
- Commit changed from f6886676362a77e529cec1382a392568df32a3b8 to df360b4067d14deda1e2078f4bec911421f08aeb
Branch pushed to git repo; I updated commit sha1. New commits:
df360b4 | methods for comparison
|
comment:24 Changed 4 years ago by
- Commit changed from df360b4067d14deda1e2078f4bec911421f08aeb to 3bbd89e807999e30e13ddea1062409000d8b24fd
Branch pushed to git repo; I updated commit sha1. New commits:
3bbd89e | Repair and tests for Whitney twisting
|
comment:25 Changed 4 years ago by
- Commit changed from 3bbd89e807999e30e13ddea1062409000d8b24fd to 0b1956d01e3ed4218a13d32baaf583017db12580
comment:26 Changed 4 years ago by
- Commit changed from 0b1956d01e3ed4218a13d32baaf583017db12580 to 8862db7c018be180ac8758b69154bdf3738ca222
Branch pushed to git repo; I updated commit sha1. New commits:
8862db7 | cleaned documentation a bit
|
comment:27 Changed 4 years ago by
- Commit changed from 8862db7c018be180ac8758b69154bdf3738ca222 to f187172ffb5eec7e62f9d24b6398ff3eceb059c9
Branch pushed to git repo; I updated commit sha1. New commits:
f187172 | no longer relabeling vertices; fixing tests; internal graph now immutable
|
comment:28 Changed 4 years ago by
- Commit changed from f187172ffb5eec7e62f9d24b6398ff3eceb059c9 to ddf7f77e5b697935ed2c952409f50713c0530d69
Branch pushed to git repo; I updated commit sha1. New commits:
ddf7f77 | added vertex_map method + tests
|
comment:29 Changed 4 years ago by
- Commit changed from ddf7f77e5b697935ed2c952409f50713c0530d69 to e79479daa3f007fd443ff8dd13085d8fdca32120
comment:30 Changed 4 years ago by
- Commit changed from e79479daa3f007fd443ff8dd13085d8fdca32120 to a4016906ba0c62176ab193c762bb536517bbe11d
Branch pushed to git repo; I updated commit sha1. New commits:
a401690 | graphic coextensions
|
comment:31 Changed 4 years ago by
- Commit changed from a4016906ba0c62176ab193c762bb536517bbe11d to 5124bbc7670428b7e3ec3659fc3736ebfd54dfd4
Branch pushed to git repo; I updated commit sha1. New commits:
5124bbc | fixing doctests related to constructor change
|
comment:32 Changed 4 years ago by
In the last commit, my editor removed a bunch of extra whitespace from lines.
Anyway, that's the last method I intended to add. It will be ready for review once I fix has_minor() and write documentation.
comment:33 Changed 4 years ago by
- Dependencies changed from #23300, #7304, #23290 to #23300, #7304, #23290, #23382
This conflicts with #23382.
comment:34 Changed 4 years ago by
- Commit changed from 5124bbc7670428b7e3ec3659fc3736ebfd54dfd4 to a523bcf59c0336f35f1ac38ef4d942f887870baa
Branch pushed to git repo; I updated commit sha1. New commits:
decc560 | Progress on _has_minor(); fix to advanced.py since I'm already here
|
221bf30 | fixed import statements and added tests
|
b443da7 | modified imports according to trac comment
|
54afceb | Merge branch 't/23139/graphic_matroid_class' into t/23300/non_absolute_import_in_basisexchangematroid
|
a523bcf | Merge branch 't/23300/non_absolute_import_in_basisexchangematroid' into t/23139/graphic_matroid_class
|
comment:35 Changed 4 years ago by
- Commit changed from a523bcf59c0336f35f1ac38ef4d942f887870baa to f62d81f3a879f670886cdd806cb6e7efcda0f656
comment:36 Changed 4 years ago by
- Commit changed from f62d81f3a879f670886cdd806cb6e7efcda0f656 to 4233c04634662c647cc11cd4e2d4b860419e4f99
Branch pushed to git repo; I updated commit sha1. New commits:
4233c04 | minor typo fix
|
comment:37 Changed 4 years ago by
- Commit changed from 4233c04634662c647cc11cd4e2d4b860419e4f99 to 6a5f736260dd32b93c6c98d8c194b5b5a9f76de7
comment:38 Changed 4 years ago by
- Commit changed from 6a5f736260dd32b93c6c98d8c194b5b5a9f76de7 to aeb384eee86f36388a0aa8e6daca5ba540bc6d61
Branch pushed to git repo; I updated commit sha1. New commits:
aeb384e | This simpler fix works too
|
comment:39 Changed 4 years ago by
All methods work now. I'll set to needs review after merging in #23382.
comment:40 Changed 4 years ago by
- Commit changed from aeb384eee86f36388a0aa8e6daca5ba540bc6d61 to 9e5449c3733d743a06e289ad12244fbfda05d83a
Branch pushed to git repo; I updated commit sha1. New commits:
9e5449c | revert documentation changes to advanced.py
|
comment:41 Changed 4 years ago by
- Commit changed from 9e5449c3733d743a06e289ad12244fbfda05d83a to 6f39bed25bc3dcdafd9fecde54ab9d80e02c93dd
comment:42 Changed 4 years ago by
- Commit changed from 6f39bed25bc3dcdafd9fecde54ab9d80e02c93dd to 6f3be59fe168dc62c522768be7241f008f69ed37
Branch pushed to git repo; I updated commit sha1. New commits:
23a7260 | Clean up matroid constructor
|
e25d425 | Merge branch 't/23382/clean_up_matroid_constructor' into t/23139/graphic_matroid_class
|
59353c6 | fixing error related to merge
|
6be79b6 | efficiency improvements, which changed a lot of tests
|
6f3be59 | removed methods where the default implementation is faster
|
comment:44 Changed 4 years ago by
- Commit changed from 6f3be59fe168dc62c522768be7241f008f69ed37 to 1624418e89eaba215f385c3e79038bceacbfdd8c
Branch pushed to git repo; I updated commit sha1. New commits:
1624418 | bug fix to graphic_coextensions
|
comment:45 Changed 4 years ago by
- Commit changed from 1624418e89eaba215f385c3e79038bceacbfdd8c to afe42d5867721db8489c9d32a4a4771021574943
Branch pushed to git repo; I updated commit sha1. New commits:
afe42d5 | removing redundant lines
|
comment:46 Changed 4 years ago by
- Commit changed from afe42d5867721db8489c9d32a4a4771021574943 to 32805418f0e8756bbd4a958b17562f19b06bc582
Branch pushed to git repo; I updated commit sha1. New commits:
3280541 | fixed a serious error regarding ground set labels
|
comment:47 Changed 3 years ago by
- Reviewers set to Stefan van Zwam
- Status changed from needs_review to needs_work
I have a lot of (mostly minor) comments. They are broken down by file and by line. The functions graphic_extensions and graphic_coextensions need the most work, I think.
Comments for Trac:23139 graphicmatroid.py ================= l.22 include a "regular_matroid" method that returns the RegularMatroid associated with M(G). Use this in the Matroid constructor function too. Do this on a new ticket. l.82 remove Stefan van Zwam l.108 include OUTPUT block. l.108ish include documentation explaining the treatment of disconnected graphs (maybe as ..NOTE:: or ..WARNING:: block?). Change the examples block as follows (example stolen from the __init__ method) EXAMPLES:: sage: from sage.matroids.advanced import * sage: M = GraphicMatroid(graphs.BullGraph()); M Graphic matroid of rank 4 on 5 elements sage: N = GraphicMatroid(graphs.CompleteBipartiteGraph(3,3)); N Graphic matroid of rank 5 on 9 elements A disconnected input will get converted to a connected graph internally:: sage: G1 = graphs.CycleGraph(3); G2 = graphs.DiamondGraph() sage: G = G1.disjoint_union(G2) sage: len(G) 7 sage: G.is_connected() False sage: M = GraphicMatroid(G) sage: M Graphic matroid of rank 5 on 8 elements sage: H = M.graph() sage: H Looped multi-graph on 6 vertices sage: H.is_connected() True sage: M.is_connected() False You can still locate an edge using the vertices of the input graph:: sage: G1 = graphs.CycleGraph(3); G2 = graphs.DiamondGraph() sage: G = G1.disjoint_union(G2) sage: M = Matroid(G) sage: H = M.graph() sage: vm = M.vertex_map() sage: (u, v, l) = G.random_edge() sage: H.has_edge(vm[u], vm[v]) True l. 343 We made a choice for testing equality: the underlying graphs need to be the same. Document this here, with plenty of examples of things that either do or do not compare as equal! Include: isomorphic graphs, same edge labels, different vertex labels; disconnected matroids with different graph presentations; etc. A more subtle example where the vertex labels differ:: sage: G1 = Graph([(0,1,0),(0,2,1),(1,2,2)]) sage: G2 = Graph([(3,4,3),(3,5,4),(4,5,5),(4,6,6),(5,6,7)]) sage: G = G1.disjoint_union(G2) sage: H = G2.disjoint_union(G1) sage: Matroid(G) == Matroid(H) False sage: Matroid(G).equals(Matroid(H)) True l. 499 Include examples where N is not 3-connected. l. 533 space missing l. 733 slightly more efficient (only one "set" data structure gets created): vertices = set([u for (u, v, l) in edges]) vertices.union_update([v for (u, v, l) in edges]) l. 793 subset of ``X`` l. 830 This check slows things down unnecessarily. Instead, add an "else" statement to the for loop of l. 838 (if the loop finishes normally, i.e. the set was a forest, the else statement will be executed) l. 966, 1001 and numerous other places: when using keyword arguments, don't put spaces around = see https://www.python.org/dev/peps/pep-0008/#other-recommendations l. 1015 instead of reverting to abstract matroid isomorphism, maybe try to convert to a RegularMatroid instead? The same would be wise if N is a GraphicMatroid but 3-connectivity fails (then convert both to RegularMatroid instances simultaneously). l. 1054: this should probably be the only line of code for this method. Reverting to the abstract Matroid class is worse than just always carrying out this command, imho. l. 1178: This can be a one-liner: return [(self._groundset_edge_map[x][0], self._groundset_edge_map[x][1], x) for x in X] l. 1233 spaces again l. 1234 Documentation needs improvement. You need to mention explicitly the behavior when the vertex label is new. And when both labels are new, the new graph will do one of its automatic merges, which should be documented. Example: sage: M = Matroid(graphs.PetersenGraph()) sage: M.graphic_extension('a', 'b', 'c').graph().vertices() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'b'] Note no vertex 'a' exists. One way to reduce user error going undetected, would be to require that 'u' is a vertex of the current graph. l. 1266 This comment is wrong l. 1275 same l. 1282 add an option "simple=False". If true, no parallel edges are added. l. 1285 add a paragraph explaining this function. Specifically, mention that it does not take 2-isomorphism into account, and only extends the current graph representation. l. 1325 the argument to "issubset" does not need to be a set, can just be an iterable. l. 1344 instead of this, research and use the "yield" command. l. 1348 explain what happens if X is None. l. 1360 coextended l. 1429 I don't trust this line. e.g.: sage: M = Matroid(Graph()) sage: N = M.graphic_coextension(0) sage: N Graphic matroid of rank 0 on 1 elements That's not what you meant, right? l. 1433 maybe have an optional argument for the new vertex label? l. 1435 no need for named vertices l. 1440 maybe another argument cosimple=False? If set to True, only do the vertex splits that have >= two edges on each side. l. 1442 Again, write more documentation about what this does, and how it handles low connectivity. l. 1456 Thinking about this, there are only two logical design choices that I can see. Either the method returns "every vertex split in every possible way", or it returns "one extension by a coloop, one copy of each coextension by a series element, and otherwise simple coextensions." I'm inclined to prefer the latter: it seems to mimic the behavior of the graphic_extensions method better, and fits the typical use case of generating all non-isomorphic matroids up to a certain size. Whichever choice you make, go all the way. Right now, the method does something in-between (in l. 1537, if both u and v are in "vertices", only one copy of the new edge will be created, attached to the latter). Also: document clearly what the method does! l. 1522 see l. 1325 l. 1528 again, use "yield" for more efficient code (in terms of memory consumption). Especially important in the cographic case. l. 1531 again, perhaps add an optional argument for the new vertex label? l. 1537 if (u, v, l) is such an edge then the new edge will be attached to v. But we want to attach it to u if u is in the set "vertices" but v is not. l. 1550 this bit can be cleaner. Start with l. 1555: just pick an element that will always be part of "g". Then iterate over all partitions of the rest. l. 1652 no "set" needed in argument for union l. 1659 can use "pop()" here l. 1800 no need for named arguments utilities.py: ============= l. 728 spaces l. 739, 741 inconsistent capitalization linear_matroid.pyx ================== l. 504 as long as you're editing this line anyway, change "it's" to "its" constructor.py ============== Here, too, you should include an example that illustrate what happens to disconnected graphs. You can reuse the one from above.
comment:48 Changed 3 years ago by
- Commit changed from 32805418f0e8756bbd4a958b17562f19b06bc582 to f8c07a629e59794c6dcc3b6e4059eb26813e3152
Branch pushed to git repo; I updated commit sha1. New commits:
7d0a0db | some unimpactful changes
|
0521ad6 | added disconnected example to constructor
|
30b06de | changes to graphic_extensions and graphic_coextensions
|
ca187b5 | further changes to graphic_coextensions
|
c65b05d | purging spaces from equals signs for keywords
|
f8b4165 | added regular matroid stuff;
|
8bdcdb4 | fix to graphic_extension
|
f8c07a6 | documentation improvements
|
comment:49 Changed 3 years ago by
Thanks for the feedback. The line numbers have changed, of course, but here are some issues I had according to the line numbers in your comments.
- l.22 When I first read "do this in a new ticket", I thought you meant adding the example in the constructor. I went ahead and made the
regular_matroid()
method. I think that's fine, since I use it now in_is_isomorphic()
and_has_minor()
. - l. 1456 I don't really follow this... Right now the method will (1) add a single coloop, (2), add edges in series to the relevant edges, and (3) split every vertex of degree 4 or greater in every way possible, as long as there are at least two edges on each side. I thought that (3) was precisely the (co)simple coextensions.
- l. 1659 I don't think
pop()
is what I want here, since I use the setvertices
later in the method and I don't want to modify it.
comment:50 Changed 3 years ago by
- Commit changed from f8c07a629e59794c6dcc3b6e4059eb26813e3152 to 8715022529eb41b02ab180fbbb8db0fb08337bca
comment:51 Changed 3 years ago by
- Commit changed from 8715022529eb41b02ab180fbbb8db0fb08337bca to 65fe6b6b76d26473d156685fb27bc37e427c94cb
Branch pushed to git repo; I updated commit sha1. New commits:
65fe6b6 | small copy-paste error
|
comment:52 Changed 3 years ago by
- Commit changed from 65fe6b6b76d26473d156685fb27bc37e427c94cb to f7594d5b0b5b35862700770cded87fb531daed3f
Branch pushed to git repo; I updated commit sha1. New commits:
f7594d5 | fixed some edge cases in graphic_coextension
|
comment:53 Changed 3 years ago by
- Status changed from needs_work to needs_review
comment:54 Changed 3 years ago by
- Commit changed from f7594d5b0b5b35862700770cded87fb531daed3f to ab082da122cbad128dba340f84414211443cc900
Branch pushed to git repo; I updated commit sha1. New commits:
ab082da | redacted unnessary lines
|
comment:55 Changed 3 years ago by
- Commit changed from ab082da122cbad128dba340f84414211443cc900 to 60b72c41e44857ccd652710144f4b4baf3b6ee48
Branch pushed to git repo; I updated commit sha1. New commits:
60b72c4 | graphic_coextensions now respects series classes
|
comment:56 Changed 3 years ago by
It should be good to go now, except for any future merge conflicts.
comment:57 Changed 3 years ago by
- Status changed from needs_review to needs_work
A few more edits. Note that there's a merge conflict again!
graphic_matroid.py ================== l.116 ``instance'' should be singular l.382 ``must'' -> ``to be'' l.531,564 missing OUTPUT blocks (check elsewhere too, please) l.1095 space l.1312 documentation does not match examples and behavior (``u`` can't be a new vertex) l.1349 add test showing the addition of a coloop to the empty graph. sage: M = Matroid(Graph()) sage: M.graphic_extension(0,1,'a') Graphic matroid of rank 1 on 1 elements l.1561 It makes more sense to modify this method so that ``u`` is always a vertex of the graph, just as in graphic_extension l.1699 If is_cosimple=True, the empty graphic matroid should not have any coextensions. DOCTESTS: ========= avoid printing frozensets, as the order is not guaranteed to remain constant (it's a set after all). I had the following failures: sage -t --warn-long 15.0 src/sage/matroids/graphic_matroid.py ********************************************************************** File "src/sage/matroids/graphic_matroid.py", line 844, in sage.matroids.graphic_matroid.GraphicMatroid._max_coindependent Failed example: N.max_coindependent([0,1,2,'a']) Expected: frozenset({1, 2, 'a'}) Got: frozenset({'a', 1, 2}) ********************************************************************** File "src/sage/matroids/graphic_matroid.py", line 961, in sage.matroids.graphic_matroid.GraphicMatroid._coclosure Failed example: N._coclosure([3]) Expected: frozenset({3, 4, 'a'}) Got: frozenset({'a', 3, 4}) ********************************************************************** 2 items had failures: 1 of 8 in sage.matroids.graphic_matroid.GraphicMatroid._coclosure 1 of 6 in sage.matroids.graphic_matroid.GraphicMatroid._max_coindependent [334 tests, 2 failures, 1.46 s]
comment:58 Changed 3 years ago by
- Commit changed from 60b72c41e44857ccd652710144f4b4baf3b6ee48 to e06c11d264f9f197417fed26f41eb684ed453383
Branch pushed to git repo; I updated commit sha1. New commits:
d95a2dc | changes to documentation and doctests
|
2af2646 | Merge branch 'develop' into t/23139/graphic_matroid_class
|
4ec92d0 | removed most frozensets from tests
|
e95e825 | Empty graphic matroid now has a graph of order 1
|
e06c11d | adding test for new error
|
comment:59 Changed 3 years ago by
- Status changed from needs_work to needs_review
I changed __init__()
so the empty graphic matroid will have a single vertex for its graph. This eliminates the need to test for empty graphs from the extension and coextension methods, and it solves the problem of not being able to extend and coextend in an empty matroid.
comment:60 Changed 3 years ago by
I'm still getting doctest errors. This is related to #23590. Perhaps you can change these so they don't mix strings and integers?
********************************************************************** File "src/sage/matroids/graphic_matroid.py", line 860, in sage.matroids.graphic_matroid.GraphicMatroid._max_coindependent Failed example: sorted(N.max_coindependent([0,1,2,'a'])) Expected: [1, 2, 'a'] Got: ['a', 1, 2] ********************************************************************** File "src/sage/matroids/graphic_matroid.py", line 977, in sage.matroids.graphic_matroid.GraphicMatroid._coclosure Failed example: sorted(N._coclosure([3])) Expected: [3, 4, 'a'] Got: ['a', 3, 4] **********************************************************************
After that you'll get a positive review.
comment:61 Changed 3 years ago by
- Status changed from needs_review to needs_work
comment:62 Changed 3 years ago by
In fact, that might even completely break when we go to Python3. For mixing types with strings, it is best to use str
as the key. Although that may not be the best in production code (as opposed to in doctests).
comment:63 Changed 3 years ago by
- Commit changed from e06c11d264f9f197417fed26f41eb684ed453383 to 93dadf81dd72bda85d3f318a7c51ce4dc93cd057
Branch pushed to git repo; I updated commit sha1. New commits:
93dadf8 | changed some examples
|
comment:64 Changed 3 years ago by
- Status changed from needs_work to needs_review
I assume a general fix for that, if we need one, is outside the scope of this ticket.
comment:65 Changed 3 years ago by
- Status changed from needs_review to positive_review
It all looks good now. Setting it to positive review; I also edited the "Authors" field.
comment:66 Changed 3 years ago by
- Status changed from positive_review to needs_work
See also patchbot
sage -t --long src/sage/algebras/orlik_solomon.py # 7 doctests failed
comment:67 Changed 3 years ago by
- Commit changed from 93dadf81dd72bda85d3f318a7c51ce4dc93cd057 to 8f2673678c1c445d35bfe18fe79eecedab3d8e87
comment:68 Changed 3 years ago by
- Status changed from needs_work to needs_review
I didn't realize those patchbot errors were relevant. Doctests pass in that file now.
comment:69 follow-up: ↓ 70 Changed 3 years ago by
- Milestone changed from sage-8.0 to sage-8.1
- Status changed from needs_review to needs_info
Am I correct in my understanding that these tests were failing because you were constructing isomorphic-but-not-identical matroids? If so, that means this changes is backwards incompatible as the doctests indicate. Actually, perhaps to avoid backwards-incompatible changes, it is better for unlabeled graphs with no multiple edges to have an ground set be the edge pairs.
Actually, I am not sure I understand why this change is needed as the groundset is range(len(G.edges()))
:
@@ -359,7 +359,7 @@ class OrlikSolomonAlgebra(CombinatorialFreeModule): TESTS:: sage: G = Graph([[1,2],[1,2],[2,3],[2,3],[1,3],[1,3]], multiedges=True) - sage: M = Matroid(G) + sage: M = Matroid(G, regular=True) sage: sorted([sorted(c) for c in M.circuits()]) [[0, 1], [0, 2, 4], [0, 2, 5], [0, 3, 4], [0, 3, 5], [1, 2, 4], [1, 2, 5], [1, 3, 4],
Also, the doctest failure
AttributeError: 'GraphicMatroid' object has no attribute 'groundset_list'
indicates that there is an inconsistency with other types of matroids.
Some other quick comments/questions:
- Remove "SageMath" from the doc, especially where it is being used as an adjective.
- Your
INPUT:
blocks should be of the form:- ``var_name`` -- some short description with no capitalization or period
Even if this is done is other matroid files, IMO it is good to try and follow Sage's documentation conventions. - For comments:
if foo: # It is easier to read and understand if the comments # are at the next level
- For PEP8, use, e.g.,
Matroid(G, regular=True)
, notMatroid(G, regular = True)
. - In
_coclosure
, you need a blankline afterINPUT
. - I hate tables of methods, so IMO, it should be killed with fire and holy water. Everything you need is included below, and they are a pain to maintain (because you have to do it manually). However, that is my personal opinion, and I won't say you need to remove it. Yet, what you are referencing are methods, not functions, so use
:meth:
instead of:func:
. RegularMatroid
is not a module, but a class. So-:mod:`RegularMatroid <sage.matroids.linear_matroid.RegularMatroid>` +:class:`~sage.matroids.linear_matroid.RegularMatroid`
- The leading tilde
~
just has the last object displayed in the doc, so you can do-:meth:`regular_matroid <sage.matroids.graphic_matroids.GraphicMatroid.regular_matroid>` +:meth:`~sage.matroids.graphic_matroids.GraphicMatroid.regular_matroid`
- I think it would be good to add a
TestSuite(M).run()
in theGraphicMatroid.__init__
method on some graphic matroidM
.
comment:70 in reply to: ↑ 69 ; follow-up: ↓ 73 Changed 3 years ago by
Replying to tscrim:
Am I correct in my understanding that these tests were failing because you were constructing isomorphic-but-not-identical matroids?
Yes, but in two different ways. Some tests fail because the ground set labels are different, and some tests fail because it wants a BasisExchangeMatroid
and gets a GraphicMatroid
.
As I understand it, when the constructor takes a graph to make a RegularMatroid
, it will use vertex tuples as ground set labels unless there are multiedges, where it will use integers instead. I think this is the right behavior for representing a graph with a matrix, since we lose the context of the graph, but I think it's unnecessary when we still have the graph attached to the matroid.
The method groundset_list()
belongs to BasisExchangeMatroid
, which is a superclass of RegularMatroid
. It looks like other matroid classes don't have it, and it doesn't seem like it would translate easily since only BasisExchangeMatroid
s have the attribute _E
. When orlik-solomon.py was written, they were probably expecting a regular matroid, which is why I changed the test to give it one.
Actually, I am not sure I understand why this change is needed as the groundset is
range(len(G.edges()))
:@@ -359,7 +359,7 @@ class OrlikSolomonAlgebra(CombinatorialFreeModule): TESTS:: sage: G = Graph([[1,2],[1,2],[2,3],[2,3],[1,3],[1,3]], multiedges=True) - sage: M = Matroid(G) + sage: M = Matroid(G, regular=True) sage: sorted([sorted(c) for c in M.circuits()]) [[0, 1], [0, 2, 4], [0, 2, 5], [0, 3, 4], [0, 3, 5], [1, 2, 4], [1, 2, 5], [1, 3, 4],
That particular change probably wasn't needed. I just went through and changed them all to be regular matroids.
I'll look into the other documentation and spacing conventions, and make changes soon.
comment:71 Changed 3 years ago by
- Commit changed from 8f2673678c1c445d35bfe18fe79eecedab3d8e87 to a55743d1abffc10baf0f95d4ca8b99d238c11189
Branch pushed to git repo; I updated commit sha1. New commits:
c011d58 | Revert "changing examples so matroids from graphs are RegularMatroids where necessary"
|
0296beb | fixing orlik_solomon doctests, minimally
|
ac0aaf4 | removed spaces from keyword assignments
|
206d736 | removed SageMath
|
a55743d | added missing blankline
|
comment:72 follow-up: ↓ 74 Changed 3 years ago by
Not too sure what to do to fix the input blocks. The documentation I could find on the conventions http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings indicates that they're short with no capitalization at the beginning or punctuation at the end, unless they're long and verbose.
comment:73 in reply to: ↑ 70 Changed 3 years ago by
Replying to zgershkoff:
Replying to tscrim:
Am I correct in my understanding that these tests were failing because you were constructing isomorphic-but-not-identical matroids?
Yes, but in two different ways. Some tests fail because the ground set labels are different, and some tests fail because it wants a
BasisExchangeMatroid
and gets aGraphicMatroid
.As I understand it, when the constructor takes a graph to make a
RegularMatroid
, it will use vertex tuples as ground set labels unless there are multiedges, where it will use integers instead. I think this is the right behavior for representing a graph with a matrix, since we lose the context of the graph, but I think it's unnecessary when we still have the graph attached to the matroid.
My point about backwards incompatibility is still valid, as well as my recommendation about the groundset for unlabeled (simple) graphs to try and alleviate the problem. You do loose the association between the groundset and the graph by not using the edges as the groundset for unlabeled graphs. So I do not completely agree with your point.
The method
groundset_list()
belongs toBasisExchangeMatroid
, which is a superclass ofRegularMatroid
. It looks like other matroid classes don't have it, and it doesn't seem like it would translate easily since onlyBasisExchangeMatroid
s have the attribute_E
. When orlik-solomon.py was written, they were probably expecting a regular matroid, which is why I changed the test to give it one.
Well, it's not explicitly used within the code of the Orlik-Solomon algebras, but only for this method. If it is something only for RegualrMatroid
, then we can just change the input to sort the groundset, which would be in line with what the OS code does.
comment:74 in reply to: ↑ 72 Changed 3 years ago by
Replying to zgershkoff:
Not too sure what to do to fix the input blocks. The documentation I could find on the conventions http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings indicates that they're short with no capitalization at the beginning or punctuation at the end, unless they're long and verbose.
For example:
- - `X` -- an object with Python's ``frozenset`` interface. + - ``X`` -- an object with Python's ``frozenset`` interface
- - ``other`` -- A matroid. + - ``other`` -- a matroid
- - ``contractions`` -- frozenset, subset of ``self.groundset()`` to be contracted - - ``deletions`` -- frozenset, subset of ``self.groundset()`` to be deleted + - ``contractions`` -- frozenset; subset of ``self.groundset()`` to be contracted + - ``deletions`` -- frozenset; subset of ``self.groundset()`` to be deleted
- - ``N`` - A matroid. - - ``certificate`` - (default: ``False``) If ``True``, returns - either ``False, None`` or - ``True, (X, Y, dic) where ``N`` is isomorphic to ``self.minor(X, Y)``, - and ``dic`` is an isomorphism between ``N`` and ``self.minor(X, Y)``. + - ``N`` -- a matroid + - ``certificate`` -- (default: ``False``) if ``True``, returns the certificate + isomorphism from the minor of ``self`` to ``N``
(The data on the certificate should be in the OUTPUT
block.)
- - ``X`` -- An object with Python's ``frozenset`` interface containing - a subset of ``self.groundset()``. + - ``X`` -- an object with Python's ``frozenset`` interface containing + a subset of ``self.groundset()``
There are others. Also, remove the INPUT:
when there is no (non-self
) input.
comment:75 Changed 3 years ago by
- Commit changed from a55743d1abffc10baf0f95d4ca8b99d238c11189 to 9cb9b7d02f4ec9a583ffa570fba3effb574d366c
comment:76 follow-up: ↓ 77 Changed 3 years ago by
Travis, regarding backwards compatibility: would you be happy with the following compromise?
CHANGE:
Matroid(G)
returnsGraphicMatroid
instead ofRegularMatroid
matroids.CompleteGraphic()
returnsGraphicMatroid
instead ofRegularMatroid
- same for
matroids.Wheel()
if no field is given,matroids.named_matroids.Terrahawk()
STAY THE SAME:
- default groundset generator for the
Matroid()
constructor function on input of a graph - groundsets for the special matroids mentioned above.
EDIT: this way, the identity function on the groundset is an isomorphism, but the different classes don't overlap completely in their methods.
comment:77 in reply to: ↑ 76 Changed 3 years ago by
Replying to Stefan:
Travis, regarding backwards compatibility: would you be happy with the following compromise?
CHANGE:
Matroid(G)
returnsGraphicMatroid
instead ofRegularMatroid
matroids.CompleteGraphic()
returnsGraphicMatroid
instead ofRegularMatroid
- same for
matroids.Wheel()
if no field is given,matroids.named_matroids.Terrahawk()
STAY THE SAME:
- default groundset generator for the
Matroid()
constructor function on input of a graph- groundsets for the special matroids mentioned above.
That was precisely what I was proposing (although I may have done so horribly). So, sorry, that is not much of a compromise. :P (Edit: I am saying I agree to this completely.)
IMO, having the groundset being the edges is a little more clear.
EDIT: this way, the identity function on the groundset is an isomorphism, but the different classes don't overlap completely in their methods.
That is okay for now. We can fix things as we go along as we find the methods that are missing. I just pointed out groundset_list
because it became relevant via the doctest (but I agree that it does not make sense beyond the RegularMatroid
class).
comment:78 Changed 3 years ago by
Imposing an order on the groundset is not important for most matroid classes; it becomes useful when the elements label columns of a matrix or something. I see no need to have it added to the GraphicMatroid? class.
comment:79 Changed 3 years ago by
- Commit changed from 9cb9b7d02f4ec9a583ffa570fba3effb574d366c to aeb20302bf35c1a0da2f27fbafbcf2e116d01cf2
Branch pushed to git repo; I updated commit sha1. New commits:
fea316d | added test using testsuite
|
b9bf5ad | fixing :meth: and :class: and such
|
e57a248 | trying ~ shortcut. will have to docbuild and look at it later
|
af0137f | backwards compatibility for groundset
|
3327bb0 | this groundset override is no longer necessary
|
aeb2030 | updating catalog documentation to reflect constructor changes
|
comment:80 Changed 3 years ago by
Maybe changing the type of matroids.Wheel()
and matroids.named_matroids.Terrahawk()
should be in another ticket?
matroids.CompleteGraphic()
automatically changed to GraphicMatroid
when the constructor was changed, but the others look like a bit of work (Wheel
in particular, since using range(2n)
for the groundset doesn't assign labels to the edges in the best way, and since the cases when n is one of {0,1,2} will probably have to be handled separately.)
comment:81 Changed 3 years ago by
Ok, save those for another ticket.
comment:82 Changed 3 years ago by
Do you really want the (essentially useless) table of methods for that class that you have to manually maintain? There are not anywhere near enough methods to justify such a table. If you really insist on that clutter table, then at least make it automatic as what graph.py
does (manually maintaining it is too much of a pain and easy to forget). However, that is not currently compatible with Cython if this ends up being Cythonized (which is something that might be a good followup ticket).
comment:83 Changed 3 years ago by
- Commit changed from aeb20302bf35c1a0da2f27fbafbcf2e116d01cf2 to 7c7b7883c4140d5a12c1c50b2c2b6dcbb0c5c3d3
Branch pushed to git repo; I updated commit sha1. New commits:
7c7b788 | removing method table
|
comment:84 Changed 3 years ago by
- Status changed from needs_info to needs_review
I don't mind removing it. The main reason to have it there is so a user can scroll past overrides like is_valid
, but there aren't many of those.
I can't get the documentation to build correctly on my machine. I'll probably have to delete sage and install it again. Before I do that, I'll try to get these tickets closed.
comment:85 Changed 3 years ago by
- Reviewers changed from Stefan van Zwam to Stefan van Zwam, Travis Scrimshaw
- Status changed from needs_review to positive_review
Thank you for all the changes and your work on this (including Stefan and his review).
comment:86 Changed 3 years ago by
- Keywords days88 IMA coding sprints added
comment:87 Changed 3 years ago by
- Dependencies changed from #23300, #7304, #23290, #23382 to #23300, #23290, #23382
Removing this dependency (even though it's true) in case it's causing a problem for the release script.
comment:88 Changed 3 years ago by
- Status changed from positive_review to needs_work
On 32-bit:
File "src/sage/matroids/graphic_matroid.py", line 591, in sage.matroids.graphic_matroid.GraphicMatroid._has_minor Failed example: M._has_minor(N, certificate=True) Expected: (True, (frozenset({3, 6, 8}), frozenset({2, 4, 5}), {0: 0, 1: 1, 2: 7})) Got: (True, (frozenset({1, 5, 6}), frozenset({4, 7, 8}), {0: 2, 1: 0, 2: 3})) ********************************************************************** 1 item had failures: 1 of 18 in sage.matroids.graphic_matroid.GraphicMatroid._has_minor [345 tests, 1 failure, 1.37 s]
comment:89 Changed 3 years ago by
- Commit changed from 7c7b7883c4140d5a12c1c50b2c2b6dcbb0c5c3d3 to b02233a376d2dbe58fc5474df28ee6754d967be3
Branch pushed to git repo; I updated commit sha1. New commits:
b02233a | changing test for _has_minor
|
comment:90 Changed 3 years ago by
- Status changed from needs_work to needs_review
Everything passes on my end, but I changed that example to just count the elements instead of telling us what they are.
comment:91 Changed 3 years ago by
I think a better test is to verify that the certificate is an isomorphism:
sage: val, cert = M._has_minor(N1, certificate=True) sage: Mp = M.minor(cert[0], cert[1]) sage: M.is_isomorphism(N1, cert[2]) True
comment:92 Changed 3 years ago by
Given that it's the hidden-from-end-users version of the method, I'm ok with either solution.
comment:93 Changed 3 years ago by
- Commit changed from b02233a376d2dbe58fc5474df28ee6754d967be3 to b930927f030c1871d84cc8d921a21b4c8e9a6b1c
Branch pushed to git repo; I updated commit sha1. New commits:
b930927 | removed minor certificates from displaying in tests
|
comment:94 Changed 3 years ago by
I changed it so none of the certificates print in the tests, just in case they're different on some other system.
comment:96 Changed 3 years ago by
- Branch changed from u/zgershkoff/graphic_matroid_class to b930927f030c1871d84cc8d921a21b4c8e9a6b1c
- Resolution set to fixed
- Status changed from positive_review to closed
comment:97 Changed 3 years ago by
- Commit b930927f030c1871d84cc8d921a21b4c8e9a6b1c deleted
I'm uploading my progress for visibility's sake. I still need to implement Whitney switching, make an override for
_has_minor()
, and write the documentation and examples, among other things.New commits:
The basic idea