Graphic Matroid class

[Zach Gershkoff]

Implement a graphic matroid class, instances of which will be based on graphs. The class will have methods and algorithms specifically for graphs.

[Zach Gershkoff]

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:

​33b0a83

The basic idea

[git]

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

​dd5ef4f

Beginnings of _has_minor()

[git]

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

​92b0831

Refinements to _minor()

[git]

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

​f47fdd3

New methods + general tidiness

[git]

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

​ca11a70	_closure() method
​dcd2fde	Repairs to how contraction is handled
​fd54096	circuit, cocircuit, coclosure, is_coindependent, is_independent

[git]

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

​1e4fbcd	Renaming cocircuit_edges to codependent_edges for clarity
​02f7d4a	Added _is_cocircuit(), _is_isomorphic(), _isomorphism(). _isomorphism() needs debugging

[git]

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

[git]

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

​fb7f8e7

Moved contract_edge() to utilities; added _closure()

[git]

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

​d63368a	__init__ now forces the graph to be connected
​7d854eb	Moved internal method to utilities; changed an example

[git]

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

​eae836b	small fix to a test
​fc45f1f	documented said method; wrote user-facing groundset_to_edges

[git]

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

​42bca83	Merge branch 'develop' into t/23139/graphic_matroid_class
​81d47a3	Improvements to __init__ and _rank

[git]

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

​cb4e56e

Whitney twisting

[git]

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

​62e7658

__init__ forces vertex labels to be integers

[git]

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

[Zach Gershkoff]

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.

[git]

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

​c367dad

typo in documentation

[git]

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

​f201350

added a few examples

[git]

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

[git]

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

​e9f12b9	a few tweaks, a lot of documentation
​4beeefe	Removed contract_edge() and update_edges()
​f688667	Repair to _minor method + additional test

[git]

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

​df360b4

methods for comparison

[git]

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

​3bbd89e

Repair and tests for Whitney twisting

[git]

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

​95a28b1	Removed option to name vertex from graphic coextension; added tests
​e36b5b9	split_vertex method in utilities
​5081226	Repair to __copy__ before I forget
​0b1956d	one_sum method to arrange matroid components

[git]

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

​8862db7

cleaned documentation a bit

[git]

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

​f187172

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

[git]

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

​ddf7f77

added vertex_map method + tests

[git]

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

​ccfb9b5	Changing _repr_ to fit conventions
​4aa0854	check in matroid constructor
​e79479d	copying, loading, doctesting

[git]

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

​a401690

graphic coextensions

[git]

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

​5124bbc

fixing doctests related to constructor change

[Zach Gershkoff]

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.

[Jeroen Demeyer]

This conflicts with #23382.

[git]

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

[git]

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

​b2d6b5f	all methods documented except _has_minor
​f62d81f	Wrote class documentation and organized methods

[git]

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

​4233c04

minor typo fix

[git]

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

​2994919	efficiency improvement to graphic_coextensions
​6a5f736	_has_minor now working properly

[git]

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

​aeb384e

This simpler fix works too

[Zach Gershkoff]

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

[git]

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

​9e5449c

revert documentation changes to advanced.py

[git]

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

​ded03cb	documentation
​40c1e98	documentation
​6f39bed	documentation actually builds now

[git]

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

[Zach Gershkoff]

Should be all set now.

[git]

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

​1624418

bug fix to graphic_coextensions

[git]

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

​afe42d5

removing redundant lines

[git]

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

​3280541

fixed a serious error regarding ground set labels

[Stefan]

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.

[git]

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

[Zach Gershkoff]

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.

[git]

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

​9a9b644	more documentation improvements
​8715022	documentation builds correctly now

[git]

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

​65fe6b6

small copy-paste error

[git]

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

​f7594d5

fixed some edge cases in graphic_coextension

[git]

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

​ab082da

redacted unnessary lines

[git]

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

​60b72c4

graphic_coextensions now respects series classes

[Zach Gershkoff]

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

[Stefan]

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]

[git]

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

[Zach Gershkoff]

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.

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

[Travis Scrimshaw]

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

[git]

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

​93dadf8

changed some examples

[Zach Gershkoff]

I assume a general fix for that, if we need one, is outside the scope of this ticket.

[Stefan]

It all looks good now. Setting it to positive review; I also edited the "Authors" field.

[Volker Braun]

See also patchbot

sage -t --long src/sage/algebras/orlik_solomon.py  # 7 doctests failed

[git]

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

​dc945a3	documenting that GraphicMatroid is available from advanced.py
​8f26736	changing examples so matroids from graphs are RegularMatroids where necessary

[Zach Gershkoff]

I didn't realize those patchbot errors were relevant. Doctests pass in that file now.

[Travis Scrimshaw]

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.

[Zach Gershkoff]

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.

[git]

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

[Zach Gershkoff]

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.

[Travis Scrimshaw]

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.

[Travis Scrimshaw]

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.

[git]

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

​a31d7c6	addressing a python3 complaint of patchbot
​7a6b95e	changing indentation levels of some comments
​9cb9b7d	changing style of input and output blocks

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

[Travis Scrimshaw]

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

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

[git]

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

[Zach Gershkoff]

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

[Stefan]

Ok, save those for another ticket.

[Travis Scrimshaw]

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

[git]

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

​7c7b788

removing method table

[Zach Gershkoff]

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.

[Travis Scrimshaw]

Thank you for all the changes and your work on this (including Stefan and his review).

[Zach Gershkoff]

Removing this dependency (even though it's true) in case it's causing a problem for the release script.

[Volker Braun]

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]

[git]

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

​b02233a

changing test for _has_minor

[Zach Gershkoff]

Everything passes on my end, but I changed that example to just count the elements instead of telling us what they are.

[Travis Scrimshaw]

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

[Stefan]

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

[git]

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

​b930927

removed minor certificates from displaying in tests

[Zach Gershkoff]

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

[Travis Scrimshaw]

LGTM. Thanks.