1 /*!
2 \file
3 \brief A simple frequent itemset discovery program to test GKlib's routines
4
5 \date 6/12/2008
6 \author George
7 \version \verbatim $Id: gkgraph.c 11408 2012-01-25 15:05:58Z karypis $ \endverbatim
8 */
9
10 #include <GKlib.h>
11
12 /*************************************************************************/
13 /*! Data structures for the code */
14 /*************************************************************************/
15 typedef struct {
16 int type;
17 int niter;
18 float eps;
19 float lamda;
20
21 char *infile;
22 char *outfile;
23 } params_t;
24
25 /*************************************************************************/
26 /*! Constants */
27 /*************************************************************************/
28 #define CMD_NITER 1
29 #define CMD_EPS 2
30 #define CMD_LAMDA 3
31 #define CMD_TYPE 4
32 #define CMD_HELP 10
33
34
35 /*************************************************************************/
36 /*! Local variables */
37 /*************************************************************************/
38 static struct gk_option long_options[] = {
39 {"type", 1, 0, CMD_TYPE},
40 {"niter", 1, 0, CMD_NITER},
41 {"lamda", 1, 0, CMD_LAMDA},
42 {"eps", 1, 0, CMD_EPS},
43 {"help", 0, 0, CMD_HELP},
44 {0, 0, 0, 0}
45 };
46
47
48 /*-------------------------------------------------------------------*/
49 /* Mini help */
50 /*-------------------------------------------------------------------*/
51 static char helpstr[][100] = {
52 " ",
53 "Usage: gkgraph [options] <graph-file> [<out-file>]",
54 " ",
55 " Required parameters",
56 " graph-file",
57 " The name of the file storing the graph. The file is in ",
58 " Metis' graph format.",
59 " ",
60 " Optional parameters",
61 " -niter=int",
62 " Specifies the maximum number of iterations. [default: 100]",
63 " ",
64 " -lamda=float",
65 " Specifies the follow-the-adjacent-links probability. [default: 0.80]",
66 " ",
67 " -eps=float",
68 " Specifies the error tollerance. [default: 1e-10]",
69 " ",
70 " -help",
71 " Prints this message.",
72 ""
73 };
74
75 static char shorthelpstr[][100] = {
76 " ",
77 " Usage: gkgraph [options] <graph-file> [<out-file>]",
78 " use 'gkgraph -help' for a summary of the options.",
79 ""
80 };
81
82
83
84 /*************************************************************************/
85 /*! Function prototypes */
86 /*************************************************************************/
87 double compute_compactness(params_t *params, gk_graph_t *graph, int32_t *perm);
88 void reorder_centroid(params_t *params, gk_graph_t *graph, int32_t *perm);
89 void print_init_info(params_t *params, gk_graph_t *graph);
90 void print_final_info(params_t *params);
91 params_t *parse_cmdline(int argc, char *argv[]);
92
93
94 /*************************************************************************/
95 /*! the entry point */
96 /**************************************************************************/
main(int argc,char * argv[])97 int main(int argc, char *argv[])
98 {
99 ssize_t i, j, v;
100 params_t *params;
101 gk_graph_t *graph, *pgraph;
102 int32_t *perm;
103
104 /* get command-line options */
105 params = parse_cmdline(argc, argv);
106
107 /* read the data */
108 graph = gk_graph_Read(params->infile, GK_GRAPH_FMT_METIS, 0, 0, 0);
109
110 /* display some basic stats */
111 print_init_info(params, graph);
112
113
114 /* determine the initial compactness of the graph */
115 printf("Initial compactness: %le\n", compute_compactness(params, graph, NULL));
116
117 /* compute the BFS ordering and re-order the graph */
118 //for (i=0; i<params->niter; i++) {
119 for (i=0; i<1; i++) {
120 v = RandomInRange(graph->nvtxs);
121 gk_graph_ComputeBFSOrdering(graph, v, &perm, NULL);
122 printf("BFS from %8d. Compactness: %le\n",
123 (int) v, compute_compactness(params, graph, perm));
124
125 pgraph = gk_graph_Reorder(graph, perm, NULL);
126 gk_graph_Write(pgraph, "bfs.metis", GK_GRAPH_FMT_METIS);
127 gk_graph_Free(&pgraph);
128
129 gk_graph_ComputeBestFOrdering(graph, v, params->type, &perm, NULL);
130 printf("BestF from %8d. Compactness: %le\n",
131 (int) v, compute_compactness(params, graph, perm));
132
133 pgraph = gk_graph_Reorder(graph, perm, NULL);
134 gk_graph_Write(pgraph, "bestf.metis", GK_GRAPH_FMT_METIS);
135 gk_graph_Free(&pgraph);
136
137 #ifdef XXX
138 for (j=0; j<params->niter; j++) {
139 reorder_centroid(params, graph, perm);
140 printf("\tAfter centroid; Compactness: %le\n",
141 compute_compactness(params, graph, perm));
142 }
143
144 pgraph = gk_graph_Reorder(graph, perm, NULL);
145 gk_graph_Write(pgraph, "centroid.metis", GK_GRAPH_FMT_METIS);
146 gk_graph_Free(&pgraph);
147 #endif
148 gk_free((void **)&perm, LTERM);
149 }
150
151 gk_graph_Free(&graph);
152 //gk_graph_Free(&pgraph);
153
154 print_final_info(params);
155 }
156
157
158
159
160 /*************************************************************************/
161 /*! This function computes the compactness of the graph's adjacency list */
162 /*************************************************************************/
compute_compactness(params_t * params,gk_graph_t * graph,int32_t * perm)163 double compute_compactness(params_t *params, gk_graph_t *graph, int32_t *perm)
164 {
165 int i, v, u, nvtxs;
166 ssize_t j, *xadj;
167 int32_t *adjncy;
168 double compactness=0.0;
169 int *freq;
170
171 nvtxs = graph->nvtxs;
172 xadj = graph->xadj;
173 adjncy = graph->adjncy;
174
175 freq = gk_ismalloc(nvtxs, 0, "compute_compactness: freq");
176
177 for (i=0; i<nvtxs; i++) {
178 v = (perm == NULL ? i : perm[i]);
179 for (j=xadj[i]; j<xadj[i+1]; j++) {
180 u = (perm == NULL ? adjncy[j] : perm[adjncy[j]]);
181 compactness += fabs(v-u);
182 freq[gk_abs(v-u)]++;
183 }
184 }
185
186 /*
187 for (i=0; i<nvtxs; i++) {
188 if (freq[i] > 0)
189 printf("%7d %6d\n", i, freq[i]);
190 }
191 */
192 printf("\tnsmall: %d\n", freq[1]+freq[2]+freq[3]);
193
194 return compactness/xadj[nvtxs];
195 }
196
197
198 /*************************************************************************/
199 /*! This function uses a centroid-based approach to refine the ordering */
200 /*************************************************************************/
reorder_centroid(params_t * params,gk_graph_t * graph,int32_t * perm)201 void reorder_centroid(params_t *params, gk_graph_t *graph, int32_t *perm)
202 {
203 int i, v, u, nvtxs;
204 ssize_t j, *xadj;
205 int32_t *adjncy;
206 gk_fkv_t *cand;
207 double displacement;
208
209 nvtxs = graph->nvtxs;
210 xadj = graph->xadj;
211 adjncy = graph->adjncy;
212
213 cand = gk_fkvmalloc(nvtxs, "reorder_centroid: cand");
214
215 for (i=0; i<nvtxs; i++) {
216 v = perm[i];
217 displacement = 0.0;
218
219 for (j=xadj[i]; j<xadj[i+1]; j++) {
220 u = perm[adjncy[j]];
221 displacement += u-v;
222 //displacement += sign(u-v, sqrt(fabs(u-v)));
223 }
224
225 cand[i].val = i;
226 cand[i].key = v + displacement*params->lamda/(xadj[i+1]-xadj[i]);
227 }
228
229 /* sort them based on the target position in increasing order */
230 gk_fkvsorti(nvtxs, cand);
231
232
233 /* derive the permutation from the ordered list */
234 gk_i32set(nvtxs, -1, perm);
235 for (i=0; i<nvtxs; i++) {
236 if (perm[cand[i].val] != -1)
237 errexit("Resetting perm[%d] = %d\n", cand[i].val, perm[cand[i].val]);
238 perm[cand[i].val] = i;
239 }
240
241 gk_free((void **)&cand, LTERM);
242 }
243
244
245
246
247
248
249
250
251 /*************************************************************************/
252 /*! This function prints run parameters */
253 /*************************************************************************/
print_init_info(params_t * params,gk_graph_t * graph)254 void print_init_info(params_t *params, gk_graph_t *graph)
255 {
256 printf("*******************************************************************************\n");
257 printf(" gkgraph\n\n");
258 printf("Graph Information ----------------------------------------------------------\n");
259 printf(" input file=%s, [%d, %zd]\n",
260 params->infile, graph->nvtxs, graph->xadj[graph->nvtxs]);
261
262 printf("\n");
263 printf("Options --------------------------------------------------------------------\n");
264 printf(" type=%d, niter=%d, lamda=%f, eps=%e\n",
265 params->type, params->niter, params->lamda, params->eps);
266
267 printf("\n");
268 printf("Working... -----------------------------------------------------------------\n");
269 }
270
271
272 /*************************************************************************/
273 /*! This function prints final statistics */
274 /*************************************************************************/
print_final_info(params_t * params)275 void print_final_info(params_t *params)
276 {
277 printf("\n");
278 printf("Memory Usage Information -----------------------------------------------------\n");
279 printf(" Maximum memory used: %10zd bytes\n", (ssize_t) gk_GetMaxMemoryUsed());
280 printf(" Current memory used: %10zd bytes\n", (ssize_t) gk_GetCurMemoryUsed());
281 printf("********************************************************************************\n");
282 }
283
284
285 /*************************************************************************/
286 /*! This is the entry point of the command-line argument parser */
287 /*************************************************************************/
parse_cmdline(int argc,char * argv[])288 params_t *parse_cmdline(int argc, char *argv[])
289 {
290 int i;
291 int c, option_index;
292 params_t *params;
293
294 params = (params_t *)gk_malloc(sizeof(params_t), "parse_cmdline: params");
295
296 /* initialize the params data structure */
297 params->type = 1;
298 params->niter = 1;
299 params->eps = 1e-10;
300 params->lamda = 0.20;
301 params->infile = NULL;
302
303
304 /* Parse the command line arguments */
305 while ((c = gk_getopt_long_only(argc, argv, "", long_options, &option_index)) != -1) {
306 switch (c) {
307 case CMD_TYPE:
308 if (gk_optarg) params->type = atoi(gk_optarg);
309 break;
310 case CMD_NITER:
311 if (gk_optarg) params->niter = atoi(gk_optarg);
312 break;
313 case CMD_EPS:
314 if (gk_optarg) params->eps = atof(gk_optarg);
315 break;
316 case CMD_LAMDA:
317 if (gk_optarg) params->lamda = atof(gk_optarg);
318 break;
319
320 case CMD_HELP:
321 for (i=0; strlen(helpstr[i]) > 0; i++)
322 printf("%s\n", helpstr[i]);
323 exit(0);
324 break;
325 case '?':
326 default:
327 printf("Illegal command-line option(s)\nUse %s -help for a summary of the options.\n", argv[0]);
328 exit(0);
329 }
330 }
331
332 if (argc-gk_optind != 1) {
333 printf("Unrecognized parameters.");
334 for (i=0; strlen(shorthelpstr[i]) > 0; i++)
335 printf("%s\n", shorthelpstr[i]);
336 exit(0);
337 }
338
339 params->infile = gk_strdup(argv[gk_optind++]);
340
341 if (argc-gk_optind > 0)
342 params->outfile = gk_strdup(argv[gk_optind++]);
343 else
344 params->outfile = gk_strdup("gkgraph.out");
345
346 if (!gk_fexists(params->infile))
347 errexit("input file %s does not exist.\n", params->infile);
348
349 return params;
350 }
351
352