[Nauty-list] Directed graphs with loops
Sterten at aol.com
Sterten at aol.com
Sun Sep 12 17:49:01 EST 2010
OK, n=4 is easy
here is a short but slow BASIC-program to print them
10 DEFINT A-Z:INPUT N:DIM A(N+1,N+1),B(N+1),U(N)
12 F=1:FOR I=1 TO N:F=F*I:NEXT:DIM P(F,N),Q(F,N):F=0
15 ' -------create the permutations in S_n-------------
20 I=0
30 I=I+1:B(I)=0:IF I>N THEN 62
40 B(I)=B(I)+1:IF B(I)>N THEN 64
50 IF U(B(I)) THEN 40
60 U(B(I))=1:GOTO 30
62 F=F+1:FOR I=1 TO N:P(F,I)=B(I):Q(F,B(I))=I:NEXT
64 I=I-1:U(B(I))=0:IF I>0 THEN 40
68 ' --------backtrack through n*n matrices over {0,1}----------
70 X=0:Z=0
80 X=X+1:Y=0:IF X>N THEN X=N:Y=N+1:GOTO 110
90 Y=Y+1:A(X,Y)=-1:IF Y>N THEN 80
100 A(X,Y)=A(X,Y)+1:IF A(X,Y)>1 THEN 150
101 GOTO 90
110 B$="":FOR I=1 TO N:FOR J=1 TO N:B$=B$+CHR$(48+A(I,J)):NEXT J,I
120 Q=0:FOR P=1 TO F:A$="":FOR I=1 TO N:FOR J=1 TO
N:A$=A$+CHR$(48+A(P(P,I),P(P,J))):NEXT J,I:Q=Q-(A$<B$):NEXT
130 IF Q=0 THEN Z=Z+1: PRINT B$
150 Y=Y-1:IF Y>0 THEN 100
160 X=X-1:IF X>0 THEN Y=N:GOTO 100
170 PRINT N;F;Z:STOP
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20100912/8401c84c/attachment.html
More information about the Nauty
mailing list