From: bdm@cs.anu.edu.au (Brendan McKay)
Subject: Re: Efficient way to determine if Greechie diagrams are isomorphic?
Date: Sat, 1 May 1999 12:32:40 +1000
Newsgroups: sci.math.research

Norman D. Megill <ndm@shore.net> wrote:

> A Greechie diagram is an m x 3 matrix populated with numbers 1 thru n,
> where n < 3.m, and where all numbers are used at least once.
>...
> Two Greechie diagrams are isomorphic when one is obtained from the other
> by (1) exchanging any two rows, (2) exchanging two elements within a
> row, (3) simultaneously renumbering all elements with a permutation of 1
> thru n.
>... 
> What I need is a computationally efficient way to determine if two
> Greechie diagrams are isomorphic.
>...
> I need something better.  Determining a canonical form such as I
> described would be ideal since I'll be working with thousands of
> diagrams.

This can be handled by converting it to a graph isomorphism problem.
I'll demonstrate for the case where the three entries in each row 
are distinct, but the more general case is not much harder.

Define a graph G with two classes of vertices:

R[1..m] : representing rows
V[1..n] : representing values of entries

There are 3m edges:  If row r contains the values i,j,k then join
R[r] to V[i], V[j] and V[k].

Finally, colour the vertices of G with the two colours R and V.

It is easy to see that the isomorphism/automorphism behaviour of the
graph exactly follows that of the array.  (Relabelling the rows of
the array corresponds to relabelling the R vertices, etc.)

By using an efficient graph isomorphism package, such as my program
nauty ( http://cs.anu.edu.au/~bdm/nauty ) you will be able to 
canonically label Greechie diagrams of the size you mention in a
millisecond or so.

Brendan.