Graphviz 13.1.2~dev.20250807.2324
Loading...
Searching...
No Matches
minglemain.cpp
Go to the documentation of this file.
1
2/*************************************************************************
3 * Copyright (c) 2011 AT&T Intellectual Property
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * https://www.eclipse.org/legal/epl-v10.html
8 *
9 *************************************************************************/
10
11#include "config.h"
12#include "../tools/openFile.h"
13#include <algorithm>
14#include <cgraph/cgraph.h>
15#include <cgraph/ingraphs.h>
16#include <getopt.h>
17#include <iomanip>
18#include <iostream>
19#include <sstream>
20#include <unordered_map>
21#include <utility>
22#include <util/debug.h>
23#include <util/exit.h>
24#include <vector>
25
26#include <sparse/DotIO.h>
29
30typedef enum {
33} fmt_t;
34
35typedef struct {
37 int idx;
38} etoi_t;
39
40#define ED_idx(e) (((etoi_t*)AGDATA(e))->idx)
41
42typedef struct {
44 int method;
46 double K;
51 double angle;
52} opts_t;
53
54static char *fname;
55static FILE *outfile;
56static char **Files;
57
58static const char use_msg[] =
59"Usage: mingle <options> <file>\n\
60 -a t - max. turning angle [0-180] (40)\n\
61 -c i - compatibility measure; 0 : distance, 1: full (default)\n\
62 -i iter: number of outer iterations/subdivisions (4)\n\
63 -k k - number of neighbors in the nearest neighbor graph of edges (10)\n\
64 -K k - the force constant\n\
65 -m method - method used. 0 (force directed), 1 (agglomerative ink saving, default), 2 (cluster+ink saving)\n\
66 -o fname - write output to file fname (stdout)\n\
67 -p t - balance for avoiding sharp angles\n\
68 The larger the t, the more sharp angles are allowed\n\
69 -r R - max. recursion level with agglomerative ink saving method (100)\n\
70 -T fmt - output format: gv (default) or simple\n\
71 -v - verbose\n";
72
73static void
75{
76 std::cerr << use_msg;
78}
79
80/* checkG:
81 * Return non-zero if g has loops or multiedges.
82 * Relies on multiedges occurring consecutively in edge list.
83 */
84static int
86{
87 Agedge_t* e;
88 Agnode_t* n;
89 Agnode_t* h;
90 Agnode_t* prevh = nullptr;
91
92 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
93 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
94 if ((h = aghead(e)) == n) return 1; // loop
95 if (h == prevh) return 1; // multiedge
96 prevh = h;
97 }
98 prevh = nullptr; // reset
99 }
100 return 0;
101}
102
103static void init(int argc, char *argv[], opts_t &opts) {
104 int c;
105 char* cmd = argv[0];
106 double s;
107 int i;
108
109 opterr = 0;
110 opts.outer_iter = 4;
113 opts.K = -1;
114 opts.fmt = FMT_GV;
115 opts.nneighbors = 10;
116 opts.max_recursion = 100;
117 opts.angle_param = -1;
118 opts.angle = 40.0/180.0*M_PI;
119
120 while ((c = getopt(argc, argv, ":a:c:i:k:K:m:o:p:r:T:v:?")) != -1) {
121 switch (c) {
122 case 'a':
123 if (sscanf(optarg, "%lf", &s) > 0 && s >= 0)
124 opts.angle = M_PI * s / 180;
125 else
126 std::cerr << "-a arg " << optarg << " must be positive real - ignored\n";
127 break;
128 case 'c':
129 if (sscanf(optarg, "%d", &i) > 0 && 0 <= i && i <= COMPATIBILITY_FULL)
131 else
132 std::cerr << "-c arg " << optarg << " must be an integer in [0,"
133 << COMPATIBILITY_FULL << "] - ignored\n";
134 break;
135 case 'i':
136 if (sscanf(optarg, "%d", &i) > 0 && i >= 0)
137 opts.outer_iter = i;
138 else
139 std::cerr << "-i arg " << optarg << " must be a non-negative integer - "
140 "ignored\n";
141 break;
142 case 'k':
143 if (sscanf(optarg, "%d", &i) > 0 && i >= 2)
144 opts.nneighbors = i;
145 else
146 std::cerr << "-k arg " << optarg << " must be an integer >= 2 - ignored\n";
147 break;
148 case 'K':
149 if (sscanf(optarg, "%lf", &s) > 0 && s > 0)
150 opts.K = s;
151 else
152 std::cerr << "-K arg " << optarg << " must be positive real - ignored\n";
153 break;
154 case 'm':
155 if (sscanf(optarg, "%d", &i) > 0 && 0 <= i && i <= METHOD_INK)
156 opts.method = i;
157 else
158 std::cerr << "-k arg " << optarg << " must be an integer >= 2 - ignored\n";
159 break;
160 case 'o':
161 outfile = openFile(cmd, optarg, "w");
162 break;
163 case 'p':
164 if (sscanf(optarg, "%lf", &s) > 0)
166 else
167 std::cerr << "-p arg " << optarg << " must be real - ignored\n";
168 break;
169 case 'r':
170 if (sscanf(optarg, "%d", &i) > 0 && i >= 0)
172 else
173 std::cerr << "-r arg " << optarg << " must be a non-negative integer - "
174 "ignored\n";
175 break;
176 case 'T':
177 if (!strcmp(optarg, "gv"))
178 opts.fmt = FMT_GV;
179 else if (!strcmp(optarg,"simple"))
181 else
182 std::cerr << "-T arg " << optarg << " must be \"gv\" or \"simple\" - "
183 "ignored\n";
184 break;
185 case 'v':
186 Verbose = 1;
187 if (sscanf(optarg, "%d", &i) > 0 && i >= 0)
188 Verbose = static_cast<unsigned char>(i);
189 else
190 optind--;
191 break;
192 case ':':
193 if (optopt == 'v')
194 Verbose = 1;
195 else {
196 std::cerr << cmd << ": option -" << optopt << " missing argument\n";
197 usage(1);
198 }
199 break;
200 case '?':
201 if (optopt == '\0' || optopt == '?')
202 usage(0);
203 else {
204 std::cerr << cmd << ": option -" << optopt << " unrecognized\n";
205 usage(1);
206 }
207 break;
208 default:
209 break;
210 }
211 }
212 argv += optind;
213 argc -= optind;
214
215 if (argc > 0)
216 Files = argv;
217 if (!outfile) outfile = stdout;
218 if (Verbose) {
219 std::cerr
220 << "Mingle params:\n"
221 << " outer_iter = " << opts.outer_iter << '\n'
222 << " method = " << opts.method << '\n'
223 << " compatibility_method = " << opts.compatibility_method << '\n'
224 << " K = " << std::setprecision(2) << opts.K << '\n'
225 << " fmt = " << (opts.fmt ? "simple" : "gv") << '\n'
226 << " nneighbors = " << opts.nneighbors << '\n'
227 << " max_recursion = " << opts.max_recursion << '\n'
228 << " angle_param = " << std::setprecision(2) << opts.angle_param << '\n'
229 << " angle = " << std::setprecision(2) << (180 * opts.angle / M_PI) << '\n';
230 }
231}
232
233/* genBundleSpline:
234 * We have ninterval+1 points. We drop the ninterval-1 internal points, and add 4 points to the first
235 * and last intervals, and 3 to the rest, giving the needed 3*ninterval+4 points.
236 */
237static void genBundleSpline(const pedge &edge, std::ostream &os) {
238 int k, j;
239 const int dim = edge.dim;
240 const std::vector<double> &x = edge.x;
241
242 for (j = 0; j < edge.npoints; j++){
243 if (j != 0) {
244 os << ' ';
245 const std::vector<double> tt1{0.15, 0.5, 0.85};
246 const std::vector<double> tt2{0.15, 0.4, 0.6, 0.85};
247 const std::vector<double> &tt = (j == 1 || j == edge.npoints - 1) ? tt2 : tt1;
248 for (const double t : tt){
249 for (k = 0; k < dim; k++) {
250 if (k != 0) os << ',';
251 os << std::setprecision(3) << (x[(j-1)*dim+k]*(1-t)+x[j*dim+k]*t);
252 }
253 os << ' ';
254 }
255 }
256 if (j == 0 || j == edge.npoints - 1) {
257 for (k = 0; k < dim; k++) {
258 if (k != 0) os << ',';
259 os << std::setprecision(3) << x[j * dim + k];
260 }
261 }
262 }
263}
264
265static void genBundleInfo(const pedge &edge, std::ostream &os) {
266 int k, j;
267 const int dim = edge.dim;
268 const std::vector<double> &x = edge.x;
269
270 for (j = 0; j < edge.npoints; j++){
271 if (j != 0) os << ':';
272 for (k = 0; k < dim; k++) {
273 if (k != 0) os << ',';
274 os << std::setprecision(3) << x[j * dim + k];
275 }
276
277 if (j < edge.npoints - 1 && !edge.wgts.empty()) {
278 os << ';' << std::setprecision(3) << edge.wgts[j];
279 }
280 }
281}
282
283static void genBundleColors(const pedge &edge, std::ostream &os,
284 double maxwgt) {
285 int k, j, r, g, b;
286 double len, t, len_total0 = 0;
287 const int dim = edge.dim;
288 const std::vector<double> &x = edge.x;
289 std::vector<double> lens(edge.npoints);
290
291 for (j = 0; j < edge.npoints - 1; j++){
292 len = 0;
293 for (k = 0; k < dim; k++){
294 len += (x[dim*j+k] - x[dim*(j+1)+k])*(x[dim*j+k] - x[dim*(j+1)+k]);
295 }
296 lens[j] = len = sqrt(len/k);
297 len_total0 += len;
298 }
299 for (j = 0; j < edge.npoints - 1; j++){
300 t = edge.wgts[j] / maxwgt;
301 /* interpolate between red (t = 1) to blue (t = 0) */
302 r = 255*t; g = 0; b = 255*(1-t);
303 if (j != 0) os << ':';
304 os << std::hex << std::setw(2) << std::setfill('0') << '#' << r << g << b
305 << 85;
306 if (j < edge.npoints - 2) {
307 os << ';' << (lens[j] / len_total0);
308 }
309 }
310 os << std::dec << std::setw(0); // reset stream characteristics
311}
312
313static void export_dot(FILE *fp, int ne, const std::vector<pedge> &edges,
314 Agraph_t *g) {
315 Agsym_t* epos = agattr_text(g, AGEDGE, const_cast<char*>("pos"), "");
316 Agsym_t* esects = agattr_text(g, AGEDGE, const_cast<char*>("bundle"), "");
317 Agsym_t* eclrs = nullptr;
318 Agnode_t* n;
319 Agedge_t* e;
320 int i, j;
321 double maxwgt = 0;
322
323 /* figure out max number of bundled original edges in a pedge */
324 for (i = 0; i < ne; i++){
325 const pedge &edge = edges[i];
326 if (!edge.wgts.empty()) {
327 for (j = 0; j < edge.npoints - 1; j++){
328 maxwgt = std::max(maxwgt, edge.wgts[j]);
329 }
330 }
331 }
332
333 std::ostringstream buf;
334 for (n = agfstnode (g); n; n = agnxtnode (g, n)) {
335 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
336 const pedge &edge = edges[ED_idx(e)];
337
338 genBundleSpline(edge, buf);
339 agxset(e, epos, buf.str().c_str());
340 buf.str("");
341
342 genBundleInfo(edge, buf);
343 agxset(e, esects, buf.str().c_str());
344 buf.str("");
345
346 if (!edge.wgts.empty()) {
347 if (!eclrs) eclrs = agattr_text(g, AGEDGE, const_cast<char*>("color"), "");
348 genBundleColors(edge, buf, maxwgt);
349 agxset(e, eclrs, buf.str().c_str());
350 buf.str("");
351 }
352 }
353 }
354 agwrite(g, fp);
355}
356
358struct PointHash {
359public:
360 size_t operator()(const std::pair<int, int> &x) const {
361 return std::hash<int>{}(x.first) ^ std::hash<int>{}(x.second);
362 }
363};
364
365using PointMap = std::unordered_map<std::pair<int, int>, int, PointHash>;
366
367static int bundle(Agraph_t *g, const opts_t &opts) {
368 double *x = nullptr;
369 int dim = 2;
370 int i;
371
372 if (checkG(g)) {
373 agerrorf("Graph %s (%s) contains loops or multiedges\n", agnameof(g), fname);
374 return 1;
375 }
376 initDotIO(g);
378 if (!A){
379 agerrorf("Error: could not convert graph %s (%s) into matrix\n", agnameof(g), fname);
380 return 1;
381 }
382 if (x == nullptr) {
383 agerr (AGPREV, " in file %s\n", fname);
384 return 1;
385 }
386
387 A = SparseMatrix_symmetrize(A, true);
388 if (opts.fmt == FMT_GV) {
389 PointMap pm; // map from node id pairs to edge index
390 Agnode_t* n;
391 Agedge_t* e;
392 int idx = 0;
393
394 const int *ia = A->ia;
395 const int *ja = A->ja;
396 for (i = 0; i < A->m; i++){
397 for (int j = ia[i]; j < ia[i+1]; j++){
398 if (ja[j] > i){
399 pm[std::pair(i, ja[j])] = idx++;
400 }
401 }
402 }
403 for (i = 0, n = agfstnode(g); n; n = agnxtnode(g,n)) {
404 setDotNodeID(n, i++);
405 }
406 for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
407 for (e = agfstout (g, n); e; e = agnxtout (g, e)) {
408 i = getDotNodeID (agtail(e));
409 int j = getDotNodeID (aghead(e));
410 if (j < i) {
411 std::swap(i, j);
412 }
413 const int k = pm[std::pair(i, j)];
414 agbindrec (e, "info", sizeof(etoi_t), true);
415 ED_idx(e) = k;
416 }
417 }
418 }
419
420 const int *ia = A->ia;
421 const int *ja = A->ja;
422 int nz = A->nz;
423 std::vector<double> xx(nz * 4);
424 nz = 0;
425 dim = 4;
426 for (i = 0; i < A->m; i++){
427 for (int j = ia[i]; j < ia[i+1]; j++){
428 if (ja[j] > i){
429 xx[nz*dim] = x[i*2];
430 xx[nz*dim+1] = x[i*2+1];
431 xx[nz*dim+2] = x[ja[j]*2];
432 xx[nz*dim+3] = x[ja[j]*2+1];
433 nz++;
434 }
435 }
436 }
437 GV_DEBUG("n = %d nz = %d", A->m, nz);
438
439 SparseMatrix B = nearest_neighbor_graph(nz, std::min(opts.nneighbors, nz), xx);
440
442 A = B;
443 free(x);
444
445 std::vector<pedge> edges =
449
450 if (opts.fmt == FMT_GV) {
451 export_dot(outfile, A->m, edges, g);
452 }
453 else {
454 pedge_export_gv(outfile, A->m, edges);
455 }
456 return 0;
457}
458
459int main(int argc, char *argv[])
460{
461 Agraph_t *g;
462 Agraph_t *prev = nullptr;
463 ingraph_state ig;
464 int rv = 0;
465 opts_t opts;
466
467 init(argc, argv, opts);
468 newIngraph(&ig, Files);
469
470 while ((g = nextGraph(&ig)) != 0) {
471 if (prev)
472 agclose(prev);
473 prev = g;
474 fname = fileName(&ig);
475 GV_INFO("Process graph %s in file %s", agnameof(g), fname);
476 rv |= bundle(g, opts);
477 }
478
479 graphviz_exit(rv);
480}
481
SparseMatrix SparseMatrix_import_dot(Agraph_t *g, int dim, double **x, int format)
Definition DotIO.c:81
int getDotNodeID(Agnode_t *n)
Definition DotIO.c:658
void initDotIO(Agraph_t *g)
Definition DotIO.c:648
void setDotNodeID(Agnode_t *n, int v)
Definition DotIO.c:653
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, bool pattern_symmetric_only)
void SparseMatrix_delete(SparseMatrix A)
@ FORMAT_CSR
#define M_PI
Definition arith.h:41
abstract graph C library, Cgraph API
static char * cmd
Definition acyclic.c:40
helpers for verbose/debug printing
#define GV_DEBUG(...)
Definition debug.h:39
#define GV_INFO(...)
Definition debug.h:15
std::vector< pedge > edge_bundling(SparseMatrix A0, int dim, const std::vector< double > &x, int maxit_outer, double K, int method, int nneighbor, int compatibility_method, int max_recursion, double angle_param, double angle)
void pedge_export_gv(FILE *fp, int ne, const std::vector< pedge > &edges)
@ METHOD_INK
@ METHOD_INK_AGGLOMERATE
@ COMPATIBILITY_FULL
static NORETURN void graphviz_exit(int status)
Definition exit.h:23
#define A(n, t)
Definition expr.h:76
static int eval(Agraph_t *g, int root)
Definition gc.c:270
static double len(glCompPoint p)
Definition glutils.c:136
static bool Verbose
Definition gml2gv.c:24
void free(void *)
edge
Definition gmlparse.y:239
Agsym_t * agattr_text(Agraph_t *g, int kind, char *name, const char *value)
creates or looks up text attributes of a graph
Definition attr.c:334
int agxset(void *obj, Agsym_t *sym, const char *value)
Definition attr.c:522
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define agtail(e)
Definition cgraph.h:988
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
void agerrorf(const char *fmt,...)
Definition agerror.c:165
int agerr(agerrlevel_t level, const char *fmt,...)
Definition agerror.c:155
@ AGPREV
Definition cgraph.h:957
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:95
int agwrite(Agraph_t *g, void *chan)
Return 0 on success, EOF on failure.
Definition write.c:696
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
@ AGEDGE
Definition cgraph.h:207
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Definition rec.c:89
static opts_t opts
Definition gvgen.c:401
static const char * usage
Definition gvpr.c:49
#define B
Definition hierarchy.c:118
$2 u p prev
Definition htmlparse.y:297
char * fileName(ingraph_state *sp)
Return name of current file being processed.
Definition ingraphs.c:154
Agraph_t * nextGraph(ingraph_state *sp)
Definition ingraphs.c:59
ingraph_state * newIngraph(ingraph_state *sp, char **files)
Definition ingraphs.c:138
supports user-supplied data
#define ED_idx(e)
static const char use_msg[]
std::unordered_map< std::pair< int, int >, int, PointHash > PointMap
static int bundle(Agraph_t *g, const opts_t &opts)
static void genBundleSpline(const pedge &edge, std::ostream &os)
static void genBundleInfo(const pedge &edge, std::ostream &os)
static int checkG(Agraph_t *g)
fmt_t
@ FMT_SIMPLE
@ FMT_GV
static char ** Files
static void init(int argc, char *argv[], opts_t &opts)
static void export_dot(FILE *fp, int ne, const std::vector< pedge > &edges, Agraph_t *g)
static FILE * outfile
static char * fname
static void genBundleColors(const pedge &edge, std::ostream &os, double maxwgt)
SparseMatrix nearest_neighbor_graph(int nPts, int num_neighbors, const std::vector< double > &x)
static const int dim
static FILE * openFile(const char *argv0, const char *name, const char *mode)
Definition openFile.h:8
graph or subgraph
Definition cgraph.h:424
implementation of Agrec_t
Definition cgraph.h:172
string attribute descriptor symbol in Agattr_s.dict
Definition cgraph.h:651
a hash derivation function for int pairs
size_t operator()(const std::pair< int, int > &x) const
Agrec_t hdr
int max_recursion
double angle_param
double K
int nneighbors
int method
fmt_t fmt
int compatibility_method
int outer_iter
double angle
int main()
Definition grammar.c:89