Graphviz  2.41.20170921.2350
mincross.c
Go to the documentation of this file.
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 
15 /*
16  * dot_mincross(g) takes a ranked graphs, and finds an ordering
17  * that avoids edge crossings. clusters are expanded.
18  * N.B. the rank structure is global (not allocated per cluster)
19  * because mincross may compare nodes in different clusters.
20  */
21 
22 #include "dot.h"
23 
24 /* #define DEBUG */
25 #define MARK(v) (ND_mark(v))
26 #define saveorder(v) (ND_coord(v)).x
27 #define flatindex(v) ND_low(v)
28 
29  /* forward declarations */
30 static boolean medians(graph_t * g, int r0, int r1);
31 static int nodeposcmpf(node_t ** n0, node_t ** n1);
32 static int edgeidcmpf(edge_t ** e0, edge_t ** e1);
33 static void flat_breakcycles(graph_t * g);
34 static void flat_reorder(graph_t * g);
35 static void flat_search(graph_t * g, node_t * v);
36 static void init_mincross(graph_t * g);
37 static void merge2(graph_t * g);
38 static void init_mccomp(graph_t * g, int c);
39 static void cleanup2(graph_t * g, int nc);
40 static int mincross_clust(graph_t * par, graph_t * g, int);
41 static int mincross(graph_t * g, int startpass, int endpass, int);
42 static void mincross_step(graph_t * g, int pass);
43 static void mincross_options(graph_t * g);
44 static void save_best(graph_t * g);
45 static void restore_best(graph_t * g);
46 static adjmatrix_t *new_matrix(int i, int j);
47 static void free_matrix(adjmatrix_t * p);
48 static int ordercmpf(int *i0, int *i1);
49 #ifdef DEBUG
50 #if DEBUG > 1
51 static int gd_minrank(Agraph_t *g) {return GD_minrank(g);}
52 static int gd_maxrank(Agraph_t *g) {return GD_maxrank(g);}
53 static rank_t *gd_rank(Agraph_t *g, int r) {return &GD_rank(g)[r];}
54 static int nd_order(Agnode_t *v) { return ND_order(v); }
55 #endif
56 void check_rs(graph_t * g, int null_ok);
57 void check_order(void);
58 void check_vlists(graph_t * g);
59 void node_in_root_vlist(node_t * n);
60 #endif
61 
62 
63  /* mincross parameters */
64 static int MinQuit;
65 static double Convergence;
66 
67 static graph_t *Root;
68 static int GlobalMinRank, GlobalMaxRank;
69 static edge_t **TE_list;
70 static int *TI_list;
71 static boolean ReMincross;
72 
73 #if DEBUG > 1
74 static void indent(graph_t* g)
75 {
76  if (g->parent) {
77  fprintf (stderr, " ");
78  indent(g->parent);
79  }
80 }
81 
82 static char* nname(node_t* v)
83 {
84  static char buf[1000];
85  if (ND_node_type(v)) {
86  if (ND_ranktype(v) == CLUSTER)
87  sprintf (buf, "v%s_%p", agnameof(ND_clust(v)), v);
88  else
89  sprintf (buf, "v_%p", v);
90  } else
91  sprintf (buf, "%s", agnameof(v));
92  return buf;
93 }
94 static void dumpg (graph_t* g)
95 {
96  int j, i, r;
97  node_t* v;
98  edge_t* e;
99 
100  fprintf (stderr, "digraph A {\n");
101  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
102  fprintf (stderr, " subgraph {rank=same ");
103  for (i = 0; i < GD_rank(g)[r].n; i++) {
104  v = GD_rank(g)[r].v[i];
105  if (i > 0)
106  fprintf (stderr, " -> %s", nname(v));
107  else
108  fprintf (stderr, "%s", nname(v));
109  }
110  if (i > 1) fprintf (stderr, " [style=invis]}\n");
111  else fprintf (stderr, " }\n");
112  }
113  for (r = GD_minrank(g); r < GD_maxrank(g); r++) {
114  for (i = 0; i < GD_rank(g)[r].n; i++) {
115  v = GD_rank(g)[r].v[i];
116  for (j = 0; (e = ND_out(v).list[j]); j++) {
117  fprintf (stderr, "%s -> ", nname(v));
118  fprintf (stderr, "%s\n", nname(aghead(e)));
119  }
120  }
121  }
122  fprintf (stderr, "}\n");
123 }
124 static void dumpr (graph_t* g, int edges)
125 {
126  int j, i, r;
127  node_t* v;
128  edge_t* e;
129 
130  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
131  fprintf (stderr, "[%d] ", r);
132  for (i = 0; i < GD_rank(g)[r].n; i++) {
133  v = GD_rank(g)[r].v[i];
134  fprintf (stderr, "%s(%.02f,%d) ", nname(v), saveorder(v),ND_order(v));
135  }
136  fprintf (stderr, "\n");
137  }
138  if (edges == 0) return;
139  for (r = GD_minrank(g); r < GD_maxrank(g); r++) {
140  for (i = 0; i < GD_rank(g)[r].n; i++) {
141  v = GD_rank(g)[r].v[i];
142  for (j = 0; (e = ND_out(v).list[j]); j++) {
143  fprintf (stderr, "%s -> ", nname(v));
144  fprintf (stderr, "%s\n", nname(aghead(e)));
145  }
146  }
147  }
148 }
149 #endif
150 
151 typedef struct {
153  int x, lo, hi;
155 } info_t;
156 
157 #define ND_x(n) (((info_t*)AGDATA(n))->x)
158 #define ND_lo(n) (((info_t*)AGDATA(n))->lo)
159 #define ND_hi(n) (((info_t*)AGDATA(n))->hi)
160 #define ND_np(n) (((info_t*)AGDATA(n))->np)
161 #define ND_idx(n) (ND_order(ND_np(n)))
162 
163 static void
164 emptyComp (graph_t* sg)
165 {
166  Agnode_t* n;
167  Agnode_t* nxt;
168 
169  for (n = agfstnode(sg); n; n = nxt) {
170  nxt = agnxtnode (sg, n);
171  agdelnode(sg,n);
172  }
173 }
174 
175 #define isBackedge(e) (ND_idx(aghead(e)) > ND_idx(agtail(e)))
176 
177 static Agnode_t*
178 findSource (Agraph_t* g, Agraph_t* sg)
179 {
180  Agnode_t* n;
181 
182  for (n = agfstnode(sg); n; n = agnxtnode(sg, n))
183  if (agdegree(g,n,1,0) == 0) return n;
184  return NULL;
185 }
186 
187 static int
188 topsort (Agraph_t* g, Agraph_t* sg, Agnode_t** arr)
189 {
190  Agnode_t* n;
191  Agedge_t* e;
192  Agedge_t* nxte;
193  int cnt = 0;
194 
195  while ((n = findSource(g, sg))) {
196  arr[cnt++] = ND_np(n);
197  agdelnode(sg, n);
198  for (e = agfstout(g, n); e; e = nxte) {
199  nxte = agnxtout(g, e);
200  agdeledge(g, e);
201  }
202  }
203  return cnt;
204 }
205 
206 static int
207 getComp (graph_t* g, node_t* n, graph_t* comp, int* indices)
208 {
209  int backedge = 0;
210  Agedge_t* e;
211 
212  ND_x(n) = 1;
213  indices[agnnodes(comp)] = ND_idx(n);
214  agsubnode(comp, n, 1);
215  for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
216  if (isBackedge(e)) backedge++;
217  if (!ND_x(aghead(e)))
218  backedge += getComp(g, aghead(e), comp, indices);
219  }
220  for (e = agfstin(g,n); e; e = agnxtin(g,e)) {
221  if (isBackedge(e)) backedge++;
222  if (!ND_x(agtail(e)))
223  backedge += getComp(g, agtail(e), comp, indices);
224  }
225  return backedge;
226 }
227 
228 /* fixLabelOrder:
229  * For each pair of nodes (labels), we add an edge
230  */
231 static void
232 fixLabelOrder (graph_t* g, rank_t* rk)
233 {
234  int cnt, haveBackedge = FALSE;
235  Agnode_t** arr;
236  int* indices;
237  Agraph_t* sg;
238  Agnode_t* n;
239  Agnode_t* nxtp;
240  Agnode_t* v;
241 
242  for (n = agfstnode(g); n; n = nxtp) {
243  v = nxtp = agnxtnode(g, n);
244  for (; v; v = agnxtnode(g, v)) {
245  if (ND_hi(v) <= ND_lo(n)) {
246  haveBackedge = TRUE;
247  agedge(g, v, n, NULL, 1);
248  }
249  else if (ND_hi(n) <= ND_lo(v)) {
250  agedge(g, n, v, NULL, 1);
251  }
252  }
253  }
254  if (!haveBackedge) return;
255 
256  sg = agsubg(g, "comp", 1);
257  arr = N_NEW(agnnodes(g), Agnode_t*);
258  indices = N_NEW(agnnodes(g), int);
259 
260  for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
261  if (ND_x(n) || (agdegree(g,n,1,1) == 0)) continue;
262  if (getComp(g, n, sg, indices)) {
263  int i, sz = agnnodes(sg);
264  cnt = topsort (g, sg, arr);
265  assert (cnt == sz);
266  qsort(indices, cnt, sizeof(int), (qsort_cmpf)ordercmpf);
267  for (i = 0; i < sz; i++) {
268  ND_order(arr[i]) = indices[i];
269  rk->v[indices[i]] = arr[i];
270  }
271  }
272  emptyComp(sg);
273  }
274  free (arr);
275 }
276 
277 /* checkLabelOrder:
278  * Check that the ordering of labels for flat edges is consistent.
279  * This is necessary because dot_position will attempt to force the label
280  * to be between the edge's vertices. This can lead to an infeasible problem.
281  *
282  * We check each rank for any flat edge labels (as dummy nodes) and create a
283  * graph with a node for each label. If the graph contains more than 1 node, we
284  * call fixLabelOrder to see if there really is a problem and, if so, fix it.
285  */
286 void
288 {
289  int j, r, lo, hi;
290  graph_t* lg = NULL;
291  char buf[BUFSIZ];
292  rank_t* rk;
293  Agnode_t* u;
294  Agnode_t* n;
295  Agedge_t* e;
296 
297  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
298  rk = GD_rank(g)+r;
299  for (j = 0; j < rk->n; j++) {
300  u = rk->v[j];
301  if ((e = (edge_t*)ND_alg(u))) {
302  if (!lg) lg = agopen ("lg", Agstrictdirected, 0);
303  sprintf (buf, "%d", j);
304  n = agnode(lg, buf, 1);
305  agbindrec(n, "info", sizeof(info_t), 1);
306  lo = ND_order(aghead(ND_out(u).list[0]));
307  hi = ND_order(aghead(ND_out(u).list[1]));
308  if (lo > hi) {
309  int tmp;
310  tmp = lo;
311  lo = hi;
312  hi = tmp;
313  }
314  ND_lo(n) = lo;
315  ND_hi(n) = hi;
316  ND_np(n) = u;
317  }
318  }
319  if (lg) {
320  if (agnnodes(lg) > 1) fixLabelOrder (lg, rk);
321  agclose(lg);
322  lg = NULL;
323  }
324  }
325 }
326 
327 /* dot_mincross:
328  * Minimize edge crossings
329  * Note that nodes are not placed into GD_rank(g) until mincross()
330  * is called.
331  */
332 void dot_mincross(graph_t * g, int doBalance)
333 {
334  int c, nc;
335  char *s;
336 
337  init_mincross(g);
338 
339  for (nc = c = 0; c < GD_comp(g).size; c++) {
340  init_mccomp(g, c);
341  nc += mincross(g, 0, 2, doBalance);
342  }
343 
344  merge2(g);
345 
346  /* run mincross on contents of each cluster */
347  for (c = 1; c <= GD_n_cluster(g); c++) {
348  nc += mincross_clust(g, GD_clust(g)[c], doBalance);
349 #ifdef DEBUG
350  check_vlists(GD_clust(g)[c]);
351  check_order();
352 #endif
353  }
354 
355  if ((GD_n_cluster(g) > 0)
356  && (!(s = agget(g, "remincross")) || (mapbool(s)))) {
357  mark_lowclusters(g);
358  ReMincross = TRUE;
359  nc = mincross(g, 2, 2, doBalance);
360 #ifdef DEBUG
361  for (c = 1; c <= GD_n_cluster(g); c++)
362  check_vlists(GD_clust(g)[c]);
363 #endif
364  }
365  cleanup2(g, nc);
366 }
367 
368 static adjmatrix_t *new_matrix(int i, int j)
369 {
370  adjmatrix_t *rv = NEW(adjmatrix_t);
371  rv->nrows = i;
372  rv->ncols = j;
373  rv->data = N_NEW(i * j, char);
374  return rv;
375 }
376 
377 static void free_matrix(adjmatrix_t * p)
378 {
379  if (p) {
380  free(p->data);
381  free(p);
382  }
383 }
384 
385 #define ELT(M,i,j) (M->data[((i)*M->ncols)+(j)])
386 
387 static void init_mccomp(graph_t * g, int c)
388 {
389  int r;
390 
391  GD_nlist(g) = GD_comp(g).list[c];
392  if (c > 0) {
393  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
394  GD_rank(g)[r].v = GD_rank(g)[r].v + GD_rank(g)[r].n;
395  GD_rank(g)[r].n = 0;
396  }
397  }
398 }
399 
400 static int betweenclust(edge_t * e)
401 {
402  while (ED_to_orig(e))
403  e = ED_to_orig(e);
404  return (ND_clust(agtail(e)) != ND_clust(aghead(e)));
405 }
406 
407 static void do_ordering_node (graph_t * g, node_t* n, int outflag)
408 {
409  int i, ne;
410  node_t *u, *v;
411  edge_t *e, *f, *fe;
412  edge_t **sortlist = TE_list;
413 
414  if (ND_clust(n))
415  return;
416  if (outflag) {
417  for (i = ne = 0; (e = ND_out(n).list[i]); i++)
418  if (!betweenclust(e))
419  sortlist[ne++] = e;
420  } else {
421  for (i = ne = 0; (e = ND_in(n).list[i]); i++)
422  if (!betweenclust(e))
423  sortlist[ne++] = e;
424  }
425  if (ne <= 1)
426  return;
427  /* write null terminator at end of list.
428  requires +1 in TE_list alloccation */
429  sortlist[ne] = 0;
430  qsort(sortlist, ne, sizeof(sortlist[0]), (qsort_cmpf) edgeidcmpf);
431  for (ne = 1; (f = sortlist[ne]); ne++) {
432  e = sortlist[ne - 1];
433  if (outflag) {
434  u = aghead(e);
435  v = aghead(f);
436  } else {
437  u = agtail(e);
438  v = agtail(f);
439  }
440  if (find_flat_edge(u, v))
441  return;
442  fe = new_virtual_edge(u, v, NULL);
443  ED_edge_type(fe) = FLATORDER;
444  flat_edge(g, fe);
445  }
446 }
447 
448 static void do_ordering(graph_t * g, int outflag)
449 {
450  /* Order all nodes in graph */
451  node_t *n;
452 
453  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
454  do_ordering_node (g, n, outflag);
455  }
456 }
457 
458 static void do_ordering_for_nodes(graph_t * g)
459 {
460  /* Order nodes which have the "ordered" attribute */
461  node_t *n;
462  const char *ordering;
463 
464  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
465  if ((ordering = late_string(n, N_ordering, NULL))) {
466  if (streq(ordering, "out"))
467  do_ordering_node(g, n, TRUE);
468  else if (streq(ordering, "in"))
469  do_ordering_node(g, n, FALSE);
470  else if (ordering[0])
471  agerr(AGERR, "ordering '%s' not recognized for node '%s'.\n", ordering, agnameof(n));
472  }
473  }
474 }
475 
476 /* ordered_edges:
477  * handle case where graph specifies edge ordering
478  * If the graph does not have an ordering attribute, we then
479  * check for nodes having the attribute.
480  * Note that, in this implementation, the value of G_ordering
481  * dominates the value of N_ordering.
482  */
483 static void ordered_edges(graph_t * g)
484 {
485  char *ordering;
486 
487  if (!G_ordering && !N_ordering)
488  return;
489  if ((ordering = late_string(g, G_ordering, NULL))) {
490  if (streq(ordering, "out"))
491  do_ordering(g, TRUE);
492  else if (streq(ordering, "in"))
493  do_ordering(g, FALSE);
494  else if (ordering[0])
495  agerr(AGERR, "ordering '%s' not recognized.\n", ordering);
496  }
497  else
498  {
499  graph_t *subg;
500 
501  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
502  /* clusters are processed by separate calls to ordered_edges */
503  if (!is_cluster(subg))
504  ordered_edges(subg);
505  }
506  if (N_ordering) do_ordering_for_nodes (g);
507  }
508 }
509 
510 static int mincross_clust(graph_t * par, graph_t * g, int doBalance)
511 {
512  int c, nc;
513 
514  expand_cluster(g);
515  ordered_edges(g);
516  flat_breakcycles(g);
517  flat_reorder(g);
518  nc = mincross(g, 2, 2, doBalance);
519 
520  for (c = 1; c <= GD_n_cluster(g); c++)
521  nc += mincross_clust(g, GD_clust(g)[c], doBalance);
522 
523  save_vlist(g);
524  return nc;
525 }
526 
527 static int left2right(graph_t * g, node_t * v, node_t * w)
528 {
529  adjmatrix_t *M;
530  int rv;
531 
532  /* CLUSTER indicates orig nodes of clusters, and vnodes of skeletons */
533  if (ReMincross == FALSE) {
534  if ((ND_clust(v) != ND_clust(w)) && (ND_clust(v)) && (ND_clust(w))) {
535  /* the following allows cluster skeletons to be swapped */
536  if ((ND_ranktype(v) == CLUSTER)
537  && (ND_node_type(v) == VIRTUAL))
538  return FALSE;
539  if ((ND_ranktype(w) == CLUSTER)
540  && (ND_node_type(w) == VIRTUAL))
541  return FALSE;
542  return TRUE;
543  /*return ((ND_ranktype(v) != CLUSTER) && (ND_ranktype(w) != CLUSTER)); */
544  }
545  } else {
546  if ((ND_clust(v)) != (ND_clust(w)))
547  return TRUE;
548  }
549  M = GD_rank(g)[ND_rank(v)].flat;
550  if (M == NULL)
551  rv = FALSE;
552  else {
553  if (GD_flip(g)) {
554  node_t *t = v;
555  v = w;
556  w = t;
557  }
558  rv = ELT(M, flatindex(v), flatindex(w));
559  }
560  return rv;
561 }
562 
563 static int in_cross(node_t * v, node_t * w)
564 {
565  register edge_t **e1, **e2;
566  register int inv, cross = 0, t;
567 
568  for (e2 = ND_in(w).list; *e2; e2++) {
569  register int cnt = ED_xpenalty(*e2);
570 
571  inv = ND_order((agtail(*e2)));
572 
573  for (e1 = ND_in(v).list; *e1; e1++) {
574  t = ND_order(agtail(*e1)) - inv;
575  if ((t > 0)
576  || ((t == 0)
577  && ( ED_tail_port(*e1).p.x > ED_tail_port(*e2).p.x)))
578  cross += ED_xpenalty(*e1) * cnt;
579  }
580  }
581  return cross;
582 }
583 
584 static int out_cross(node_t * v, node_t * w)
585 {
586  register edge_t **e1, **e2;
587  register int inv, cross = 0, t;
588 
589  for (e2 = ND_out(w).list; *e2; e2++) {
590  register int cnt = ED_xpenalty(*e2);
591  inv = ND_order(aghead(*e2));
592 
593  for (e1 = ND_out(v).list; *e1; e1++) {
594  t = ND_order(aghead(*e1)) - inv;
595  if ((t > 0)
596  || ((t == 0)
597  && ((ED_head_port(*e1)).p.x > (ED_head_port(*e2)).p.x)))
598  cross += ((ED_xpenalty(*e1)) * cnt);
599  }
600  }
601  return cross;
602 
603 }
604 
605 static void exchange(node_t * v, node_t * w)
606 {
607  int vi, wi, r;
608 
609  r = ND_rank(v);
610  vi = ND_order(v);
611  wi = ND_order(w);
612  ND_order(v) = wi;
613  GD_rank(Root)[r].v[wi] = v;
614  ND_order(w) = vi;
615  GD_rank(Root)[r].v[vi] = w;
616 }
617 
618 static void balanceNodes(graph_t * g, int r, node_t * v, node_t * w)
619 {
620  node_t *s; /* separator node */
621  int sepIndex = 0;
622  int nullType; /* type of null nodes */
623  int cntDummy = 0, cntOri = 0;
624  int k = 0, m = 0, k1 = 0, m1 = 0, i = 0;
625 
626  /* we only consider v and w of different types */
627  if (ND_node_type(v) == ND_node_type(w))
628  return;
629 
630  /* count the number of dummy and original nodes */
631  for (i = 0; i < GD_rank(g)[r].n; i++) {
632  if (ND_node_type(GD_rank(g)[r].v[i]) == NORMAL)
633  cntOri++;
634  else
635  cntDummy++;
636  }
637 
638  if (cntOri < cntDummy) {
639  if (ND_node_type(v) == NORMAL)
640  s = v;
641  else
642  s = w;
643  } else {
644  if (ND_node_type(v) == NORMAL)
645  s = w;
646  else
647  s = v;
648  }
649 
650  /* get the separator node index */
651  for (i = 0; i < GD_rank(g)[r].n; i++) {
652  if (GD_rank(g)[r].v[i] == s)
653  sepIndex = i;
654  }
655 
656  nullType = (ND_node_type(s) == NORMAL) ? VIRTUAL : NORMAL;
657 
658  /* count the number of null nodes to the left and
659  * right of the separator node
660  */
661  for (i = sepIndex - 1; i >= 0; i--) {
662  if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
663  k++;
664  else
665  break;
666  }
667 
668  for (i = sepIndex + 1; i < GD_rank(g)[r].n; i++) {
669  if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
670  m++;
671  else
672  break;
673  }
674 
675  /* now exchange v,w and calculate the same counts */
676 
677  exchange(v, w);
678 
679  /* get the separator node index */
680  for (i = 0; i < GD_rank(g)[r].n; i++) {
681  if (GD_rank(g)[r].v[i] == s)
682  sepIndex = i;
683  }
684 
685  /* count the number of null nodes to the left and
686  * right of the separator node
687  */
688  for (i = sepIndex - 1; i >= 0; i--) {
689  if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
690  k1++;
691  else
692  break;
693  }
694 
695  for (i = sepIndex + 1; i < GD_rank(g)[r].n; i++) {
696  if (ND_node_type(GD_rank(g)[r].v[i]) == nullType)
697  m1++;
698  else
699  break;
700  }
701 
702  if (abs(k1 - m1) > abs(k - m)) {
703  exchange(v, w); //revert to the original ordering
704  }
705 }
706 
707 static int balance(graph_t * g)
708 {
709  int i, c0, c1, rv;
710  node_t *v, *w;
711  int r;
712 
713  rv = 0;
714 
715  for (r = GD_maxrank(g); r >= GD_minrank(g); r--) {
716 
717  GD_rank(g)[r].candidate = FALSE;
718  for (i = 0; i < GD_rank(g)[r].n - 1; i++) {
719  v = GD_rank(g)[r].v[i];
720  w = GD_rank(g)[r].v[i + 1];
721  assert(ND_order(v) < ND_order(w));
722  if (left2right(g, v, w))
723  continue;
724  c0 = c1 = 0;
725  if (r > 0) {
726  c0 += in_cross(v, w);
727  c1 += in_cross(w, v);
728  }
729 
730  if (GD_rank(g)[r + 1].n > 0) {
731  c0 += out_cross(v, w);
732  c1 += out_cross(w, v);
733  }
734 #if 0
735  if ((c1 < c0) || ((c0 > 0) && reverse && (c1 == c0))) {
736  exchange(v, w);
737  rv += (c0 - c1);
738  GD_rank(Root)[r].valid = FALSE;
739  GD_rank(g)[r].candidate = TRUE;
740 
741  if (r > GD_minrank(g)) {
742  GD_rank(Root)[r - 1].valid = FALSE;
743  GD_rank(g)[r - 1].candidate = TRUE;
744  }
745  if (r < GD_maxrank(g)) {
746  GD_rank(Root)[r + 1].valid = FALSE;
747  GD_rank(g)[r + 1].candidate = TRUE;
748  }
749  }
750 #endif
751 
752  if (c1 <= c0) {
753  balanceNodes(g, r, v, w);
754  }
755  }
756  }
757  return rv;
758 }
759 
760 static int transpose_step(graph_t * g, int r, int reverse)
761 {
762  int i, c0, c1, rv;
763  node_t *v, *w;
764 
765  rv = 0;
766  GD_rank(g)[r].candidate = FALSE;
767  for (i = 0; i < GD_rank(g)[r].n - 1; i++) {
768  v = GD_rank(g)[r].v[i];
769  w = GD_rank(g)[r].v[i + 1];
770  assert(ND_order(v) < ND_order(w));
771  if (left2right(g, v, w))
772  continue;
773  c0 = c1 = 0;
774  if (r > 0) {
775  c0 += in_cross(v, w);
776  c1 += in_cross(w, v);
777  }
778  if (GD_rank(g)[r + 1].n > 0) {
779  c0 += out_cross(v, w);
780  c1 += out_cross(w, v);
781  }
782  if ((c1 < c0) || ((c0 > 0) && reverse && (c1 == c0))) {
783  exchange(v, w);
784  rv += (c0 - c1);
785  GD_rank(Root)[r].valid = FALSE;
786  GD_rank(g)[r].candidate = TRUE;
787 
788  if (r > GD_minrank(g)) {
789  GD_rank(Root)[r - 1].valid = FALSE;
790  GD_rank(g)[r - 1].candidate = TRUE;
791  }
792  if (r < GD_maxrank(g)) {
793  GD_rank(Root)[r + 1].valid = FALSE;
794  GD_rank(g)[r + 1].candidate = TRUE;
795  }
796  }
797  }
798  return rv;
799 }
800 
801 static void transpose(graph_t * g, int reverse)
802 {
803  int r, delta;
804 
805  for (r = GD_minrank(g); r <= GD_maxrank(g); r++)
806  GD_rank(g)[r].candidate = TRUE;
807  do {
808  delta = 0;
809 #ifdef NOTDEF
810  /* don't run both the upward and downward passes- they cancel.
811  i tried making it depend on whether an odd or even pass,
812  but that didn't help. */
813  for (r = GD_maxrank(g); r >= GD_minrank(g); r--)
814  if (GD_rank(g)[r].candidate)
815  delta += transpose_step(g, r, reverse);
816 #endif
817  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
818  if (GD_rank(g)[r].candidate) {
819  delta += transpose_step(g, r, reverse);
820  }
821  }
822  /*} while (delta > ncross(g)*(1.0 - Convergence)); */
823  } while (delta >= 1);
824 }
825 
826 static int mincross(graph_t * g, int startpass, int endpass, int doBalance)
827 {
828  int maxthispass, iter, trying, pass;
829  int cur_cross, best_cross;
830 
831  if (startpass > 1) {
832  cur_cross = best_cross = ncross(g);
833  save_best(g);
834  } else
835  cur_cross = best_cross = INT_MAX;
836  for (pass = startpass; pass <= endpass; pass++) {
837  if (pass <= 1) {
838  maxthispass = MIN(4, MaxIter);
839  if (g == dot_root(g))
840  build_ranks(g, pass);
841  if (pass == 0)
842  flat_breakcycles(g);
843  flat_reorder(g);
844 
845  if ((cur_cross = ncross(g)) <= best_cross) {
846  save_best(g);
847  best_cross = cur_cross;
848  }
849  trying = 0;
850  } else {
851  maxthispass = MaxIter;
852  if (cur_cross > best_cross)
853  restore_best(g);
854  cur_cross = best_cross;
855  }
856  trying = 0;
857  for (iter = 0; iter < maxthispass; iter++) {
858  if (Verbose)
859  fprintf(stderr,
860  "mincross: pass %d iter %d trying %d cur_cross %d best_cross %d\n",
861  pass, iter, trying, cur_cross, best_cross);
862  if (trying++ >= MinQuit)
863  break;
864  if (cur_cross == 0)
865  break;
866  mincross_step(g, iter);
867  if ((cur_cross = ncross(g)) <= best_cross) {
868  save_best(g);
869  if (cur_cross < Convergence * best_cross)
870  trying = 0;
871  best_cross = cur_cross;
872  }
873  }
874  if (cur_cross == 0)
875  break;
876  }
877  if (cur_cross > best_cross)
878  restore_best(g);
879  if (best_cross > 0) {
880  transpose(g, FALSE);
881  best_cross = ncross(g);
882  }
883  if (doBalance) {
884  for (iter = 0; iter < maxthispass; iter++)
885  balance(g);
886  }
887 
888  return best_cross;
889 }
890 
891 static void restore_best(graph_t * g)
892 {
893  node_t *n;
894  int i, r;
895 
896  /* for (n = GD_nlist(g); n; n = ND_next(n)) */
897  /* ND_order(n) = saveorder(n); */
898  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
899  for (i = 0; i < GD_rank(g)[r].n; i++) {
900  n = GD_rank(g)[r].v[i];
901  ND_order(n) = saveorder(n);
902  }
903  }
904  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
905  GD_rank(Root)[r].valid = FALSE;
906  qsort(GD_rank(g)[r].v, GD_rank(g)[r].n, sizeof(GD_rank(g)[0].v[0]),
907  (qsort_cmpf) nodeposcmpf);
908  }
909 }
910 
911 static void save_best(graph_t * g)
912 {
913  node_t *n;
914  /* for (n = GD_nlist(g); n; n = ND_next(n)) */
915  /* saveorder(n) = ND_order(n); */
916  int i, r;
917  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
918  for (i = 0; i < GD_rank(g)[r].n; i++) {
919  n = GD_rank(g)[r].v[i];
920  saveorder(n) = ND_order(n);
921  }
922  }
923 }
924 
925 /* merges the connected components of g */
926 static void merge_components(graph_t * g)
927 {
928  int c;
929  node_t *u, *v;
930 
931  if (GD_comp(g).size <= 1)
932  return;
933  u = NULL;
934  for (c = 0; c < GD_comp(g).size; c++) {
935  v = GD_comp(g).list[c];
936  if (u)
937  ND_next(u) = v;
938  ND_prev(v) = u;
939  while (ND_next(v)) {
940  v = ND_next(v);
941  }
942  u = v;
943  }
944  GD_comp(g).size = 1;
945  GD_nlist(g) = GD_comp(g).list[0];
946  GD_minrank(g) = GlobalMinRank;
947  GD_maxrank(g) = GlobalMaxRank;
948 }
949 
950 /* merge connected components, create globally consistent rank lists */
951 static void merge2(graph_t * g)
952 {
953  int i, r;
954  node_t *v;
955 
956  /* merge the components and rank limits */
957  merge_components(g);
958 
959  /* install complete ranks */
960  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
961  GD_rank(g)[r].n = GD_rank(g)[r].an;
962  GD_rank(g)[r].v = GD_rank(g)[r].av;
963  for (i = 0; i < GD_rank(g)[r].n; i++) {
964  v = GD_rank(g)[r].v[i];
965  if (v == NULL) {
966  if (Verbose)
967  fprintf(stderr,
968  "merge2: graph %s, rank %d has only %d < %d nodes\n",
969  agnameof(g), r, i, GD_rank(g)[r].n);
970  GD_rank(g)[r].n = i;
971  break;
972  }
973  ND_order(v) = i;
974  }
975  }
976 }
977 
978 static void cleanup2(graph_t * g, int nc)
979 {
980  int i, j, r, c;
981  node_t *v;
982  edge_t *e;
983 
984  if (TI_list) {
985  free(TI_list);
986  TI_list = NULL;
987  }
988  if (TE_list) {
989  free(TE_list);
990  TE_list = NULL;
991  }
992  /* fix vlists of clusters */
993  for (c = 1; c <= GD_n_cluster(g); c++)
994  rec_reset_vlists(GD_clust(g)[c]);
995 
996  /* remove node temporary edges for ordering nodes */
997  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
998  for (i = 0; i < GD_rank(g)[r].n; i++) {
999  v = GD_rank(g)[r].v[i];
1000  ND_order(v) = i;
1001  if (ND_flat_out(v).list) {
1002  for (j = 0; (e = ND_flat_out(v).list[j]); j++)
1003  if (ED_edge_type(e) == FLATORDER) {
1004  delete_flat_edge(e);
1005  free(e->base.data);
1006  free(e);
1007  j--;
1008  }
1009  }
1010  }
1011  free_matrix(GD_rank(g)[r].flat);
1012  }
1013  if (Verbose)
1014  fprintf(stderr, "mincross %s: %d crossings, %.2f secs.\n",
1015  agnameof(g), nc, elapsed_sec());
1016 }
1017 
1018 static node_t *neighbor(node_t * v, int dir)
1019 {
1020  node_t *rv;
1021 
1022  rv = NULL;
1023 assert(v);
1024  if (dir < 0) {
1025  if (ND_order(v) > 0)
1026  rv = GD_rank(Root)[ND_rank(v)].v[ND_order(v) - 1];
1027  } else
1028  rv = GD_rank(Root)[ND_rank(v)].v[ND_order(v) + 1];
1029 assert((rv == 0) || (ND_order(rv)-ND_order(v))*dir > 0);
1030  return rv;
1031 }
1032 
1033 static int is_a_normal_node_of(graph_t * g, node_t * v)
1034 {
1035  return ((ND_node_type(v) == NORMAL) && agcontains(g, v));
1036 }
1037 
1038 static int is_a_vnode_of_an_edge_of(graph_t * g, node_t * v)
1039 {
1040  if ((ND_node_type(v) == VIRTUAL)
1041  && (ND_in(v).size == 1) && (ND_out(v).size == 1)) {
1042  edge_t *e = ND_out(v).list[0];
1043  while (ED_edge_type(e) != NORMAL)
1044  e = ED_to_orig(e);
1045  if (agcontains(g, e))
1046  return TRUE;
1047  }
1048  return FALSE;
1049 }
1050 
1051 static int inside_cluster(graph_t * g, node_t * v)
1052 {
1053  return (is_a_normal_node_of(g, v) | is_a_vnode_of_an_edge_of(g, v));
1054 }
1055 
1056 static node_t *furthestnode(graph_t * g, node_t * v, int dir)
1057 {
1058  node_t *u, *rv;
1059 
1060  rv = u = v;
1061  while ((u = neighbor(u, dir))) {
1062  if (is_a_normal_node_of(g, u))
1063  rv = u;
1064  else if (is_a_vnode_of_an_edge_of(g, u))
1065  rv = u;
1066  }
1067  return rv;
1068 }
1069 
1071 {
1072  int r;
1073 
1074  if (GD_rankleader(g))
1075  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1076  GD_rankleader(g)[r] = GD_rank(g)[r].v[0];
1077  }
1078 }
1079 
1081 {
1082  int c;
1083 
1084  save_vlist(g);
1085  for (c = 1; c <= GD_n_cluster(g); c++)
1086  rec_save_vlists(GD_clust(g)[c]);
1087 }
1088 
1089 
1091 {
1092  int r, c;
1093  node_t *u, *v, *w;
1094 
1095  /* fix vlists of sub-clusters */
1096  for (c = 1; c <= GD_n_cluster(g); c++)
1097  rec_reset_vlists(GD_clust(g)[c]);
1098 
1099  if (GD_rankleader(g))
1100  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1101  v = GD_rankleader(g)[r];
1102 #ifdef DEBUG
1103  node_in_root_vlist(v);
1104 #endif
1105  u = furthestnode(g, v, -1);
1106  w = furthestnode(g, v, 1);
1107  GD_rankleader(g)[r] = u;
1108 #ifdef DEBUG
1109  assert(GD_rank(dot_root(g))[r].v[ND_order(u)] == u);
1110 #endif
1111  GD_rank(g)[r].v = GD_rank(dot_root(g))[r].v + ND_order(u);
1112  GD_rank(g)[r].n = ND_order(w) - ND_order(u) + 1;
1113  }
1114 }
1115 
1116 /* realFillRanks:
1117  * The structures in crossing minimization and positioning require
1118  * that clusters have some node on each rank. This function recursively
1119  * guarantees this property. It takes into account nodes and edges in
1120  * a cluster, the latter causing dummy nodes for intervening ranks.
1121  * For any rank without node, we create a real node of small size. This
1122  * is stored in the subgraph sg, for easy removal later.
1123  *
1124  * I believe it is not necessary to do this for the root graph, as these
1125  * are laid out one component at a time and these will necessarily have a
1126  * node on each rank from source to sink levels.
1127  */
1128 static Agraph_t*
1129 realFillRanks (Agraph_t* g, int rnks[], int rnks_sz, Agraph_t* sg)
1130 {
1131  int i, c;
1132  Agedge_t* e;
1133  Agnode_t* n;
1134 
1135  for (c = 1; c <= GD_n_cluster(g); c++)
1136  sg = realFillRanks (GD_clust(g)[c], rnks, rnks_sz, sg);
1137 
1138  if (dot_root(g) == g)
1139  return sg;
1140  memset (rnks, 0, sizeof(int)*rnks_sz);
1141  for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
1142  rnks[ND_rank(n)] = 1;
1143  for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
1144  for (i = ND_rank(n)+1; i <= ND_rank(aghead(e)); i++)
1145  rnks[i] = 1;
1146  }
1147  }
1148  for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
1149  if (rnks[i] == 0) {
1150  if (!sg) {
1151  sg = agsubg (dot_root(g), "_new_rank", 1);
1152  }
1153  n = agnode (sg, NULL, 1);
1154  agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);
1155  ND_rank(n) = i;
1156  ND_lw(n) = ND_rw(n) = 0.5;
1157  ND_ht(n) = 1;
1158  ND_UF_size(n) = 1;
1159  alloc_elist(4, ND_in(n));
1160  alloc_elist(4, ND_out(n));
1161  agsubnode (g, n, 1);
1162  }
1163  }
1164  return sg;
1165 }
1166 
1167 static void
1168 fillRanks (Agraph_t* g)
1169 {
1170  Agraph_t* sg;
1171  int rnks_sz = GD_maxrank(g) + 2;
1172  int* rnks = N_NEW(rnks_sz, int);
1173  sg = realFillRanks (g, rnks, rnks_sz, NULL);
1174  free (rnks);
1175 }
1176 
1177 static void init_mincross(graph_t * g)
1178 {
1179  int size;
1180 
1181  if (Verbose)
1182  start_timer();
1183 
1184  ReMincross = FALSE;
1185  Root = g;
1186  /* alloc +1 for the null terminator usage in do_ordering() */
1187  /* also, the +1 avoids attempts to alloc 0 sizes, something
1188  that efence complains about */
1189  size = agnedges(dot_root(g)) + 1;
1190  TE_list = N_NEW(size, edge_t *);
1191  TI_list = N_NEW(size, int);
1192  mincross_options(g);
1193  if (GD_flags(g) & NEW_RANK)
1194  fillRanks (g);
1195  class2(g);
1196  decompose(g, 1);
1197  allocate_ranks(g);
1198  ordered_edges(g);
1199  GlobalMinRank = GD_minrank(g);
1200  GlobalMaxRank = GD_maxrank(g);
1201 }
1202 
1204 {
1205  int j;
1206  Agedge_t *rev;
1207 
1208  if (!ND_flat_out(aghead(e)).list)
1209  rev = NULL;
1210  else
1211  for (j = 0; (rev = ND_flat_out(aghead(e)).list[j]); j++)
1212  if (aghead(rev) == agtail(e))
1213  break;
1214  if (rev) {
1215  merge_oneway(e, rev);
1216  if (ED_to_virt(e) == 0)
1217  ED_to_virt(e) = rev;
1218  if ((ED_edge_type(rev) == FLATORDER)
1219  && (ED_to_orig(rev) == 0))
1220  ED_to_orig(rev) = e;
1221  elist_append(e, ND_other(agtail(e)));
1222  } else {
1223  rev = new_virtual_edge(aghead(e), agtail(e), e);
1224  if (ED_edge_type(e) == FLATORDER)
1225  ED_edge_type(rev) = FLATORDER;
1226  else
1227  ED_edge_type(rev) = REVERSED;
1228  ED_label(rev) = ED_label(e);
1229  flat_edge(g, rev);
1230  }
1231 }
1232 
1233 static void flat_search(graph_t * g, node_t * v)
1234 {
1235  int i;
1236  boolean hascl;
1237  edge_t *e;
1238  adjmatrix_t *M = GD_rank(g)[ND_rank(v)].flat;
1239 
1240  ND_mark(v) = TRUE;
1241  ND_onstack(v) = TRUE;
1242  hascl = (GD_n_cluster(dot_root(g)) > 0);
1243  if (ND_flat_out(v).list)
1244  for (i = 0; (e = ND_flat_out(v).list[i]); i++) {
1245  if (hascl
1246  && NOT(agcontains(g, agtail(e)) && agcontains(g, aghead(e))))
1247  continue;
1248  if (ED_weight(e) == 0)
1249  continue;
1250  if (ND_onstack(aghead(e)) == TRUE) {
1251  assert(flatindex(aghead(e)) < M->nrows);
1252  assert(flatindex(agtail(e)) < M->ncols);
1253  ELT(M, flatindex(aghead(e)), flatindex(agtail(e))) = 1;
1254  delete_flat_edge(e);
1255  i--;
1256  if (ED_edge_type(e) == FLATORDER)
1257  continue;
1258  flat_rev(g, e);
1259  } else {
1260  assert(flatindex(aghead(e)) < M->nrows);
1261  assert(flatindex(agtail(e)) < M->ncols);
1262  ELT(M, flatindex(agtail(e)), flatindex(aghead(e))) = 1;
1263  if (ND_mark(aghead(e)) == FALSE)
1264  flat_search(g, aghead(e));
1265  }
1266  }
1267  ND_onstack(v) = FALSE;
1268 }
1269 
1270 static void flat_breakcycles(graph_t * g)
1271 {
1272  int i, r, flat;
1273  node_t *v;
1274 
1275  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1276  flat = 0;
1277  for (i = 0; i < GD_rank(g)[r].n; i++) {
1278  v = GD_rank(g)[r].v[i];
1279  ND_mark(v) = ND_onstack(v) = FALSE;
1280  flatindex(v) = i;
1281  if ((ND_flat_out(v).size > 0) && (flat == 0)) {
1282  GD_rank(g)[r].flat =
1283  new_matrix(GD_rank(g)[r].n, GD_rank(g)[r].n);
1284  flat = 1;
1285  }
1286  }
1287  if (flat) {
1288  for (i = 0; i < GD_rank(g)[r].n; i++) {
1289  v = GD_rank(g)[r].v[i];
1290  if (ND_mark(v) == FALSE)
1291  flat_search(g, v);
1292  }
1293  }
1294  }
1295 }
1296 
1297 /* allocate_ranks:
1298  * Allocate rank structure, determining number of nodes per rank.
1299  * Note that no nodes are put into the structure yet.
1300  */
1302 {
1303  int r, low, high, *cn;
1304  node_t *n;
1305  edge_t *e;
1306 
1307  cn = N_NEW(GD_maxrank(g) + 2, int); /* must be 0 based, not GD_minrank */
1308  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1309  cn[ND_rank(n)]++;
1310  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1311  low = ND_rank(agtail(e));
1312  high = ND_rank(aghead(e));
1313  if (low > high) {
1314  int t = low;
1315  low = high;
1316  high = t;
1317  }
1318  for (r = low + 1; r < high; r++)
1319  cn[r]++;
1320  }
1321  }
1322  GD_rank(g) = N_NEW(GD_maxrank(g) + 2, rank_t);
1323  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1324  GD_rank(g)[r].an = GD_rank(g)[r].n = cn[r];
1325  GD_rank(g)[r].av = GD_rank(g)[r].v = N_NEW(cn[r] + 1, node_t *);
1326  }
1327  free(cn);
1328 }
1329 
1330 /* install a node at the current right end of its rank */
1332 {
1333  int i, r;
1334 
1335  r = ND_rank(n);
1336  i = GD_rank(g)[r].n;
1337  if (GD_rank(g)[r].an <= 0) {
1338  agerr(AGERR, "install_in_rank, line %d: %s %s rank %d i = %d an = 0\n",
1339  __LINE__, agnameof(g), agnameof(n), r, i);
1340  return;
1341  }
1342 
1343  GD_rank(g)[r].v[i] = n;
1344  ND_order(n) = i;
1345  GD_rank(g)[r].n++;
1346  assert(GD_rank(g)[r].n <= GD_rank(g)[r].an);
1347 #ifdef DEBUG
1348  {
1349  node_t *v;
1350 
1351  for (v = GD_nlist(g); v; v = ND_next(v))
1352  if (v == n)
1353  break;
1354  assert(v != NULL);
1355  }
1356 #endif
1357  if (ND_order(n) > GD_rank(Root)[r].an) {
1358  agerr(AGERR, "install_in_rank, line %d: ND_order(%s) [%d] > GD_rank(Root)[%d].an [%d]\n",
1359  __LINE__, agnameof(n), ND_order(n), r, GD_rank(Root)[r].an);
1360  return;
1361  }
1362  if ((r < GD_minrank(g)) || (r > GD_maxrank(g))) {
1363  agerr(AGERR, "install_in_rank, line %d: rank %d not in rank range [%d,%d]\n",
1364  __LINE__, r, GD_minrank(g), GD_maxrank(g));
1365  return;
1366  }
1367  if (GD_rank(g)[r].v + ND_order(n) >
1368  GD_rank(g)[r].av + GD_rank(Root)[r].an) {
1369  agerr(AGERR, "install_in_rank, line %d: GD_rank(g)[%d].v + ND_order(%s) [%d] > GD_rank(g)[%d].av + GD_rank(Root)[%d].an [%d]\n",
1370  __LINE__, r, agnameof(n),GD_rank(g)[r].v + ND_order(n), r, r, GD_rank(g)[r].av+GD_rank(Root)[r].an);
1371  return;
1372  }
1373 }
1374 
1375 /* install nodes in ranks. the initial ordering ensure that series-parallel
1376  * graphs such as trees are drawn with no crossings. it tries searching
1377  * in- and out-edges and takes the better of the two initial orderings.
1378  */
1379 void build_ranks(graph_t * g, int pass)
1380 {
1381  int i, j;
1382  node_t *n, *n0;
1383  edge_t **otheredges;
1384  nodequeue *q;
1385 
1386  q = new_queue(GD_n_nodes(g));
1387  for (n = GD_nlist(g); n; n = ND_next(n))
1388  MARK(n) = FALSE;
1389 
1390 #ifdef DEBUG
1391  {
1392  edge_t *e;
1393  for (n = GD_nlist(g); n; n = ND_next(n)) {
1394  for (i = 0; (e = ND_out(n).list[i]); i++)
1395  assert(MARK(aghead(e)) == FALSE);
1396  for (i = 0; (e = ND_in(n).list[i]); i++)
1397  assert(MARK(agtail(e)) == FALSE);
1398  }
1399  }
1400 #endif
1401 
1402  for (i = GD_minrank(g); i <= GD_maxrank(g); i++)
1403  GD_rank(g)[i].n = 0;
1404 
1405  for (n = GD_nlist(g); n; n = ND_next(n)) {
1406  otheredges = ((pass == 0) ? ND_in(n).list : ND_out(n).list);
1407  if (otheredges[0] != NULL)
1408  continue;
1409  if (MARK(n) == FALSE) {
1410  MARK(n) = TRUE;
1411  enqueue(q, n);
1412  while ((n0 = dequeue(q))) {
1413  if (ND_ranktype(n0) != CLUSTER) {
1414  install_in_rank(g, n0);
1415  enqueue_neighbors(q, n0, pass);
1416  } else {
1417  install_cluster(g, n0, pass, q);
1418  }
1419  }
1420  }
1421  }
1422  if (dequeue(q))
1423  agerr(AGERR, "surprise\n");
1424  for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
1425  GD_rank(Root)[i].valid = FALSE;
1426  if (GD_flip(g) && (GD_rank(g)[i].n > 0)) {
1427  int n, ndiv2;
1428  node_t **vlist = GD_rank(g)[i].v;
1429  n = GD_rank(g)[i].n - 1;
1430  ndiv2 = n / 2;
1431  for (j = 0; j <= ndiv2; j++)
1432  exchange(vlist[j], vlist[n - j]);
1433  }
1434  }
1435 
1436  if ((g == dot_root(g)) && ncross(g) > 0)
1437  transpose(g, FALSE);
1438  free_queue(q);
1439 }
1440 
1441 void enqueue_neighbors(nodequeue * q, node_t * n0, int pass)
1442 {
1443  int i;
1444  edge_t *e;
1445 
1446  if (pass == 0) {
1447  for (i = 0; i < ND_out(n0).size; i++) {
1448  e = ND_out(n0).list[i];
1449  if ((MARK(aghead(e))) == FALSE) {
1450  MARK(aghead(e)) = TRUE;
1451  enqueue(q, aghead(e));
1452  }
1453  }
1454  } else {
1455  for (i = 0; i < ND_in(n0).size; i++) {
1456  e = ND_in(n0).list[i];
1457  if ((MARK(agtail(e))) == FALSE) {
1458  MARK(agtail(e)) = TRUE;
1459  enqueue(q, agtail(e));
1460  }
1461  }
1462  }
1463 }
1464 
1465 static int constraining_flat_edge(Agraph_t *g, Agnode_t *v, Agedge_t *e)
1466 {
1467  if (ED_weight(e) == 0) return FALSE;
1468  if (!inside_cluster(g,agtail(e))) return FALSE;
1469  if (!inside_cluster(g,aghead(e))) return FALSE;
1470  return TRUE;
1471 }
1472 
1473 
1474 /* construct nodes reachable from 'here' in post-order.
1475 * This is the same as doing a topological sort in reverse order.
1476 */
1477 static int postorder(graph_t * g, node_t * v, node_t ** list, int r)
1478 {
1479  edge_t *e;
1480  int i, cnt = 0;
1481 
1482  MARK(v) = TRUE;
1483  if (ND_flat_out(v).size > 0) {
1484  for (i = 0; (e = ND_flat_out(v).list[i]); i++) {
1485  if (!constraining_flat_edge(g,v,e)) continue;
1486  if (MARK(aghead(e)) == FALSE)
1487  cnt += postorder(g, aghead(e), list + cnt, r);
1488  }
1489  }
1490  assert(ND_rank(v) == r);
1491  list[cnt++] = v;
1492  return cnt;
1493 }
1494 
1495 static void flat_reorder(graph_t * g)
1496 {
1497  int i, j, r, pos, n_search, local_in_cnt, local_out_cnt, base_order;
1498  node_t *v, **left, **right, *t;
1499  node_t **temprank = NULL;
1500  edge_t *flat_e, *e;
1501 
1502  if (GD_has_flat_edges(g) == FALSE)
1503  return;
1504  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1505  if (GD_rank(g)[r].n == 0) continue;
1506  base_order = ND_order(GD_rank(g)[r].v[0]);
1507  for (i = 0; i < GD_rank(g)[r].n; i++)
1508  MARK(GD_rank(g)[r].v[i]) = FALSE;
1509  temprank = ALLOC(i + 1, temprank, node_t *);
1510  pos = 0;
1511 
1512  /* construct reverse topological sort order in temprank */
1513  for (i = 0; i < GD_rank(g)[r].n; i++) {
1514  if (GD_flip(g)) v = GD_rank(g)[r].v[i];
1515  else v = GD_rank(g)[r].v[GD_rank(g)[r].n - i - 1];
1516 
1517  local_in_cnt = local_out_cnt = 0;
1518  for (j = 0; j < ND_flat_in(v).size; j++) {
1519  flat_e = ND_flat_in(v).list[j];
1520  if (constraining_flat_edge(g,v,flat_e)) local_in_cnt++;
1521  }
1522  for (j = 0; j < ND_flat_out(v).size; j++) {
1523  flat_e = ND_flat_out(v).list[j];
1524  if (constraining_flat_edge(g,v,flat_e)) local_out_cnt++;
1525  }
1526  if ((local_in_cnt == 0) && (local_out_cnt == 0))
1527  temprank[pos++] = v;
1528  else {
1529  if ((MARK(v) == FALSE) && (local_in_cnt == 0)) {
1530  left = temprank + pos;
1531  n_search = postorder(g, v, left, r);
1532  pos += n_search;
1533  }
1534  }
1535  }
1536 
1537  if (pos) {
1538  if (GD_flip(g) == FALSE) {
1539  left = temprank;
1540  right = temprank + pos - 1;
1541  while (left < right) {
1542  t = *left;
1543  *left = *right;
1544  *right = t;
1545  left++;
1546  right--;
1547  }
1548  }
1549  for (i = 0; i < GD_rank(g)[r].n; i++) {
1550  v = GD_rank(g)[r].v[i] = temprank[i];
1551  ND_order(v) = i + base_order;
1552  }
1553 
1554  /* nonconstraint flat edges must be made LR */
1555  for (i = 0; i < GD_rank(g)[r].n; i++) {
1556  v = GD_rank(g)[r].v[i];
1557  if (ND_flat_out(v).list) {
1558  for (j = 0; (e = ND_flat_out(v).list[j]); j++) {
1559  if ( ((GD_flip(g) == FALSE) && (ND_order(aghead(e)) < ND_order(agtail(e)))) ||
1560  ( (GD_flip(g)) && (ND_order(aghead(e)) > ND_order(agtail(e)) ))) {
1561  assert(constraining_flat_edge(g,v,e) == FALSE);
1562  delete_flat_edge(e);
1563  j--;
1564  flat_rev(g, e);
1565  }
1566  }
1567  }
1568  }
1569  /* postprocess to restore intended order */
1570  }
1571  /* else do no harm! */
1572  GD_rank(Root)[r].valid = FALSE;
1573  }
1574  if (temprank)
1575  free(temprank);
1576 }
1577 
1578 static void reorder(graph_t * g, int r, int reverse, int hasfixed)
1579 {
1580  int changed = 0, nelt;
1581  boolean muststay, sawclust;
1582  node_t **vlist = GD_rank(g)[r].v;
1583  node_t **lp, **rp, **ep = vlist + GD_rank(g)[r].n;
1584 
1585  for (nelt = GD_rank(g)[r].n - 1; nelt >= 0; nelt--) {
1586  lp = vlist;
1587  while (lp < ep) {
1588  /* find leftmost node that can be compared */
1589  while ((lp < ep) && (ND_mval(*lp) < 0))
1590  lp++;
1591  if (lp >= ep)
1592  break;
1593  /* find the node that can be compared */
1594  sawclust = muststay = FALSE;
1595  for (rp = lp + 1; rp < ep; rp++) {
1596  if (sawclust && ND_clust(*rp))
1597  continue; /* ### */
1598  if (left2right(g, *lp, *rp)) {
1599  muststay = TRUE;
1600  break;
1601  }
1602  if (ND_mval(*rp) >= 0)
1603  break;
1604  if (ND_clust(*rp))
1605  sawclust = TRUE; /* ### */
1606  }
1607  if (rp >= ep)
1608  break;
1609  if (muststay == FALSE) {
1610  register int p1 = (ND_mval(*lp));
1611  register int p2 = (ND_mval(*rp));
1612  if ((p1 > p2) || ((p1 == p2) && (reverse))) {
1613  exchange(*lp, *rp);
1614  changed++;
1615  }
1616  }
1617  lp = rp;
1618  }
1619  if ((hasfixed == FALSE) && (reverse == FALSE))
1620  ep--;
1621  }
1622 
1623  if (changed) {
1624  GD_rank(Root)[r].valid = FALSE;
1625  if (r > 0)
1626  GD_rank(Root)[r - 1].valid = FALSE;
1627  }
1628 }
1629 
1630 static void mincross_step(graph_t * g, int pass)
1631 {
1632  int r, other, first, last, dir;
1633  int hasfixed, reverse;
1634 
1635  if ((pass % 4) < 2)
1636  reverse = TRUE;
1637  else
1638  reverse = FALSE;
1639  if (pass % 2) {
1640  r = GD_maxrank(g) - 1;
1641  dir = -1;
1642  } /* up pass */
1643  else {
1644  r = 1;
1645  dir = 1;
1646  } /* down pass */
1647 
1648  if (pass % 2 == 0) { /* down pass */
1649  first = GD_minrank(g) + 1;
1650  if (GD_minrank(g) > GD_minrank(Root))
1651  first--;
1652  last = GD_maxrank(g);
1653  dir = 1;
1654  } else { /* up pass */
1655  first = GD_maxrank(g) - 1;
1656  last = GD_minrank(g);
1657  if (GD_maxrank(g) < GD_maxrank(Root))
1658  first++;
1659  dir = -1;
1660  }
1661 
1662  for (r = first; r != last + dir; r += dir) {
1663  other = r - dir;
1664  hasfixed = medians(g, r, other);
1665  reorder(g, r, reverse, hasfixed);
1666  }
1667  transpose(g, NOT(reverse));
1668 }
1669 
1670 static int local_cross(elist l, int dir)
1671 {
1672  int i, j, is_out;
1673  int cross = 0;
1674  edge_t *e, *f;
1675  if (dir > 0)
1676  is_out = TRUE;
1677  else
1678  is_out = FALSE;
1679  for (i = 0; (e = l.list[i]); i++) {
1680  if (is_out)
1681  for (j = i + 1; (f = l.list[j]); j++) {
1682  if ((ND_order(aghead(f)) - ND_order(aghead(e)))
1683  * (ED_tail_port(f).p.x - ED_tail_port(e).p.x) < 0)
1684  cross += ED_xpenalty(e) * ED_xpenalty(f);
1685  } else
1686  for (j = i + 1; (f = l.list[j]); j++) {
1687  if ((ND_order(agtail(f)) - ND_order(agtail(e)))
1688  * (ED_head_port(f).p.x - ED_head_port(e).p.x) < 0)
1689  cross += ED_xpenalty(e) * ED_xpenalty(f);
1690  }
1691  }
1692  return cross;
1693 }
1694 
1695 static int rcross(graph_t * g, int r)
1696 {
1697  static int *Count, C;
1698  int top, bot, cross, max, i, k;
1699  node_t **rtop, *v;
1700 
1701  cross = 0;
1702  max = 0;
1703  rtop = GD_rank(g)[r].v;
1704 
1705  if (C <= GD_rank(Root)[r + 1].n) {
1706  C = GD_rank(Root)[r + 1].n + 1;
1707  Count = ALLOC(C, Count, int);
1708  }
1709 
1710  for (i = 0; i < GD_rank(g)[r + 1].n; i++)
1711  Count[i] = 0;
1712 
1713  for (top = 0; top < GD_rank(g)[r].n; top++) {
1714  register edge_t *e;
1715  if (max > 0) {
1716  for (i = 0; (e = ND_out(rtop[top]).list[i]); i++) {
1717  for (k = ND_order(aghead(e)) + 1; k <= max; k++)
1718  cross += Count[k] * ED_xpenalty(e);
1719  }
1720  }
1721  for (i = 0; (e = ND_out(rtop[top]).list[i]); i++) {
1722  register int inv = ND_order(aghead(e));
1723  if (inv > max)
1724  max = inv;
1725  Count[inv] += ED_xpenalty(e);
1726  }
1727  }
1728  for (top = 0; top < GD_rank(g)[r].n; top++) {
1729  v = GD_rank(g)[r].v[top];
1730  if (ND_has_port(v))
1731  cross += local_cross(ND_out(v), 1);
1732  }
1733  for (bot = 0; bot < GD_rank(g)[r + 1].n; bot++) {
1734  v = GD_rank(g)[r + 1].v[bot];
1735  if (ND_has_port(v))
1736  cross += local_cross(ND_in(v), -1);
1737  }
1738  return cross;
1739 }
1740 
1741 int ncross(graph_t * g)
1742 {
1743  int r, count, nc;
1744 
1745  g = Root;
1746  count = 0;
1747  for (r = GD_minrank(g); r < GD_maxrank(g); r++) {
1748  if (GD_rank(g)[r].valid)
1749  count += GD_rank(g)[r].cache_nc;
1750  else {
1751  nc = GD_rank(g)[r].cache_nc = rcross(g, r);
1752  count += nc;
1753  GD_rank(g)[r].valid = TRUE;
1754  }
1755  }
1756  return count;
1757 }
1758 
1759 static int ordercmpf(int *i0, int *i1)
1760 {
1761  return (*i0) - (*i1);
1762 }
1763 
1764 /* flat_mval:
1765  * Calculate a mval for nodes with no in or out non-flat edges.
1766  * Assume (ND_out(n).size == 0) && (ND_in(n).size == 0)
1767  * Find flat edge a->n where a has the largest order and set
1768  * n.mval = a.mval+1, assuming a.mval is defined (>=0).
1769  * If there are no flat in edges, find flat edge n->a where a
1770  * has the smallest order and set * n.mval = a.mval-1, assuming
1771  * a.mval is > 0.
1772  * Return true if n.mval is left -1, indicating a fixed node for sorting.
1773  */
1774 static int flat_mval(node_t * n)
1775 {
1776  int i;
1777  edge_t *e, **fl;
1778  node_t *nn;
1779 
1780  if (ND_flat_in(n).size > 0) {
1781  fl = ND_flat_in(n).list;
1782  nn = agtail(fl[0]);
1783  for (i = 1; (e = fl[i]); i++)
1784  if (ND_order(agtail(e)) > ND_order(nn))
1785  nn = agtail(e);
1786  if (ND_mval(nn) >= 0) {
1787  ND_mval(n) = ND_mval(nn) + 1;
1788  return FALSE;
1789  }
1790  } else if (ND_flat_out(n).size > 0) {
1791  fl = ND_flat_out(n).list;
1792  nn = aghead(fl[0]);
1793  for (i = 1; (e = fl[i]); i++)
1794  if (ND_order(aghead(e)) < ND_order(nn))
1795  nn = aghead(e);
1796  if (ND_mval(nn) > 0) {
1797  ND_mval(n) = ND_mval(nn) - 1;
1798  return FALSE;
1799  }
1800  }
1801  return TRUE;
1802 }
1803 
1804 #define VAL(node,port) (MC_SCALE * ND_order(node) + (port).order)
1805 
1806 static boolean medians(graph_t * g, int r0, int r1)
1807 {
1808  int i, j, j0, lm, rm, lspan, rspan, *list;
1809  node_t *n, **v;
1810  edge_t *e;
1811  boolean hasfixed = FALSE;
1812 
1813  list = TI_list;
1814  v = GD_rank(g)[r0].v;
1815  for (i = 0; i < GD_rank(g)[r0].n; i++) {
1816  n = v[i];
1817  j = 0;
1818  if (r1 > r0)
1819  for (j0 = 0; (e = ND_out(n).list[j0]); j0++) {
1820  if (ED_xpenalty(e) > 0)
1821  list[j++] = VAL(aghead(e), ED_head_port(e));
1822  } else
1823  for (j0 = 0; (e = ND_in(n).list[j0]); j0++) {
1824  if (ED_xpenalty(e) > 0)
1825  list[j++] = VAL(agtail(e), ED_tail_port(e));
1826  }
1827  switch (j) {
1828  case 0:
1829  ND_mval(n) = -1;
1830  break;
1831  case 1:
1832  ND_mval(n) = list[0];
1833  break;
1834  case 2:
1835  ND_mval(n) = (list[0] + list[1]) / 2;
1836  break;
1837  default:
1838  qsort(list, j, sizeof(int), (qsort_cmpf) ordercmpf);
1839  if (j % 2)
1840  ND_mval(n) = list[j / 2];
1841  else {
1842  /* weighted median */
1843  rm = j / 2;
1844  lm = rm - 1;
1845  rspan = list[j - 1] - list[rm];
1846  lspan = list[lm] - list[0];
1847  if (lspan == rspan)
1848  ND_mval(n) = (list[lm] + list[rm]) / 2;
1849  else {
1850  int w = list[lm] * rspan + list[rm] * lspan;
1851  ND_mval(n) = w / (lspan + rspan);
1852  }
1853  }
1854  }
1855  }
1856  for (i = 0; i < GD_rank(g)[r0].n; i++) {
1857  n = v[i];
1858  if ((ND_out(n).size == 0) && (ND_in(n).size == 0))
1859  hasfixed |= flat_mval(n);
1860  }
1861  return hasfixed;
1862 }
1863 
1864 static int nodeposcmpf(node_t ** n0, node_t ** n1)
1865 {
1866  return (ND_order(*n0) - ND_order(*n1));
1867 }
1868 
1869 static int edgeidcmpf(edge_t ** e0, edge_t ** e1)
1870 {
1871  return (AGSEQ(*e0) - AGSEQ(*e1));
1872 }
1873 
1874 /* following code deals with weights of edges of "virtual" nodes */
1875 #define ORDINARY 0
1876 #define SINGLETON 1
1877 #define VIRTUALNODE 2
1878 #define NTYPES 3
1879 
1880 #define C_EE 1
1881 #define C_VS 2
1882 #define C_SS 2
1883 #define C_VV 4
1884 
1885 static int table[NTYPES][NTYPES] = {
1886  /* ordinary */ {C_EE, C_EE, C_EE},
1887  /* singleton */ {C_EE, C_SS, C_VS},
1888  /* virtual */ {C_EE, C_VS, C_VV}
1889 };
1890 
1891 static int endpoint_class(node_t * n)
1892 {
1893  if (ND_node_type(n) == VIRTUAL)
1894  return VIRTUALNODE;
1895  if (ND_weight_class(n) <= 1)
1896  return SINGLETON;
1897  return ORDINARY;
1898 }
1899 
1901 {
1902  int t;
1903  t = table[endpoint_class(agtail(e))][endpoint_class(aghead(e))];
1904  ED_weight(e) *= t;
1905 }
1906 
1907 #ifdef DEBUG
1908 void check_rs(graph_t * g, int null_ok)
1909 {
1910  int i, r;
1911  node_t *v, *prev;
1912 
1913  fprintf(stderr, "\n\n%s:\n", agnameof(g));
1914  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1915  fprintf(stderr, "%d: ", r);
1916  prev = NULL;
1917  for (i = 0; i < GD_rank(g)[r].n; i++) {
1918  v = GD_rank(g)[r].v[i];
1919  if (v == NULL) {
1920  fprintf(stderr, "NULL\t");
1921  if (null_ok == FALSE)
1922  abort();
1923  } else {
1924  fprintf(stderr, "%s(%f)\t", agnameof(v), ND_mval(v));
1925  assert(ND_rank(v) == r);
1926  assert(v != prev);
1927  prev = v;
1928  }
1929  }
1930  fprintf(stderr, "\n");
1931  }
1932 }
1933 
1934 void check_order(void)
1935 {
1936  int i, r;
1937  node_t *v;
1938  graph_t *g = Root;
1939 
1940  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1941  assert(GD_rank(g)[r].v[GD_rank(g)[r].n] == NULL);
1942  for (i = 0; (v = GD_rank(g)[r].v[i]); i++) {
1943  assert(ND_rank(v) == r);
1944  assert(ND_order(v) == i);
1945  }
1946  }
1947 }
1948 #endif
1949 
1950 static void mincross_options(graph_t * g)
1951 {
1952  char *p;
1953  double f;
1954 
1955  /* set default values */
1956  MinQuit = 8;
1957  MaxIter = 24;
1958  Convergence = .995;
1959 
1960  p = agget(g, "mclimit");
1961  if (p && ((f = atof(p)) > 0.0)) {
1962  MinQuit = MAX(1, MinQuit * f);
1963  MaxIter = MAX(1, MaxIter * f);
1964  }
1965 }
1966 
1967 #ifdef DEBUG
1968 void check_exchange(node_t * v, node_t * w)
1969 {
1970  int i, r;
1971  node_t *u;
1972 
1973  if ((ND_clust(v) == NULL) && (ND_clust(w) == NULL))
1974  return;
1975  assert((ND_clust(v) == NULL) || (ND_clust(w) == NULL));
1976  assert(ND_rank(v) == ND_rank(w));
1977  assert(ND_order(v) < ND_order(w));
1978  r = ND_rank(v);
1979 
1980  for (i = ND_order(v) + 1; i < ND_order(w); i++) {
1981  u = GD_rank(dot_root(v))[r].v[i];
1982  if (ND_clust(u))
1983  abort();
1984  }
1985 }
1986 
1987 void check_vlists(graph_t * g)
1988 {
1989  int c, i, j, r;
1990  node_t *u;
1991 
1992  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
1993  for (i = 0; i < GD_rank(g)[r].n; i++) {
1994  u = GD_rank(g)[r].v[i];
1995  j = ND_order(u);
1996  assert(GD_rank(Root)[r].v[j] == u);
1997  }
1998  if (GD_rankleader(g)) {
1999  u = GD_rankleader(g)[r];
2000  j = ND_order(u);
2001  assert(GD_rank(Root)[r].v[j] == u);
2002  }
2003  }
2004  for (c = 1; c <= GD_n_cluster(g); c++)
2005  check_vlists(GD_clust(g)[c]);
2006 }
2007 
2008 void node_in_root_vlist(node_t * n)
2009 {
2010  node_t **vptr;
2011 
2012  for (vptr = GD_rank(Root)[ND_rank(n)].v; *vptr; vptr++)
2013  if (*vptr == n)
2014  break;
2015  if (*vptr == 0)
2016  abort();
2017 }
2018 #endif /* DEBUG code */
CGRAPH_API int agdeledge(Agraph_t *g, Agedge_t *arg_e)
Definition: edge.c:357
int x
Definition: mincross.c:153
#define MAX(a, b)
Definition: agerror.c:17
#define AGSEQ(obj)
Definition: cgraph.h:115
#define ND_rank(n)
Definition: types.h:529
CGRAPH_API Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
Definition: cgraph.h:388
CGRAPH_API Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
Definition: graph.c:44
#define GD_nlist(g)
Definition: types.h:401
void start_timer(void)
Definition: timing.c:45
#define N_NEW(n, t)
Definition: memory.h:36
#define elist_append(item, L)
Definition: types.h:272
#define ND_x(n)
Definition: mincross.c:157
#define GD_rankleader(g)
Definition: types.h:405
CGRAPH_API int agdegree(Agraph_t *g, Agnode_t *n, int in, int out)
Definition: graph.c:229
#define SINGLETON
Definition: mincross.c:1876
CGRAPH_API int agdelnode(Agraph_t *g, Agnode_t *arg_n)
Definition: node.c:192
#define FLATORDER
Definition: const.h:31
Agedge_t * find_flat_edge(Agnode_t *, Agnode_t *)
Definition: fastgr.c:57
#define MIN(a, b)
Definition: arith.h:35
#define exchange(h, i, j)
Definition: closest.c:93
#define ND_idx(n)
Definition: mincross.c:161
#define GD_n_cluster(g)
Definition: types.h:396
#define ND_lo(n)
Definition: mincross.c:158
#define C_VV
Definition: mincross.c:1883
CGRAPH_API Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition: edge.c:56
#define ND_node_type(n)
Definition: types.h:518
#define ALLOC(size, ptr, type)
Definition: memory.h:41
#define MARK(v)
Definition: mincross.c:25
#define ED_head_port(e)
Definition: types.h:591
#define C
Definition: pack.c:29
#define ND_flat_in(n)
Definition: types.h:498
#define assert(x)
Definition: cghdr.h:47
void rec_reset_vlists(Agraph_t *)
Definition: mincross.c:1090
void decompose(graph_t *g, int pass)
Definition: decomp.c:200
#define ND_UF_size(n)
Definition: types.h:493
EXTERN Agsym_t * G_ordering
Definition: globals.h:88
#define ED_to_orig(e)
Definition: types.h:601
void checkLabelOrder(graph_t *g)
Definition: mincross.c:287
#define ED_weight(e)
Definition: types.h:606
#define ED_label(e)
Definition: types.h:592
#define GD_has_flat_edges(g)
Definition: types.h:374
#define GD_flags(g)
Definition: types.h:369
void build_ranks(Agraph_t *, int)
Definition: mincross.c:1379
int ncross(Agraph_t *)
Definition: mincross.c:1741
void delete_flat_edge(Agedge_t *)
Definition: fastgr.c:267
#define alloc_elist(n, L)
Definition: types.h:273
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
CGRAPH_API Agraph_t * agfstsubg(Agraph_t *g)
Definition: subg.c:72
CGRAPH_API int agcontains(Agraph_t *, void *)
Definition: obj.c:245
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
int ncols
Definition: types.h:206
void enqueue(nodequeue *q, node_t *n)
Definition: utils.c:51
#define ND_mark(n)
Definition: types.h:514
void allocate_ranks(Agraph_t *)
Definition: mincross.c:1301
int is_cluster(Agraph_t *)
Definition: rank.c:585
#define ND_clust(n)
Definition: types.h:495
char * agget(void *obj, char *name)
Definition: attr.c:428
#define C_SS
Definition: mincross.c:1882
CGRAPH_API Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
nodequeue * new_queue(int sz)
Definition: utils.c:34
CGRAPH_API Agdesc_t Agstrictdirected
Definition: cgraph.h:419
#define NEW_RANK
Definition: const.h:279
char * data
Definition: types.h:207
CGRAPH_API Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition: subg.c:52
#define VAL(node, port)
Definition: mincross.c:1804
#define ED_tail_port(e)
Definition: types.h:600
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
Definition: types.h:261
#define ND_ht(n)
Definition: types.h:506
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
#define max(x, y)
Definition: stress.c:794
#define ND_order(n)
Definition: types.h:520
CGRAPH_API int agclose(Agraph_t *g)
Definition: graph.c:93
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define ND_mval(n)
Definition: types.h:515
#define VIRTUAL
Definition: const.h:28
#define GD_maxrank(g)
Definition: types.h:389
int n
Definition: types.h:211
void mark_lowclusters(Agraph_t *root)
Definition: cluster.c:395
void flat_rev(Agraph_t *g, Agedge_t *e)
Definition: mincross.c:1203
#define ELT(M, i, j)
Definition: mincross.c:385
void merge_oneway(Agedge_t *, Agedge_t *)
Definition: fastgr.c:334
int(* qsort_cmpf)(const void *, const void *)
Definition: types.h:45
#define ND_has_port(n)
Definition: types.h:501
#define ND_rw(n)
Definition: types.h:531
#define NTYPES
Definition: mincross.c:1878
#define C_VS
Definition: mincross.c:1881
edge_t ** list
Definition: types.h:262
node_t * dequeue(nodequeue *q)
Definition: utils.c:58
#define REVERSED
Definition: const.h:30
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Definition: grammar.c:79
#define GD_clust(g)
Definition: types.h:364
Definition: cgraph.h:83
Agraph_t * parent
Definition: cgraph.h:247
#define GD_flip(g)
Definition: types.h:385
Agobj_t base
Definition: cgraph.h:140
Agraph_t * dot_root(void *p)
Definition: dotinit.c:513
void rec_save_vlists(Agraph_t *)
Definition: mincross.c:1080
void free_queue(nodequeue *q)
Definition: utils.c:45
void flat_edge(Agraph_t *, Agedge_t *)
Definition: fastgr.c:260
#define GD_n_nodes(g)
Definition: types.h:397
Agedge_t * new_virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:162
#define ED_to_virt(e)
Definition: types.h:602
#define ND_lw(n)
Definition: types.h:513
#define ND_alg(n)
Definition: types.h:490
#define NULL
Definition: logic.h:39
node_t ** v
Definition: types.h:212
#define CLUSTER
Definition: const.h:43
#define ND_np(n)
Definition: mincross.c:160
#define ND_hi(n)
Definition: mincross.c:159
#define ND_onstack(n)
Definition: types.h:519
#define NOT(x)
Definition: cgraph.h:41
double elapsed_sec(void)
Definition: timing.c:50
#define ND_in(n)
Definition: types.h:507
void save_vlist(Agraph_t *)
Definition: mincross.c:1070
#define right(i)
Definition: closest.c:87
#define streq(s, t)
Definition: cghdr.h:52
#define ND_next(n)
Definition: types.h:517
EXTERN unsigned char Verbose
Definition: globals.h:64
#define top(sp)
Definition: stack.h:35
#define GD_comp(g)
Definition: types.h:366
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
int nrows
Definition: types.h:205
Agrec_t * data
Definition: cgraph.h:109
boolean mapbool(char *p)
Definition: utils.c:472
#define ND_out(n)
Definition: types.h:522
CGRAPH_API Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
#define VIRTUALNODE
Definition: mincross.c:1877
EXTERN Agsym_t * N_ordering
Definition: globals.h:95
#define ED_xpenalty(e)
Definition: types.h:604
#define ND_ranktype(n)
Definition: types.h:530
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
#define ND_other(n)
Definition: types.h:521
#define left
Definition: dthdr.h:16
void install_in_rank(Agraph_t *, Agnode_t *)
Definition: mincross.c:1331
CGRAPH_API Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition: edge.c:70
void class2(graph_t *g)
Definition: class2.c:172
#define C_EE
Definition: mincross.c:1880
void virtual_weight(Agedge_t *)
Definition: mincross.c:1900
char * late_string(void *obj, attrsym_t *attr, char *def)
Definition: utils.c:122
#define ND_weight_class(n)
Definition: types.h:541
CGRAPH_API int agnedges(Agraph_t *g)
Definition: graph.c:167
#define GD_minrank(g)
Definition: types.h:391
bool rm(Agraph_t *g)
Definition: gv.cpp:765
Agrec_t h
Definition: mincross.c:152
#define ORDINARY
Definition: mincross.c:1875
void enqueue_neighbors(nodequeue *q, node_t *n0, int pass)
Definition: mincross.c:1441
#define saveorder(v)
Definition: mincross.c:26
#define ND_flat_out(n)
Definition: types.h:499
#define GD_rank(g)
Definition: types.h:404
Definition: types.h:210
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define NORMAL
Definition: const.h:27
#define isBackedge(e)
Definition: mincross.c:175
Agnode_t * np
Definition: mincross.c:154
void expand_cluster(graph_t *subg)
Definition: cluster.c:282
#define ND_prev(n)
Definition: types.h:527
#define ED_edge_type(e)
Definition: types.h:585
EXTERN int MaxIter
Definition: globals.h:78
#define FALSE
Definition: cgraph.h:35
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
void dot_mincross(Agraph_t *, int)
Definition: mincross.c:332
void install_cluster(graph_t *g, node_t *n, int pass, nodequeue *q)
Definition: cluster.c:379
#define flatindex(v)
Definition: mincross.c:27
#define INT_MAX
Definition: arith.h:52
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:38