species - substitution and multisort

[Martin Rubey]

Hi Mike,

since you posted that you are going to work on species this weekend, I thought
I'd ask where you are currently.

Do you have ideas how to solve the problem of producing representatives of the
isotypes of substitutions (ordinary, not functorial)? Did you check whether
the idea I had some time ago (store a map that "produces" the labels together
with the structure) might be feasible?

Do you believe that you can will be able to deal with isotypes of general
functorial compositions using nauty or something similar?

I'd be most interested in that, and in close cooperation, of course. I'm quite
happy to see, at least from paging through
http://blog.phasing.org/static/species/ -- I cannot read Python code though,
that you seem to have been able to use Ralf's and my ideas in Python. I very
much hope that we can continue this way, and perhaps eventually merge.

All the best,

Martin


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/

[Mike Hansen]

Hi Martin,

Post by Martin Rubey
Do you have ideas how to solve the problem of producing representatives of the
isotypes of substitutions (ordinary, not functorial)? Did you check whether
the idea I had some time ago (store a map that "produces" the labels together
with the structure) might be feasible?

I do have a version of my code where the labels are stored separately
from the internal structure within the generated structures. This has
allowed me to create a canonical_label method which, given a
structure, produces the representative of its isomorphism class. I
have this defined and working for all of the species except for
composition and functorial composition. I will finish cleaning up the
changes and post them in the next day or two.

I spent most of the non-coding time reading and learning about
canonical augmentation which is the algorithm that McKay uses for his
isomorph-free graph generation. Robert Miller uses this algorithm in
Sage for graphs and self-orthogonal binary codes and has been working
on generalizing the framework to make it easy to use for other
objects.

Did you have a specific algorithm in mind for generating composition
isomorphs with this new data structure?

Post by Martin Rubey
Do you believe that you can will be able to deal with isotypes of general
functorial compositions using nauty or something similar?

I think canonical augmentation, if anything, will be the best bet.

Post by Martin Rubey
I'd be most interested in that, and in close cooperation, of course. I'm quite
happy to see, at least from paging through
http://blog.phasing.org/static/species/ -- I cannot read Python code though,
that you seem to have been able to use Ralf's and my ideas in Python. I very
much hope that we can continue this way, and perhaps eventually merge.

Sounds good!

--Mike

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/

[Martin Rubey]

Dear Mike,

Post by Martin Rubey
Do you have ideas how to solve the problem of producing representatives of
the isotypes of substitutions (ordinary, not functorial)? Did you check
whether the idea I had some time ago (store a map that "produces" the
labels together with the structure) might be feasible?

I do have a version of my code where the labels are stored separately from
the internal structure within the generated structures. This has allowed me
to create a canonical_label method which, given a structure, produces the
representative of its isomorphism class. I have this defined and working for
all of the species except for composition and functorial composition. I will
finish cleaning up the changes and post them in the next day or two.

Wow, great!

I spent most of the non-coding time reading and learning about canonical
augmentation which is the algorithm that McKay uses for his isomorph-free
graph generation. Robert Miller uses this algorithm in Sage for graphs and
self-orthogonal binary codes and has been working on generalizing the
framework to make it easy to use for other objects.

That's what I *should* have studied, too. I didn't, I was too lazy...

Post by Martin Rubey
Do you believe that you can will be able to deal with isotypes of general
functorial compositions using nauty or something similar?

I think canonical augmentation, if anything, will be the best bet.

Well, clearly this works for many objects that can be written as functorial
compositions, so I agree that *if* there is a acceptably "fast" algorithm, then
it will use this. But I admit that I know nearly nothing about it. Maybe you
remember that Petr Hlineny uses an adaptation for generation of matroids?

Did you have a specific algorithm in mind for generating composition
isomorphs with this new data structure?

Well, I believe that it should be possible to adapt the algorithm I describe in
the iso-experiment branch -- you will need to read the documentation (i.e.,
species.as.nw) from line 3676, \subsection{Composition of Species}.
(Unfortunately, there is no online version, so you have to

svn co svn://svn.risc.uni-linz.ac.at/hemmecke/combinat combinat
cd combinat/branches/iso-experiment/combinat
make colored dvi

(or make colored pdf, if you wish)

Remember, that in my framework, the concept "isomorphismType" is actually a
little generalised: I allow a multiset of labels, so it is possible to have
equivalent and inequivalent labels in one "isomorphismType". And I need that
every species is able to generate such a generalised isomorphismType. Eg,

isomorphismTypes([1,1,1,2,2])$Cycle

should yield the two "structures" 11122, 12121.

I believe that in principle this generalisation is unavoidable, but in fact
also quite practical. One has two choices now:

A) do univariate species this way.

B) use multivariate ("multisort") species. Such generalised isotypes can be
seen as a special case then. In the cycle example above, one would generate
representatives of structures of bivariate cycles, and take isotypes with
respect to both variables.

I'm not sure what's easier.

The second thing that may need explanation are "multiset partitions", i.e.,
the multiset [1,1,1,2,2]=[1^3,2^2] can be partitioned for example as

[1]^3 [2]^2; or
[1,2]^2 [1]; or
[1,1,2,2] [1], etc.

These are generate by an algorithm due to Knuth, which may or may not be
optimal. I didn't care, and I copied his algorithm verbatim.

I hope this helps a little.

Martin


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/

[Nicolas M. Thiery]

Dear Martin, Mike, Ralf, Robert,

We all have our own programming styles, so working together means some
compromises. But it's a pleasure to see you work all together on
species, and make something happen I have dreamed of for years
(*-combinat + species + polya + orderly generation + ...)! I can tell
you that whenever my research will call for it (sooner than later),
I'll put the code to serious use :-)

Keep up the good work!

Cheers,
Nicolas