1 #include "config.h"
2 #if defined HAVE_LIBNAUTY && defined HAVE_NAUTY_NAUTUTIL_H
3 #include "nauty/nausparse.h"
4 #include "nauty/nautinv.h"
5 #include "nautywrapper.h"
6 
7 static DEFAULTOPTIONS_GRAPH(opts_undir);
8 static DEFAULTOPTIONS_DIGRAPH(opts_dir);
9 
10 typedef struct { int a,b; } pair;
11 
pair_less(const void * p,const void * q)12 int pair_less(const void *p,const void *q) {
13     return ((pair*)p)->a-((pair*)q)->a;
14 }
15 
color_graph(int n,int * lab,int * ptn,int * col)16 void color_graph(int n,int *lab,int *ptn,int *col) {
17     pair *lst=(pair*)malloc(n*sizeof(pair));
18     for (int i=0;i<n;++i) {
19         pair *p=&lst[i];
20         p->a=col[i];
21         p->b=i;
22     }
23     qsort((void*)lst,(size_t)n,sizeof(pair),pair_less);
24     for (int i=0;i<n;++i) {
25         pair *p=&lst[i];
26         lab[i]=p->b;
27         ptn[i]=(i>=n-1 || p->a!=lst[i+1].a)?0:1;
28     }
29     free(lst);
30 }
31 
int_less(const void * p,const void * q)32 int int_less(const void *p,const void *q) {
33     return *(int*)p-*(int*)q;
34 }
35 
nautywrapper_words_needed(int n)36 int nautywrapper_words_needed(int n) {
37     return SETWORDSNEEDED(n);
38 }
39 
nautywrapper_is_isomorphic(int isdir,int n,int * adj1,int * adj2,int * sigma)40 int nautywrapper_is_isomorphic(int isdir,int n,int *adj1,int *adj2,int *sigma) {
41     DYNALLSTAT(int,lab1,lab1_sz);
42     DYNALLSTAT(int,lab2,lab2_sz);
43     DYNALLSTAT(int,ptn1,ptn1_sz);
44     DYNALLSTAT(int,ptn2,ptn2_sz);
45     DYNALLSTAT(int,col1,col1_sz);
46     DYNALLSTAT(int,col2,col2_sz);
47     DYNALLSTAT(int,orbits,orbits_sz);
48     DYNALLSTAT(graph,g1,g1_sz);
49     DYNALLSTAT(graph,g2,g2_sz);
50     DYNALLSTAT(graph,cg1,cg1_sz);
51     DYNALLSTAT(graph,cg2,cg2_sz);
52     optionblk *options=isdir!=0?&opts_dir:&opts_undir;
53     statsblk stats;
54     int m=SETWORDSNEEDED(n);
55     nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
56     DYNALLOC1(int,lab1,lab1_sz,n,"malloc");
57     DYNALLOC1(int,lab2,lab2_sz,n,"malloc");
58     DYNALLOC1(int,ptn1,ptn1_sz,n,"malloc");
59     DYNALLOC1(int,ptn2,ptn2_sz,n,"malloc");
60     DYNALLOC1(int,col1,col1_sz,n,"malloc");
61     DYNALLOC1(int,col2,col2_sz,n,"malloc");
62     DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
63     DYNALLOC2(graph,g1,g1_sz,n,m,"malloc");
64     EMPTYGRAPH(g1,m,n);
65     DYNALLOC2(graph,g2,g2_sz,n,m,"malloc");
66     EMPTYGRAPH(g2,m,n);
67     DYNALLOC2(graph,cg1,cg1_sz,n,m,"malloc");
68     DYNALLOC2(graph,cg2,cg2_sz,n,m,"malloc");
69     options->getcanon=TRUE;
70     options->writeautoms=FALSE;
71     options->outfile=NULL;
72     options->defaultptn=FALSE;
73     int i=0,j=0,k,read_col=1;
74     /* create the first graph */
75     while (1) {
76         if ((k=adj1[i++])==-1) { if ((++j)==n) break; read_col=1; }
77         else if (read_col==1) { col1[j]=k; read_col=0; }
78         else if (j<k && isdir==0) { ADDONEEDGE(g1,j,k,m); }
79         else if (isdir!=0) { ADDONEARC(g1,j,k,m); }
80     }
81     /* create the second graph */
82     i=j=0;
83     read_col=1;
84     while (1) {
85         if ((k=adj2[i++])==-1) { if ((++j)==n) break; read_col=1; }
86         else if (read_col==1) { col2[j]=k; read_col=0; }
87         else if (j<k && isdir==0) { ADDONEEDGE(g2,j,k,m); }
88         else if (isdir!=0) { ADDONEARC(g2,j,k,m); }
89     }
90     color_graph(n,lab1,ptn1,col1);
91     color_graph(n,lab2,ptn2,col2);
92     boolean isomorphic;
93     qsort((void*)col1,(size_t)n,sizeof(int),int_less);
94     qsort((void*)col2,(size_t)n,sizeof(int),int_less);
95     for (i=0;i<n;++i) {
96         if (col1[i]!=col2[i])
97             break;
98     }
99     if (i==n) { // colors match
100         /* canonically label both graphs */
101         densenauty(g1,lab1,ptn1,orbits,options,&stats,m,n,cg1);
102         densenauty(g2,lab2,ptn2,orbits,options,&stats,m,n,cg2);
103         /* return nonzero iff the canonical labelings match */
104         size_t cnt=0;
105         for (;cnt<m*(size_t)n;++cnt) {
106             if (cg1[cnt]!=cg2[cnt]) break;
107         }
108         isomorphic=cnt==m*(size_t)n?TRUE:FALSE;
109         if (isomorphic && sigma!=NULL) {
110             for (i=0;i<n;++i) {
111                 sigma[lab1[i]]=lab2[i];
112             }
113         }
114     } else isomorphic=FALSE; // colors do not match
115     DYNFREE(lab1,lab1_sz);
116     DYNFREE(lab2,lab2_sz);
117     DYNFREE(ptn1,ptn1_sz);
118     DYNFREE(ptn2,ptn2_sz);
119     DYNFREE(col1,col1_sz);
120     DYNFREE(col2,col2_sz);
121     DYNFREE(orbits,orbits_sz);
122     DYNFREE(g1,g1_sz);
123     DYNFREE(g2,g2_sz);
124     DYNFREE(cg1,cg1_sz);
125     DYNFREE(cg2,cg2_sz);
126     return isomorphic;
127 }
128 
nautywrapper_aut_generators(int isdir,int n,int * adj,FILE * f)129 void nautywrapper_aut_generators(int isdir,int n,int *adj,FILE *f) {
130     DYNALLSTAT(int,lab,lab_sz);
131     DYNALLSTAT(int,ptn,ptn_sz);
132     DYNALLSTAT(int,col,col_sz);
133     DYNALLSTAT(int,orbits,orbits_sz);
134     DYNALLSTAT(graph,g,g_sz);
135     optionblk *options=isdir!=0?&opts_dir:&opts_undir;
136     statsblk stats;
137     int m=SETWORDSNEEDED(n);
138     nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
139     DYNALLOC1(int,lab,lab_sz,n,"malloc");
140     DYNALLOC1(int,ptn,ptn_sz,n,"malloc");
141     DYNALLOC1(int,col,col_sz,n,"malloc");
142     DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
143     DYNALLOC2(graph,g,g_sz,n,m,"malloc");
144     EMPTYGRAPH(g,m,n);
145     options->getcanon=FALSE;
146     options->writeautoms=TRUE;
147     options->linelength=RAND_MAX;
148     options->outfile=f;
149     options->defaultptn=FALSE;
150     int i=0,j=0,k,read_col=1;
151     /* create the graph */
152     while (1) {
153         if ((k=adj[i++])==-1) { if ((++j)==n) break; read_col=1; }
154         else if (read_col==1) { col[j]=k; read_col=0; }
155         else if (j<k && isdir==0) { ADDONEEDGE(g,j,k,m); }
156         else if (isdir!=0) { ADDONEARC(g,j,k,m); }
157     }
158     color_graph(n,lab,ptn,col);
159     densenauty(g,lab,ptn,orbits,options,&stats,m,n,NULL);
160     DYNFREE(lab,lab_sz);
161     DYNFREE(ptn,ptn_sz);
162     DYNFREE(col,col_sz);
163     DYNFREE(orbits,orbits_sz);
164     DYNFREE(g,g_sz);
165 }
166 
nautywrapper_canonical(int isdir,int n,int * adj,int * clab,unsigned long * cgrph,int * cols)167 void nautywrapper_canonical(int isdir,int n,int *adj,int *clab,unsigned long *cgrph,int *cols) {
168     DYNALLSTAT(int,lab,lab_sz);
169     DYNALLSTAT(int,ptn,ptn_sz);
170     DYNALLSTAT(int,col,col_sz);
171     DYNALLSTAT(int,orbits,orbits_sz);
172     DYNALLSTAT(graph,g,g_sz);
173     DYNALLSTAT(graph,cg,cg_sz);
174     optionblk *options=isdir!=0?&opts_dir:&opts_undir;
175     statsblk stats;
176     int m=SETWORDSNEEDED(n);
177     nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
178     DYNALLOC1(int,lab,lab_sz,n,"malloc");
179     DYNALLOC1(int,ptn,ptn_sz,n,"malloc");
180     DYNALLOC1(int,col,col_sz,n,"malloc");
181     DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
182     DYNALLOC2(graph,cg,cg_sz,n,m,"malloc");
183     DYNALLOC2(graph,g,g_sz,n,m,"malloc");
184     EMPTYGRAPH(g,m,n);
185     options->getcanon=TRUE;
186     options->writeautoms=FALSE;
187     options->outfile=NULL;
188     options->defaultptn=FALSE;
189     int i=0,j=0,k,read_col=1;
190     /* create the graph */
191     while (1) {
192         if ((k=adj[i++])==-1) { if ((++j)==n) break; read_col=1; }
193         else if (read_col==1) { col[j]=k; read_col=0; }
194         else if (j<k && isdir==0) { ADDONEEDGE(g,j,k,m); }
195         else if (isdir!=0) { ADDONEARC(g,j,k,m); }
196     }
197     color_graph(n,lab,ptn,col);
198     densenauty(g,lab,ptn,orbits,options,&stats,m,n,cg);
199     if (clab!=NULL) {
200         for (i=0;i<n;++i) {
201             clab[i]=lab[i];
202         }
203     }
204     if (cgrph!=NULL) {
205         size_t cnt=0;
206         for (;cnt<m*(size_t)n;++cnt) {
207             cgrph[cnt]=cg[cnt];
208         }
209     }
210     if (cols!=NULL) {
211         qsort((void*)col,(size_t)n,sizeof(int),int_less);
212         for (i=0;i<n;++i) {
213             cols[i]=col[i];
214         }
215     }
216     DYNFREE(lab,lab_sz);
217     DYNFREE(ptn,ptn_sz);
218     DYNFREE(col,col_sz);
219     DYNFREE(orbits,orbits_sz);
220     DYNFREE(g,g_sz);
221     DYNFREE(cg,cg_sz);
222 }
223 #else // HAVE_LIBNAUTY
224 #include <stdio.h>
nautywrapper_is_isomorphic(int isdir,int n,int * adj1,int * adj2,int * sigma)225 int nautywrapper_is_isomorphic(int isdir,int n,int *adj1,int *adj2,int *sigma){
226     return 0;
227 }
nautywrapper_aut_generators(int isdir,int n,int * adj,FILE * f)228 void nautywrapper_aut_generators(int isdir,int n,int *adj,FILE *f){}
nautywrapper_canonical(int isdir,int n,int * adj,int * clab,unsigned long * cgrph,int * cols)229 void nautywrapper_canonical(int isdir,int n,int *adj,int *clab,unsigned long *cgrph,int *cols){
230     *clab=*cgrph=*cols=16;
231 }
232 #endif // HAVE_LIBNAUTY
233