Matroids

[nathanncohen]

Matroids in Sage could be interesting from the educational point of view, as there are not so many ways to play with matroids on a computer, but also from the algorithmic point of view, as the Graph Theory section could use some help from the Matroid Union and Matroid Intersection Theorems... ( see #7476 )

Macek is a GPL+C implementation of them http://www.fi.muni.cz/~hlineny/MACEK/ which I never tried but may be a good starting point !

Nathann

Apply:

• attachment: trac_7477_setup_doc_load.patch -- changes to module_list.py, all.py, and reference manual
• attachment: trac_7477_code.patch -- code for the sage.matroids package

Depends on #14669
Depends on #14668
Depends on #9880
Depends on #8386

CC: @kcrisman @sagetrac-yomcat

Component: combinatorics

Keywords: sd48

Author: Stefan van Zwam, Rudi Pendavingh

Reviewer: Volker Braun, Rob Beezer

Merged: sage-5.12.beta1

Issue created by migration from https://trac.sagemath.org/ticket/7477

[wdjoyner]

comment:1

I think adding macek to Sage will be a lot of work... .

Another option is to add my code
http://boxen.math.washington.edu/home/wdj/sagefiles/matroid_class.sage
I don't have time right now to add this to Sage properly, due to teaching obligations. However, if anyone is interested, I can at least act as one of the referees. If not, I will try to get to this next semester.

[rbeezer]

comment:2

Attachment: matroids-beezer-20110105.sage.gz

I attended a short course on matroids at the US national math meetings in January 2011, and spent the two days hacking up as much about matroids as I could. I knew David Joyner had done something similar, but I purposely did not look at his work first. So you will see some common ideas and some differences.

This is definitely not pretty, nor efficient. The goal was to implement as much functionality as quickly as possible, so there are obvious places where things should be done differently. But it is clear that much of the hard work can be shipped off to Sage routines for graph theory, linear algebra and combinatorics.

Implements vector matroid, cycle matroid, bicircular matroid, transversal matroid, uniform matroid, and duals of matroids.

[sagetrac-Stefan]

comment:3

There is serious interest from the matroid theory community in creating a Sage package. It would provide similar functionality to the graph theory package: lots of methods (extensions, representations, Tutte polynomials, connectivity tests, isomorphism and minor testing, ...) and a database with named matroids and small matroids.

Macek has several shortcomings that make it unsuitable; I will mention a few. It only works for representable matroids over the (small number of) partial fields implemented. It has an esoteric command language based on vertex-labelled trees. It has bugs. For instance, it cannot read its own output without modification, and is known not to detect minors when they are clearly present. Its author considers it "done", and will not support it.

[nathanncohen]

comment:4

(plus it would speedup the method Graph.edge_disjoint_spanning_tree which is deeeaaad slow right now)

[rbeezer]

comment:5

Replying to @sagetrac-Stefan:

Hi Stefan,

Thanks for the information on MACEK. I didn't know the details, but it looked to me like all support had ended, so it is good to have the confirmation.

What will it take to get the matroid community started with Sage?

Rob

[wdjoyner]

comment:6

Neither Rob's code nor mine is a patch. Any preference? I'm happy to convert my code into a patch and try to integrate Rob's new aspects in, or Rob can create a patch from his.

[sagetrac-Stefan]

comment:7

Replying to @rbeezer:

Replying to @sagetrac-Stefan:

What will it take to get the matroid community started with Sage?

Short answer (I sent you a longer by email): the matroid community has already started. We had a meeting in December, and will have a followup meeting in June. Several people have committed themselves to the effort.

By the way, I changed the "Component" field to combinatorics. I hope that's ok.

[rbeezer]

comment:9

Replying to @wdjoyner:

Neither Rob's code nor mine is a patch. Any preference? I'm happy to convert my code into a patch and try to integrate Rob's new aspects in, or Rob can create a patch from his.

Hi David,

Sorry for the delay in replying to this - recovering from Bug Days.

I think the computational matroid folks are quite serious about moving a lot of their work to Sage. Maybe it would be best if we let them decide what structure will work best for their purposes, rather than putting in something now that may not work well long-term?

You and I could probably best help them by advising and reviewing their contributions, I think.

But we shouldn't wait for them forever. ;-)

Rob

[sagetrac-jeremy-l-martin]

comment:10

I am brand new to Sage development, but I do a lot of work with matroids and would like to see them implemented in Sage.

I will be teaching a graduate course in algebraic combinatorics this fall. I am thinking of having my students create a Matroid sage class as a group project. E.g., they could implement the conversions between all the various ways of presenting a matroid; basic constructions like direct sum and dual; and the Tutte polynomial.

Thoughts?

Jeremy Martin (University of Kansas)

[kcrisman]

comment:11

Sounds like a great idea! You may want to try using the code attached here as a starting point. Also, the sage-combinat folks have some great infrastructure for things like categories, and you should ask them about that. But I think this is a very reasonable project. Especially if you could somehow implement graph.matroid() and/or vecspace.basis.matroid - in the sense that one could have a graph, and then get a matroid they could do stuff with from it.

[sagetrac-Stefan]

comment:12

Hi!

There's a significant effort going on behind the screens to get matroids into Sage. You can get to our work-in-progress code at

https://bitbucket.org/matroid/sage_matroids/

and we've got a mailing list at

https://groups.google.com/group/sage-matroid

Please join in the discussion. There is still plenty to be done.

A quick description of our current status: we've got an abstract Matroid class with a bunch of subclasses: BasisMatroid, LinearMatroid, RankMatroid, CircuitClosuresMatroid are the main ones. There is support for minors and abstract duality. We have a rather fast isomorphism test, and a host of methods for standard queries. There's also a library of common matroids, and a constructor that takes various inputs (including Sage graphs). So you can write

M = Matroid(G)

We think we need some minor coding and major documentation-string-writing before we want to submit it to Sage.

[sagetrac-jeremy-l-martin]

comment:13

Thanks! I will join that Google group and see what I can do to help.

Right now I am at a sage-combinat workshop at the IMA. There is significant interest among the algebraic combinatorialists here in implementing matroids for Sage; on the other hand, I'm not sure if the sage-combinat folks know about the sage-matroid project. I will make an announcement about it and invite people to get involved.

Jeremy

[sagetrac-Stefan]

Author: Stefan van Zwam, Rudi Pendavingh

[sagetrac-Stefan]

comment:15

Note: needs Sage 5.9.rc1 to build (because the package list is now generated automatically in setup.py, this used to be manual).

Note: the documentation builds fine from scratch, but I sometimes have trouble when adding these patches to an already built reference manual.

[nathanncohen]

comment:16

This review will take a lifetime, but right now all I can say is that the code of circuits, cocircuits, noncospanning_cocircuits, and nonspanning_circuits look awfully similar.

And there are some parts of the code that are commented out, like that

+# def bitset_pickle_test(data):                                                                                                                                                               
+#     """                                                                                                                                                                                     
+#     Converts the list of integers ``data`` into a bitset, which gets pickled.                                                                                                               
+#     """                                                                                                                                                                                     
+#     cdef bitset_t bs                                                                                                                                                                        
+#     m = max(data)                                                                                                                                                                           
+#     bitset_init(bs, m+1)                                                                                                                                                                    
+#     bitset_clear(bs)                                                                                                                                                                        
+#     for i in data:                                                                                                                                                                          
+#         bitset_add(bs, i)                                                                                                                                                                   
+#     p = bitset_pickle(bs)                                                                                                                                                                   
+#     bitset_free(bs)                                                                                                                                                                         
+#     return p              

Or 4 functions in the matroid catalog.

Nathann

[sagetrac-Stefan]

comment:17

What do you mean by the comment that those functions look similar? They compute similar, but not identical, information from the matroid. And all four are useful to end users.

I guess we should have gotten rid of commented out parts (though Sage has plenty of that floating around in its source). I'll revise that soon.

[nathanncohen]

comment:18

Hellooooooo !

What do you mean by the comment that those functions look similar? They compute similar, but not identical, information from the matroid. And all four are useful to end users.

Nonono, of course you need them. I was just saying that perhaps there could have been an internal function computing all 4 things, exposed in 4 differents ways to the user. This way there is no copy/paste of code.

I guess we should have gotten rid of commented out parts (though Sage has plenty of that floating around in its source). I'll revise that soon.

Nonono I'm sorry I said that, I will give you lengthier reviews soon. Otherwise it will make you update the patch every day... :-)

Nathann

[nathanncohen]

comment:20

Hellooooooooooo again !

Well, I've been spending some time on that code, and I first have to say that it is awfully clean. I was a bit afraid that something developped outside of Sage would be more combinat-like, and that is not the case at all here.

The other thing is that, stupid as it may seem, I had not realized until a couple of minutes that I cannot realistically review 21 000 lines of code by myself. I mean, with a real job that I have to do, with 3 meals per day, everything. Looks complicated. This is one of the problems of developping everything for a while then trying to create a single patch out of it.

I will be glad to spend time on that, and also to work with the code later, but yep, I guess that I cannot review 21 000 lines of code :-)

I think that in this case, as the code looks preeeeetty clean and all, the best would really be to ask on sage-devel whether :

1. We take it in without a review (as if it were a spkg, actually)
2. Somebody (or many persons) are willing to review it together

Perhaps it would also help if you were to say in your message how you produced this code. If many persons wrote that code, if many tried it...

I think that I can't do more. Otherwise, I know that I will not set this to "positive review" before I am convinced that every single choice is a good one, or at least having asked about it. And after having thought for a while about each line, wondering if it is the best way to do it. I already spent weeks on easier reviews, and I know that I cannot do that one :-)

Nathann

[sagetrac-Stefan]

comment:21

I fully understand that you can't - I know I couldn't! I'll post on sage-devel to ask what's to be done.

--Stefan.

[sagetrac-Stefan]

Matroid code

[sagetrac-Stefan]

comment:78

Attachment: trac_7477_code.patch.gz

Replaced some variable names. All doctests pass.

[vbraun]

comment:79

Looks good.

In C/C++, identifiers starting with an underscore and followed by an upper case letter are reserved. So Solaris is standards-compliant in this case.

[kcrisman]

comment:80

So, just to be clear, to avoid

WARNING: intersphinx inventory '/Users/.../sage-5.11.beta1/devel/sage/doc/output/html/en/reference/matroids/objects.inv' not fetchable due to <type 'exceptions.IOError'>: 

errors, in the future we have to always do

sage -docbuild all html

or do this inventory thing? I don't see any mention in the documentation, nor at #14699, and I am using 5.11.beta1 here.

[vbraun]

comment:81

Only the reference manual uses the two-step build process, so its either

   sage -docbuild reference inventory     # only necessary if inventory changed
   sage -docbuild reference/DIR

or

   sage -docbuild reference html

[kcrisman]

comment:82

I had a problem with the latter, though. Anyway, I won't be changing the inventory much soon...

[dimpase]

comment:84

Replying to @kcrisman:

I had a problem with the latter, though. Anyway, I won't be changing the inventory much soon...

I suppose the latter Sage call was meant to replace the last line from the 1st code snippet, not both of them.

[jdemeyer]

Changed dependencies from #14669, #14668, #9880 to #14669, #14668, #9880, #8386

[jdemeyer]

comment:85

Please rebase to #8386.

[sagetrac-Stefan]

Attachment: trac_7477_setup_doc_load.patch.gz

Matroid setup, autoload, documentation

[sagetrac-Stefan]

comment:86

Rebased to #8386, only the reference manual's index needed updating because of a new entry introduced by #8386.

[jdemeyer]

Merged: sage-5.12.beta1

[nathanncohen]

comment:89

Wow. Sooooo it's in Sage now :-P