Opened 3 years ago

Closed 2 years ago

Last modified 2 years ago

#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 zgershkoff)

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 3 years ago by tscrim

  • Cc Stefan yomcat tscrim added
  • Component changed from PLEASE CHANGE to matroid theory
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 3 years ago by zgershkoff

  • Branch set to u/zgershkoff/graphic_matroid_class

comment:3 Changed 3 years ago by zgershkoff

  • Commit set to 33b0a831a47c28edf2a7fc1874f6d1f3be799f61
  • Description modified (diff)

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:

33b0a83The basic idea

comment:4 Changed 3 years ago by git

  • Commit changed from 33b0a831a47c28edf2a7fc1874f6d1f3be799f61 to dd5ef4f6ac1aa9e2d07989a27bc8159b0f50322e

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

dd5ef4fBeginnings of _has_minor()

comment:5 Changed 3 years ago by git

  • Commit changed from dd5ef4f6ac1aa9e2d07989a27bc8159b0f50322e to 92b08317bf3f34a9c2ed438c4a31aec54daf3029

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

92b0831Refinements to _minor()

comment:6 Changed 3 years ago by git

  • Commit changed from 92b08317bf3f34a9c2ed438c4a31aec54daf3029 to f47fdd36388353b20c1557eb2c76c2f85c3e09b8

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

f47fdd3New methods + general tidiness

comment:7 Changed 3 years ago by git

  • Commit changed from f47fdd36388353b20c1557eb2c76c2f85c3e09b8 to fd54096f67e2dab1d98e0c680344ea12066999e5

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

ca11a70_closure() method
dcd2fdeRepairs to how contraction is handled
fd54096circuit, cocircuit, coclosure, is_coindependent, is_independent

comment:8 Changed 2 years ago by git

  • Commit changed from fd54096f67e2dab1d98e0c680344ea12066999e5 to 02f7d4aae8b60455e7b1bba995b63966f37793d5

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

1e4fbcdRenaming cocircuit_edges to codependent_edges for clarity
02f7d4aAdded _is_cocircuit(), _is_isomorphic(), _isomorphism(). _isomorphism() needs debugging

comment:9 Changed 2 years ago by git

  • Commit changed from 02f7d4aae8b60455e7b1bba995b63966f37793d5 to a1f31cd328a9a74bdd1afc5f7ff0949e681b17ad

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

deab177Forgot to save comment on _isomorphism()
a71ee90Added graphic_extension(), graphic_extensions(), graphic_coextension(). Still need to test them.
d2ff13cSaving changes before I lose them
a1f31cdRefined extension/coextension methods after testing

comment:10 Changed 2 years ago by git

  • Commit changed from a1f31cd328a9a74bdd1afc5f7ff0949e681b17ad to fb7f8e7a41884aff0d99e7694fbc0db90c3d0848

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

fb7f8e7Moved contract_edge() to utilities; added _closure()

comment:11 Changed 2 years ago by git

  • Commit changed from fb7f8e7a41884aff0d99e7694fbc0db90c3d0848 to 7d854ebfe8f028d2bb2592cf5210c338f38bfb10

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

d63368a__init__ now forces the graph to be connected
7d854ebMoved internal method to utilities; changed an example

comment:12 Changed 2 years ago by git

  • Commit changed from 7d854ebfe8f028d2bb2592cf5210c338f38bfb10 to fc45f1fbd7a9bab356bd2bfc62c43df585c1a8f5

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

eae836bsmall fix to a test
fc45f1fdocumented said method; wrote user-facing groundset_to_edges

comment:13 Changed 2 years ago by zgershkoff

  • Dependencies set to 23300, 7304, 23290

comment:14 Changed 2 years ago by git

  • Commit changed from fc45f1fbd7a9bab356bd2bfc62c43df585c1a8f5 to 81d47a3c2ce61fba3da2910ea4374294554b6c36

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

42bca83Merge branch 'develop' into t/23139/graphic_matroid_class
81d47a3Improvements to __init__ and _rank

comment:15 Changed 2 years ago by git

  • Commit changed from 81d47a3c2ce61fba3da2910ea4374294554b6c36 to cb4e56e2d8c28b689908817f9f171a3599a3fc3c

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

cb4e56eWhitney twisting

comment:16 Changed 2 years ago by git

  • 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 2 years ago by git

  • Commit changed from 62e7658d83b2f5a2784a790bcaa4a85b82dcf4ce to e72b0ec4080ee8fc1cc1773f7f0857b301c33834

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

eca714eMerge branch 'develop' into t/23139/graphic_matroid_class
45a629aMerge branch 'u/zgershkoff/graphic_matroid_class' of git://trac.sagemath.org/sage into t/23139/graphic_matroid_class
e72b0ecGraphicMatroid in constructor + documentation

comment:18 Changed 2 years ago by zgershkoff

  • 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 2 years ago by git

  • Commit changed from e72b0ec4080ee8fc1cc1773f7f0857b301c33834 to c367dad1132f1defca49af1b066870f9b03626e5

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

c367dadtypo in documentation

comment:20 Changed 2 years ago by git

  • Commit changed from c367dad1132f1defca49af1b066870f9b03626e5 to f20135075836319cc2fad5b50c36028b495b7e72

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

f201350added a few examples

comment:21 Changed 2 years ago by git

  • Commit changed from f20135075836319cc2fad5b50c36028b495b7e72 to 49338d6f7d275b7fe3c430366becc740eef17cfe

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

35a7201Tabs instead of spaces. I blame the editor.
a77404fMerge branch 't/23290/ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f' into t/7304/contract_edge_in_graph
29dd861efficiency improvements
a444488additional tests
4383814redundancy in tests
645c3e7Documentation fixes
50a884fa bit of extra whitespace...
6f2a583proper demarcation of variables
000cb47Merge branch 't/7304/contract_edge_in_graph' into t/23139/graphic_matroid_class
49338d6Merge branch 'develop' into t/23139/graphic_matroid_class

comment:22 Changed 2 years ago by git

  • Commit changed from 49338d6f7d275b7fe3c430366becc740eef17cfe to f6886676362a77e529cec1382a392568df32a3b8

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

e9f12b9a few tweaks, a lot of documentation
4beeefeRemoved contract_edge() and update_edges()
f688667Repair to _minor method + additional test

comment:23 Changed 2 years ago by git

  • Commit changed from f6886676362a77e529cec1382a392568df32a3b8 to df360b4067d14deda1e2078f4bec911421f08aeb

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

df360b4methods for comparison

comment:24 Changed 2 years ago by git

  • Commit changed from df360b4067d14deda1e2078f4bec911421f08aeb to 3bbd89e807999e30e13ddea1062409000d8b24fd

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

3bbd89eRepair and tests for Whitney twisting

comment:25 Changed 2 years ago by git

  • Commit changed from 3bbd89e807999e30e13ddea1062409000d8b24fd to 0b1956d01e3ed4218a13d32baaf583017db12580

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

95a28b1Removed option to name vertex from graphic coextension; added tests
e36b5b9split_vertex method in utilities
5081226Repair to __copy__ before I forget
0b1956done_sum method to arrange matroid components

comment:26 Changed 2 years ago by git

  • Commit changed from 0b1956d01e3ed4218a13d32baaf583017db12580 to 8862db7c018be180ac8758b69154bdf3738ca222

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

8862db7cleaned documentation a bit

comment:27 Changed 2 years ago by git

  • Commit changed from 8862db7c018be180ac8758b69154bdf3738ca222 to f187172ffb5eec7e62f9d24b6398ff3eceb059c9

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

f187172no longer relabeling vertices; fixing tests; internal graph now immutable

comment:28 Changed 2 years ago by git

  • Commit changed from f187172ffb5eec7e62f9d24b6398ff3eceb059c9 to ddf7f77e5b697935ed2c952409f50713c0530d69

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

ddf7f77added vertex_map method + tests

comment:29 Changed 2 years ago by git

  • Commit changed from ddf7f77e5b697935ed2c952409f50713c0530d69 to e79479daa3f007fd443ff8dd13085d8fdca32120

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

ccfb9b5Changing _repr_ to fit conventions
4aa0854check in matroid constructor
e79479dcopying, loading, doctesting

comment:30 Changed 2 years ago by git

  • Commit changed from e79479daa3f007fd443ff8dd13085d8fdca32120 to a4016906ba0c62176ab193c762bb536517bbe11d

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

a401690graphic coextensions

comment:31 Changed 2 years ago by git

  • Commit changed from a4016906ba0c62176ab193c762bb536517bbe11d to 5124bbc7670428b7e3ec3659fc3736ebfd54dfd4

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

5124bbcfixing doctests related to constructor change

comment:32 Changed 2 years ago by zgershkoff

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 2 years ago by jdemeyer

  • Dependencies changed from #23300, #7304, #23290 to #23300, #7304, #23290, #23382

This conflicts with #23382.

comment:34 Changed 2 years ago by git

  • Commit changed from 5124bbc7670428b7e3ec3659fc3736ebfd54dfd4 to a523bcf59c0336f35f1ac38ef4d942f887870baa

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

decc560Progress on _has_minor(); fix to advanced.py since I'm already here
221bf30fixed import statements and added tests
b443da7modified imports according to trac comment
54afcebMerge branch 't/23139/graphic_matroid_class' into t/23300/non_absolute_import_in_basisexchangematroid
a523bcfMerge branch 't/23300/non_absolute_import_in_basisexchangematroid' into t/23139/graphic_matroid_class

comment:35 Changed 2 years ago by git

  • Commit changed from a523bcf59c0336f35f1ac38ef4d942f887870baa to f62d81f3a879f670886cdd806cb6e7efcda0f656

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

b2d6b5fall methods documented except _has_minor
f62d81fWrote class documentation and organized methods

comment:36 Changed 2 years ago by git

  • Commit changed from f62d81f3a879f670886cdd806cb6e7efcda0f656 to 4233c04634662c647cc11cd4e2d4b860419e4f99

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

4233c04minor typo fix

comment:37 Changed 2 years ago by git

  • Commit changed from 4233c04634662c647cc11cd4e2d4b860419e4f99 to 6a5f736260dd32b93c6c98d8c194b5b5a9f76de7

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

2994919efficiency improvement to graphic_coextensions
6a5f736_has_minor now working properly

comment:38 Changed 2 years ago by git

  • Commit changed from 6a5f736260dd32b93c6c98d8c194b5b5a9f76de7 to aeb384eee86f36388a0aa8e6daca5ba540bc6d61

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

aeb384eThis simpler fix works too

comment:39 Changed 2 years ago by zgershkoff

All methods work now. I'll set to needs review after merging in #23382.

comment:40 Changed 2 years ago by git

  • Commit changed from aeb384eee86f36388a0aa8e6daca5ba540bc6d61 to 9e5449c3733d743a06e289ad12244fbfda05d83a

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

9e5449crevert documentation changes to advanced.py

comment:41 Changed 2 years ago by git

  • Commit changed from 9e5449c3733d743a06e289ad12244fbfda05d83a to 6f39bed25bc3dcdafd9fecde54ab9d80e02c93dd

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

ded03cbdocumentation
40c1e98documentation
6f39beddocumentation actually builds now

comment:42 Changed 2 years ago by git

  • Commit changed from 6f39bed25bc3dcdafd9fecde54ab9d80e02c93dd to 6f3be59fe168dc62c522768be7241f008f69ed37

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

23a7260Clean up matroid constructor
e25d425Merge branch 't/23382/clean_up_matroid_constructor' into t/23139/graphic_matroid_class
59353c6fixing error related to merge
6be79b6efficiency improvements, which changed a lot of tests
6f3be59removed methods where the default implementation is faster

comment:43 Changed 2 years ago by zgershkoff

  • Status changed from new to needs_review

Should be all set now.

comment:44 Changed 2 years ago by git

  • Commit changed from 6f3be59fe168dc62c522768be7241f008f69ed37 to 1624418e89eaba215f385c3e79038bceacbfdd8c

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

1624418bug fix to graphic_coextensions

comment:45 Changed 2 years ago by git

  • Commit changed from 1624418e89eaba215f385c3e79038bceacbfdd8c to afe42d5867721db8489c9d32a4a4771021574943

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

afe42d5removing redundant lines

comment:46 Changed 2 years ago by git

  • Commit changed from afe42d5867721db8489c9d32a4a4771021574943 to 32805418f0e8756bbd4a958b17562f19b06bc582

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

3280541fixed a serious error regarding ground set labels

comment:47 Changed 2 years ago by Stefan

  • 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 2 years ago by git

  • Commit changed from 32805418f0e8756bbd4a958b17562f19b06bc582 to f8c07a629e59794c6dcc3b6e4059eb26813e3152

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

7d0a0dbsome unimpactful changes
0521ad6added disconnected example to constructor
30b06dechanges to graphic_extensions and graphic_coextensions
ca187b5further changes to graphic_coextensions
c65b05dpurging spaces from equals signs for keywords
f8b4165added regular matroid stuff;
8bdcdb4fix to graphic_extension
f8c07a6documentation improvements

comment:49 Changed 2 years ago by zgershkoff

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 set vertices later in the method and I don't want to modify it.

comment:50 Changed 2 years ago by git

  • Commit changed from f8c07a629e59794c6dcc3b6e4059eb26813e3152 to 8715022529eb41b02ab180fbbb8db0fb08337bca

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

9a9b644more documentation improvements
8715022documentation builds correctly now

comment:51 Changed 2 years ago by git

  • Commit changed from 8715022529eb41b02ab180fbbb8db0fb08337bca to 65fe6b6b76d26473d156685fb27bc37e427c94cb

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

65fe6b6small copy-paste error

comment:52 Changed 2 years ago by git

  • Commit changed from 65fe6b6b76d26473d156685fb27bc37e427c94cb to f7594d5b0b5b35862700770cded87fb531daed3f

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

f7594d5fixed some edge cases in graphic_coextension

comment:53 Changed 2 years ago by zgershkoff

  • Status changed from needs_work to needs_review

comment:54 Changed 2 years ago by git

  • Commit changed from f7594d5b0b5b35862700770cded87fb531daed3f to ab082da122cbad128dba340f84414211443cc900

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

ab082daredacted unnessary lines

comment:55 Changed 2 years ago by git

  • Commit changed from ab082da122cbad128dba340f84414211443cc900 to 60b72c41e44857ccd652710144f4b4baf3b6ee48

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

60b72c4graphic_coextensions now respects series classes

comment:56 Changed 2 years ago by zgershkoff

It should be good to go now, except for any future merge conflicts.

Last edited 2 years ago by zgershkoff (previous) (diff)

comment:57 Changed 2 years ago by Stefan

  • 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 2 years ago by git

  • Commit changed from 60b72c41e44857ccd652710144f4b4baf3b6ee48 to e06c11d264f9f197417fed26f41eb684ed453383

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

d95a2dcchanges to documentation and doctests
2af2646Merge branch 'develop' into t/23139/graphic_matroid_class
4ec92d0removed most frozensets from tests
e95e825Empty graphic matroid now has a graph of order 1
e06c11dadding test for new error

comment:59 Changed 2 years ago by zgershkoff

  • 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.

Last edited 2 years ago by zgershkoff (previous) (diff)

comment:60 Changed 2 years ago by Stefan

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 2 years ago by Stefan

  • Status changed from needs_review to needs_work

comment:62 Changed 2 years ago by tscrim

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 2 years ago by git

  • Commit changed from e06c11d264f9f197417fed26f41eb684ed453383 to 93dadf81dd72bda85d3f318a7c51ce4dc93cd057

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

93dadf8changed some examples

comment:64 Changed 2 years ago by zgershkoff

  • 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 2 years ago by Stefan

  • Authors set to Zachary Gershkoff
  • 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 2 years ago by vbraun

  • 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 2 years ago by git

  • Commit changed from 93dadf81dd72bda85d3f318a7c51ce4dc93cd057 to 8f2673678c1c445d35bfe18fe79eecedab3d8e87

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

dc945a3documenting that GraphicMatroid is available from advanced.py
8f26736changing examples so matroids from graphs are RegularMatroids where necessary

comment:68 Changed 2 years ago by zgershkoff

  • 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: Changed 2 years ago by tscrim

  • 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), not Matroid(G, regular = True).
  • In _coclosure, you need a blankline after INPUT.
  • 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 the GraphicMatroid.__init__ method on some graphic matroid M.

comment:70 in reply to: ↑ 69 ; follow-up: Changed 2 years ago by 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 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 BasisExchangeMatroids 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.

Last edited 2 years ago by zgershkoff (previous) (diff)

comment:71 Changed 2 years ago by git

  • Commit changed from 8f2673678c1c445d35bfe18fe79eecedab3d8e87 to a55743d1abffc10baf0f95d4ca8b99d238c11189

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

c011d58Revert "changing examples so matroids from graphs are RegularMatroids where necessary"
0296bebfixing orlik_solomon doctests, minimally
ac0aaf4removed spaces from keyword assignments
206d736removed SageMath
a55743dadded missing blankline

comment:72 follow-up: Changed 2 years ago by 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.

comment:73 in reply to: ↑ 70 Changed 2 years ago by tscrim

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 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.

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 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 BasisExchangeMatroids 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 2 years ago by tscrim

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 2 years ago by git

  • Commit changed from a55743d1abffc10baf0f95d4ca8b99d238c11189 to 9cb9b7d02f4ec9a583ffa570fba3effb574d366c

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

a31d7c6addressing a python3 complaint of patchbot
7a6b95echanging indentation levels of some comments
9cb9b7dchanging style of input and output blocks

comment:76 follow-up: Changed 2 years ago by Stefan

Travis, regarding backwards compatibility: would you be happy with the following compromise?

CHANGE:

  • Matroid(G) returns GraphicMatroid instead of RegularMatroid
  • matroids.CompleteGraphic() returns GraphicMatroid instead of RegularMatroid
  • 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.

Last edited 2 years ago by Stefan (previous) (diff)

comment:77 in reply to: ↑ 76 Changed 2 years ago by tscrim

Replying to Stefan:

Travis, regarding backwards compatibility: would you be happy with the following compromise?

CHANGE:

  • Matroid(G) returns GraphicMatroid instead of RegularMatroid
  • matroids.CompleteGraphic() returns GraphicMatroid instead of RegularMatroid
  • 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

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).

Version 0, edited 2 years ago by tscrim (next)

comment:78 Changed 2 years ago by Stefan

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.

Last edited 2 years ago by Stefan (previous) (diff)

comment:79 Changed 2 years ago by git

  • Commit changed from 9cb9b7d02f4ec9a583ffa570fba3effb574d366c to aeb20302bf35c1a0da2f27fbafbcf2e116d01cf2

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

fea316dadded test using testsuite
b9bf5adfixing :meth: and :class: and such
e57a248trying ~ shortcut. will have to docbuild and look at it later
af0137fbackwards compatibility for groundset
3327bb0this groundset override is no longer necessary
aeb2030updating catalog documentation to reflect constructor changes

comment:80 Changed 2 years ago by zgershkoff

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 2 years ago by Stefan

Ok, save those for another ticket.

comment:82 Changed 2 years ago by tscrim

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 2 years ago by git

  • Commit changed from aeb20302bf35c1a0da2f27fbafbcf2e116d01cf2 to 7c7b7883c4140d5a12c1c50b2c2b6dcbb0c5c3d3

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

7c7b788removing method table

comment:84 Changed 2 years ago by zgershkoff

  • 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 2 years ago by tscrim

  • 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 2 years ago by tscrim

  • Keywords days88 IMA coding sprints added

comment:87 Changed 2 years ago by zgershkoff

  • 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 2 years ago by vbraun

  • 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 2 years ago by git

  • Commit changed from 7c7b7883c4140d5a12c1c50b2c2b6dcbb0c5c3d3 to b02233a376d2dbe58fc5474df28ee6754d967be3

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

b02233achanging test for _has_minor

comment:90 Changed 2 years ago by zgershkoff

  • 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 2 years ago by tscrim

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 2 years ago by Stefan

Given that it's the hidden-from-end-users version of the method, I'm ok with either solution.

comment:93 Changed 2 years ago by git

  • Commit changed from b02233a376d2dbe58fc5474df28ee6754d967be3 to b930927f030c1871d84cc8d921a21b4c8e9a6b1c

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

b930927removed minor certificates from displaying in tests

comment:94 Changed 2 years ago by zgershkoff

I changed it so none of the certificates print in the tests, just in case they're different on some other system.

comment:95 Changed 2 years ago by tscrim

  • Status changed from needs_review to positive_review

LGTM. Thanks.

comment:96 Changed 2 years ago by vbraun

  • Branch changed from u/zgershkoff/graphic_matroid_class to b930927f030c1871d84cc8d921a21b4c8e9a6b1c
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:97 Changed 2 years ago by jdemeyer

  • Authors changed from Zachary Gershkoff to Zach Gershkoff
  • Commit b930927f030c1871d84cc8d921a21b4c8e9a6b1c deleted
Note: See TracTickets for help on using tickets.