gkgraph.c
Go to the documentation of this file.
1 
10 #include <GKlib.h>
11 
12 /*************************************************************************/
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 /*************************************************************************/
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 /*************************************************************************/
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 /*************************************************************************/
86 /*************************************************************************/
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 /*************************************************************************/
96 /**************************************************************************/
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 /*************************************************************************/
162 /*************************************************************************/
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 /*************************************************************************/
200 /*************************************************************************/
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 /*************************************************************************/
253 /*************************************************************************/
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 /*************************************************************************/
274 /*************************************************************************/
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 /*************************************************************************/
287 /*************************************************************************/
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 
The structure that stores the information about the command-line options.
Definition: gk_getopt.h:28
gk_graph_t * gk_graph_Read(char *filename, int format, int isfewgts, int isfvwgts, int isfvsizes)
Definition: GKlib/graph.c:85
Definition: fis.c:15
void gk_fkvsorti(size_t, gk_fkv_t *)
Definition: sort.c:245
void print_init_info(params_t *params, gk_graph_t *graph)
Definition: gkgraph.c:254
void errexit(char *f_str,...)
Definition: error.c:54
int32_t * adjncy
Definition: gk_struct.h:92
float eps
Definition: gkgraph.c:18
double compute_compactness(params_t *params, gk_graph_t *graph, int32_t *perm)
Definition: gkgraph.c:163
int gk_optind
Index in ARGV of the next element to be scanned.
Definition: getopt.c:68
gk_graph_t * gk_graph_Reorder(gk_graph_t *graph, int32_t *perm, int32_t *iperm)
Definition: GKlib/graph.c:460
ssize_t * xadj
Definition: gk_struct.h:91
int main(int argc, char *argv[])
Definition: gkgraph.c:97
void gk_graph_Write(gk_graph_t *graph, char *filename, int format)
Definition: GKlib/graph.c:277
size_t gk_GetMaxMemoryUsed()
Definition: memory.c:246
idx_t idx_t * xadj
int gk_fexists(char *fname)
Definition: fs.c:21
void gk_graph_Free(gk_graph_t **graph)
Definition: GKlib/graph.c:48
static char shorthelpstr[][100]
Definition: gkgraph.c:75
Scalar Scalar * c
Definition: benchVecAdd.cpp:17
Real fabs(const Real &a)
void print_final_info(params_t *params)
Definition: gkgraph.c:275
NonlinearFactorGraph graph
static const SmartProjectionParams params
params_t * parse_cmdline(int argc, char *argv[])
Definition: gkgraph.c:288
float lamda
Definition: gkgraph.c:19
size_t gk_GetCurMemoryUsed()
Definition: memory.c:233
#define GK_GRAPH_FMT_METIS
Definition: gk_defs.h:67
static struct gk_option long_options[]
Definition: gkgraph.c:38
Array< int, Dynamic, 1 > v
signed int int32_t
Definition: ms_stdint.h:82
void gk_graph_ComputeBFSOrdering(gk_graph_t *graph, int v, int32_t **r_perm, int32_t **r_iperm)
Definition: GKlib/graph.c:665
int type
Definition: gkgraph.c:16
idx_t idx_t idx_t idx_t idx_t * perm
int niter
Definition: gkgraph.c:17
Array< double, 1, 3 > e(1./3., 0.5, 2.)
static char helpstr[][100]
Definition: gkgraph.c:51
char * outfile
Definition: gkgraph.c:22
#define NULL
Definition: ccolamd.c:609
#define CMD_NITER
Definition: gkgraph.c:28
char * gk_strdup(char *orgstr)
Duplicates a string.
Definition: string.c:372
char * gk_optarg
For communication arguments to the caller.
Definition: getopt.c:56
#define gk_abs(x)
Definition: gk_macros.h:26
void reorder_centroid(params_t *params, gk_graph_t *graph, int32_t *perm)
Definition: gkgraph.c:201
#define CMD_HELP
Definition: gkgraph.c:32
#define CMD_LAMDA
Definition: gkgraph.c:30
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
void gk_free(void **ptr1,...)
Definition: memory.c:202
idx_t idx_t idx_t * adjncy
#define RandomInRange(u)
Definition: gk_macros.h:24
int val
Definition: gk_getopt.h:35
char * infile
Definition: gkgraph.c:21
#define CMD_EPS
Definition: gkgraph.c:29
int gk_getopt_long_only(int argc, char **argv, char *options, struct gk_option *long_options, int *opt_index)
Parse command-line arguments with only long options.
Definition: getopt.c:850
int32_t nvtxs
Definition: gk_struct.h:90
std::ptrdiff_t j
void gk_graph_ComputeBestFOrdering(gk_graph_t *graph, int v, int type, int32_t **r_perm, int32_t **r_iperm)
Definition: GKlib/graph.c:887
#define LTERM
Definition: gk_defs.h:14
#define CMD_TYPE
Definition: gkgraph.c:31


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:18