Home > matgraph > @graph > cayley.m

cayley

PURPOSE ^

cayley(g,perms) -- create a Cayley graph (undirected)

SYNOPSIS ^

function cayley(g,perms,verbose)

DESCRIPTION ^

 cayley(g,perms) -- create a Cayley graph (undirected)
 g is the graph to be written
 perms is a cell array of permutations that are the generators of a group.
 The vertices of g are the elements of the generated group. There is an
 edge from u to v in g provided there is a generator x so that u=v*x or 
 v = u*x.

 cayley(g,perms,verbose) with verbose = true displays progress as this
 function works. [Default is verbose = false.]

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function cayley(g,perms,verbose)
0002 % cayley(g,perms) -- create a Cayley graph (undirected)
0003 % g is the graph to be written
0004 % perms is a cell array of permutations that are the generators of a group.
0005 % The vertices of g are the elements of the generated group. There is an
0006 % edge from u to v in g provided there is a generator x so that u=v*x or
0007 % v = u*x.
0008 %
0009 % cayley(g,perms,verbose) with verbose = true displays progress as this
0010 % function works. [Default is verbose = false.]
0011 
0012 if nargin<3
0013     verbose = false;
0014 end
0015 
0016 if ~isa(perms,'cell')
0017     error('2nd argument must be a cell array of permutations');
0018 end
0019 
0020 perms = perms(:);    % make it 1-dimensional
0021 np = length(perms);  % number of perms
0022 
0023 % if there are no perms in the list, then the group is {1} and the graph is
0024 % a single vertex
0025 if np == 0
0026     resize(g,1);
0027     return
0028 end
0029 
0030 if verbose
0031     disp('Generating the group elements from these:')
0032 end
0033 
0034 group = gen_group(perms,verbose);
0035 
0036 if verbose
0037     disp('Generating edge list')
0038 end
0039 
0040 edges = [];
0041 
0042 ng = size(group,1);  % size of the group
0043 
0044 for i=1:ng
0045     u = group(i,:);
0046     pu = permutation(u);
0047     for k=1:np
0048         pv = pu * perms{k};
0049         v = array(pv);
0050         j = find_row(v,group);
0051         edges = [edges; [i,j]];
0052     end
0053 end
0054 
0055 edges = unique(sortrows(edges),'rows');
0056 
0057 m = size(edges,1);
0058 if verbose
0059     disp([int2str(m),' edges created']);
0060 end
0061 
0062 resize(g,0)
0063 add(g,edges);
0064 
0065 % label the nodes
0066 clear_labels(g);
0067 for u = 1:nv(g)
0068     str = display(permutation(group(u,:)));
0069     label(g,u,str);
0070 end
0071 
0072 
0073 %%
0074 function group = gen_group(perms,verbose)
0075 % create the full list of elements of a group based on a matrix of
0076 % generators.
0077 
0078 
0079 np = length(perms);
0080 psize = 0;
0081 
0082 for i=1:np
0083     pis = length(perms{i});
0084     if pis > psize
0085         psize = pis;
0086     end
0087 end
0088 
0089 
0090 gen_matrix = zeros(np, psize);
0091 for i=1:np
0092     p = perms{i} * permutation(psize);
0093     perms{i} = p;
0094     row = array(p);
0095     gen_matrix(i,:) = row;
0096     if verbose
0097         display(perms{i})
0098     end
0099 end
0100 
0101 % initially, the group is the identity and all the generators
0102 group = [1:psize; gen_matrix];
0103 group = sortrows(group);
0104 last = group;
0105 
0106 while ~isempty(last)
0107     ng = size(group,1);
0108     if verbose
0109         disp(['Expanding. Group size = ', int2str(ng)]);
0110     end
0111     new_rows = [];
0112     for k=1:size(last,1)
0113         p = permutation(last(k,:));
0114         for j=1:np
0115             q = p * perms{j};
0116             row = array(q);
0117             idx = find_row(row,group);
0118             if idx == 0
0119                 new_rows = [new_rows;row];
0120             end
0121         end
0122     end
0123     if size(new_rows,1) == 0
0124         return
0125     end
0126         
0127     new_rows = unique(sortrows(new_rows),'rows');
0128     last = [];
0129     for k=1:size(new_rows,1)
0130         r = new_rows(k,:);
0131         if find_row(r,group) == 0
0132             last = [last;r];
0133         end
0134     end
0135     group = [group; last];
0136     group = unique(sortrows(group),'rows');
0137     
0138 end
0139

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003