#23139 closed enhancement (fixed)
Graphic Matroid class
Reported by:  Zach Gershkoff  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  matroid theory  Keywords:  days88, IMA coding sprints 
Cc:  Stefan, Michael Welsh, Travis Scrimshaw  Merged in:  
Authors:  Zach Gershkoff  Reviewers:  Stefan van Zwam, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  b930927 (Commits, GitHub, GitLab)  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 6 years ago by
Cc:  Stefan Michael Welsh Travis Scrimshaw added 

Component:  PLEASE CHANGE → matroid theory 
Type:  PLEASE CHANGE → enhancement 
comment:2 Changed 6 years ago by
Branch:  → u/zgershkoff/graphic_matroid_class 

comment:3 Changed 6 years ago by
Commit:  → 33b0a831a47c28edf2a7fc1874f6d1f3be799f61 

Description:  modified (diff) 
comment:4 Changed 6 years ago by
Commit:  33b0a831a47c28edf2a7fc1874f6d1f3be799f61 → dd5ef4f6ac1aa9e2d07989a27bc8159b0f50322e 

Branch pushed to git repo; I updated commit sha1. New commits:
dd5ef4f  Beginnings of _has_minor()

comment:5 Changed 6 years ago by
Commit:  dd5ef4f6ac1aa9e2d07989a27bc8159b0f50322e → 92b08317bf3f34a9c2ed438c4a31aec54daf3029 

Branch pushed to git repo; I updated commit sha1. New commits:
92b0831  Refinements to _minor()

comment:6 Changed 6 years ago by
Commit:  92b08317bf3f34a9c2ed438c4a31aec54daf3029 → f47fdd36388353b20c1557eb2c76c2f85c3e09b8 

Branch pushed to git repo; I updated commit sha1. New commits:
f47fdd3  New methods + general tidiness

comment:7 Changed 5 years ago by
Commit:  f47fdd36388353b20c1557eb2c76c2f85c3e09b8 → fd54096f67e2dab1d98e0c680344ea12066999e5 

comment:8 Changed 5 years ago by
Commit:  fd54096f67e2dab1d98e0c680344ea12066999e5 → 02f7d4aae8b60455e7b1bba995b63966f37793d5 

comment:9 Changed 5 years ago by
Commit:  02f7d4aae8b60455e7b1bba995b63966f37793d5 → 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 5 years ago by
Commit:  a1f31cd328a9a74bdd1afc5f7ff0949e681b17ad → fb7f8e7a41884aff0d99e7694fbc0db90c3d0848 

Branch pushed to git repo; I updated commit sha1. New commits:
fb7f8e7  Moved contract_edge() to utilities; added _closure()

comment:11 Changed 5 years ago by
Commit:  fb7f8e7a41884aff0d99e7694fbc0db90c3d0848 → 7d854ebfe8f028d2bb2592cf5210c338f38bfb10 

comment:12 Changed 5 years ago by
Commit:  7d854ebfe8f028d2bb2592cf5210c338f38bfb10 → fc45f1fbd7a9bab356bd2bfc62c43df585c1a8f5 

comment:13 Changed 5 years ago by
Dependencies:  → 23300, 7304, 23290 

comment:14 Changed 5 years ago by
Commit:  fc45f1fbd7a9bab356bd2bfc62c43df585c1a8f5 → 81d47a3c2ce61fba3da2910ea4374294554b6c36 

comment:15 Changed 5 years ago by
Commit:  81d47a3c2ce61fba3da2910ea4374294554b6c36 → cb4e56e2d8c28b689908817f9f171a3599a3fc3c 

Branch pushed to git repo; I updated commit sha1. New commits:
cb4e56e  Whitney twisting

comment:16 Changed 5 years ago by
Commit:  cb4e56e2d8c28b689908817f9f171a3599a3fc3c → 62e7658d83b2f5a2784a790bcaa4a85b82dcf4ce 

Branch pushed to git repo; I updated commit sha1. New commits:
62e7658  __init__ forces vertex labels to be integers

comment:17 Changed 5 years ago by
Commit:  62e7658d83b2f5a2784a790bcaa4a85b82dcf4ce → 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 5 years ago by
Dependencies:  23300, 7304, 23290 → #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 5 years ago by
Commit:  e72b0ec4080ee8fc1cc1773f7f0857b301c33834 → c367dad1132f1defca49af1b066870f9b03626e5 

Branch pushed to git repo; I updated commit sha1. New commits:
c367dad  typo in documentation

comment:20 Changed 5 years ago by
Commit:  c367dad1132f1defca49af1b066870f9b03626e5 → f20135075836319cc2fad5b50c36028b495b7e72 

Branch pushed to git repo; I updated commit sha1. New commits:
f201350  added a few examples

comment:21 Changed 5 years ago by
Commit:  f20135075836319cc2fad5b50c36028b495b7e72 → 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 5 years ago by
Commit:  49338d6f7d275b7fe3c430366becc740eef17cfe → f6886676362a77e529cec1382a392568df32a3b8 

comment:23 Changed 5 years ago by
Commit:  f6886676362a77e529cec1382a392568df32a3b8 → df360b4067d14deda1e2078f4bec911421f08aeb 

Branch pushed to git repo; I updated commit sha1. New commits:
df360b4  methods for comparison

comment:24 Changed 5 years ago by
Commit:  df360b4067d14deda1e2078f4bec911421f08aeb → 3bbd89e807999e30e13ddea1062409000d8b24fd 

Branch pushed to git repo; I updated commit sha1. New commits:
3bbd89e  Repair and tests for Whitney twisting

comment:25 Changed 5 years ago by
Commit:  3bbd89e807999e30e13ddea1062409000d8b24fd → 0b1956d01e3ed4218a13d32baaf583017db12580 

comment:26 Changed 5 years ago by
Commit:  0b1956d01e3ed4218a13d32baaf583017db12580 → 8862db7c018be180ac8758b69154bdf3738ca222 

Branch pushed to git repo; I updated commit sha1. New commits:
8862db7  cleaned documentation a bit

comment:27 Changed 5 years ago by
Commit:  8862db7c018be180ac8758b69154bdf3738ca222 → 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 5 years ago by
Commit:  f187172ffb5eec7e62f9d24b6398ff3eceb059c9 → ddf7f77e5b697935ed2c952409f50713c0530d69 

Branch pushed to git repo; I updated commit sha1. New commits:
ddf7f77  added vertex_map method + tests

comment:29 Changed 5 years ago by
Commit:  ddf7f77e5b697935ed2c952409f50713c0530d69 → e79479daa3f007fd443ff8dd13085d8fdca32120 

comment:30 Changed 5 years ago by
Commit:  e79479daa3f007fd443ff8dd13085d8fdca32120 → a4016906ba0c62176ab193c762bb536517bbe11d 

Branch pushed to git repo; I updated commit sha1. New commits:
a401690  graphic coextensions

comment:31 Changed 5 years ago by
Commit:  a4016906ba0c62176ab193c762bb536517bbe11d → 5124bbc7670428b7e3ec3659fc3736ebfd54dfd4 

Branch pushed to git repo; I updated commit sha1. New commits:
5124bbc  fixing doctests related to constructor change

comment:32 Changed 5 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 5 years ago by
Dependencies:  #23300, #7304, #23290 → #23300, #7304, #23290, #23382 

This conflicts with #23382.
comment:34 Changed 5 years ago by
Commit:  5124bbc7670428b7e3ec3659fc3736ebfd54dfd4 → 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 5 years ago by
Commit:  a523bcf59c0336f35f1ac38ef4d942f887870baa → f62d81f3a879f670886cdd806cb6e7efcda0f656 

comment:36 Changed 5 years ago by
Commit:  f62d81f3a879f670886cdd806cb6e7efcda0f656 → 4233c04634662c647cc11cd4e2d4b860419e4f99 

Branch pushed to git repo; I updated commit sha1. New commits:
4233c04  minor typo fix

comment:37 Changed 5 years ago by
Commit:  4233c04634662c647cc11cd4e2d4b860419e4f99 → 6a5f736260dd32b93c6c98d8c194b5b5a9f76de7 

comment:38 Changed 5 years ago by
Commit:  6a5f736260dd32b93c6c98d8c194b5b5a9f76de7 → aeb384eee86f36388a0aa8e6daca5ba540bc6d61 

Branch pushed to git repo; I updated commit sha1. New commits:
aeb384e  This simpler fix works too

comment:39 Changed 5 years ago by
All methods work now. I'll set to needs review after merging in #23382.
comment:40 Changed 5 years ago by
Commit:  aeb384eee86f36388a0aa8e6daca5ba540bc6d61 → 9e5449c3733d743a06e289ad12244fbfda05d83a 

Branch pushed to git repo; I updated commit sha1. New commits:
9e5449c  revert documentation changes to advanced.py

comment:41 Changed 5 years ago by
Commit:  9e5449c3733d743a06e289ad12244fbfda05d83a → 6f39bed25bc3dcdafd9fecde54ab9d80e02c93dd 

comment:42 Changed 5 years ago by
Commit:  6f39bed25bc3dcdafd9fecde54ab9d80e02c93dd → 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 5 years ago by
Commit:  6f3be59fe168dc62c522768be7241f008f69ed37 → 1624418e89eaba215f385c3e79038bceacbfdd8c 

Branch pushed to git repo; I updated commit sha1. New commits:
1624418  bug fix to graphic_coextensions

comment:45 Changed 5 years ago by
Commit:  1624418e89eaba215f385c3e79038bceacbfdd8c → afe42d5867721db8489c9d32a4a4771021574943 

Branch pushed to git repo; I updated commit sha1. New commits:
afe42d5  removing redundant lines

comment:46 Changed 5 years ago by
Commit:  afe42d5867721db8489c9d32a4a4771021574943 → 32805418f0e8756bbd4a958b17562f19b06bc582 

Branch pushed to git repo; I updated commit sha1. New commits:
3280541  fixed a serious error regarding ground set labels

comment:47 Changed 5 years ago by
Reviewers:  → Stefan van Zwam 

Status:  needs_review → 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 multigraph 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 3connected. 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/pep0008/#otherrecommendations 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 3connectivity 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 oneliner: 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 2isomorphism 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 nonisomorphic matroids up to a certain size. Whichever choice you make, go all the way. Right now, the method does something inbetween (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 5 years ago by
Commit:  32805418f0e8756bbd4a958b17562f19b06bc582 → 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 5 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 5 years ago by
Commit:  f8c07a629e59794c6dcc3b6e4059eb26813e3152 → 8715022529eb41b02ab180fbbb8db0fb08337bca 

comment:51 Changed 5 years ago by
Commit:  8715022529eb41b02ab180fbbb8db0fb08337bca → 65fe6b6b76d26473d156685fb27bc37e427c94cb 

Branch pushed to git repo; I updated commit sha1. New commits:
65fe6b6  small copypaste error

comment:52 Changed 5 years ago by
Commit:  65fe6b6b76d26473d156685fb27bc37e427c94cb → f7594d5b0b5b35862700770cded87fb531daed3f 

Branch pushed to git repo; I updated commit sha1. New commits:
f7594d5  fixed some edge cases in graphic_coextension

comment:53 Changed 5 years ago by
Status:  needs_work → needs_review 

comment:54 Changed 5 years ago by
Commit:  f7594d5b0b5b35862700770cded87fb531daed3f → ab082da122cbad128dba340f84414211443cc900 

Branch pushed to git repo; I updated commit sha1. New commits:
ab082da  redacted unnessary lines

comment:55 Changed 5 years ago by
Commit:  ab082da122cbad128dba340f84414211443cc900 → 60b72c41e44857ccd652710144f4b4baf3b6ee48 

Branch pushed to git repo; I updated commit sha1. New commits:
60b72c4  graphic_coextensions now respects series classes

comment:56 Changed 5 years ago by
It should be good to go now, except for any future merge conflicts.
comment:57 Changed 5 years ago by
Status:  needs_review → 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 warnlong 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 5 years ago by
Commit:  60b72c41e44857ccd652710144f4b4baf3b6ee48 → 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 5 years ago by
Status:  needs_work → 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 5 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 5 years ago by
Status:  needs_review → needs_work 

comment:62 Changed 5 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 5 years ago by
Commit:  e06c11d264f9f197417fed26f41eb684ed453383 → 93dadf81dd72bda85d3f318a7c51ce4dc93cd057 

Branch pushed to git repo; I updated commit sha1. New commits:
93dadf8  changed some examples

comment:64 Changed 5 years ago by
Status:  needs_work → needs_review 

I assume a general fix for that, if we need one, is outside the scope of this ticket.
comment:65 Changed 5 years ago by
Authors:  → Zachary Gershkoff 

Status:  needs_review → positive_review 
It all looks good now. Setting it to positive review; I also edited the "Authors" field.
comment:66 Changed 5 years ago by
Status:  positive_review → needs_work 

See also patchbot
sage t long src/sage/algebras/orlik_solomon.py # 7 doctests failed
comment:67 Changed 5 years ago by
Commit:  93dadf81dd72bda85d3f318a7c51ce4dc93cd057 → 8f2673678c1c445d35bfe18fe79eecedab3d8e87 

comment:68 Changed 5 years ago by
Status:  needs_work → needs_review 

I didn't realize those patchbot errors were relevant. Doctests pass in that file now.
comment:69 followup: 70 Changed 5 years ago by
Milestone:  sage8.0 → sage8.1 

Status:  needs_review → needs_info 
Am I correct in my understanding that these tests were failing because you were constructing isomorphicbutnotidentical matroids? If so, that means this changes is backwards incompatible as the doctests indicate. Actually, perhaps to avoid backwardsincompatible 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 followup: 73 Changed 5 years ago by
Replying to tscrim:
Am I correct in my understanding that these tests were failing because you were constructing isomorphicbutnotidentical 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 orliksolomon.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 5 years ago by
Commit:  8f2673678c1c445d35bfe18fe79eecedab3d8e87 → 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 followup: 74 Changed 5 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#documentationstrings indicates that they're short with no capitalization at the beginning or punctuation at the end, unless they're long and verbose.
comment:73 Changed 5 years ago by
Replying to zgershkoff:
Replying to tscrim:
Am I correct in my understanding that these tests were failing because you were constructing isomorphicbutnotidentical 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 orliksolomon.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 OrlikSolomon 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 Changed 5 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#documentationstrings 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 (nonself
) input.
comment:75 Changed 5 years ago by
Commit:  a55743d1abffc10baf0f95d4ca8b99d238c11189 → 9cb9b7d02f4ec9a583ffa570fba3effb574d366c 

comment:76 followup: 77 Changed 5 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 Changed 5 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 5 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 5 years ago by
Commit:  9cb9b7d02f4ec9a583ffa570fba3effb574d366c → 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 5 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:82 Changed 5 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 5 years ago by
Commit:  aeb20302bf35c1a0da2f27fbafbcf2e116d01cf2 → 7c7b7883c4140d5a12c1c50b2c2b6dcbb0c5c3d3 

Branch pushed to git repo; I updated commit sha1. New commits:
7c7b788  removing method table

comment:84 Changed 5 years ago by
Status:  needs_info → 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 5 years ago by
Reviewers:  Stefan van Zwam → Stefan van Zwam, Travis Scrimshaw 

Status:  needs_review → positive_review 
Thank you for all the changes and your work on this (including Stefan and his review).
comment:86 Changed 5 years ago by
Keywords:  days88 IMA coding sprints added 

comment:87 Changed 5 years ago by
Dependencies:  #23300, #7304, #23290, #23382 → #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 5 years ago by
Status:  positive_review → needs_work 

On 32bit:
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 5 years ago by
Commit:  7c7b7883c4140d5a12c1c50b2c2b6dcbb0c5c3d3 → b02233a376d2dbe58fc5474df28ee6754d967be3 

Branch pushed to git repo; I updated commit sha1. New commits:
b02233a  changing test for _has_minor

comment:90 Changed 5 years ago by
Status:  needs_work → 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 5 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 5 years ago by
Given that it's the hiddenfromendusers version of the method, I'm ok with either solution.
comment:93 Changed 5 years ago by
Commit:  b02233a376d2dbe58fc5474df28ee6754d967be3 → b930927f030c1871d84cc8d921a21b4c8e9a6b1c 

Branch pushed to git repo; I updated commit sha1. New commits:
b930927  removed minor certificates from displaying in tests

comment:94 Changed 5 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 5 years ago by
Branch:  u/zgershkoff/graphic_matroid_class → b930927f030c1871d84cc8d921a21b4c8e9a6b1c 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:97 Changed 5 years ago by
Authors:  Zachary Gershkoff → Zach Gershkoff 

Commit:  b930927f030c1871d84cc8d921a21b4c8e9a6b1c 
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