1 /* biplabg.c version 1.0; B D McKay, Nov 19, 2003. */
2
3 #define USAGE "biplabg [-q] [infile [outfile]]"
4
5 #define HELPTEXT \
6 " Label bipartite graphs so that the colour classes are contiguous.\n\
7 The first vertex of each component is assigned the first colour.\n\
8 Vertices in each colour class have the same relative order as before.\n\
9 Non-bipartite graphs are rejected.\n\
10 \n\
11 The output file has a header if and only if the input file does.\n\
12 \n\
13 -q Suppress auxiliary information.\n"
14
15 /*************************************************************************/
16
17 #include "gtools.h"
18
19 /**************************************************************************/
20
21 static boolean
biplabel(graph * g,int m,int n,graph * h)22 biplabel(graph *g, int m, int n, graph *h)
23 /* h := bipartite labelling of g; else return FALSE */
24 {
25 register int i,j;
26 #if MAXN
27 int colour[MAXN];
28 permutation lab[MAXN];
29 #else
30 DYNALLSTAT(int,colour,colour_sz);
31 DYNALLSTAT(permutation,lab,lab_sz);
32
33 DYNALLOC1(int,colour,colour_sz,n,"biplabg");
34 DYNALLOC1(permutation,lab,lab_sz,n,"biplabg");
35 #endif
36
37 if (!twocolouring(g,colour,m,n)) return FALSE;
38
39 j = 0;
40 for (i = 0; i < n; ++i) if (colour[i] == 0) lab[j++] = i;
41 for (i = 0; i < n; ++i) if (colour[i] == 1) lab[j++] = i;
42
43 updatecan(g,h,lab,0,m,n);
44
45 return TRUE;
46 }
47
48 /**************************************************************************/
49
50 int
main(int argc,char * argv[])51 main(int argc, char *argv[])
52 {
53 char *infilename,*outfilename;
54 FILE *infile,*outfile;
55 boolean badargs,quiet;
56 int j,m,n,argnum;
57 int codetype,outcode;
58 graph *g;
59 long nin,nout,ii;
60 char *arg,sw;
61 double t;
62 #if MAXN
63 graph h[MAXN*MAXM];
64 #else
65 DYNALLSTAT(graph,h,h_sz);
66 #endif
67
68 HELP;
69
70 infilename = outfilename = NULL;
71 quiet = FALSE;
72
73 argnum = 0;
74 badargs = FALSE;
75 for (j = 1; !badargs && j < argc; ++j)
76 {
77 arg = argv[j];
78 if (arg[0] == '-' && arg[1] != '\0')
79 {
80 ++arg;
81 while (*arg != '\0')
82 {
83 sw = *arg++;
84 SWBOOLEAN('q',quiet)
85 else badargs = TRUE;
86 }
87 }
88 else
89 {
90 ++argnum;
91 if (argnum == 1) infilename = arg;
92 else if (argnum == 2) outfilename = arg;
93 else badargs = TRUE;
94 }
95 }
96
97 if (badargs)
98 {
99 fprintf(stderr,">E Usage: %s\n",USAGE);
100 GETHELP;
101 exit(1);
102 }
103
104 if (!quiet)
105 {
106 fprintf(stderr,">A biplabg");
107 if (argnum > 0) fprintf(stderr," %s",infilename);
108 if (argnum > 1) fprintf(stderr," %s",outfilename);
109 fprintf(stderr,"\n");
110 fflush(stderr);
111 }
112
113 if (infilename && infilename[0] == '-') infilename = NULL;
114 infile = opengraphfile(infilename,&codetype,FALSE,1);
115 if (!infile) exit(1);
116 if (!infilename) infilename = "stdin";
117
118 if (!outfilename || outfilename[0] == '-')
119 {
120 outfilename = "stdout";
121 outfile = stdout;
122 }
123 else if ((outfile = fopen(outfilename,"w")) == NULL)
124 {
125 fprintf(stderr,"Can't open output file %s\n",outfilename);
126 gt_abort(NULL);
127 }
128
129 if (codetype&SPARSE6) outcode = SPARSE6;
130 else outcode = GRAPH6;
131
132 if (codetype&HAS_HEADER)
133 {
134 if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER);
135 else writeline(outfile,GRAPH6_HEADER);
136 }
137
138 nautil_check(WORDSIZE,1,1,NAUTYVERSIONID);
139
140 nin = nout = 0;
141 t = CPUTIME;
142 while (TRUE)
143 {
144 if ((g = readg(infile,NULL,0,&m,&n)) == NULL) break;
145 ++nin;
146
147 #if !MAXN
148 DYNALLOC2(graph,h,h_sz,n,m,"biplabg");
149 #endif
150 if (biplabel(g,m,n,h))
151 {
152 ++nout;
153 if (outcode == SPARSE6) writes6(outfile,h,m,n);
154 else writeg6(outfile,h,m,n);
155 }
156 FREES(g);
157 }
158 t = CPUTIME - t;
159
160 if (!quiet)
161 fprintf(stderr,
162 ">Z %ld graphs read from %s; %ld written to %s; %3.2f sec.\n",
163 nin,infilename,nout,outfilename,t);
164
165 exit(0);
166 }
167