matroids9 and strange bugs

[Gordon]

Hi all

I've been trying to make the 9-element matroids available easily to a couple of people who are asking for them, and rather than keep putting them off while I (or we) figure out the _perfect_ way to do this, I thought I'd just write something quickly so that they can be immediately useful. (But not incorporate it into the release until we figure out how to do it better).

So, I have a file, called "matroids9_ranks" that contains 385369 lines, one per matroid, with each line of the following form:

0112122312232334122322332334334412232233233433442233223333443344

The gzipped version of this file is here: http://school.maths.uwa.edu.au/~gordon/matroids9_ranks.gz

Each digit gives the rank of a subset of the groundset according to the rule that the rank of the subset A = {a0, a1, ... an} is in position Sum(2^{ai}) of the string (in other words, position 0 is the rank of {}, position 1 is the rank of {0}, position 2 is the rank of {1}, position 3 is the rank of {0,1} and so on).

So I wanted some code that pulls in each string, decodes the bases, and then creates a BasisMatroid and appends it to an array called "matroids9" so that after processing the entire file, the user has an array containing all of these matroids (the reason to have an array is because the numbering of the matroids has already been used in publications).

So here goes

import gzip
from sage.matroids.all import *

sizes = {512:9, 256:8, 128:7, 64:6, 32:5, 16:4, 8:3, 4:2, 2:1}

def setToBinary(x):
    return sum([(1<<i) for i in x])

def rl2bases(l):
    sz = sizes[len(l)]
    rk = l[-1]
    groundset = frozenset(range(sz))
    bases = [b for b in Combinations(groundset,eval(rk)) if l[setToBinary(b)] == rk]
    return BasisMatroid(groundset=groundset,bases=bases)

matroids9 = [BasisMatroid(groundset=[])]
for line in gzip.open('matroids9_ranks.gz','r'):
    matroids9.append(rl2bases(line[:-1]))
    if len(matroids9)%1000 == 0:
        print len(matroids9)


This just opens the gzipped file containing all the "ranklines" as I call them, and then processes each one with the method "rl2bases" which produces the bases. The size of the matroid is determined by the length of the rank line

Here are some odd things that I observed:

- if I use "log(len(l),2)" to determine the size of the matroid from the length of the line, the whole process ran about 100-1000 times slower - the logarithm computation dominated the entire rest of the computation massively! So I replaced this with a dictionary lookup into the dictionary "sizes".

Worse,

- if I define "setToBinary(x)" as

return sum([2^i for i in x])

then the whole thing crashes, because somehow after the first matroid is processed, the setToBinary() method starts to produce incorrect results...

This is all very strange.

Anyway, this gives a method to get the matroids on up to 9-elements into sage in a reasonably simple way, and then the built-in methods can be used to do further processing..

[Stefan van Zwam]

Hi Gordon,

- if I define "setToBinary(x)" as

return sum([2^i for i in x])

then the whole thing crashes, because somehow after the first matroid is processed, the setToBinary() method starts to produce incorrect results...

Are you running this as a .py or .sage file? exponentiation in Python is ** and ^ is XOR or something. Sage has a preparer that changes those meanings.

--Stefan

This is all very strange.

Anyway, this gives a method to get the matroids on up to 9-elements into sage in a reasonably simple way, and then the built-in methods can be used to do further processing..

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

[Gordon Royle]

Are you running this as a .py or .sage file? exponentiation in Python is ** and ^ is XOR or something. Sage has a preparer that changes those meanings.

Ah.... I tested it by typing it in, and then tried to USE it via %runfile file.py

Somebody thought it was a good idea to make these behave differently!

[Gordon]

I sent my code for "matroids9" to Theo Belaire and Luis Goddyn and Theo replied that he had to add the additional line

from sage.matroids.basis_matroid import BasisMatroid

in order to make it work?


Surely "from sage.matroids.all import *" should cover it all?

[Stefan van Zwam]

Hi Gordon,

We became a bit more conservative with imports in the last version. sage.matroids.all only imports the Matroid() constructor method and the "matroids" catalog. If you want all other stuff,

from sage.matroids.advanced import *

should do the trick!

--Stefan.

[Gordon]

Do you think that the naive user (i.e. me) might suspect that 

from sage.matroids.all import *

would import "all" ??

[Stefan van Zwam]

Hi,

I think that might well be the case, but we're following Sage's conventions in that the automatic imports are located in all.py. 

The very naive user shouldn't need direct access to the subclasses; the more advanced user will find it out from the documentation, I hope... Can you check the reference manual to see if it's sufficiently obvious? There's a copy here:

https://web.math.princeton.edu/~svanzwam/programming.html

--Stefan

[tbelaire]

The search function is not working in that documentation, nor the index.

[Stefan van Zwam]

Yeah, I just ripped those files out of my local copy of the reference manual. It'll have to do until the matroids get into Sage officially, I'm afraid... And I think more documentation (like a tutorial) is very desirable after that!

--Stefan.

[Gordon]

On Wednesday, 22 May 2013 22:15:52 UTC+8, Stefan van Zwam wrote:

.. Can you check the reference manual to see if it's sufficiently obvious? There's a copy here:

Unfortunately, I don't think it is clear at the moment.

If I (the hypothetical naive user) starts at the beginning, the first page they come to is the "Matroid Construction" page (https://web.math.princeton.edu/~svanzwam/matroids/sage/matroids/constructor.html) and the very first instructions are "Within a Sage session type... ." with no mention of any imports at all. So they will grind to a halt immediately.

But also, it now behaves somewhat counterintuitively

sage: from sage.matroids.all import *sage:

 m = matroids.named_matroids.Fano()

sage: m

Fano: Binary matroid of rank 3 on 7 elements, type (3, 0)

sage: type(m)

sage.matroids.linear_matroid.BinaryMatroid

So, it _knows_ what a BinaryMatroid is, but doesn't have it in the namespace?  

Finally, it would be nice to write some documentation or a tutorial, but my first attempt - to explain to Theo and Luis how to get the matroids of order 9 - has already failed because of changes that I didn't know about rendering my document immediately incorrect. How can this problem be ameliorated? 

[Michael Welsh]

On 23/05/2013, at 6:18 PM, Gordon <gordon...@gmail.com> wrote:
> On Wednesday, 22 May 2013 22:15:52 UTC+8, Stefan van Zwam wrote:
>>
>> .. Can you check the reference manual to see if it's sufficiently obvious?
>> There's a copy here:
>>
>
> Unfortunately, I don't think it is clear at the moment.
>
> If I (the hypothetical naive user) starts at the beginning, the first page
> they come to is the "Matroid Construction" page
> (https://web.math.princeton.edu/~svanzwam/matroids/sage/matroids/constructor.html)
> and the very first instructions are "Within a Sage session type... ." with
> no mention of any imports at all. So they will grind to a halt immediately.

That's because imports are no longer needed (due to the patch). They were a necessary evil during development, but once http://trac.sagemath.org/sage_trac/ticket/7477 gets a positive review and into Sage itself, the importing will be done by Sage itself instead of the end user, as graphs.<tab> does now.

>
> But also, it now behaves somewhat counterintuitively
>
> sage: from sage.matroids.all import *sage:
> m = matroids.named_matroids.Fano()
> sage: m
> Fano: Binary matroid of rank 3 on 7 elements, type (3, 0)
> sage: type(m)
> sage.matroids.linear_matroid.BinaryMatroid
>
> So, it _knows_ what a BinaryMatroid is, but doesn't have it in the
> namespace?
>
>
> Finally, it would be nice to write some documentation or a tutorial, but my
> first attempt - to explain to Theo and Luis how to get the matroids of
> order 9 - has already failed because of changes that I didn't know about
> rendering my document immediately incorrect. How can this problem be
> ameliorated?

By waiting until it's actually in Sage. Then everyone has the same starting point and hopefully all of the development quirks have disappeared...

[Stefan van Zwam]

Hi Gordon,

Michael is right. When our code gets accepted into Sage (or when you follow the instructions in the second part of the README), the keywords "Matroid" and "matroids" will be loaded automatically on startup. So the first thing you type in Sage could be

sage: M = Matroid(field=GF(2), matrix=[[1,0,1],[0,1,1]])

This is very similar to Sage's treatment of matrices:

sage: A = Matrix(GF(2), [[1,0,1],[0,1,1]])
sage: type(A)
sage.matrix.matrix_mod2_dense.Matrix_mod2_dense

You can argue that, unlike Matrix_mod2_dense, the class BinaryMatroid is more than just a datatype, but I argue that since you can create one with the constructor method, you've got access to them anyway.

For advanced users, you can import all the extra stuff:

sage: from sage.matroids.advanced import *

This is documented in the docstring for these classes. In the same Sage session as above, type

sage: M?

and the "advanced" command is listed right there (ok... on the second page. But still.)

Cheers,

Stefan.

[Gordon Royle]

Stefan..

Which README file are you referring to?  The one on the front page of bitbucket doesn't seem to have a second part that I can refer to.

In any case, when do we expect this to be incorporated into Sage?

[Michael Welsh]

On 24/05/2013, at 3:28 PM, Gordon Royle <gordon...@gmail.com> wrote:
> Stefan..
>
> Which README file are you referring to? The one on the front page of
> bitbucket doesn't seem to have a second part that I can refer to.

The second part starts with "ADDING TO SAGE ITSELF:" and finishes just above "NOTE:"

>
> In any case, when do we expect this to be incorporated into Sage?

Judging by the recent positive comments on sage-devel (https://groups.google.com/d/topic/sage-devel/hfoFwFAw_M8/discussion), hopefully soon.

[Gordon Royle]

On Fri, May 24, 2013 at 1:32 PM, Michael Welsh <yom...@yomcat.geek.nz> wrote:

On 24/05/2013, at 3:28 PM, Gordon Royle <gordon...@gmail.com> wrote:
> Stefan..
>
> Which README file are you referring to?  The one on the front page of
> bitbucket doesn't seem to have a second part that I can refer to.

The second part starts with "ADDING TO SAGE ITSELF:" and finishes just above "NOTE:"

OK, finally worked out why I couldn't seem to see any of this.

My browser auto-completes to an address that lands me on a bitbucket page displaying the README file but, as is now apparent, the README file belonging to an older version of the code.

If I manually select "72bd82c 2013-05-02" on the little version-control drop-down menu, then I get the current version.

 

[Michael Welsh]

On 24/05/2013, at 8:56 PM, Gordon Royle <gordon...@gmail.com> wrote:
>
> OK, finally worked out why I couldn't seem to see any of this.
>
> My browser auto-completes to an address that lands me on a bitbucket page
> displaying the README file but, as is now apparent, the README file
> belonging to an older version of the code.
>
> If I manually select "72bd82c 2013-05-02" on the little version-control
> drop-down menu, then I get the current version.

Ah.

For future reference, the readme is nicely printed at the intro page - https://bitbucket.org/matroid/sage_matroids/overview