Graphviz 13.0.0~dev.20250402.0402
Loading...
Searching...
No Matches
node_distinct_coloring.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <sparse/general.h>
12#include <sparse/SparseMatrix.h>
13#include <sparse/QuadTree.h>
15#include <edgepaint/lab.h>
18#include <stdbool.h>
19#include <string.h>
20#include <util/alloc.h>
21#include <util/random.h>
22
23static void node_distinct_coloring_internal2(int scheme, QuadTree qt,
24 bool weightedQ, SparseMatrix A,
25 int cdim, double accuracy,
26 int seed, double *colors,
27 double *color_diff0,
28 double *color_diff_sum0) {
29 /* here we assume the graph is connected. And that the matrix is symmetric */
30 int i, j, *ia, *ja, n, k = 0;
31 int max_level;
32 double center[3];
33 double width;
34 double *a = NULL;
35 double dist_max;
36 double color_diff = 0, color_diff_old;
37 double color_diff_sum = 0, color_diff_sum_old, *cc;
38 int iter = 0;
39 static const int iter_max = 100;
40 double cspace_size = 0.7;
41 double red[3], black[3], min;
42 int imin;
43
44 assert(accuracy > 0);
45 max_level = MAX(1, -log(accuracy)/log(2.));
46 max_level = MIN(30, max_level);
47
48 {
49 color_rgb rgb = { .r = 255*0.5, .g = 0, .b = 0 };
50 color_lab lab = RGB2LAB(rgb);
51 red[0] = lab.l; red[1] = lab.a; red[2] = lab.b;
52 }
53
54 n = A->m;
55 if (n == 1){
56 if (scheme == COLOR_LAB){
57 assert(qt);
58 QuadTree_get_nearest(qt, black, colors, &imin, &min);
59 LAB2RGB_real_01(colors);
60 *color_diff0 = 1000; *color_diff_sum0 = 1000;
61 } else {
62 for (i = 0; i < cdim; i++) colors[i] = 0;
63 *color_diff0 = sqrt(cdim); *color_diff_sum0 = sqrt(cdim);
64 }
65 return;
66 } else if (n == 2){
67 if (scheme == COLOR_LAB){
68 assert(qt);
69 QuadTree_get_nearest(qt, black, colors, &imin, &min);
70 LAB2RGB_real_01(colors);
71
72 QuadTree_get_nearest(qt, red, colors+cdim, &imin, &min);
73 LAB2RGB_real_01(colors+cdim);
74 *color_diff0 = 1000; *color_diff_sum0 = 1000;
75
76 } else {
77 for (i = 0; i < cdim; i++) colors[i] = 0;
78 for (i = 0; i < cdim; i++) colors[cdim+i] = 0;
79 colors[cdim] = 0.5;
80 *color_diff0 = sqrt(cdim); *color_diff_sum0 = sqrt(cdim);
81 }
82 return;
83 }
84 assert(n == A->m);
85 ia = A->ia;
86 ja = A->ja;
87 if (A->type == MATRIX_TYPE_REAL && A->a){
88 a = A->a;
89 }
90
91 /* cube [0, cspace_size]^3: only uised if not LAB */
92 center[0] = center[1] = center[2] = cspace_size*0.5;
93 width = cspace_size*0.5;
94
95 /* randomly assign colors first */
96 srand(seed);
97 for (i = 0; i < n*cdim; i++) colors[i] = cspace_size*drand();
98
99 double *x = gv_calloc(cdim * n, sizeof(double));
100 double *wgt = weightedQ ? gv_calloc(n, sizeof(double)) : NULL;
101
102 color_diff = 0; color_diff_old = -1;
103 color_diff_sum = 0; color_diff_sum_old = -1;
104
105 while (iter++ < iter_max && (color_diff > color_diff_old || (color_diff == color_diff_old && color_diff_sum > color_diff_sum_old))){
106 color_diff_old = color_diff;
107 color_diff_sum_old = color_diff_sum;
108 for (i = 0; i < n; i++){
109 k = 0;
110 for (j = ia[i]; j < ia[i+1]; j++){
111 if (ja[j] == i) continue;
112 memcpy(&(x[k*cdim]), &(colors[ja[j]*cdim]), sizeof(double)*cdim);
113 if (wgt && a) wgt[k] = a[j];
114 k++;
115 }
116 cc = &(colors[i*cdim]);
117 if (scheme == COLOR_LAB){
118 furtherest_point_in_list(k, cdim, wgt, x, qt, max_level, &dist_max, &cc);
119 } else if (scheme == COLOR_RGB || scheme == COLOR_GRAY){
120 furtherest_point(k, cdim, wgt, x, center, width, max_level, &dist_max, &cc);
121 } else {
122 assert(0);
123 }
124 if (i == 0){
125 color_diff = dist_max;
126 color_diff_sum = dist_max;
127 } else {
128 color_diff = MIN(dist_max, color_diff);
129 color_diff_sum += dist_max;
130 }
131 }
132
133 if (Verbose) fprintf(stderr,"iter ---- %d ---, color_diff = %f, color_diff_sum = %f\n", iter, color_diff, color_diff_sum);
134 }
135
136 if (scheme == COLOR_LAB){
137 /* convert from LAB to RGB */
138 color_rgb rgb;
139 color_lab lab;
140 for (i = 0; i < n; i++){
141 lab = color_lab_init(colors[i*cdim], colors[i*cdim+1], colors[i*cdim+2]);
142 rgb = LAB2RGB(lab);
143 colors[i*cdim] = (rgb.r)/255;
144 colors[i*cdim+1] = (rgb.g)/255;
145 colors[i*cdim+2] = (rgb.b)/255;
146 }
147 }
148 *color_diff0 = color_diff;
149 *color_diff_sum0 = color_diff_sum;
150 free(x);
151 free(wgt);
152}
153
154static void node_distinct_coloring_internal(int scheme, QuadTree qt,
155 bool weightedQ, SparseMatrix A,
156 int cdim, double accuracy,
157 int seed, double *colors) {
158 int i;
159 double color_diff;
160 double color_diff_sum;
161 if (seed < 0) {
162 /* do multiple iterations and pick the best */
163 int iter, seed_max = -1;
164 double color_diff_max = -1;
165 srand(123);
166 iter = -seed;
167 for (i = 0; i < iter; i++){
168 seed = gv_random(100000);
169 node_distinct_coloring_internal2(scheme, qt, weightedQ, A, cdim, accuracy, seed, colors, &color_diff, &color_diff_sum);
170 if (color_diff_max < color_diff){
171 seed_max = seed; color_diff_max = color_diff;
172 }
173 }
174 seed = seed_max;
175 }
176 node_distinct_coloring_internal2(scheme, qt, weightedQ, A, cdim, accuracy, seed, colors, &color_diff, &color_diff_sum);
177
178}
179
180int node_distinct_coloring(const char *color_scheme, int *lightness,
181 bool weightedQ, SparseMatrix A0, double accuracy,
182 int seed, int *cdim0, double **colors) {
183 SparseMatrix B, A = A0;
184 int ncomps, *comps = NULL;
185 int nn, n;
186 int i, j, jj;
187 QuadTree qt = NULL;
188 int cdim;
189 int scheme = COLOR_LAB;
190 int maxcolors = 10000, max_qtree_level = 10, r, g, b;
191 const char *color_list = color_palettes_get(color_scheme);
192 if (color_list) color_scheme = color_list;
193
194 cdim = *cdim0 = 3;
195 if (strcmp(color_scheme, "lab") == 0){
196 if (Verbose) fprintf(stderr,"lab\n");
197 scheme = COLOR_LAB;
198 qt = lab_gamut_quadtree(lightness, max_qtree_level);
199 if (!qt){
200 fprintf(stderr, "out of memory\n");
201 return -1;
202 }
203 } else if (strcmp(color_scheme, "rgb") == 0){
204 if (Verbose) fprintf(stderr,"rgb\n");
205 scheme = COLOR_RGB;
206 } else if (strcmp(color_scheme, "gray") == 0){
207 scheme = COLOR_GRAY;
208 cdim = *cdim0 = 1;
209 } else if (sscanf(color_scheme,"#%02X%02X%02X", &r, &g, &b) == 3 ){
210 scheme = COLOR_LAB;
211 double *color_points = color_blend_rgb2lab(color_scheme, maxcolors);
212 assert(color_points);
213 qt = QuadTree_new_from_point_list(cdim, maxcolors, max_qtree_level,
214 color_points);
215 free(color_points);
216 assert(qt);
217 } else {
219 }
220
221
222 if (accuracy <= 0) accuracy = 0.0001;
223
224 n = A->m;
225 if (n != A->n) {
226 QuadTree_delete(qt);
227 return -1;
228 }
229
230 *colors = gv_calloc(cdim * n, sizeof(double));
231 double *ctmp = gv_calloc(cdim * n, sizeof(double));
232
233 B = SparseMatrix_symmetrize(A, false);
234 A = B;
235
236 int *comps_ptr = SparseMatrix_weakly_connected_components(A, &ncomps, &comps);
237
238 for (i = 0; i < ncomps; i++){
239 nn = comps_ptr[i+1] - comps_ptr[i];
240 B = SparseMatrix_get_submatrix(A, nn, nn, &(comps[comps_ptr[i]]), &(comps[comps_ptr[i]]));
241 node_distinct_coloring_internal(scheme, qt, weightedQ, B, cdim, accuracy, seed, ctmp);
242
243 for (j = comps_ptr[i]; j < comps_ptr[i+1]; j++){
244 jj = j - comps_ptr[i];
245 memcpy(&((*colors)[comps[j]*cdim]), &(ctmp[jj*cdim]), cdim*sizeof(double));
246 }
248 }
249 free(comps_ptr);
250 free(ctmp);
251 QuadTree_delete(qt);
252
253 if (A != A0) SparseMatrix_delete(A);
254 free(comps);
255 return 0;
256}
void QuadTree_get_nearest(QuadTree qt, double *x, double *ymin, int *imin, double *min)
Definition QuadTree.c:682
QuadTree QuadTree_new_from_point_list(int dim, int n, int max_level, double *coord)
Definition QuadTree.c:309
void QuadTree_delete(QuadTree q)
Definition QuadTree.c:375
SparseMatrix SparseMatrix_get_submatrix(SparseMatrix A, int nrow, int ncol, int *rindices, int *cindices)
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, bool pattern_symmetric_only)
void SparseMatrix_delete(SparseMatrix A)
int * SparseMatrix_weakly_connected_components(SparseMatrix A0, int *ncomp, int **comps)
@ MATRIX_TYPE_REAL
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define MIN(a, b)
Definition arith.h:28
const char * color_palettes_get(const char *color_palette_name)
static long seed
Definition exeval.c:1036
#define A(n, t)
Definition expr.h:76
void furtherest_point_in_list(int k, int dim, double *wgt, double *pts, QuadTree qt, int max_level, double *dist_max, double **argmax)
void furtherest_point(int k, int dim, double *wgt, double *pts, double *center, double width, int max_level, double *dist_max, double **argmax)
static bool Verbose
Definition gml2gv.c:23
void free(void *)
node NULL
Definition grammar.y:163
static double drand(void)
static int imin(int a, int b)
minimum of two integers
Definition gv_math.h:28
static const char black[]
#define B
Definition hierarchy.c:118
QuadTree lab_gamut_quadtree(const int *lightness, int max_qtree_level)
construct a quadtree of the LAB gamut points
Definition lab.c:186
void LAB2RGB_real_01(double *color)
Definition lab.c:74
color_lab color_lab_init(double l, double a, double b)
Definition lab.c:36
color_lab RGB2LAB(color_rgb color)
Definition lab.c:62
double * color_blend_rgb2lab(const char *color_list, const int maxpoints)
Definition lab.c:212
color_rgb LAB2RGB(color_lab color)
Definition lab.c:87
static void node_distinct_coloring_internal(int scheme, QuadTree qt, bool weightedQ, SparseMatrix A, int cdim, double accuracy, int seed, double *colors)
int node_distinct_coloring(const char *color_scheme, int *lightness, bool weightedQ, SparseMatrix A0, double accuracy, int seed, int *cdim0, double **colors)
static void node_distinct_coloring_internal2(int scheme, QuadTree qt, bool weightedQ, SparseMatrix A, int cdim, double accuracy, int seed, double *colors, double *color_diff0, double *color_diff_sum0)
@ ERROR_BAD_COLOR_SCHEME
int gv_random(int bound)
Definition random.c:89
random number generation
double b
l: 0 to 100, a,b: -128 to 128
Definition lab.h:24
double a
Definition lab.h:24
double l
Definition lab.h:24
double r
Definition lab.h:14
double g
Definition lab.h:14
double b
Definition lab.h:14
static point center(point vertex[], size_t n)
#define MAX(a, b)
Definition write.c:31