[Nauty] Indicator function again - canonical label

[Edward Turner]

I understand that an indicator function maps a given graph+ordered
partition+partition nest on to some linearly ordered set:

 

L: G(V) x Ord_Partition(V) x Partition_Nest(V) -> Lin_Ord_Set

 

 And we can define a subsequent indicator function based on this:

 

LL(G,Ord_Partition,TreeNode) = (L(G,Ord_Partition,TreeNode(1)),
L(G,Ord_Partition,TreeNode(2)), ., L(G,Ord_Partition,TreeNode(k))),

 

where k = |TreeNode|

 

I believe LL above is used to find the canonical label of a graph i.e., we
choose the maximum element in the ordering given some set of terminal nodes
of some search tree. But I am struggling to see how we can define L in the
first place - using adjacency matrices and their binary number ordering
would be good, but not all partition nests have a discrete partition in them
(which corresponds to some permutation of the vertices), and so we won't
have an adjacency matrix/binary number associated with these partition
nests.

 

To find the canonical label given a search tree, could we choose the
terminal tree node with the highest binary number associated with its
adjacency matrix (this matrix being produced by applying the permutation
defined by the last, ie discrete, partition of this node)?

 

For anyone else who's finding this quite tricky, another good description of
nauty's workings can be found in the Graph Isomorphism chapter of the
Combinatorial Algorithms book http://www.math.mtu.edu/~kreher/cages.html
(Thanks Chad!).

 

Edd.

 

==================================

Edward Turner

Declarative Systems and Software Engineering

Electronics and Computer Science

University of Southampton

http://www.ecs.soton.ac.uk/~ent03r

==================================

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20050711/84ad2523/attachment.html