Page MenuHomePhorge
Files F27033623

nautyex8.c
No OneTemporary
Actions

Authored By
Unknown
Size
3 KB
Referenced Files
None
Subscribers
None

nautyex8.c
View Options

/* This program demonstrates how an isomorphism is found between
two graphs, using the Moebius graphs as an example.
This version uses dense form with dynamic allocation.
*/
#include "nauty.h"
int
main(int argc, char *argv[])
{
DYNALLSTAT(int,lab1,lab1_sz);
DYNALLSTAT(int,lab2,lab2_sz);
DYNALLSTAT(int,ptn,ptn_sz);
DYNALLSTAT(int,orbits,orbits_sz);
DYNALLSTAT(int,map,map_sz);
DYNALLSTAT(graph,g1,g1_sz);
DYNALLSTAT(graph,g2,g2_sz);
DYNALLSTAT(graph,cg1,cg1_sz);
DYNALLSTAT(graph,cg2,cg2_sz);
static DEFAULTOPTIONS_GRAPH(options);
statsblk stats;
int n,m,i;
size_t k;
/* Select option for canonical labelling */
options.getcanon = TRUE;
while (1)
{
printf("\nenter n : ");
if (scanf("%d",&n) == 1 && n > 0)
{
if (n%2 != 0)
{
fprintf(stderr,"Sorry, n must be even\n");
continue;
}
m = SETWORDSNEEDED(n);
nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
DYNALLOC1(int,lab1,lab1_sz,n,"malloc");
DYNALLOC1(int,lab2,lab2_sz,n,"malloc");
DYNALLOC1(int,ptn,ptn_sz,n,"malloc");
DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
DYNALLOC1(int,map,map_sz,n,"malloc");
/* Now make the first graph */
DYNALLOC2(graph,g1,g1_sz,n,m,"malloc");
EMPTYGRAPH(g1,m,n);
for (i = 0; i < n; i += 2) /* Spokes */
ADDONEEDGE(g1,i,i+1,m);
for (i = 0; i < n-2; ++i) /* Cycle */
ADDONEEDGE(g1,i,i+2,m);
ADDONEEDGE(g1,1,n-2,m);
ADDONEEDGE(g1,0,n-1,m);
/* Now make the second graph */
DYNALLOC2(graph,g2,g2_sz,n,m,"malloc");
EMPTYGRAPH(g2,m,n);
for (i = 0; i < n; ++i)
{
ADDONEEDGE(g2,i,(i+1)%n,m); /* Rim */
ADDONEEDGE(g2,i,(i+n/2)%n,m); /* Diagonals */
}
/* Create canonical graphs */
DYNALLOC2(graph,cg1,cg1_sz,n,m,"malloc");
DYNALLOC2(graph,cg2,cg2_sz,n,m,"malloc");
densenauty(g1,lab1,ptn,orbits,&options,&stats,m,n,cg1);
densenauty(g2,lab2,ptn,orbits,&options,&stats,m,n,cg2);
/* Compare canonically labelled graphs */
for (k = 0; k < m*(size_t)n; ++k)
if (cg1[k] != cg2[k]) break;
if (k == m*(size_t)n)
{
printf("Isomorphic.\n");
if (n <= 1000)
{
/* Write the isomorphism. For each i, vertex lab1[i]
of sg1 maps onto vertex lab2[i] of sg2. We compute
the map in order of labelling because it looks better. */
for (i = 0; i < n; ++i) map[lab1[i]] = lab2[i];
for (i = 0; i < n; ++i) printf(" %d-%d",i,map[i]);
printf("\n");
}
}
else
printf("Not isomorphic.\n");
}
else
break;
}
exit(0);
}

File Metadata

Mime Type
text/x-c
Expires
Tue, Oct 27, 4:40 PM (1 d, 2 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
407960
Default Alt Text
nautyex8.c (3 KB)

Event Timeline