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#define STANDALONE
15#include "general.h"
16#include "DotIO.h"
17#include "clustering.h"
18#include "mq.h"
19/* #include "spring_electrical.h" */
20#include "color_palette.h"
21#include "colorutil.h"
22
23typedef struct {
24 Agrec_t h;
25 unsigned int id;
26} Agnodeinfo_t;
27
28#define ND_id(n) (((Agnodeinfo_t*)((n)->base.data))->id)
29
30#if 0
31static void
32posStr (int len_buf, char* buf, int dim, real* x, double sc)
33{
34 char s[1000];
35 int i;
36 int len = 0;
37
38 buf[0] = '\0';
39 for (i = 0; i < dim; i++){
40 if (i < dim - 1){
41 sprintf(s,"%f,",sc*x[i]);
42 } else {
43 sprintf(s,"%f",sc*x[i]);
44 }
45 len += strlen(s);
46 assert(len < len_buf);
47 buf = strcat(buf, s);
48 }
49}
50
51static void
52attach_embedding (Agraph_t* g, int dim, double sc, real *x)
53{
54 Agsym_t* sym = agattr(g, AGNODE, "pos", NULL);
55 Agnode_t* n;
56#define SLEN 1024
57 char buf[SLEN];
58 int i = 0;
59
60 if (!sym)
61 sym = agattr (g, AGNODE, "pos", "");
62
63 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
64 assert (i == ND_id(n));
65 posStr (SLEN, buf, dim, x + i*dim, sc);
66 agxset (n, sym, buf);
67 i++;
68 }
69
70}
71#endif
72
73static void color_string(int slen, char *buf, int dim, real *color){
74 if (dim > 3 || dim < 1){
75 fprintf(stderr,"can only 1, 2 or 3 dimensional color space. with color value between 0 to 1\n");
76 assert(0);
77 }
78 assert(slen >= 3);
79 if (dim == 3){
80 sprintf(buf,"#%02x%02x%02x", MIN((unsigned int)(color[0]*255),255),
81 MIN((unsigned int) (color[1]*255), 255), MIN((unsigned int)(color[2]*255), 255));
82 } else if (dim == 1){
83 sprintf(buf,"#%02x%02x%02x", MIN((unsigned int)(color[0]*255),255),
84 MIN((unsigned int) (color[0]*255), 255), MIN((unsigned int)(color[0]*255), 255));
85 } else if (dim == 2){
86 sprintf(buf,"#%02x%02x%02x", MIN((unsigned int)(color[0]*255),255),
87 0, MIN((unsigned int)(color[1]*255), 255));
88 }
89}
90
91void attach_edge_colors(Agraph_t* g, int dim, real *colors){
92 /* colors is array of dim*nedges, with color for edge i at colors[dim*i, dim(i+1))
93 */
94 Agsym_t* sym = agattr(g, AGEDGE, "color", 0);
95 Agedge_t* e;
96 Agnode_t* n;
97 enum {slen = 1024};
98 char buf[slen];
99 int row, col;
100 int ie = 0;
101
102 if (!sym)
103 sym = agattr (g, AGEDGE, "color", "");
104
105 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
106 row = ND_id(n);
107 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
108 col = ND_id(aghead(e));
109 if (row == col) continue;
110 color_string(slen, buf, dim, colors + ie*dim);
111 agxset(e, sym, buf);
112 ie++;
113 }
114 }
115
116}
117
118/* SparseMatrix_read_dot:
119 * Wrapper for reading dot graph from file
120 */
121Agraph_t*
122SparseMatrix_read_dot(FILE* f)
123{
124 Agraph_t* g;
125 g = agread (f, 0);
126 aginit(g, AGNODE, "nodeinfo", sizeof(Agnodeinfo_t), TRUE);
127 return g;
128}
129
130/* SparseMatrix_import_dot:
131 * Assumes g is connected and simple, i.e., we can have a->b and b->a
132 * but not a->b and a->b
133 */
134SparseMatrix
135SparseMatrix_import_dot (Agraph_t* g, int dim, real **label_sizes, real **x, int *n_edge_label_nodes, int **edge_label_nodes, int format, SparseMatrix *D)
136{
137 SparseMatrix A = 0;
138 Agnode_t* n;
139 Agedge_t* e;
140 Agsym_t *sym, *symD = NULL;
141 Agsym_t *psym;
142 int nnodes;
143 int nedges;
144 int i, row;
145 int* I;
146 int* J;
147 real *val, *valD = NULL;
148 real v;
149 int type = MATRIX_TYPE_REAL;
150 size_t sz = sizeof(real);
151 real padding = 10;
152 int nedge_nodes = 0;
153
154
155
156 if (!g) return NULL;
157 nnodes = agnnodes (g);
158 nedges = agnedges (g);
159 if (format != FORMAT_CSR && format != FORMAT_COORD) {
160 fprintf (stderr, "Format %d not supported\n", format);
161 exit (1);
162 }
163
164 /* Assign node ids */
165 i = 0;
166 for (n = agfstnode (g); n; n = agnxtnode (g, n))
167 ND_id(n) = i++;
168
169 if (format == FORMAT_COORD){
170 A = SparseMatrix_new(i, i, nedges, MATRIX_TYPE_REAL, format);
171 A->nz = nedges;
172 I = A->ia;
173 J = A->ja;
174 val = (real*) A->a;
175 } else {
176 I = N_NEW(nedges, int);
177 J = N_NEW(nedges, int);
178 val = N_NEW(nedges, real);
179 }
180
181 sym = agattr(g, AGEDGE, "weight", NULL);
182 if (D) {
183 symD = agattr(g, AGEDGE, "len", NULL);
184 valD = N_NEW(nedges, real);
185 }
186 i = 0;
187 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
188 if (edge_label_nodes && strncmp(agnameof(n), "|edgelabel|",11)==0) nedge_nodes++;
189 row = ND_id(n);
190 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
191 I[i] = row;
192 J[i] = ND_id(aghead(e));
193
194 /* edge weight */
195 if (sym) {
196 if (sscanf (agxget(e,sym), "%lf", &v) != 1) v = 1;
197 } else {
198 v = 1;
199 }
200 val[i] = v;
201
202 /* edge length */
203 if (symD) {
204 if (sscanf (agxget (e, symD), "%lf", &v) != 1) {
205 v = 72;
206 } else {
207 v *= 72;/* len is specified in inch. Convert to points */
208 }
209 valD[i] = v;
210 } else if (valD) {
211 valD[i] = 72;
212 }
213
214 i++;
215 }
216 }
217
218 if (edge_label_nodes) {
219 *edge_label_nodes = MALLOC(sizeof(int)*nedge_nodes);
220 nedge_nodes = 0;
221 }
222
223
224 if (label_sizes) *label_sizes = MALLOC(sizeof(real)*2*nnodes);
225 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
226 real sz;
227 i = ND_id(n);
228 if (edge_label_nodes && strncmp(agnameof(n), "|edgelabel|",11)==0) {
229 (*edge_label_nodes)[nedge_nodes++] = i;
230 }
231 if (label_sizes){
232 if (agget(n, "width") && agget(n, "height")){
233 sscanf(agget(n, "width"), "%lf", &sz);
234 /* (*label_sizes)[i*2] = POINTS(sz)*.6;*/
235 (*label_sizes)[i*2] = POINTS(sz)*.5 + padding*0.5;
236 sscanf(agget(n, "height"), "%lf", &sz);
237 /*(*label_sizes)[i*2+1] = POINTS(sz)*.6;*/
238 (*label_sizes)[i*2+1] = POINTS(sz)*.5 + padding*0.5;
239 } else {
240 (*label_sizes)[i*2] = 4*POINTS(0.75)*.5;
241 (*label_sizes)[i*2+1] = 4*POINTS(0.5)*.5;
242 }
243 }
244 }
245
246 if (x && (psym = agattr(g, AGNODE, "pos", NULL))) {
247 int has_positions = TRUE;
248 char* pval;
249 if (!(*x)) {
250 *x = MALLOC(sizeof(real)*dim*nnodes);
251 assert(*x);
252 }
253 for (n = agfstnode (g); n && has_positions; n = agnxtnode (g, n)) {
254 real xx,yy, zz,ww;
255 int nitems;
256 i = ND_id(n);
257 if ((pval = agxget(n, psym)) && *pval) {
258 if (dim == 2){
259 nitems = sscanf(pval, "%lf,%lf", &xx, &yy);
260 if (nitems != 2) {
261 has_positions = FALSE;
262 agerr(AGERR, "Node \"%s\" pos has %d < 2 values", agnameof(n), nitems);
263 }
264 (*x)[i*dim] = xx;
265 (*x)[i*dim+1] = yy;
266 } else if (dim == 3){
267 nitems = sscanf(pval, "%lf,%lf,%lf", &xx, &yy, &zz);
268 if (nitems != 3) {
269 has_positions = FALSE;
270 agerr(AGERR, "Node \"%s\" pos has %d < 3 values", agnameof(n), nitems);
271 }
272 (*x)[i*dim] = xx;
273 (*x)[i*dim+1] = yy;
274 (*x)[i*dim+2] = zz;
275 } else if (dim == 4){
276 nitems = sscanf(pval, "%lf,%lf,%lf,%lf", &xx, &yy, &zz,&ww);
277 if (nitems != 4) {
278 has_positions = FALSE;
279 agerr(AGERR, "Node \"%s\" pos has %d < 4 values", agnameof(n), nitems);
280 }
281 (*x)[i*dim] = xx;
282 (*x)[i*dim+1] = yy;
283 (*x)[i*dim+2] = zz;
284 (*x)[i*dim+3] = ww;
285 } else if (dim == 1){
286 nitems = sscanf(pval, "%lf", &xx);
287 if (nitems != 1){
288 A = NULL;
289 goto done;
290 }
291 (*x)[i*dim] = xx;
292 } else {
293 assert(0);
294 }
295 } else {
296 has_positions = FALSE;
297 agerr(AGERR, "Node \"%s\" lacks position info", agnameof(n));
298 }
299 }
300 if (!has_positions) {
301 FREE(*x);
302 *x = NULL;
303 }
304 }
305 else if (x)
306 agerr (AGERR, "Error: graph %s has missing \"pos\" information", agnameof(g));
307
308 if (format == FORMAT_CSR) A = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J, val, type, sz);
309 if (edge_label_nodes) *n_edge_label_nodes = nedge_nodes;
310
311 if (D) *D = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J, valD, type, sz);
312
313done:
314 if (format != FORMAT_COORD){
315 FREE(I);
316 FREE(J);
317 FREE(val);
318 }
319 if (valD) FREE(valD);
320
321 return A;
322}
323
324
325static real dist(int dim, real *x, real *y){
326 int k;
327 real d = 0;
328 for (k = 0; k < dim; k++) d += (x[k] - y[k])*(x[k]-y[k]);
329 return sqrt(d);
330}
331
332/* get spline info */
333int Import_dot_splines(Agraph_t* g, int *ne, char ***xsplines){
334 /* get the list of splines for the edges in the order they appear, and store as a list of strings in xspline.
335 If *xsplines = NULL, it will be allocated. On exit (*xsplines)[i] is the control point string for the i-th edge. This string
336 is of the form "x1,y1 x2,y2...", the two end points of the edge is not included per Dot format
337 Return 1 if success. 0 if not.
338 */
339 Agnode_t* n;
340 Agedge_t* e;
341 Agsym_t *sym;
342 int nedges;
343 int i;
344
345 if (!g){
346 return 0;
347 }
348
349 *ne = nedges = agnedges (g);
350
351 /* Assign node ids */
352 i = 0;
353 for (n = agfstnode (g); n; n = agnxtnode (g, n))
354 ND_id(n) = i++;
355
356 sym = agattr(g, AGEDGE, "pos", 0);
357 if (!sym) return 0;
358
359 if (!(*xsplines)) *xsplines = malloc(sizeof(char*)*nedges);
360
361 i = 0;
362 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
363 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
364 /* edge weight */
365 if (sym) {
366 char *pos = agxget (e, sym);
367 (*xsplines)[i] = malloc(sizeof(char)*(strlen(pos)+1));
368 strcpy((*xsplines)[i], pos);
369 } else {
370 (*xsplines)[i] = NULL;
371 }
372 i++;
373 }
374 }
375 return 1;
376}
377
378void edgelist_export(FILE* f, SparseMatrix A, int dim, real *x){
379 int n = A->m, *ia = A->ia, *ja = A->ja;
380 int i, j, len;
381 real max_edge_len, min_edge_len;
382
383 for (i = 0; i < n; i++){
384 for (j = ia[i]; j < ia[i+1]; j++){
385 max_edge_len = MAX(max_edge_len, dist(dim, &x[dim*i], &x[dim*ja[j]]));
386 if (min_edge_len < 0){
387 min_edge_len = dist(dim, &x[dim*i], &x[dim*ja[j]]);
388 } else {
389 min_edge_len = MIN(min_edge_len, dist(dim, &x[dim*i], &x[dim*ja[j]]));
390 }
391 }
392 }
393 /* format:
394 n
395 nz
396 dim
397 x (length n*dim)
398 min_edge_length
399 max_edge_length
400 v1
401 neighbors of v1
402 v2
403 neighbors of v2
404 ...
405 */
406 fprintf(stderr,"writing a total of %d edges\n",A->nz);
407 fwrite(&(A->n), sizeof(int), 1, f);
408 fwrite(&(A->nz), sizeof(int), 1, f);
409 fwrite(&dim, sizeof(int), 1, f);
410 fwrite(x, sizeof(real), dim*n, f);
411 fwrite(&min_edge_len, sizeof(real), 1, f);
412 fwrite(&max_edge_len, sizeof(real), 1, f);
413 for (i = 0; i < n; i++){
414 if (i%1000 == 0) fprintf(stderr,"%6.2f%% done\r", i/(real) n*100);
415 fwrite(&i, sizeof(int), 1, f);
416 len = ia[i+1] - ia[i];
417 fwrite(&len, sizeof(int), 1, f);
418 fwrite(&(ja[ia[i]]), sizeof(int), len, f);
419 }
420}
421
422
423void dump_coordinates(char *name, int n, int dim, real *x){
424 char fn[1000];
425 FILE *fp;
426 int i, k;
427
428 if (!name){
429 name = "";
430 } else {
431 name = strip_dir(name);
432 }
433
434 strcpy(fn, name);
435 strcat(fn,".x");
436 fp = fopen(fn,"w");
437 fprintf(fp, "%d %d\n",n, dim);
438 for (i = 0; i < n; i++){
439 for (k = 0; k < dim; k++){
440 fprintf(fp,"%f ",x[i*dim+k]);
441 }
442 fprintf(fp,"\n");
443 }
444 fclose(fp);
445
446}
447
448static Agnode_t*
449mkNode (Agraph_t* g, char* name)
450{
451 Agnode_t* n = agnode(g, name, 1);
452 agbindrec(n, "info", sizeof(Agnodeinfo_t), TRUE);
453 return n;
454}
455
456Agraph_t*
457makeDotGraph (SparseMatrix A, char *name, int dim, real *x, int with_color, int with_label, int use_matrix_value)
458{
459 Agraph_t* g;
460 Agnode_t* n;
461 Agnode_t* h;
462 Agedge_t* e;
463 int i, j;
464 char buf[1024], buf2[1024];
465 Agsym_t *sym, *sym2 = NULL, *sym3 = NULL;
466 int* ia=A->ia;
467 int* ja=A->ja;
468 real* val = (real*)(A->a);
469 Agnode_t** arr = N_NEW (A->m, Agnode_t*);
470 real *color = NULL;
471 char cstring[8];
472 char *label_string;
473
474 if (!name){
475 name = "stdin";
476 } else {
477 name = strip_dir(name);
478 }
479 label_string = MALLOC(sizeof(char)*1000);
480
481 if (SparseMatrix_known_undirected(A)){
482 g = agopen ("G", Agundirected, 0);
483 } else {
484 g = agopen ("G", Agdirected, 0);
485 }
486 sprintf (buf, "%f", 1.0);
487
488 label_string = strcpy(label_string, name);
489 label_string = strcat(label_string, ". ");
490 sprintf (buf, "%d", A->m);
491 label_string = strcat(label_string, buf);
492 label_string = strcat(label_string, " nodes, ");
493 sprintf (buf, "%d", A->nz);
494 label_string = strcat(label_string, buf);
495 /* label_string = strcat(label_string, " edges. Created by Yifan Hu");*/
496 label_string = strcat(label_string, " edges.");
497
498
499 if (with_label) sym = agattr(g, AGRAPH, "label", label_string);
500 sym = agattr(g, AGRAPH, "fontcolor", "#808090");
501 if (with_color) sym = agattr(g, AGRAPH, "bgcolor", "black");
502 sym = agattr(g, AGRAPH, "outputorder", "edgesfirst");
503
504 if (A->m > 100) {
505 /* -Estyle=setlinewidth(0.0)' -Eheadclip=false -Etailclip=false -Nstyle=invis*/
506 agattr(g, AGNODE, "style", "invis");
507 } else {
508 /* width=0, height = 0, label="", style=filled*/
509 agattr(g, AGNODE, "shape", "point");
510 if (A->m < 50){
511 agattr(g, AGNODE, "width", "0.03");
512 } else {
513 agattr(g, AGNODE, "width", "0");
514 }
515 agattr(g, AGNODE, "label", "");
516 agattr(g, AGNODE, "style", "filled");
517 if (with_color) {
518 agattr(g, AGNODE, "color", "#FF0000");
519 } else {
520 agattr(g, AGNODE, "color", "#000000");
521 }
522 }
523
524 agattr(g, AGEDGE, "headclip", "false");
525 agattr(g, AGEDGE, "tailclip", "false");
526 if (A->m < 50){
527 agattr(g, AGEDGE, "style", "setlinewidth(2)");
528 } else if (A->m < 500){
529 agattr(g, AGEDGE, "style", "setlinewidth(0.5)");
530 } else if (A->m < 5000){
531 agattr(g, AGEDGE, "style", "setlinewidth(0.1)");
532 } else {
533 agattr(g, AGEDGE, "style", "setlinewidth(0.0)");
534 }
535
536 if (with_color) {
537 sym2 = agattr(g, AGEDGE, "color", "");
538 sym3 = agattr(g, AGEDGE, "wt", "");
539 }
540 for (i = 0; i < A->m; i++) {
541 sprintf (buf, "%d", i);
542 n = mkNode (g, buf);
543 ND_id(n) = i;
544 arr[i] = n;
545 }
546
547 if (with_color){
548 real maxdist = 0.;
549 real mindist = 0.;
550 int first = TRUE;
551 color = malloc(sizeof(real)*A->nz);
552 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
553 i = ND_id(n);
554 if (A->type != MATRIX_TYPE_REAL || !use_matrix_value){
555 for (j = ia[i]; j < ia[i+1]; j++) {
556 color[j] = distance(x, dim, i, ja[j]);
557 if (i != ja[j]){
558 if (first){
559 mindist = color[j];
560 first = FALSE;
561 } else {
562 mindist = MIN(mindist, color[j]);
563 }
564 }
565 maxdist = MAX(color[j], maxdist);
566 }
567 } else {
568 for (j = ia[i]; j < ia[i+1]; j++) {
569 color[j] = ABS(val[j]);
570 if (i != ja[j]){
571 if (first){
572 mindist = color[j];
573 first = FALSE;
574 } else {
575 mindist = MIN(mindist, color[j]);
576 }
577 }
578 maxdist = MAX(color[j], maxdist);
579 }
580 }
581 }
582 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
583 i = ND_id(n);
584 for (j = ia[i]; j < ia[i+1]; j++) {
585 if (i != ja[j]){
586 color[j] = ((color[j] - mindist)/MAX(maxdist-mindist, 0.000001));
587 } else {
588 color[j] = 0;
589 }
590 }
591 }
592 }
593
594 i = 0;
595 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
596 i = ND_id(n);
597 for (j = ia[i]; j < ia[i+1]; j++) {
598 h = arr [ja[j]];
599 if (val){
600 switch (A->type){
601 case MATRIX_TYPE_REAL:
602 sprintf (buf, "%f", ((real*)A->a)[j]);
603 break;
604 case MATRIX_TYPE_INTEGER:
605 sprintf (buf, "%d", ((int*)A->a)[j]);
606 break;
607 case MATRIX_TYPE_COMPLEX:/* take real part as weight */
608 sprintf (buf, "%f", ((real*)A->a)[2*j]);
609 break;
610 }
611 if (with_color) {
612 if (i != ja[j]){
613 sprintf (buf2, "%s", hue2rgb(.65*color[j], cstring));
614 } else {
615 sprintf (buf2, "#000000");
616 }
617 }
618 } else {
619 sprintf (buf, "%f", 1.);
620 if (with_color) {
621 if (i != ja[j]){
622 sprintf (buf2, "%s", hue2rgb(.65*color[j], cstring));
623 } else {
624 sprintf (buf2, "#000000");
625 }
626 }
627 }
628 e = agedge (g, n, h, NULL, 1);
629 if (with_color) {
630 agxset (e, sym2, buf2);
631 sprintf (buf2, "%f", color[j]);
632 agxset (e, sym3, buf2);
633 }
634 }
635 }
636
637 FREE(color);
638 FREE (arr);
639 FREE(label_string);
640 return g;
641}
642
643
644char *cat_string(char *s1, char *s2){
645 char *s;
646 s = malloc(sizeof(char)*(strlen(s1)+strlen(s2)+1+1));
647 strcpy(s,s1);
648 strcat(s,"|");
649 strcat(s,s2);
650 return s;
651}
652
653char *cat_string3(char *s1, char *s2, char *s3, int id){
654 char *s;
655 char sid[1000];
656 sprintf(sid,"%d",id);
657 s = malloc(sizeof(char)*(strlen(s1)+strlen(s2)+strlen(s3)+strlen(sid)+1+3));
658 strcpy(s,s1);
659 strcat(s,"|");
660 strcat(s,s2);
661 strcat(s,"|");
662 strcat(s,s3);
663 strcat(s,"|");
664 strcat(s,sid);
665 return s;
666}
667
668
669Agraph_t *convert_edge_labels_to_nodes(Agraph_t* g){
670 if (!g) return NULL;
671
672 Agnode_t *n, *newnode;
673 Agraph_t *dg;
674
675 int nnodes;
676 int nedges;
677
678
679 Agedge_t *ep, *e;
680 int i = 0;
681 Agnode_t **ndmap = NULL;
682 char *s;
683 char *elabel;
684 int id = 0;
685
686 Agsym_t* sym = agattr(g, AGEDGE, "label", NULL);
687
688 dg = agopen("test", g->desc, 0);
689
690 nnodes = agnnodes (g);
691 nedges = agnedges (g);
692
693 ndmap = malloc(sizeof(Agnode_t *)*nnodes);
694
695 agattr(dg, AGNODE, "label", "\\N");
696 agattr(dg, AGNODE, "shape", "ellipse");
697 agattr(dg, AGNODE, "width","0.00001");
698 agattr(dg, AGNODE, "height", "0.00001");
699 agattr(dg, AGNODE, "margin","0.");
700 agattr(dg, AGEDGE, "arrowsize", "0.5");
701
702 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
703 newnode = mkNode(dg, agnameof(n));
704 agset(newnode,"shape","box");
705 ndmap[i] = newnode;
706 ND_id(n) = i++;
707 }
708
709
710 /*
711 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
712 for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
713 if (agtail(ep) == n) continue;
714 agedge(dg, ndmap[ND_id(agtail(ep))], ndmap[ND_id(aghead(ep))]);
715 }
716 }
717 */
718
719
720
721 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
722 for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
723 if (agtail(ep) == n && (aghead(ep) != n)) continue;
724 if (sym && (elabel = agxget(ep,sym)) && strcmp(elabel,"") != 0) {
725 s = cat_string3("|edgelabel",agnameof(agtail(ep)), agnameof(aghead(ep)), id++);
726 newnode = mkNode(dg,s);
727 agset(newnode,"label",elabel);
728 agset(newnode,"shape","plaintext");
729 e = agedge(dg, ndmap[ND_id(agtail(ep))], newnode, NULL, 1);
730 agset(e, "arrowsize","0");
731 agedge(dg, newnode, ndmap[ND_id(aghead(ep))], NULL, 1);
732 free(s);
733 } else {
734 agedge(dg, ndmap[ND_id(agtail(ep))], ndmap[ND_id(aghead(ep))], NULL, 1);
735 }
736 }
737 }
738
739 free(ndmap);
740 return dg;
741 }
742
743Agraph_t* assign_random_edge_color(Agraph_t* g){
744 char cstring[8];
745 char buf2[1024];
746 Agsym_t *sym2;
747 Agnode_t* n;
748 Agedge_t *ep;
749
750 sym2 = agattr(g, AGEDGE, "color", "");
751 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
752 for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
753 sprintf (buf2, "%s", hue2rgb(0.65*drand(), cstring));
754 agxset (ep, sym2, buf2);
755 }
756 }
757
758 return g;
759 }
760
761
762static int hex2int(char h){
763 if (h >= '0' && h <= '9') return h - '0';
764 if (h >= 'a' && h <= 'f') return 10 + h - 'a';
765 if (h >= 'A' && h <= 'F') return 10 + h - 'A';
766 return 0;
767}
768static float hexcol2rgb(char *h){
769 return (hex2int(h[0])*16 + hex2int(h[1]))/255.;
770}
771
772void Dot_SetClusterColor(Agraph_t* g, float *rgb_r, float *rgb_g, float *rgb_b, int *clusters){
773
774 Agnode_t* n;
775 char scluster[20];
776 int i;
777 Agsym_t* clust_clr_sym = agattr(g, AGNODE, "clustercolor", NULL);
778
779 if (!clust_clr_sym) clust_clr_sym = agattr(g, AGNODE, "clustercolor", "-1");
780 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
781 i = ND_id(n);
782 if (rgb_r && rgb_g && rgb_b) {
783 rgb2hex((rgb_r)[(clusters)[i]],(rgb_g)[(clusters)[i]],(rgb_b)[(clusters)[i]], scluster, NULL);
784 //sprintf(scluster,"#%2x%2x%2x", (int) (255*((rgb_r)[(clusters)[i]])), (int) (255*((rgb_g)[(clusters)[i]])), (int) (255*((rgb_b)[(clusters)[i]])));
785 }
786 agxset(n,clust_clr_sym,scluster);
787 }
788}
789
790SparseMatrix Import_coord_clusters_from_dot(Agraph_t* g, int maxcluster, int dim, int *nn, real **label_sizes, real **x, int **clusters, float **rgb_r, float **rgb_g, float **rgb_b, float **fsz, char ***labels, int default_color_scheme, int clustering_scheme, int useClusters){
791 SparseMatrix A = 0;
792 Agnode_t* n;
793 Agedge_t* e;
794 Agsym_t* sym;
795 Agsym_t* clust_sym;
796 Agsym_t* clust_clr_sym;
797 int nnodes;
798 int nedges;
799 int i, row, ic,nc, j;
800 int* I;
801 int* J;
802 real* val;
803 real v;
804 int type = MATRIX_TYPE_REAL;
805 size_t sz = sizeof(real);
806 char scluster[100];
807 float ff;
808
809 int MAX_GRPS, MIN_GRPS, noclusterinfo = FALSE, first = TRUE;
810 float *pal;
811 int max_color = MAX_COLOR;
812
813 switch (default_color_scheme){
814 case COLOR_SCHEME_BLUE_YELLOW:
815 pal = &(palette_blue_to_yellow[0][0]);
816 break;
817 case COLOR_SCHEME_WHITE_RED:
818 pal = &(palette_white_to_red[0][0]);
819 break;
820 case COLOR_SCHEME_GREY_RED:
821 pal = &(palette_grey_to_red[0][0]);
822 break;
823 case COLOR_SCHEME_GREY:
824 pal = &(palette_grey[0][0]);
825 break;
826 case COLOR_SCHEME_PASTEL:
827 pal = &(palette_pastel[0][0]);
828 break;
829 case COLOR_SCHEME_SEQUENTIAL_SINGLEHUE_RED:
830 fprintf(stderr," HERE!\n");
831 pal = &(palette_sequential_singlehue_red[0][0]);
832 break;
833 case COLOR_SCHEME_SEQUENTIAL_SINGLEHUE_RED_LIGHTER:
834 fprintf(stderr," HERE!\n");
835 pal = &(palette_sequential_singlehue_red_lighter[0][0]);
836 break;
837 case COLOR_SCHEME_PRIMARY:
838 pal = &(palette_primary[0][0]);
839 break;
840 case COLOR_SCHEME_ADAM_BLEND:
841 pal = &(palette_adam_blend[0][0]);
842 break;
843 case COLOR_SCHEME_ADAM:
844 pal = &(palette_adam[0][0]);
845 max_color = 11;
846 break;
847 case COLOR_SCHEME_NONE:
848 pal = NULL;
849 break;
850 default:
851 pal = &(palette_pastel[0][0]);
852 break;
853 }
854
855 if (!g) return NULL;
856 nnodes = agnnodes (g);
857 nedges = agnedges (g);
858 *nn = nnodes;
859
860 /* Assign node ids */
861 i = 0;
862 for (n = agfstnode (g); n; n = agnxtnode (g, n))
863 ND_id(n) = i++;
864
865 /* form matrix */
866 I = N_NEW(nedges, int);
867 J = N_NEW(nedges, int);
868 val = N_NEW(nedges, real);
869
870 sym = agattr(g, AGEDGE, "weight", NULL);
871 clust_sym = agattr(g, AGNODE, "cluster", NULL);
872 clust_clr_sym = agattr(g, AGNODE, "clustercolor", NULL);
873 //sym = agattr(g, AGEDGE, "wt", NULL);
874 i = 0;
875 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
876 row = ND_id(n);
877 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
878 I[i] = row;
879 J[i] = ND_id(aghead(e));
880 if (sym) {
881 if (sscanf (agxget(e,sym), "%lf", &v) != 1)
882 v = 1;
883 }
884 else
885 v = 1;
886 val[i] = v;
887 i++;
888 }
889 }
890 A = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J, val, type, sz);
891
892 /* get clustering info */
893 *clusters = MALLOC(sizeof(int)*nnodes);
894 nc = 1;
895 MIN_GRPS = 0;
896 /* if useClusters, the nodes in each top-level cluster subgraph are assigned to
897 * clusters 2, 3, .... Any nodes not in a cluster subgraph are tossed into cluster 1.
898 */
899 if (useClusters) {
900 Agraph_t* sg;
901 int gid = 1;
902 memset (*clusters, 0, sizeof(int)*nnodes);
903 for (sg = agfstsubg(g); sg; sg = agnxtsubg(sg)) {
904 if (strncmp(agnameof(sg), "cluster", 7)) continue;
905 gid++;
906 for (n = agfstnode(sg); n; n = agnxtnode (sg, n)) {
907 i = ND_id(n);
908 if ((*clusters)[i])
909 fprintf (stderr, "Warning: node %s appears in multiple clusters.\n", agnameof(n));
910 else
911 (*clusters)[i] = gid;
912 }
913 }
914 for (n = agfstnode(g); n; n = agnxtnode (g, n)) {
915 i = ND_id(n);
916 if ((*clusters)[i] == 0)
917 (*clusters)[i] = 1;
918 }
919 MIN_GRPS = 1;
920 nc = gid;
921 }
922 else if (clust_sym) {
923 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
924 i = ND_id(n);
925 if ((sscanf(agxget(n,clust_sym), "%d", &ic)>0)) {
926 (*clusters)[i] = ic;
927 nc = MAX(nc, ic);
928 if (first){
929 MIN_GRPS = ic;
930 first = FALSE;
931 } else {
932 MIN_GRPS = MIN(MIN_GRPS, ic);
933 }
934 } else {
935 noclusterinfo = TRUE;
936 break;
937 }
938 }
939 }
940 else
941 noclusterinfo = TRUE;
942 MAX_GRPS = nc;
943
944 if (noclusterinfo) {
945 int use_value = TRUE, flag = 0;
946 real modularity;
947 if (!clust_sym) clust_sym = agattr(g,AGNODE,"cluster","-1");
948
949 if (clustering_scheme == CLUSTERING_MQ){
950 mq_clustering(A, FALSE, maxcluster, use_value,
951 &nc, clusters, &modularity, &flag);
952 } else if (clustering_scheme == CLUSTERING_MODULARITY){
953 modularity_clustering(A, FALSE, maxcluster, use_value,
954 &nc, clusters, &modularity, &flag);
955 } else {
956 assert(0);
957 }
958 for (i = 0; i < nnodes; i++) (*clusters)[i]++;/* make into 1 based */
959 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
960 i = ND_id(n);
961 sprintf(scluster,"%d",(*clusters)[i]);
962 agxset(n,clust_sym,scluster);
963 }
964 MIN_GRPS = 1;
965 MAX_GRPS = nc;
966 if (Verbose){
967 fprintf(stderr," no complement clustering info in dot file, using modularity clustering. Modularity = %f, ncluster=%d\n",modularity, nc);
968 }
969 }
970
971 *label_sizes = MALLOC(sizeof(real)*dim*nnodes);
972 if (pal || (!noclusterinfo && clust_clr_sym)){
973 *rgb_r = MALLOC(sizeof(float)*(1+MAX_GRPS));
974 *rgb_g = MALLOC(sizeof(float)*(1+MAX_GRPS));
975 *rgb_b = MALLOC(sizeof(float)*(1+MAX_GRPS));
976 } else {
977 *rgb_r = NULL;
978 *rgb_g = NULL;
979 *rgb_b = NULL;
980 }
981 *fsz = MALLOC(sizeof(float)*nnodes);
982 *labels = MALLOC(sizeof(char*)*nnodes);
983
984 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
985 gvcolor_t color;
986 real sz;
987 i = ND_id(n);
988 if (agget(n, "width") && agget(n, "height")){
989 sscanf(agget(n, "width"), "%lf", &sz);
990 (*label_sizes)[i*2] = POINTS(sz*0.5);
991 sscanf(agget(n, "height"), "%lf", &sz);
992 (*label_sizes)[i*2+1] = POINTS(sz*0.5);
993 } else {
994 (*label_sizes)[i*2] = POINTS(0.75/2);
995 (*label_sizes)[i*2+1] = POINTS(0.5*2);
996 }
997
998 if (agget(n, "fontsize")){
999 sscanf(agget(n, "fontsize"), "%f", &ff);
1000 (*fsz)[i] = ff;
1001 } else {
1002 (*fsz)[i] = 14;
1003 }
1004
1005 if (agget(n, "label") && strcmp(agget(n, "label"), "") != 0 && strcmp(agget(n, "label"), "\\N") != 0){
1006 char *lbs;
1007 lbs = agget(n, "label");
1008 (*labels)[i] = MALLOC(sizeof(char)*(strlen(lbs)+1));
1009 strcpy((*labels)[i], lbs);
1010 } else {
1011 (*labels)[i] = MALLOC(sizeof(char)*(strlen(agnameof(n))+1));
1012 strcpy((*labels)[i], agnameof(n));
1013 }
1014
1015
1016
1017 j = (*clusters)[i];
1018 if (MAX_GRPS-MIN_GRPS < max_color) {
1019 j = (j-MIN_GRPS)*((int)((max_color-1)/MAX((MAX_GRPS-MIN_GRPS),1)));
1020 } else {
1021 j = (j-MIN_GRPS)%max_color;
1022 }
1023
1024 if (pal){
1025 // assert((*clusters)[i] >= 0 && (*clusters)[i] <= MAX_GRPS);
1026 (*rgb_r)[(*clusters)[i]] = pal[3*j+0];
1027 (*rgb_g)[(*clusters)[i]] = pal[3*j+1];
1028 (*rgb_b)[(*clusters)[i]] = pal[3*j+2];
1029 }
1030
1031 if (!noclusterinfo && clust_clr_sym && (colorxlate(agxget(n,clust_clr_sym),&color,RGBA_DOUBLE) == COLOR_OK)) {
1032 (*rgb_r)[(*clusters)[i]] = color.u.RGBA[0];
1033 (*rgb_g)[(*clusters)[i]] = color.u.RGBA[1];
1034 (*rgb_b)[(*clusters)[i]] = color.u.RGBA[2];
1035 }
1036
1037 if (!noclusterinfo && agget(n, "cluster") && agget(n, "clustercolor") && strlen(agget(n, "clustercolor") ) >= 7 && pal){
1038 char cc[10];
1039 strcpy(cc, agget(n, "clustercolor"));
1040 (*rgb_r)[(*clusters)[i]] = hexcol2rgb(cc+1);
1041 (*rgb_g)[(*clusters)[i]] = hexcol2rgb(cc+3);
1042 (*rgb_b)[(*clusters)[i]] = hexcol2rgb(cc+5);
1043 }
1044
1045 }
1046
1047
1048 if (x){
1049 int has_position = FALSE;
1050 *x = MALLOC(sizeof(real)*dim*nnodes);
1051 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
1052 real xx,yy;
1053 i = ND_id(n);
1054 if (agget(n, "pos")){
1055 has_position = TRUE;
1056 sscanf(agget(n, "pos"), "%lf,%lf", &xx, &yy);
1057 (*x)[i*dim] = xx;
1058 (*x)[i*dim+1] = yy;
1059 } else {
1060 fprintf(stderr,"WARNING: pos field missing for node %d, set to origin\n",i);
1061 (*x)[i*dim] = 0;
1062 (*x)[i*dim+1] = 0;
1063 }
1064 }
1065 if (!has_position){
1066 FREE(*x);
1067 *x = NULL;
1068 }
1069 }
1070
1071
1072 FREE(I);
1073 FREE(J);
1074 FREE(val);
1075
1076 return A;
1077}
1078
1079void attached_clustering(Agraph_t* g, int maxcluster, int clustering_scheme){
1080 SparseMatrix A = 0;
1081 Agnode_t* n;
1082 Agedge_t* e;
1083 Agsym_t *sym, *clust_sym;
1084 int nnodes;
1085 int nedges;
1086 int i, row,nc;
1087 int* I;
1088 int* J;
1089 real* val;
1090 real v;
1091 int type = MATRIX_TYPE_REAL;
1092 size_t sz = sizeof(real);
1093 char scluster[100];
1094
1095
1096 int *clusters;
1097
1098
1099
1100 if (!g) return;
1101 nnodes = agnnodes (g);
1102 nedges = agnedges (g);
1103
1104 /* Assign node ids */
1105 i = 0;
1106 for (n = agfstnode (g); n; n = agnxtnode (g, n))
1107 ND_id(n) = i++;
1108
1109 /* form matrix */
1110 I = N_NEW(nedges, int);
1111 J = N_NEW(nedges, int);
1112 val = N_NEW(nedges, real);
1113
1114 sym = agattr(g, AGEDGE, "weight", NULL);
1115 clust_sym = agattr(g, AGNODE, "cluster", NULL);
1116
1117 i = 0;
1118 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
1119 row = ND_id(n);
1120 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
1121 I[i] = row;
1122 J[i] = ND_id(aghead(e));
1123 if (sym) {
1124 if (sscanf (agxget(e,sym), "%lf", &v) != 1)
1125 v = 1;
1126 }
1127 else
1128 v = 1;
1129 val[i] = v;
1130 i++;
1131 }
1132 }
1133 A = SparseMatrix_from_coordinate_arrays(nedges, nnodes, nnodes, I, J, val, type, sz);
1134
1135 clusters = MALLOC(sizeof(int)*nnodes);
1136
1137 {
1138 int use_value = TRUE, flag = 0;
1139 real modularity;
1140 if (!clust_sym) clust_sym = agattr(g,AGNODE,"cluster","-1");
1141
1142 if (clustering_scheme == CLUSTERING_MQ){
1143 mq_clustering(A, FALSE, maxcluster, use_value,
1144 &nc, &clusters, &modularity, &flag);
1145 } else if (clustering_scheme == CLUSTERING_MODULARITY){
1146 modularity_clustering(A, FALSE, maxcluster, use_value,
1147 &nc, &clusters, &modularity, &flag);
1148 } else {
1149 assert(0);
1150 }
1151 for (i = 0; i < nnodes; i++) (clusters)[i]++;/* make into 1 based */
1152 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
1153 i = ND_id(n);
1154 sprintf(scluster,"%d",(clusters)[i]);
1155 agxset(n,clust_sym,scluster);
1156 }
1157 if (Verbose){
1158 fprintf(stderr," no complement clustering info in dot file, using modularity clustering. Modularity = %f, ncluster=%d\n",modularity, nc);
1159 }
1160 }
1161
1162 FREE(I);
1163 FREE(J);
1164 FREE(val);
1165 FREE(clusters);
1166
1167 SparseMatrix_delete(A);
1168
1169}
1170
1171
1172
1173void initDotIO (Agraph_t *g)
1174{
1175 aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), TRUE);
1176}
1177
1178void setDotNodeID (Agnode_t* n, int v)
1179{
1180 ND_id(n) = v;
1181}
1182
1183int getDotNodeID (Agnode_t* n)
1184{
1185 return ND_id(n);
1186}
1187
1188