Opened 11 years ago

Last modified 8 years ago

#7477 closed enhancement

Matroids — at Version 14

Reported by: ncohen Owned by: jkantor
Priority: major Milestone: sage-5.12
Component: combinatorics Keywords: sd48
Cc: kcrisman, yomcat Merged in:
Authors: Stefan van Zwam, Rudi Pendavingh Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Stefan)

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:

Change History (15)

comment:1 Changed 11 years ago by wdj

  • Report Upstream set to N/A

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.

Changed 10 years ago by rbeezer

comment:2 Changed 10 years ago by rbeezer

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.

comment:3 follow-up: Changed 10 years ago by Stefan

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.

comment:4 Changed 10 years ago by ncohen

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

comment:5 in reply to: ↑ 3 ; follow-up: Changed 10 years ago by rbeezer

Replying to 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

comment:6 follow-up: Changed 10 years ago by wdj

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.

comment:7 in reply to: ↑ 5 Changed 10 years ago by Stefan

  • Component changed from numerical to combinatorics

Replying to rbeezer:

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

comment:8 Changed 10 years ago by kcrisman

  • Cc kcrisman added

comment:9 in reply to: ↑ 6 Changed 10 years ago by rbeezer

Replying to wdj:

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

comment:10 Changed 9 years ago by jeremy.l.martin

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)

Last edited 9 years ago by jeremy.l.martin (previous) (diff)

comment:11 Changed 9 years ago by kcrisman

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.

comment:12 Changed 9 years ago by Stefan

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.

comment:13 Changed 9 years ago by jeremy.l.martin

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

comment:14 Changed 8 years ago by Stefan

  • Authors set to Stefan van Zwam, Rudi Pendavingh
  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-5.10
  • Status changed from new to needs_review
Note: See TracTickets for help on using tickets.