Graphviz 12.0.1~dev.20240716.0800
Loading...
Searching...
No Matches
edge_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 <cgraph/alloc.h>
12#include <sparse/general.h>
13#include <math.h>
14#include <stdbool.h>
15#include <string.h>
16#include <time.h>
17#include <sparse/SparseMatrix.h>
18#include <edgepaint/edge_distinct_coloring.h>
19#include <edgepaint/node_distinct_coloring.h>
20#include <sparse/DotIO.h>
21#include <edgepaint/intersection.h>
22#include <sparse/QuadTree.h>
23
24static int splines_intersect(size_t dim,
25 double cos_critical, int check_edges_with_same_endpoint,
26 char *xsplines1, char *xsplines2){
27 /* cos_critical: cos of critical angle
28 check_edges_with_same_endpoint: whether need to treat two splines from
29 . the same end point specially in ignoring splines that exit/enter the same end pont at around 180
30 xsplines1,xsplines2: the first and second splines corresponding to two edges
31
32 */
33 size_t len1 = 100, len2 = 100;
34 size_t ns1 = 0, ns2 = 0;
35 int iter1 = 0, iter2 = 0;
36 double cos_a, tmp[2];
37 int endp1 = 0, endp2 = 0;
38
39 tmp[0] = tmp[1] = 0;
40 double *x1 = gv_calloc(len1, sizeof(double));
41 double *x2 = gv_calloc(len2, sizeof(double));
42
43 assert(dim <= 3);
44
45 /* splines could be a list of
46 1. 3n points
47 2. of the form "e,x,y" followed by 3n points, where x,y is really padded to the end of the 3n points
48 3. of the form "s,x,y" followed by 3n points, where x,y is padded to the start of the 3n points
49 */
50 if (xsplines1){
51 if(strstr(xsplines1, "e,")){
52 endp1 = 1;
53 xsplines1 = strstr(xsplines1, "e,") + 2;
54 } else if (strstr(xsplines1, "s,")){
55 xsplines1 = strstr(xsplines1, "s,") + 2;
56 }
57 }
58 while (xsplines1 && sscanf(xsplines1,"%lf,%lf", &(x1[ns1*dim]), &x1[ns1*dim + 1]) == 2){
59 if (endp1 && iter1 == 0){
60 tmp[0] = x1[ns1*dim]; tmp[1] = x1[ns1*dim + 1];
61 } else {
62 ns1++;
63 }
64 iter1++;
65 xsplines1 = strchr(xsplines1, ' ');
66 if (!xsplines1) break;
67 xsplines1++;
68 if (ns1*dim >= len1){
69 size_t new_len1 = ns1 * dim + MAX(10u, ns1 * dim / 5);
70 x1 = gv_recalloc(x1, len1, new_len1, sizeof(double));
71 len1 = new_len1;
72 }
73 }
74 if (endp1){/* pad the end point at the last position */
75 ns1++;
76 if (ns1*dim >= len1){
77 size_t new_len1 = ns1 * dim + MAX(10u, ns1 * dim / 5);
78 x1 = gv_recalloc(x1, len1, new_len1, sizeof(double));
79 len1 = new_len1;
80 }
81 x1[(ns1-1)*dim] = tmp[0]; x1[(ns1-1)*dim + 1] = tmp[1];
82 }
83
84
85 /* splines could be a list of
86 1. 3n points
87 2. of the form "e,x,y" followed by 3n points, where x,y is really padded to the end of the 3n points
88 3. of the form "s,x,y" followed by 3n points, where x,y is padded to the start of the 3n points
89 */
90 if (xsplines2){
91 if(strstr(xsplines2, "e,")){
92 endp2 = 1;
93 xsplines2 = strstr(xsplines2, "e,") + 2;
94 } else if (strstr(xsplines2, "s,")){
95 xsplines2 = strstr(xsplines2, "s,") + 2;
96 }
97 }
98 while (xsplines2 && sscanf(xsplines2,"%lf,%lf", &(x2[ns2*dim]), &x2[ns2*dim + 1]) == 2){
99 if (endp2 && iter2 == 0){
100 tmp[0] = x2[ns2*dim]; tmp[1] = x2[ns2*dim + 1];
101 } else {
102 ns2++;
103 }
104 iter2++;
105 xsplines2 = strchr(xsplines2, ' ');
106 if (!xsplines2) break;
107 xsplines2++;
108 if (ns2*dim >= len2){
109 size_t new_len2 = ns2 * dim + MAX(10u, ns2 * dim / 5);
110 x2 = gv_recalloc(x2, len2, new_len2, sizeof(double));
111 len2 = new_len2;
112 }
113 }
114 if (endp2){/* pad the end point at the last position */
115 ns2++;
116 if (ns2*dim >= len2){
117 size_t new_len2 = ns2 * dim + MAX(10u, ns2 * dim / 5);
118 x2 = gv_recalloc(x2, len2, new_len2, sizeof(double));
119 len2 = new_len2;
120 }
121 x2[(ns2-1)*dim] = tmp[0]; x2[(ns2-1)*dim + 1] = tmp[1];
122 }
123
124 for (size_t i = 0; i < ns1 - 1; i++) {
125 for (size_t j = 0; j < ns2 - 1; j++) {
126 cos_a = intersection_angle(&(x1[dim*i]), &(x1[dim*(i + 1)]), &(x2[dim*j]), &(x2[dim*(j+1)]));
127 if (!check_edges_with_same_endpoint && cos_a >= -1) cos_a = fabs(cos_a);
128 if (cos_a > cos_critical) {
129 free(x1);
130 free(x2);
131 return 1;
132 }
133
134 }
135 }
136
137 free(x1);
138 free(x2);
139 return 0;
140}
141
142Agraph_t *edge_distinct_coloring(char *color_scheme, int *lightness,
143 Agraph_t *g, double angle, double accuracy,
144 int check_edges_with_same_endpoint, int seed) {
145 /* color the edges of a graph so that conflicting edges are as dinstrinct in color as possibl.
146 color_scheme: rgb, lab, gray, or a list of comma separaterd RGB colors in hex, like #ff0000,#00ff00
147 lightness: of the form 0,70, specifying the range of lightness of LAB color. Ignored if scheme is not COLOR_LAB.
148 g: the graph
149 angle: if two edges cross at an angle < "angle", consider they as conflict
150 accuracy: how accurate when finding color of an edge to be as different from others
151 check_edges_with_same_endpoint: if TRUE, we will check edges with same end point and only consider them as conflict if
152 . their angle is very small. Edges that share an end point and is close to 180 degree
153 . are not consider conflict.
154 seed: random_seed. If negative, consider -seed as the number of random start iterations
155 */
156 double *x = NULL;
157 int dim = 2;
158 SparseMatrix A, B, C;
159 int *irn, *jcn, nz, nz2 = 0;
160 double cos_critical = cos(angle/180*3.14159), cos_a;
161 int u1, v1, u2, v2, i, j;
162 double *colors = NULL;
163 int flag, ne;
164 char **xsplines = NULL;
165 int cdim;
166
167 A = SparseMatrix_import_dot(g, dim, &x, FORMAT_COORD);
168 if (!x){
169 fprintf(stderr,"The gv file contains no or improper 2D coordinates\n");
170 return NULL;
171 }
172
173
174 irn = A->ia; jcn = A->ja;
175 nz = A->nz;
176
177 /* get rid of self edges */
178 for (i = 0; i < nz; i++){
179 if (irn[i] != jcn[i]){
180 irn[nz2] = irn[i];
181 jcn[nz2++] = jcn[i];
182 }
183 }
184
185 if (Verbose)
186 fprintf(stderr,"cos = %f, nz2 = %d\n", cos_critical, nz2);
187 /* now find edge collision */
188 B = SparseMatrix_new(nz2, nz2, 1, MATRIX_TYPE_REAL, FORMAT_COORD);
189
190 if (Import_dot_splines(g, &ne, &xsplines)){
191#ifdef TIME
192 clock_t start = clock();
193#endif
194 assert(ne == nz2);
195 cos_a = 1.;/* for splines we exit conflict check as soon as we find an conflict, so the anle may not be representitive, hence set to constant */
196 for (i = 0; i < nz2; i++){
197 for (j = i+1; j < nz2; j++){
198 if (splines_intersect((size_t)dim, cos_critical,
199 check_edges_with_same_endpoint, xsplines[i],
200 xsplines[j])) {
201 B = SparseMatrix_coordinate_form_add_entry(B, i, j, &cos_a);
202 }
203 }
204 }
205#ifdef TIME
206 fprintf(stderr, "cpu for dual graph =%10.3f", ((double) (clock() - start))/CLOCKS_PER_SEC);
207#endif
208
209 } else {
210 /* no splines, justsimple edges */
211#ifdef TIME
212 clock_t start = clock();
213#endif
214
215
216 for (i = 0; i < nz2; i++){
217 u1 = irn[i]; v1 = jcn[i];
218 for (j = i+1; j < nz2; j++){
219 u2 = irn[j]; v2 = jcn[j];
220 cos_a = intersection_angle(&(x[dim*u1]), &(x[dim*v1]), &(x[dim*u2]), &(x[dim*v2]));
221 if (!check_edges_with_same_endpoint && cos_a >= -1) cos_a = fabs(cos_a);
222 if (cos_a > cos_critical) {
223 B = SparseMatrix_coordinate_form_add_entry(B, i, j, &cos_a);
224 }
225 }
226 }
227#ifdef TIME
228 fprintf(stderr, "cpu for dual graph (splines) =%10.3f\n", ((double) (clock() - start))/CLOCKS_PER_SEC);
229#endif
230 }
231 C = SparseMatrix_from_coordinate_format(B);
232 if (B != C) SparseMatrix_delete(B);
233
234 {
235#ifdef TIME
236 clock_t start = clock();
237#endif
238 const bool weightedQ = false;
239 flag = node_distinct_coloring(color_scheme, lightness, weightedQ, C,
240 accuracy, seed, &cdim, &colors);
241 if (flag) goto RETURN;
242#ifdef TIME
243 fprintf(stderr, "cpu for color assignmment =%10.3f\n", ((double) (clock() - start))/CLOCKS_PER_SEC);
244#endif
245 }
246
247 if (Verbose)
248 fprintf(stderr,"The edge conflict graph has %d nodes and %d edges\n", C->m, C->nz);
249
250 attach_edge_colors(g, cdim, colors);
251
252 RETURN:
253 SparseMatrix_delete(A);
254 SparseMatrix_delete(C);
255 free(colors);
256 free(x);
257 if (xsplines){
258 for (i = 0; i < ne; i++){
259 free(xsplines[i]);
260 }
261 free(xsplines);
262 }
263 return g;
264}
SparseMatrix_import_dot
SparseMatrix SparseMatrix_import_dot(Agraph_t *g, int dim, double **x, int format)
Definition DotIO.c:80
attach_edge_colors
void attach_edge_colors(Agraph_t *g, int dim, double *colors)
Definition DotIO.c:50
Import_dot_splines
int Import_dot_splines(Agraph_t *g, int *ne, char ***xsplines)
Definition DotIO.c:217
SparseMatrix_from_coordinate_format
SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A)
Definition SparseMatrix.c:535
SparseMatrix_coordinate_form_add_entry
SparseMatrix SparseMatrix_coordinate_form_add_entry(SparseMatrix A, int irn, int jcn, const void *val)
Definition SparseMatrix.c:1276
SparseMatrix_delete
void SparseMatrix_delete(SparseMatrix A)
Definition SparseMatrix.c:381
SparseMatrix_new
SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format)
Definition SparseMatrix.c:354
FORMAT_COORD
@ FORMAT_COORD
Definition SparseMatrix.h:23
MATRIX_TYPE_REAL
@ MATRIX_TYPE_REAL
Definition SparseMatrix.h:45
alloc.h
Memory allocation wrappers that exit on failure.
gv_recalloc
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
gv_calloc
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
edge_distinct_coloring
Agraph_t * edge_distinct_coloring(char *color_scheme, int *lightness, Agraph_t *g, double angle, double accuracy, int check_edges_with_same_endpoint, int seed)
Definition edge_distinct_coloring.c:142
splines_intersect
static int splines_intersect(size_t dim, double cos_critical, int check_edges_with_same_endpoint, char *xsplines1, char *xsplines2)
Definition edge_distinct_coloring.c:24
edge_distinct_coloring.h
seed
static long seed
Definition exeval.c:1035
A
#define A(n, t)
Definition expr.h:76
Verbose
static int Verbose
Definition gml2gv.c:22
free
void free(void *)
NULL
node NULL
Definition grammar.y:149
B
#define B
Definition hierarchy.c:117
intersection_angle
double intersection_angle(double *p1, double *p2, double *q1, double *q2)
Definition intersection.c:114
node_distinct_coloring
int node_distinct_coloring(char *color_scheme, int *lightness, bool weightedQ, SparseMatrix A0, double accuracy, int seed, int *cdim0, double **colors)
Definition node_distinct_coloring.c:179
node_distinct_coloring.h
C
#define C
Definition pack.c:30
RETURN
#define RETURN(v)
Definition strmatch.c:144
Agraph_s
graph or subgraph
Definition cgraph.h:425
SparseMatrix_struct
Definition SparseMatrix.h:29
MAX
#define MAX(a, b)
Definition write.c:31