Dear Mike,
"Mike Hansen" <[EMAIL PROTECTED]> writes:
> > 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...
> > 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=/
_______________________________________________
Aldor-combinat-devel mailing list
Aldor-combinat-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
