[Nauty] counting graphs
Sterten at aol.com
Sterten at aol.com
Thu Dec 5 18:41:03 EST 2002
>* Sterten at aol.com <Sterten at aol.com> [021204 21:26]:
>>
>> So, apparently there are better methods to count graphs than geng.
>> What methods are these ?
>
>This is the Polya or Polya-Redfield method which uses group theory.
searching for these keywords I found a small code-snippets online.
Presumably "GAP" - language. See below.
Someone can use it in GAP or knows how to convert it to C ?
>It is explained in many graph theory books. It can also be
>applied to some other classes of graphs, but not (easily) to
>all classes. For example, I believe that the exact enumeration
>of triangle-free graphs is an open problem still.
>
>Brendan.
#
# graph - count unlabeled graphs via the Polya-Redfield method.
#
# Calling sequence:
# graph(n)
# graph(n,a)
#
# Parameters:
# n - a positive integer
# a - an expression
#
# The symmetric group S_n embeds into S_m (where m = n*(n-1)/2) via
# permutations of the edges of the complete graph on n points.
#
# graph(n) computes the symmetric function corresponding to the induction of
# the trivial character of S_n up to S_m. This amounts to the cycle index of
# S_n acting on unordered pairs; i.e., for each partition lambda of m, the
# coefficient of the power-sum indexed by lambda in graph(n) is (1/n!) times
# the number of permutations in S_n whose cycle-type in S_m is lambda.
#
# With two arguments, graph(n,a) applies a standard plethystic substitution
# to the cycle-index graph(n). That is, for each occurrence of the power-sum
# p.j in graph(n), the substitution p.j -> a<j> will be applied, where a<j>
# denotes the result obtained by substituting x -> x^j for every variable
# name x in a. In other words, graph(n,a) is functionally equivalent to
# (but faster than) computing evalsf(graph(n),a).
#
# Examples:
# with(SF);
# graph(6);
# The edge generating function for graphs on 7 points:
# graph(7,1+q);
# The number of graphs on 15 points:
# graph(15,2);
# The edge generating function for (loopless) multigraphs on 5 points:
# f:=graph(5,1/(1-q));
# taylor(normal(f),q,20);
graph:=proc(n) local res,new,terms,cfs,d,i,j,k,y,x;
if nargs>1 then
y:=[seq(subs({seq(x=x^j,x=indets(args[2]))},args[2]),j=1..n*n/4+1)]
else y:=[seq(cat('p',j),j=1..n*n/4+1)]
fi;
cfs:=[coeffs(SF['top'](cat('h',n)),[seq(cat('p',i),i=1..n)],'terms')];
terms:=[terms]; res:=0;
for i to nops(terms) do
new:=cfs[i];
d:=[seq(degree(terms[i],cat('p',j)),j=1..n)];
for j to n do
if d[j]=0 then next fi;
new:=new*y[j]^(j*d[j]*(d[j]-1)/2);
if modp(j,2)=0 then
new:=new*y[j]^(d[j]*(j-2)/2)*y[j/2]^d[j]
else
new:=new*y[j]^(d[j]*(j-1)/2)
fi;
for k to j-1 do
if d[k]>0 then new:=new*y[ilcm(k,j)]^(d[k]*d[j]*igcd(j,k)) fi
od
od;
res:=res+new;
od;
collect(res,indets(y),'distributed');
end;
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20021205/7b97e38b/attachment.html
More information about the Nauty
mailing list