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