Google Summer of Code

[Stefan van Zwam]

Hi all,

Sage is a mentoring organization for the Google Summer of Code, and I'd like to get a student (or two?) to work on some aspect or other of the matroid code. The Sage organization is happy to have us propose a project, so I'm open for suggestions! Here's a list of stuff that I collected, that needs to be done at some point. I suggest we single out a handful of them. Let me know which ones you feel strongly about! And feel free to suggest your own.

- Advanced minor testing (MACEK-like)
- Connectivity tests
- show()
- Managing sets of matroids (databases! More advanced equivalence-free generation, fast - membership tests where appropriate)
- Partial fields (DyadicMatroid etc.)
- Automorphism group
- Matroid union
- Matroid matching
- Custom graphic matroids
- Signed-graphic matroids
- Gammoids
- Lattice path matroids
- Faster RegularMatroid (use BinaryMatroid when possible)
- Matroid sums (direct, 2-, 3-)
- Generalized Parallel Connection
- OrientedMatroid(?)
- Advanced computation of the Tutte polynomial
- Option to return certificates with some tests (e.g. has_minor)
- Decomposition (Bixby-Cunningham into 3-c components, tree of flowers, …)
- Branch-decomposition (appx)?
- Graphicness test for abstract matroids (+ certificate)
- Interact with Sage's LinearCode methods
- Method to rename the groundset (with custom implementations for the subclasses)
- Option in the catalog (for relevant matroids) to get a representation over the desired field. Maybe also get _all_ representations where applicable?
- Get *all* matroids from Oxley's catalog into Sage

Cheers,

Stefan

[Gordon Royle]

My highest priority would be fundamental structural routines and facilities for manipulating (large) sets of matroids.

This means that I would pick from your list:

- optimised connectivity routines

- optimised minor routines

- decomposition and composition routines

- sets of matroids. Rudi has a rudimentary (no pun intended) class MatroidSet that I am using at the moment that maintains a collection of pairwise nonisomorphic matroids via a set of dictionaries keyed by a quickly-computable invariant

- database access, either to an internal collection or to a genuine external database, or both. In particular we should have all the matroids of rank 9 AND their minor structure built in.

--

---
You received this message because you are subscribed to the Google Groups "sage-matroid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Dillon Mayhew]

On Fri, Apr 19, 2013 at 2:22 PM, Gordon Royle <gordon...@gmail.com> wrote:

My highest priority would be fundamental structural routines and facilities for manipulating (large) sets of matroids.

This means that I would pick from your list:

- optimised connectivity routines

- optimised minor routines

I second these in particular.

Dillon

[Irene Pivotto]

I'm all in favour of

- Advanced minor testing (MACEK-like)
- Connectivity tests

- Custom graphic matroids
- Signed-graphic matroids

- Matroid sums (direct, 2-, 3-)

- Generalized Parallel Connection

Cheers,

Irene

On Fri, Apr 19, 2013 at 4:59 AM, Stefan van Zwam <stefan...@gmail.com> wrote:

[Stefan van Zwam]

Hi all,

Thanks for your input! I'm a little reluctant to leave some of the core functionality to a student who isn't intimately familiar with the mathematics. Especially for sets of matroids I have some specific ideas in mind. I want a

MatroidCollection

class, which has a membership test. I want subclasses such as

MinorClosedMatroidCollection, ThreeConnectedMatroids, BinaryMatroids, ...

Each of these should come with routines for extending a matroid that is already in the class. Moreover, I would like us to be able to take intersections of such classes (and maybe unions?).

Classes like AllMatroids and BinaryMatroids could carry databases for better speed, but I'm not entirely clear on what that kind of user interface to connect to that. I'm hoping to spend time in La Vacquerie discussing these issues.

On the other hand, our time is limited, and an eager and talented student can accomplish much more over one summer than two of us could do in a year.

Cheers,

Stefan.

[Rudi Pendavingh]

Hi Stefan,

What an excellent list! I'd like to add

- testing if a matroid is binary, ternary, quaternary.

I agree with the others that generation of matroid classes has highest priority, and I also agree with your later mail that this requires some careful planning. You are thinking how to interface with the user, I'm thinking how we should interface with the low-level functions. We should definitely take time in la Vacquerie to discuss and plan all this.

There are many items on your list that do not require digging into the core of the code. For example, anyone can start writing connectivity routines in python right now, just interfacing with the abstract matroid class.

About the student.. I may know one or two that can code well. But what is the deal? Do they need to go to Princeton?

Cheers,

Rudi

[Michael Welsh]

On 20/04/2013, at 5:16 PM, Rudi Pendavingh <rudi.pe...@gmail.com> wrote:
>
> About the student.. I may know one or two that can code well. But what is the deal? Do they need to go to Princeton?

Nope, Google does it: https://developers.google.com/open-source/soc/

[Michael Welsh]

On 19/04/2013, at 8:59 AM, Stefan van Zwam <stefan...@gmail.com> wrote:
>
>
> - Get *all* matroids from Oxley's catalog into Sage

I'm currently doing this, and cleaning up the catalog generally. A few questions:

1. Should I bother with is_valid() on binary, ternary, and GF(4)-ary matroids? It seems like a good idea and a silly idea at the same time...
2. In the back, Oxley has a bunch of matroids that we have in the catalog as part of classes - such as U24 and K4. Should I bother to add them in special?
3. Is there a hierarchy for input? Something like Regular > Binary > Ternary > GF(4) > CC (depending on the matroid of course)
4. Where do all the references hide? it looks like matroid.pyx
5. When I first did all the doctests, I just basically randomly picked functions and used them, regardless of what they actually mean. Should I continue with this, or just stick to doctests that I can verify without sage?

I think that's all.. :)

Michael

[Stefan van Zwam]

Hi Michael,

On Apr 29, 2013, at 12:06 AM, Michael Welsh <yom...@yomcat.geek.nz> wrote:

> On 19/04/2013, at 8:59 AM, Stefan van Zwam <stefan...@gmail.com> wrote:
>>
>>
>> - Get *all* matroids from Oxley's catalog into Sage
>
> I'm currently doing this, and cleaning up the catalog generally. A few questions:
>
> 1. Should I bother with is_valid() on binary, ternary, and GF(4)-ary matroids? It seems like a good idea and a silly idea at the same time...

It's kind of silly, for now.

> 2. In the back, Oxley has a bunch of matroids that we have in the catalog as part of classes - such as U24 and K4. Should I bother to add them in special?

No, I wouldn't do that.

> 3. Is there a hierarchy for input? Something like Regular > Binary > Ternary > GF(4) > CC (depending on the matroid of course)

I think that's a good hierarchy. Note that I hope to give the user a
choice in the future (between fields, at least. They can create a
BasisMatroid or CCMatroid themselves).

> 4. Where do all the references hide? it looks like matroid.pyx

Yes. When docbuilding I got annoying errors about double references.
This is my way out. The links work from the reference manual.

> 5. When I first did all the doctests, I just basically randomly picked functions and used them, regardless of what they actually mean. Should I continue with this, or just stick to doctests that I can verify without sage?

Do a mix. If you can illustrate some of the minor/extension relations
or other explicit properties, that would be more meaningful.

>
> I think that's all.. :)
>
> Michael

Cheers,

Stefan.