1 /* deledgeg.c version 1.4; B D McKay, Jan 2015. */
2
3 #define USAGE "deledgeg [-lq] [-d#] [-z] [infile [outfile]]"
4
5 #define HELPTEXT \
6 " For each edge e, output G-e\n\
7 \n\
8 The output file has a header if and only if the input file does.\n\
9 \n\
10 -z Consider as digraph and delete directed edges\n\
11 -l Canonically label outputs\n\
12 -d# Specify a lower bound on the minimum out-degree of the output\n\
13 -q Suppress auxiliary information\n"
14
15 /*************************************************************************/
16
17 #include "gtools.h"
18
19 /**************************************************************************/
20
21 int
main(int argc,char * argv[])22 main(int argc, char *argv[])
23 {
24 char *infilename,*outfilename;
25 FILE *infile,*outfile;
26 boolean badargs,dolabel,quiet,dswitch;
27 boolean digraph;
28 int i,j,m,n,v,w,argnum;
29 int codetype,outcode;
30 graph *g,*gq;
31 nauty_counter nin,nout;
32 char *arg,sw;
33 setword *gv,*gw;
34 int mindeg,actmindeg,degv;
35 boolean zswitch;
36 double t;
37 #if MAXN
38 graph h[MAXN*MAXM];
39 int deg[MAXN];
40 #else
41 DYNALLSTAT(graph,h,h_sz);
42 DYNALLSTAT(int,deg,deg_sz);
43 #endif
44
45 HELP; PUTVERSION;
46
47 infilename = outfilename = NULL;
48 badargs = FALSE;
49 zswitch = dswitch = dolabel = quiet = FALSE;
50
51 argnum = 0;
52 badargs = FALSE;
53 for (j = 1; !badargs && j < argc; ++j)
54 {
55 arg = argv[j];
56 if (arg[0] == '-' && arg[1] != '\0')
57 {
58 ++arg;
59 while (*arg != '\0')
60 {
61 sw = *arg++;
62 SWBOOLEAN('l',dolabel)
63 else SWBOOLEAN('z',zswitch)
64 else SWBOOLEAN('q',quiet)
65 else SWINT('d',dswitch,mindeg,">E deledgeg -d")
66 else badargs = TRUE;
67 }
68 }
69 else
70 {
71 ++argnum;
72 if (argnum == 1) infilename = arg;
73 else if (argnum == 2) outfilename = arg;
74 else badargs = TRUE;
75 }
76 }
77
78 if (badargs)
79 {
80 fprintf(stderr,">E Usage: %s\n",USAGE);
81 GETHELP;
82 exit(1);
83 }
84
85 if (!quiet)
86 {
87 fprintf(stderr,">A deledgeg");
88 if (dolabel || zswitch) fprintf(stderr," -");
89 if (dolabel) fprintf(stderr,"l");
90 if (zswitch) fprintf(stderr,"z");
91 if (dswitch) fprintf(stderr," -d%d",mindeg);
92 if (argnum > 0) fprintf(stderr," %s",infilename);
93 if (argnum > 1) fprintf(stderr," %s",outfilename);
94 fprintf(stderr,"\n");
95 fflush(stderr);
96 }
97
98 if (infilename && infilename[0] == '-') infilename = NULL;
99 infile = opengraphfile(infilename,&codetype,FALSE,1);
100 if (!infile) exit(1);
101 if (!infilename) infilename = "stdin";
102
103 if (!outfilename || outfilename[0] == '-')
104 {
105 outfilename = "stdout";
106 outfile = stdout;
107 }
108 else if ((outfile = fopen(outfilename,"w")) == NULL)
109 {
110 fprintf(stderr,"Can't open output file %s\n",outfilename);
111 gt_abort(NULL);
112 }
113
114 if (codetype&SPARSE6) outcode = SPARSE6;
115 else if (codetype&DIGRAPH6) outcode = DIGRAPH6;
116 else outcode = GRAPH6;
117
118 if (codetype&HAS_HEADER)
119 {
120 if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER);
121 else if (outcode == DIGRAPH6) writeline(outfile,DIGRAPH6_HEADER);
122 else writeline(outfile,GRAPH6_HEADER);
123 }
124 if (!dswitch) mindeg = 0;
125
126 if (dolabel) nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
127
128 nin = nout = 0;
129 t = CPUTIME;
130 while (TRUE)
131 {
132 if ((g = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break;
133 ++nin;
134
135 #if !MAXN
136 DYNALLOC1(int,deg,deg_sz,n,"deledgeg");
137 #endif
138
139 actmindeg = n;
140 for (v = 0, gv = g; v < n; ++v, gv += m)
141 {
142 degv = 0;
143 for (i = 0; i < m; ++i)
144 degv += POPCOUNT(gv[i]);
145 if (degv < actmindeg) actmindeg = degv;
146 deg[v] = degv;
147 }
148
149 if (actmindeg < mindeg) continue;
150
151 if (zswitch || digraph)
152 {
153 for (v = 0, gv = g; v < n; ++v, gv += m)
154 {
155 if (deg[v] <= mindeg) continue;
156
157 for (w = -1; (w = nextelement(gv,m,w)) >= 0; )
158 {
159 DELELEMENT(gv,w);
160 gq = g;
161
162 if (dolabel)
163 {
164 #if !MAXN
165 DYNALLOC2(graph,h,h_sz,n,m,"deledgeg");
166 #endif
167 fcanonise(g,m,n,h,NULL,TRUE);
168 gq = h;
169 }
170 writed6(outfile,gq,m,n);
171 ++nout;
172 ADDELEMENT(gv,w);
173 }
174 }
175 }
176 else
177 {
178 for (v = 0, gv = g; v < n; ++v, gv += m)
179 {
180 if (deg[v] <= mindeg) continue;
181
182 for (w = v-1; (w = nextelement(gv,m,w)) >= 0; )
183 {
184 if (deg[w] <= mindeg || (w == v && deg[w] <= mindeg+1)) continue;
185
186 gw = GRAPHROW(g,w,m);
187 DELELEMENT(gv,w);
188 DELELEMENT(gw,v);
189 gq = g;
190
191 if (dolabel)
192 {
193 #if !MAXN
194 DYNALLOC2(graph,h,h_sz,n,m,"deledgeg");
195 #endif
196 fcanonise(g,m,n,h,NULL,FALSE);
197 gq = h;
198 }
199 if (outcode == SPARSE6) writes6(outfile,gq,m,n);
200 else writeg6(outfile,gq,m,n);
201 ++nout;
202 ADDELEMENT(gv,w);
203 ADDELEMENT(gw,v);
204 }
205 }
206 }
207 FREES(g);
208 }
209 t = CPUTIME - t;
210
211 if (!quiet)
212 fprintf(stderr,
213 ">Z " COUNTER_FMT " graphs read from %s, "
214 COUNTER_FMT " written to %s; %3.2f sec.\n",
215 nin,infilename,nout,outfilename,t);
216
217 exit(0);
218 }
219