1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "config.h"
15
16#define STANDALONE
17#include "cgraph.h"
18/* #include "arith.h" */
19#include <stdio.h>
20#include <stdlib.h>
21#include <string.h>
22#include <math.h>
23#include <assert.h>
24#include "mmio.h"
25#include "agxbuf.h"
26#include "SparseMatrix.h"
27#include "matrix_market.h"
28#include <getopt.h>
29
30#define MALLOC malloc
31#define FREE free
32#define test_flag(a, flag) ((a)&(flag))
33#define real double
34#define BUFS 1024
35
36typedef struct {
37 Agrec_t h;
38 int id;
39} Agnodeinfo_t;
40
41#define ND_id(n) (((Agnodeinfo_t*)(n->base.data))->id)
42
43static char *cmd;
44
45static real Hue2RGB(real v1, real v2, real H)
46{
47 if (H < 0.0)
48 H += 1.0;
49 if (H > 1.0)
50 H -= 1.0;
51 if ((6.0 * H) < 1.0)
52 return (v1 + (v2 - v1) * 6.0 * H);
53 if ((2.0 * H) < 1.0)
54 return v2;
55 if ((3.0 * H) < 2.0)
56 return (v1 + (v2 - v1) * ((2.0 / 3.0) - H) * 6.0);
57 return v1;
58}
59
60char *hex[16] =
61 { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d",
62"e", "f" };
63
64static char *hue2rgb(real hue, char *color)
65{
66 real v1, v2, lightness = .5, saturation = 1;
67 int red, blue, green;
68
69 if (lightness < 0.5)
70 v2 = lightness * (1.0 + saturation);
71 else
72 v2 = (lightness + saturation) - (saturation * lightness);
73
74 v1 = 2.0 * lightness - v2;
75
76 red = (int) (255.0 * Hue2RGB(v1, v2, hue + (1.0 / 3.0)) + 0.5);
77 green = (int) (255.0 * Hue2RGB(v1, v2, hue) + 0.5);
78 blue = (int) (255.0 * Hue2RGB(v1, v2, hue - (1.0 / 3.0)) + 0.5);
79 color[0] = '#';
80 sprintf(color + 1, "%s", hex[red / 16]);
81 sprintf(color + 2, "%s", hex[red % 16]);
82 sprintf(color + 3, "%s", hex[green / 16]);
83 sprintf(color + 4, "%s", hex[green % 16]);
84 sprintf(color + 5, "%s", hex[blue / 16]);
85 sprintf(color + 6, "%s", hex[blue % 16]);
86 color[7] = '\0';
87 return color;
88}
89
90#if 0
91static void posStr(char *buf, int dim, real * x, double sc)
92{
93 if (dim == 3) {
94 sprintf(buf, "%f,%f,%f", sc * x[0], sc * x[1], sc * x[2]);
95 } else {
96 sprintf(buf, "%f,%f", sc * x[0], sc * x[1]);
97 }
98}
99
100static void attach_embedding(Agraph_t * g, int dim, double sc, real * x)
101{
102 Agsym_t *sym = agattr(g, AGNODE, "pos", 0);
103 Agnode_t *n;
104 char buf[BUFS];
105 int i = 0;
106
107 if (!sym)
108 sym = agattr(g, AGNODE, "pos", "");
109
110 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
111 assert(i == ND_id(n));
112 posStr(buf, dim, x + i * dim, sc);
113 agxset(n, sym, buf);
114 i++;
115 }
116
117}
118
119/* SparseMatrix_import_dot:
120 * Assumes g is connected and simple, i.e., we can have a->b and b->a
121 * but not a->b and a->b
122 */
123SparseMatrix
124SparseMatrix_import_dot(Agraph_t * g, int dim, real ** label_sizes,
125 real ** x, int format)
126{
127 SparseMatrix A = 0;
128 Agnode_t *n;
129 Agedge_t *e;
130 Agsym_t *sym;
131 int nnodes;
132 int nedges;
133 int i, row;
134 int *I;
135 int *J;
136 real *val;
137 real v;
138 int type = MATRIX_TYPE_REAL;
139 real padding = 10;
140
141 if (!g)
142 return NULL;
143 nnodes = agnnodes(g);
144 nedges = agnedges(g);
145 if (format != FORMAT_CSR) {
146 fprintf(stderr, "Format %d not supported\n", format);
147 exit(1);
148 }
149
150 /* Assign node ids */
151 i = 0;
152 for (n = agfstnode(g); n; n = agnxtnode(g, n))
153 ND_id(n) = i++;
154
155 I = N_NEW(nedges, int);
156 J = N_NEW(nedges, int);
157 val = N_NEW(nedges, real);
158
159 sym = agndattr(g->proto->e, "wt");
160 i = 0;
161 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
162 row = ND_id(n);
163 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
164 I[i] = row;
165 J[i] = ND_id(e->head);
166 if (sym) {
167 if (sscanf(agxget(e, sym->index), "%lf", &v) != 1)
168 v = 1;
169 } else
170 v = 1;
171 val[i] = v;
172 i++;
173 }
174 }
175
176 *label_sizes = N_NEW(2 * nnodes, real);
177 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
178 real sz;
179 i = ND_id(n);
180 if (agget(n, "width") && agget(n, "height")) {
181 sscanf(agget(n, "width"), "%lf", &sz);
182 /* (*label_sizes)[i*2] = POINTS(sz)*.6; */
183 (*label_sizes)[i * 2] = POINTS(sz) * .5 + padding * 0.5;
184 sscanf(agget(n, "height"), "%lf", &sz);
185 /*(*label_sizes)[i*2+1] = POINTS(sz)*.6; */
186 (*label_sizes)[i * 2 + 1] = POINTS(sz) * .5 + padding * 0.5;
187 } else {
188 (*label_sizes)[i * 2] = 4 * POINTS(0.75) * .5;
189 (*label_sizes)[i * 2 + 1] = 4 * POINTS(0.5) * .5;
190 }
191 }
192
193 if (x) {
194 *x = N_NEW(dim * nnodes, real);
195 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
196 real xx, yy;
197 i = ND_id(n);
198 if (agget(n, "pos")) {
199 sscanf(agget(n, "pos"), "%lf,%lf", &xx, &yy);
200 (*x)[i * dim] = xx;
201 (*x)[i * dim + 1] = yy;
202 } else {
203 (*x)[i * dim] = 0;
204 (*x)[i * dim + 1] = 0;
205 }
206 }
207 }
208
209 A = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J,
210 val, type);
211
212 FREE(I);
213 FREE(J);
214 FREE(val);
215
216 return A;
217}
218#endif
219
220static Agraph_t *makeDotGraph(SparseMatrix A, char *name, int dim,
221 real * x, int with_color, int with_label, int with_val)
222{
223 Agraph_t *g;
224 Agnode_t *n;
225 Agnode_t *h;
226 Agedge_t *e;
227 int i, j;
228 agxbuf xb;
229 char buf[BUFS];
230 unsigned char string[BUFS];
231 Agsym_t *sym, *sym2 = NULL, *sym3 = NULL;
232 int *ia = A->ia;
233 int *ja = A->ja;
234 real *val = (real *) (A->a);
235 Agnode_t **arr = N_NEW(A->m, Agnode_t *);
236 real *color = NULL;
237 char cstring[8];
238
239 name = strip_dir(name);
240
241 if (with_color) {
242 if ((A->type == MATRIX_TYPE_REAL) && !val) {
243 fprintf (stderr, "Warning: input matrix has no values, -c flag ignored\n");
244 with_color = 0;
245 }
246 else if ((A->type != MATRIX_TYPE_REAL) && !x) {
247 fprintf (stderr, "Warning: input has no coordinates, -c flag ignored\n");
248 with_color = 0;
249 }
250 }
251
252 if (SparseMatrix_known_undirected(A)) {
253 g = agopen("G", Agundirected, (Agdisc_t *) 0);
254 } else {
255 g = agopen("G", Agdirected, (Agdisc_t *) 0);
256 }
257
258 if (with_val) {
259 sym = agattr(g, AGEDGE, "len", "1");
260 }
261 agxbinit (&xb, BUFS, string);
262 if (with_label) {
263 agxbput (&xb, name);
264 agxbput (&xb, ". ");
265 sprintf(buf, "%d", A->m);
266 agxbput (&xb, buf);
267 agxbput (&xb, " nodes, ");
268 sprintf(buf, "%d", A->nz);
269 agxbput (&xb, buf);
270 agxbput (&xb, " edges.");
271 agattr(g, AGRAPH, "label", agxbuse (&xb));
272 }
273
274 for (i = 0; i < A->m; i++) {
275 sprintf(buf, "%d", i);
276 n = agnode(g, buf, 1);
277 agbindrec(n, "nodeinfo", sizeof(Agnodeinfo_t), TRUE);
278 ND_id(n) = i;
279 arr[i] = n;
280 }
281
282 if (with_color) {
283 real maxdist = 0.;
284 real mindist = 0.;
285 int first = TRUE;
286
287 sym2 = agattr(g, AGEDGE, "color", "");
288 sym3 = agattr(g, AGEDGE, "wt", "");
289 agattr(g, AGRAPH, "bgcolor", "black");
290 color = N_NEW(A->nz, real);
291 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
292 i = ND_id(n);
293 if (A->type != MATRIX_TYPE_REAL) {
294 for (j = ia[i]; j < ia[i + 1]; j++) {
295 color[j] = distance(x, dim, i, ja[j]);
296 if (i != ja[j]) {
297 if (first) {
298 mindist = color[j];
299 first = FALSE;
300 } else {
301 mindist = MIN(mindist, color[j]);
302 }
303 }
304 maxdist = MAX(color[j], maxdist);
305 }
306 } else {
307 for (j = ia[i]; j < ia[i + 1]; j++) {
308 if (val) color[j] = ABS(val[j]);
309 else color[j] = 1;
310 if (i != ja[j]) {
311 if (first) {
312 mindist = color[j];
313 first = FALSE;
314 } else {
315 mindist = MIN(mindist, color[j]);
316 }
317 }
318 maxdist = MAX(color[j], maxdist);
319 }
320 }
321 }
322 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
323 i = ND_id(n);
324 for (j = ia[i]; j < ia[i + 1]; j++) {
325 color[j] =
326 ((color[j] - mindist) / MAX(maxdist - mindist,
327 0.000001));
328 }
329 }
330 }
331
332 i = 0;
333 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
334 i = ND_id(n);
335 for (j = ia[i]; j < ia[i + 1]; j++) {
336 h = arr[ja[j]];
337 e = agedge(g, n, h, NULL, 1);
338 if (with_val && val) {
339 sprintf(buf, "%f", val[j]);
340 agxset(e, sym, buf);
341 }
342 if (with_color) {
343 agxset (e, sym2, hue2rgb(.65 * color[j], cstring));
344 sprintf(buf, "%f", color[j]);
345 agxset(e, sym3, buf);
346 }
347 }
348 }
349
350 agxbfree (&xb);
351 FREE(color);
352 FREE(arr);
353 return g;
354}
355
356static char* useString = "Usage: %s [-uvcl] [-o file] matrix_market_filename\n\
357 -u - make graph undirected\n\
358 -U i - treat non-square matrix as a bipartite graph\n\
359 i = 0 never\n\
360 i = 1 if pattern unsymmetric (default)\n\
361 i = 2 if matrix unsymmetric\n\
362 i = 3 always\n\
363 -v - assign len to edges\n\
364 -c - assign color and wt to edges\n\
365 -l - add label\n\
366 -o <file> - output file \n";
367
368static void usage(int eval)
369{
370 fprintf(stderr, useString, cmd);
371 exit(eval);
372}
373
374static FILE *openF(char *fname, char *mode)
375{
376 FILE *f = fopen(fname, mode);
377 if (!f) {
378 fprintf(stderr, "Could not open %s for %s\n", fname,
379 ((*mode == 'r') ? "reading" : "writing"));
380 exit(1);
381 }
382 return f;
383}
384
385typedef struct {
386 FILE *inf;
387 FILE *outf;
388 char *infile;
389 int undirected;
390 int with_label;
391 int with_color;
392 int with_val;
393 int bipartite;
394} parms_t;
395
396static void init(int argc, char **argv, parms_t * p)
397{
398 int c;
399
400 cmd = argv[0];
401 opterr = 0;
402 while ((c = getopt(argc, argv, ":o:uvclU:")) != -1) {
403 switch (c) {
404 case 'o':
405 p->outf = openF(optarg, "w");
406 break;
407 case 'l':
408 p->with_label = 1;
409 break;
410 case 'u':
411 p->undirected = 1;
412 break;
413 case 'v':
414 p->with_val = 1;
415 break;
416 case 'c':
417 p->with_color = 1;
418 break;
419 case 'U':{
420 int u;
421 if (sscanf(optarg,"%d",&u) <= 0 || u < 0 || u > BIPARTITE_ALWAYS) {
422 usage(1);
423 } else {
424 p->bipartite = u;
425 }
426 break;
427 }
428 case ':':
429 fprintf(stderr, "%s: option -%c missing argument - ignored\n", cmd, optopt);
430 break;
431 case '?':
432 if (optopt == '?')
433 usage(0);
434 else
435 fprintf(stderr,
436 "%s: option -%c unrecognized - ignored\n", cmd,
437 optopt);
438 break;
439 }
440 }
441 argv += optind;
442 argc -= optind;
443
444 if (argc > 0) {
445 p->infile = argv[0];
446 p->inf = openF(argv[0], "r");
447 }
448}
449
450int main(int argc, char *argv[])
451{
452 Agraph_t *g = 0;
453 SparseMatrix A = NULL;
454 int dim=0;
455 parms_t pv;
456
457 /* ======================= set parameters ==================== */
458 pv.inf = stdin;
459 pv.outf = stdout;
460 pv.infile = "stdin";
461 pv.undirected = 0;
462 pv.with_label = 0;
463 pv.with_color = 0;
464 pv.with_val = 0;
465 pv.bipartite = BIPARTITE_PATTERN_UNSYM;
466 init(argc, argv, &pv);
467
468 /* ======================= read graph ==================== */
469
470 A = SparseMatrix_import_matrix_market(pv.inf, FORMAT_CSR);
471 if (!A) {
472 fprintf (stderr, "Unable to read input file \"%s\"\n", pv.infile);
473 usage(1);
474 }
475
476 A = SparseMatrix_to_square_matrix(A, pv.bipartite);
477
478 if (!A) {
479 fprintf(stderr, "cannot import from file %s\n", pv.infile);
480 exit(1);
481 }
482
483 if (pv.undirected) {
484 SparseMatrix B;
485 B = SparseMatrix_make_undirected(A);
486 SparseMatrix_delete(A);
487 A = B;
488 }
489 g = makeDotGraph(A, pv.infile, dim, NULL, pv.with_color, pv.with_label, pv.with_val);
490
491 agwrite(g, pv.outf);
492
493 return 0;
494}
495
496