DotIO.c

Go to the documentation of this file.

/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
#include "config.h"
 
#define STANDALONE
#include <assert.h>
#include <cgraph/cghdr.h>
#include <limits.h>
#include <math.h>
#include <sparse/DotIO.h>
#include <sparse/clustering.h>
#include <sparse/color_palette.h>
#include <sparse/colorutil.h>
#include <sparse/general.h>
#include <sparse/mq.h>
#include <stdbool.h>
#include <stddef.h>
#include <string.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/itos.h>
#include <util/startswith.h>
#include <util/unreachable.h>
 
typedef struct {
  Agrec_t h;
  int id;
} Agnodeinfo_t;
 
#define ND_id(n) (((Agnodeinfo_t *)((n)->base.data))->id)
 
static void color_string(agxbuf *buf, size_t dim, double *color) {
  if (dim > 3 || dim < 1) {
    fprintf(stderr, "can only 1, 2 or 3 dimensional color space. with color "
                    "value between 0 to 1\n");
    assert(0);
  }
  if (dim == 3) {
    agxbprint(buf, "#%02x%02x%02x", MIN((unsigned int)(color[0] * 255), 255),
              MIN((unsigned int)(color[1] * 255), 255),
              MIN((unsigned int)(color[2] * 255), 255));
  } else if (dim == 1) {
    agxbprint(buf, "#%02x%02x%02x", MIN((unsigned int)(color[0] * 255), 255),
              MIN((unsigned int)(color[0] * 255), 255),
              MIN((unsigned int)(color[0] * 255), 255));
  } else if (dim == 2) {
    agxbprint(buf, "#%02x%02x%02x", MIN((unsigned int)(color[0] * 255), 255), 0,
              MIN((unsigned int)(color[1] * 255), 255));
  }
}
 
void attach_edge_colors(Agraph_t *g, size_t dim, double *colors) {
  /* colors is array of dim*nedges, with color for edge i at colors[dim*i,
   * dim(i+1))
   */
  Agsym_t *sym = agattr_text(g, AGEDGE, "color", 0);
  Agedge_t *e;
  Agnode_t *n;
  agxbuf buf = {0};
  size_t ie = 0;
 
  if (!sym)
    sym = agattr_text(g, AGEDGE, "color", "");
 
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    const int row = ND_id(n);
    for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
      const int col = ND_id(aghead(e));
      if (row == col)
        continue;
      color_string(&buf, dim, colors + ie * dim);
      agxset(e, sym, agxbuse(&buf));
      ie++;
    }
  }
  agxbfree(&buf);
}
 
/* SparseMatrix_import_dot:
 * Assumes g is connected and simple, i.e., we can have a->b and b->a
 * but not a->b and a->b
 */
SparseMatrix SparseMatrix_import_dot(Agraph_t *g, double **x, int format) {
  assert(x != NULL);
  enum { DIM = 2 };
  SparseMatrix A = 0;
  Agsym_t *psym;
  int *I;
  int *J;
  double *val;
  double v;
  int type = MATRIX_TYPE_REAL;
 
  if (!g)
    return NULL;
  const size_t nnodes = agnnodes_z(g);
  const size_t nedges = (size_t)agnedges(g);
  assert(format == FORMAT_CSR || format == FORMAT_COORD);
 
  /* Assign node ids */
  int i = 0;
  for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n))
    ND_id(n) = i++;
 
  if (format == FORMAT_COORD) {
    A = SparseMatrix_new((size_t)i, i, nedges, MATRIX_TYPE_REAL, format);
    A->nz = nedges;
    I = A->ia;
    J = A->ja;
    val = A->a;
  } else {
    I = gv_calloc(nedges, sizeof(int));
    J = gv_calloc(nedges, sizeof(int));
    val = gv_calloc(nedges, sizeof(double));
  }
 
  Agsym_t *const sym = agattr_text(g, AGEDGE, "weight", NULL);
  i = 0;
  for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
    const int row = ND_id(n);
    for (Agedge_t *e = agfstout(g, n); e; e = agnxtout(g, e)) {
      I[i] = row;
      J[i] = ND_id(aghead(e));
 
      /* edge weight */
      if (sym) {
        if (sscanf(agxget(e, sym), "%lf", &v) != 1)
          v = 1;
      } else {
        v = 1;
      }
      val[i] = v;
 
      i++;
    }
  }
 
  if ((psym = agattr_text(g, AGNODE, "pos", NULL))) {
    bool has_positions = true;
    char *pval;
    *x = gv_calloc(DIM * nnodes, sizeof(double));
    for (Agnode_t *n = agfstnode(g); n && has_positions; n = agnxtnode(g, n)) {
      double xx, yy;
      i = ND_id(n);
      if ((pval = agxget(n, psym)) && *pval) {
        const int nitems = sscanf(pval, "%lf,%lf", &xx, &yy);
        if (nitems != 2) {
          has_positions = false;
          agerrorf("Node \"%s\" pos has %d < 2 values", agnameof(n), nitems);
        }
        (*x)[i * DIM] = xx;
        (*x)[i * DIM + 1] = yy;
      } else {
        has_positions = false;
        agerrorf("Node \"%s\" lacks position info", agnameof(n));
      }
    }
    if (!has_positions) {
      free(*x);
      *x = NULL;
    }
  } else
    agerrorf("Error: graph %s has missing \"pos\" information", agnameof(g));
 
  size_t sz = sizeof(double);
  if (format == FORMAT_CSR) {
    assert(nnodes <= INT_MAX);
    A = SparseMatrix_from_coordinate_arrays(nedges, nnodes, (int)nnodes, I, J,
                                            val, type, sz);
  }
 
  if (format != FORMAT_COORD) {
    free(I);
    free(J);
    free(val);
  }
 
  return A;
}
 
/* get spline info */
int Import_dot_splines(Agraph_t *g, int *ne, char ***xsplines) {
  /* get the list of splines for the edges in the order they appear, and store
     as a list of strings in xspline. If *xsplines = NULL, it will be allocated.
     On exit (*xsplines)[i] is the control point string for the i-th edge. This
     string is of the form "x1,y1 x2,y2...", the two end points of the edge is
     not included per Dot format Return 1 if success. 0 if not.
  */
  Agnode_t *n;
  Agedge_t *e;
  Agsym_t *sym;
  int nedges;
 
  if (!g) {
    return 0;
  }
 
  *ne = nedges = agnedges(g);
 
  /* Assign node ids */
  int i = 0;
  for (n = agfstnode(g); n; n = agnxtnode(g, n))
    ND_id(n) = i++;
 
  sym = agattr_text(g, AGEDGE, "pos", 0);
  if (!sym)
    return 0;
 
  *xsplines = gv_calloc(nedges, sizeof(char *));
 
  i = 0;
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
      /* edge weight */
      char *pos = agxget(e, sym);
      (*xsplines)[i] = strdup(pos);
      i++;
    }
  }
  return 1;
}
 
static int hex2int(char h) {
  if (h >= '0' && h <= '9')
    return h - '0';
  if (h >= 'a' && h <= 'f')
    return 10 + h - 'a';
  if (h >= 'A' && h <= 'F')
    return 10 + h - 'A';
  return 0;
}
 
static float hexcol2rgb(const char *h) {
  return (float)(hex2int(h[0]) * 16 + hex2int(h[1])) / 255.0f;
}
 
void Dot_SetClusterColor(Agraph_t *g, float *rgb_r, float *rgb_g, float *rgb_b,
                         int *clusters) {
 
  Agnode_t *n;
  agxbuf scluster = {0};
  Agsym_t *clust_clr_sym = agattr_text(g, AGNODE, "clustercolor", NULL);
 
  if (!clust_clr_sym)
    clust_clr_sym = agattr_text(g, AGNODE, "clustercolor", "-1");
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    const int i = ND_id(n);
    if (rgb_r && rgb_g && rgb_b) {
      rgb2hex(rgb_r[clusters[i]], rgb_g[clusters[i]], rgb_b[clusters[i]],
              &scluster, NULL);
    }
    agxset(n, clust_clr_sym, agxbuse(&scluster));
  }
  agxbfree(&scluster);
}
 
SparseMatrix Import_coord_clusters_from_dot(
    Agraph_t *g, int maxcluster, int dim, int *nn, double **label_sizes,
    double **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) {
  SparseMatrix A = 0;
  Agnode_t *n;
  Agedge_t *e;
  Agsym_t *sym;
  Agsym_t *clust_sym;
  Agsym_t *clust_clr_sym;
  int nnodes;
  int nedges;
  int i, row, ic, nc, j;
  double v;
  int type = MATRIX_TYPE_REAL;
  float ff;
 
  int MAX_GRPS, MIN_GRPS;
  bool noclusterinfo = false;
  bool first = true;
  const float *pal;
  int max_color = MAX_COLOR;
 
  switch (default_color_scheme) {
  case COLOR_SCHEME_BLUE_YELLOW:
    pal = &palette_blue_to_yellow[0][0];
    break;
  case COLOR_SCHEME_WHITE_RED:
    pal = &palette_white_to_red[0][0];
    break;
  case COLOR_SCHEME_GREY_RED:
    pal = &palette_grey_to_red[0][0];
    break;
  case COLOR_SCHEME_GREY:
    pal = &palette_grey[0][0];
    break;
  case COLOR_SCHEME_PASTEL:
    pal = &palette_pastel[0][0];
    break;
  case COLOR_SCHEME_SEQUENTIAL_SINGLEHUE_RED:
    pal = &palette_sequential_singlehue_red[0][0];
    break;
  case COLOR_SCHEME_SEQUENTIAL_SINGLEHUE_RED_LIGHTER:
    pal = &palette_sequential_singlehue_red_lighter[0][0];
    break;
  case COLOR_SCHEME_PRIMARY:
    pal = &palette_primary[0][0];
    break;
  case COLOR_SCHEME_ADAM_BLEND:
    pal = &palette_adam_blend[0][0];
    break;
  case COLOR_SCHEME_ADAM:
    pal = &palette_adam[0][0];
    max_color = 11;
    break;
  case COLOR_SCHEME_NONE:
    pal = NULL;
    break;
  default:
    pal = &palette_pastel[0][0];
    break;
  }
 
  if (!g)
    return NULL;
  nnodes = agnnodes(g);
  nedges = agnedges(g);
  *nn = nnodes;
 
  /* Assign node ids */
  i = 0;
  for (n = agfstnode(g); n; n = agnxtnode(g, n))
    ND_id(n) = i++;
 
  /* form matrix */
  int *I = gv_calloc(nedges, sizeof(int));
  int *J = gv_calloc(nedges, sizeof(int));
  double *val = gv_calloc(nedges, sizeof(double));
 
  sym = agattr_text(g, AGEDGE, "weight", NULL);
  clust_sym = agattr_text(g, AGNODE, "cluster", NULL);
  clust_clr_sym = agattr_text(g, AGNODE, "clustercolor", NULL);
  i = 0;
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    row = ND_id(n);
    for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
      I[i] = row;
      J[i] = ND_id(aghead(e));
      if (sym) {
        if (sscanf(agxget(e, sym), "%lf", &v) != 1)
          v = 1;
      } else
        v = 1;
      val[i] = v;
      i++;
    }
  }
  A = SparseMatrix_from_coordinate_arrays(
      (size_t)nedges, (size_t)nnodes, nnodes, I, J, val, type, sizeof(double));
 
  /* get clustering info */
  *clusters = gv_calloc(nnodes, sizeof(int));
  nc = 1;
  MIN_GRPS = 0;
  /* if useClusters, the nodes in each top-level cluster subgraph are assigned
   * to clusters 2, 3, .... Any nodes not in a cluster subgraph are tossed into
   * cluster 1.
   */
  if (useClusters) {
    Agraph_t *sg;
    int gid = 1;
    memset(*clusters, 0, sizeof(int) * nnodes);
    for (sg = agfstsubg(g); sg; sg = agnxtsubg(sg)) {
      if (!startswith(agnameof(sg), "cluster"))
        continue;
      gid++;
      for (n = agfstnode(sg); n; n = agnxtnode(sg, n)) {
        i = ND_id(n);
        if ((*clusters)[i])
          fprintf(stderr, "Warning: node %s appears in multiple clusters.\n",
                  agnameof(n));
        else
          (*clusters)[i] = gid;
      }
    }
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
      i = ND_id(n);
      if ((*clusters)[i] == 0)
        (*clusters)[i] = 1;
    }
    MIN_GRPS = 1;
    nc = gid;
  } else if (clust_sym) {
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
      i = ND_id(n);
      if (sscanf(agxget(n, clust_sym), "%d", &ic) > 0) {
        (*clusters)[i] = ic;
        nc = MAX(nc, ic);
        if (first) {
          MIN_GRPS = ic;
          first = false;
        } else {
          MIN_GRPS = MIN(MIN_GRPS, ic);
        }
      } else {
        noclusterinfo = true;
        break;
      }
    }
  } else
    noclusterinfo = true;
  MAX_GRPS = nc;
 
  if (noclusterinfo) {
    double modularity;
    if (!clust_sym)
      clust_sym = agattr_text(g, AGNODE, "cluster", "-1");
 
    if (clustering_scheme == CLUSTERING_MQ) {
      mq_clustering(A, maxcluster, &nc, clusters, &modularity);
    } else if (clustering_scheme == CLUSTERING_MODULARITY) {
      modularity_clustering(A, false, maxcluster, &nc, clusters, &modularity);
    } else {
      UNREACHABLE();
    }
    for (i = 0; i < nnodes; i++)
      (*clusters)[i]++; /* make into 1 based */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
      i = ND_id(n);
      agxset(n, clust_sym, ITOS((*clusters)[i]));
    }
    MIN_GRPS = 1;
    MAX_GRPS = nc;
    if (Verbose) {
      fprintf(stderr,
              " no complement clustering info in dot file, using modularity "
              "clustering. Modularity = %f, ncluster=%d\n",
              modularity, nc);
    }
  }
 
  *label_sizes = gv_calloc(dim * nnodes, sizeof(double));
  if (pal || (!noclusterinfo && clust_clr_sym)) {
    *rgb_r = gv_calloc(1 + MAX_GRPS, sizeof(float));
    *rgb_g = gv_calloc(1 + MAX_GRPS, sizeof(float));
    *rgb_b = gv_calloc(1 + MAX_GRPS, sizeof(float));
  } else {
    *rgb_r = NULL;
    *rgb_g = NULL;
    *rgb_b = NULL;
  }
  *fsz = gv_calloc(nnodes, sizeof(float));
  *labels = gv_calloc(nnodes, sizeof(char *));
 
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    gvcolor_t color;
    double sz;
    i = ND_id(n);
    if (agget(n, "width") && agget(n, "height")) {
      sscanf(agget(n, "width"), "%lf", &sz);
      (*label_sizes)[i * 2] = POINTS(sz * 0.5);
      sscanf(agget(n, "height"), "%lf", &sz);
      (*label_sizes)[i * 2 + 1] = POINTS(sz * 0.5);
    } else {
      (*label_sizes)[i * 2] = POINTS(0.75 / 2);
      (*label_sizes)[i * 2 + 1] = POINTS(0.5 * 2);
    }
 
    if (agget(n, "fontsize")) {
      sscanf(agget(n, "fontsize"), "%f", &ff);
      (*fsz)[i] = ff;
    } else {
      (*fsz)[i] = 14;
    }
 
    if (agget(n, "label") && strcmp(agget(n, "label"), "") != 0 &&
        strcmp(agget(n, "label"), "\\N") != 0) {
      char *lbs = agget(n, "label");
      (*labels)[i] = strdup(lbs);
    } else {
      (*labels)[i] = strdup(agnameof(n));
    }
 
    j = (*clusters)[i];
    if (MAX_GRPS - MIN_GRPS < max_color) {
      j = (j - MIN_GRPS) *
          ((int)((max_color - 1) / MAX((MAX_GRPS - MIN_GRPS), 1)));
    } else {
      j = (j - MIN_GRPS) % max_color;
    }
 
    if (pal) {
      (*rgb_r)[(*clusters)[i]] = pal[3 * j + 0];
      (*rgb_g)[(*clusters)[i]] = pal[3 * j + 1];
      (*rgb_b)[(*clusters)[i]] = pal[3 * j + 2];
    }
 
    if (!noclusterinfo && clust_clr_sym &&
        (colorxlate(agxget(n, clust_clr_sym), &color, RGBA_DOUBLE) ==
         COLOR_OK)) {
      (*rgb_r)[(*clusters)[i]] = (float)color.u.RGBA[0];
      (*rgb_g)[(*clusters)[i]] = (float)color.u.RGBA[1];
      (*rgb_b)[(*clusters)[i]] = (float)color.u.RGBA[2];
    }
 
    const char *cc = agget(n, "clustercolor");
    if (!noclusterinfo && agget(n, "cluster") && cc && strlen(cc) >= 7 && pal) {
      (*rgb_r)[(*clusters)[i]] = hexcol2rgb(cc + 1);
      (*rgb_g)[(*clusters)[i]] = hexcol2rgb(cc + 3);
      (*rgb_b)[(*clusters)[i]] = hexcol2rgb(cc + 5);
    }
  }
 
  assert(x != NULL);
  bool has_position = false;
  *x = gv_calloc(dim * nnodes, sizeof(double));
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    double xx, yy;
    i = ND_id(n);
    if (agget(n, "pos")) {
      has_position = true;
      sscanf(agget(n, "pos"), "%lf,%lf", &xx, &yy);
      (*x)[i * dim] = xx;
      (*x)[i * dim + 1] = yy;
    } else {
      fprintf(stderr, "WARNING: pos field missing for node %d, set to origin\n",
              i);
      (*x)[i * dim] = 0;
      (*x)[i * dim + 1] = 0;
    }
  }
  if (!has_position) {
    free(*x);
    *x = NULL;
  }
 
  free(I);
  free(J);
  free(val);
 
  return A;
}
 
void attached_clustering(Agraph_t *g, int maxcluster, int clustering_scheme) {
  SparseMatrix A = 0;
  Agnode_t *n;
  Agedge_t *e;
  Agsym_t *sym, *clust_sym;
  int nnodes;
  int nedges;
  int i, row, nc;
  double v;
  int type = MATRIX_TYPE_REAL;
  size_t sz = sizeof(double);
 
  if (!g)
    return;
  nnodes = agnnodes(g);
  nedges = agnedges(g);
 
  /* Assign node ids */
  i = 0;
  for (n = agfstnode(g); n; n = agnxtnode(g, n))
    ND_id(n) = i++;
 
  /* form matrix */
  int *I = gv_calloc(nedges, sizeof(int));
  int *J = gv_calloc(nedges, sizeof(int));
  double *val = gv_calloc(nedges, sizeof(double));
 
  sym = agattr_text(g, AGEDGE, "weight", NULL);
  clust_sym = agattr_text(g, AGNODE, "cluster", NULL);
 
  i = 0;
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    row = ND_id(n);
    for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
      I[i] = row;
      J[i] = ND_id(aghead(e));
      if (sym) {
        if (sscanf(agxget(e, sym), "%lf", &v) != 1)
          v = 1;
      } else
        v = 1;
      val[i] = v;
      i++;
    }
  }
  A = SparseMatrix_from_coordinate_arrays((size_t)nedges, (size_t)nnodes,
                                          nnodes, I, J, val, type, sz);
 
  int *clusters = gv_calloc(nnodes, sizeof(int));
 
  {
    double modularity;
    if (!clust_sym)
      clust_sym = agattr_text(g, AGNODE, "cluster", "-1");
 
    if (clustering_scheme == CLUSTERING_MQ) {
      mq_clustering(A, maxcluster, &nc, &clusters, &modularity);
    } else if (clustering_scheme == CLUSTERING_MODULARITY) {
      modularity_clustering(A, false, maxcluster, &nc, &clusters, &modularity);
    } else {
      UNREACHABLE();
    }
    for (i = 0; i < nnodes; i++)
      (clusters)[i]++; /* make into 1 based */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
      i = ND_id(n);
      agxset(n, clust_sym, ITOS(clusters[i]));
    }
    if (Verbose) {
      fprintf(stderr,
              " no complement clustering info in dot file, using modularity "
              "clustering. Modularity = %f, ncluster=%d\n",
              modularity, nc);
    }
  }
 
  free(I);
  free(J);
  free(val);
  free(clusters);
 
  SparseMatrix_delete(A);
}
 
void initDotIO(Agraph_t *g) {
  aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), true);
}
 
void setDotNodeID(Agnode_t *n, int v) { ND_id(n) = v; }
 
int getDotNodeID(Agnode_t *n) { return ND_id(n); }