Graphviz  2.41.20170921.2350
rank.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  * Rank the nodes of a directed graph, subject to user-defined
17  * sets of nodes to be kept on the same, min, or max rank.
18  * The temporary acyclic fast graph is constructed and ranked
19  * by a network-simplex technique. Then ranks are propagated
20  * to non-leader nodes and temporary edges are deleted.
21  * Leaf nodes and top-level clusters are left collapsed, though.
22  * Assigns global minrank and maxrank of graph and all clusters.
23  *
24  * TODO: safety code. must not be in two clusters at same level.
25  * must not be in same/min/max/rank and a cluster at the same time.
26  * watch out for interactions between leaves and clusters.
27  */
28 
29 #include "dot.h"
30 
31 static void dot1_rank(graph_t * g, aspect_t* asp);
32 static void dot2_rank(graph_t * g, aspect_t* asp);
33 
34 static void
35 renewlist(elist * L)
36 {
37  int i;
38  for (i = L->size; i >= 0; i--)
39  L->list[i] = NULL;
40  L->size = 0;
41 }
42 
43 static void
44 cleanup1(graph_t * g)
45 {
46  node_t *n;
47  edge_t *e, *f;
48  int c;
49 
50  for (c = 0; c < GD_comp(g).size; c++) {
51  GD_nlist(g) = GD_comp(g).list[c];
52  for (n = GD_nlist(g); n; n = ND_next(n)) {
53  renewlist(&ND_in(n));
54  renewlist(&ND_out(n));
55  ND_mark(n) = FALSE;
56  }
57  }
58  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
59  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
60  f = ED_to_virt(e);
61  /* Null out any other references to f to make sure we don't
62  * handle it a second time. For example, parallel multiedges
63  * share a virtual edge.
64  */
65  if (f && (e == ED_to_orig(f))) {
66  edge_t *e1, *f1;
67  node_t *n1;
68  for (n1 = agfstnode(g); n1; n1 = agnxtnode(g, n1)) {
69  for (e1 = agfstout(g, n1); e1; e1 = agnxtout(g, e1)) {
70  if (e != e1) {
71  f1 = ED_to_virt(e1);
72  if (f1 && (f == f1)) {
73  ED_to_virt(e1) = NULL;
74  }
75  }
76  }
77  }
78  free(f->base.data);
79  free(f);
80  }
81  ED_to_virt(e) = NULL;
82  }
83  }
84  free(GD_comp(g).list);
85  GD_comp(g).list = NULL;
86  GD_comp(g).size = 0;
87 }
88 
89 /* When there are edge labels, extra ranks are reserved here for the virtual
90  * nodes of the labels. This is done by doubling the input edge lengths.
91  * The input rank separation is adjusted to compensate.
92  */
93 static void
94 edgelabel_ranks(graph_t * g)
95 {
96  node_t *n;
97  edge_t *e;
98 
99  if (GD_has_labels(g->root) & EDGE_LABEL) {
100  for (n = agfstnode(g); n; n = agnxtnode(g, n))
101  for (e = agfstout(g, n); e; e = agnxtout(g, e))
102  ED_minlen(e) *= 2;
103  GD_ranksep(g) = (GD_ranksep(g) + 1) / 2;
104  }
105 }
106 
107 /* Merge the nodes of a min, max, or same rank set. */
108 static void
109 collapse_rankset(graph_t * g, graph_t * subg, int kind)
110 {
111  node_t *u, *v;
112 
113  u = v = agfstnode(subg);
114  if (u) {
115  ND_ranktype(u) = kind;
116  while ((v = agnxtnode(subg, v))) {
117  UF_union(u, v);
118  ND_ranktype(v) = ND_ranktype(u);
119  }
120  switch (kind) {
121  case MINRANK:
122  case SOURCERANK:
123  if (GD_minset(g) == NULL)
124  GD_minset(g) = u;
125  else
126  GD_minset(g) = UF_union(GD_minset(g), u);
127  break;
128  case MAXRANK:
129  case SINKRANK:
130  if (GD_maxset(g) == NULL)
131  GD_maxset(g) = u;
132  else
133  GD_maxset(g) = UF_union(GD_maxset(g), u);
134  break;
135  }
136  switch (kind) {
137  case SOURCERANK:
138  ND_ranktype(GD_minset(g)) = kind;
139  break;
140  case SINKRANK:
141  ND_ranktype(GD_maxset(g)) = kind;
142  break;
143  }
144  }
145 }
146 
147 static int
148 rank_set_class(graph_t * g)
149 {
150  static char *name[] = { "same", "min", "source", "max", "sink", NULL };
151  static int class[] =
153  int val;
154 
155  if (is_cluster(g))
156  return CLUSTER;
157  val = maptoken(agget(g, "rank"), name, class);
158  GD_set_type(g) = val;
159  return val;
160 }
161 
162 static int
163 make_new_cluster(graph_t * g, graph_t * subg)
164 {
165  int cno;
166  cno = ++(GD_n_cluster(g));
167  GD_clust(g) = ZALLOC(cno + 1, GD_clust(g), graph_t *, GD_n_cluster(g));
168  GD_clust(g)[cno] = subg;
169  do_graph_label(subg);
170  return cno;
171 }
172 
173 static void
174 node_induce(graph_t * par, graph_t * g)
175 {
176  node_t *n, *nn;
177  edge_t *e;
178  int i;
179 
180  /* enforce that a node is in at most one cluster at this level */
181  for (n = agfstnode(g); n; n = nn) {
182  nn = agnxtnode(g, n);
183  if (ND_ranktype(n)) {
184  agdelete(g, n);
185  continue;
186  }
187  for (i = 1; i < GD_n_cluster(par); i++)
188  if (agcontains(GD_clust(par)[i], n))
189  break;
190  if (i < GD_n_cluster(par))
191  agdelete(g, n);
192  ND_clust(n) = NULL;
193  }
194 
195  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
196  for (e = agfstout(dot_root(g), n); e; e = agnxtout(dot_root(g), e)) {
197  if (agcontains(g, aghead(e)))
198  agsubedge(g,e,1);
199  }
200  }
201 }
202 
203 void
205 {
206  node_t *n, *leader = NULL;
207  GD_minrank(g) = MAXSHORT;
208  GD_maxrank(g) = -1;
209  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
210  if (GD_maxrank(g) < ND_rank(n))
211  GD_maxrank(g) = ND_rank(n);
212  if (GD_minrank(g) > ND_rank(n))
213  GD_minrank(g) = ND_rank(n);
214  if (leader == NULL)
215  leader = n;
216  else {
217  if (ND_rank(n) < ND_rank(leader))
218  leader = n;
219  }
220  }
221  GD_leader(g) = leader;
222 }
223 
224 static void
225 cluster_leader(graph_t * clust)
226 {
227  node_t *leader, *n;
228  int maxrank = 0;
229 
230  /* find number of ranks and select a leader */
231  leader = NULL;
232  for (n = GD_nlist(clust); n; n = ND_next(n)) {
233  if ((ND_rank(n) == 0) && (ND_node_type(n) == NORMAL))
234  leader = n;
235  if (maxrank < ND_rank(n))
236  maxrank = ND_rank(n);
237  }
238  assert(leader != NULL);
239  GD_leader(clust) = leader;
240 
241  for (n = agfstnode(clust); n; n = agnxtnode(clust, n)) {
242  assert((ND_UF_size(n) <= 1) || (n == leader));
243  UF_union(n, leader);
244  ND_ranktype(n) = CLUSTER;
245  }
246 }
247 
248 /*
249  * A cluster is collapsed in three steps.
250  * 1) The nodes of the cluster are ranked locally.
251  * 2) The cluster is collapsed into one node on the least rank.
252  * 3) In class1(), any inter-cluster edges are converted using
253  * the "virtual node + 2 edges" trick.
254  */
255 static void
256 collapse_cluster(graph_t * g, graph_t * subg)
257 {
258  if (GD_parent(subg)) {
259  return;
260  }
261  GD_parent(subg) = g;
262  node_induce(g, subg);
263  if (agfstnode(subg) == NULL)
264  return;
265  make_new_cluster(g, subg);
266  if (CL_type == LOCAL) {
267  dot1_rank(subg, 0);
268  cluster_leader(subg);
269  } else
270  dot_scan_ranks(subg);
271 }
272 
273 /* Execute union commands for "same rank" subgraphs and clusters. */
274 static void
275 collapse_sets(graph_t *rg, graph_t *g)
276 {
277  int c;
278  graph_t *subg;
279 #ifdef OBSOLETE
280  node_t *n;
281 #endif
282 
283  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
284  c = rank_set_class(subg);
285  if (c) {
286  if ((c == CLUSTER) && CL_type == LOCAL)
287  collapse_cluster(rg, subg);
288  else
289  collapse_rankset(rg, subg, c);
290  }
291  else collapse_sets(rg, subg);
292 
293 #ifdef OBSOLETE
294  Collapsing leaves is currently obsolete
295 
296  /* mark nodes with ordered edges so their leaves are not collapsed */
297  if (agget(subg, "ordering"))
298  for (n = agfstnode(subg); n; n = agnxtnode(subg, n))
299  ND_order(n) = 1;
300 #endif
301  }
302 }
303 
304 static void
305 find_clusters(graph_t * g)
306 {
307  graph_t *subg;
308  for (subg = agfstsubg(dot_root(g)); subg; subg = agnxtsubg(subg)) {
309  if (GD_set_type(subg) == CLUSTER)
310  collapse_cluster(g, subg);
311  }
312 }
313 
314 static void
315 set_minmax(graph_t * g)
316 {
317  int c;
318 
319  GD_minrank(g) += ND_rank(GD_leader(g));
320  GD_maxrank(g) += ND_rank(GD_leader(g));
321  for (c = 1; c <= GD_n_cluster(g); c++)
322  set_minmax(GD_clust(g)[c]);
323 }
324 
325 /* To ensure that min and max rank nodes always have the intended rank
326  * assignment, reverse any incompatible edges.
327  */
328 static point
329 minmax_edges(graph_t * g)
330 {
331  node_t *n;
332  edge_t *e;
333  point slen;
334 
335  slen.x = slen.y = 0;
336  if ((GD_maxset(g) == NULL) && (GD_minset(g) == NULL))
337  return slen;
338  if (GD_minset(g) != NULL)
339  GD_minset(g) = UF_find(GD_minset(g));
340  if (GD_maxset(g) != NULL)
341  GD_maxset(g) = UF_find(GD_maxset(g));
342 
343  if ((n = GD_maxset(g))) {
344  slen.y = (ND_ranktype(GD_maxset(g)) == SINKRANK);
345  while ((e = ND_out(n).list[0])) {
346  assert(aghead(e) == UF_find(aghead(e)));
347  reverse_edge(e);
348  }
349  }
350  if ((n = GD_minset(g))) {
351  slen.x = (ND_ranktype(GD_minset(g)) == SOURCERANK);
352  while ((e = ND_in(n).list[0])) {
353  assert(agtail(e) == UF_find(agtail(e)));
354  reverse_edge(e);
355  }
356  }
357  return slen;
358 }
359 
360 static int
361 minmax_edges2(graph_t * g, point slen)
362 {
363  node_t *n;
364  edge_t *e = 0;
365 
366  if ((GD_maxset(g)) || (GD_minset(g))) {
367  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
368  if (n != UF_find(n))
369  continue;
370  if ((ND_out(n).size == 0) && GD_maxset(g) && (n != GD_maxset(g))) {
371  e = virtual_edge(n, GD_maxset(g), NULL);
372  ED_minlen(e) = slen.y;
373  ED_weight(e) = 0;
374  }
375  if ((ND_in(n).size == 0) && GD_minset(g) && (n != GD_minset(g))) {
376  e = virtual_edge(GD_minset(g), n, NULL);
377  ED_minlen(e) = slen.x;
378  ED_weight(e) = 0;
379  }
380  }
381  }
382  return (e != 0);
383 }
384 
385 /* Run the network simplex algorithm on each component. */
386 void rank1(graph_t * g)
387 {
388  int maxiter = INT_MAX;
389  int c;
390  char *s;
391 
392  if ((s = agget(g, "nslimit1")))
393  maxiter = atof(s) * agnnodes(g);
394  for (c = 0; c < GD_comp(g).size; c++) {
395  GD_nlist(g) = GD_comp(g).list[c];
396  rank(g, (GD_n_cluster(g) == 0 ? 1 : 0), maxiter); /* TB balance */
397  }
398 }
399 
400 /*
401  * Assigns ranks of non-leader nodes.
402  * Expands same, min, max rank sets.
403  * Leaf sets and clusters remain merged.
404  * Sets minrank and maxrank appropriately.
405  */
406 static void expand_ranksets(graph_t * g, aspect_t* asp)
407 {
408  int c;
409  node_t *n, *leader;
410 
411  if ((n = agfstnode(g))) {
412  GD_minrank(g) = MAXSHORT;
413  GD_maxrank(g) = -1;
414  while (n) {
415  leader = UF_find(n);
416  /* The following works because ND_rank(n) == 0 if n is not in a
417  * cluster, and ND_rank(n) = the local rank offset if n is in
418  * a cluster. */
419  if ((leader != n) && (!asp || (ND_rank(n) == 0)))
420  ND_rank(n) += ND_rank(leader);
421 
422  if (GD_maxrank(g) < ND_rank(n))
423  GD_maxrank(g) = ND_rank(n);
424  if (GD_minrank(g) > ND_rank(n))
425  GD_minrank(g) = ND_rank(n);
426 
427  if (ND_ranktype(n) && (ND_ranktype(n) != LEAFSET))
428  UF_singleton(n);
429  n = agnxtnode(g, n);
430  }
431  if (g == dot_root(g)) {
432  if (CL_type == LOCAL) {
433  for (c = 1; c <= GD_n_cluster(g); c++)
434  set_minmax(GD_clust(g)[c]);
435  } else {
436  find_clusters(g);
437  }
438  }
439  } else {
440  GD_minrank(g) = GD_maxrank(g) = 0;
441  }
442 }
443 
444 #ifdef ALLOW_LEVELS
445 void
446 setRanks (graph_t* g, attrsym_t* lsym)
447 {
448  node_t* n;
449  char* s;
450  char* ep;
451  long v;
452 
453  for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
454  s = agxget (n, lsym);
455  v = strtol (s, &ep, 10);
456  if (ep == s)
457  agerr(AGWARN, "no level attribute for node \"%s\"\n", agnameof(n));
458  ND_rank(n) = v;
459  }
460 }
461 #endif
462 
463 #ifdef UNUSED
464 static node_t **virtualEdgeHeadList = NULL;
465 static node_t **virtualEdgeTailList = NULL;
466 static int nVirtualEdges = 0;
467 
468 static void
469 saveVirtualEdges(graph_t *g)
470 {
471  edge_t *e;
472  node_t *n;
473  int cnt = 0;
474  int lc;
475 
476  if (virtualEdgeHeadList != NULL) {
477  free(virtualEdgeHeadList);
478  }
479  if (virtualEdgeTailList != NULL) {
480  free(virtualEdgeTailList);
481  }
482 
483  /* allocate memory */
484  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
485  for (lc = 0; lc < ND_in(n).size; lc++) {
486  e = ND_in(n).list[lc];
487  if (ED_edge_type(e) == VIRTUAL) cnt++;
488  }
489  }
490 
491  nVirtualEdges = cnt;
492  virtualEdgeHeadList = N_GNEW(cnt, node_t*);
493  virtualEdgeTailList = N_GNEW(cnt, node_t*);
494 
495  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
496  for (lc = 0, cnt = 0; lc < ND_in(n).size; lc++) {
497  e = ND_in(n).list[lc];
498  if (ED_edge_type(e) == VIRTUAL) {
499  virtualEdgeHeadList[cnt] = e->head;
500  virtualEdgeTailList[cnt] = e->tail;
501  if (Verbose)
502  printf("saved virtual edge: %s->%s\n",
503  virtualEdgeTailList[cnt]->name,
504  virtualEdgeHeadList[cnt]->name);
505  cnt++;
506  }
507  }
508  }
509 }
510 
511 static void
512 restoreVirtualEdges(graph_t *g)
513 {
514  int i;
515  edge_t e;
516 
517  for (i = 0; i < nVirtualEdges; i++) {
518  if (virtualEdgeTailList[i] && virtualEdgeHeadList[i]) {
519  if (Verbose)
520  printf("restoring virtual edge: %s->%s\n",
521  virtualEdgeTailList[i]->name, virtualEdgeHeadList[i]->name);
522  virtual_edge(virtualEdgeTailList[i], virtualEdgeHeadList[i], NULL);
523  }
524  }
525  if (Verbose)
526  printf("restored %d virt edges\n", nVirtualEdges);
527 }
528 #endif
529 
530 /* dot1_rank:
531  * asp != NULL => g is root
532  */
533 static void dot1_rank(graph_t * g, aspect_t* asp)
534 {
535  point p;
536 #ifdef ALLOW_LEVELS
537  attrsym_t* N_level;
538 #endif
539  edgelabel_ranks(g);
540 
541  if (asp) {
542  init_UF_size(g);
543  initEdgeTypes(g);
544  }
545 
546  collapse_sets(g,g);
547  /*collapse_leaves(g); */
548  class1(g);
549  p = minmax_edges(g);
550  decompose(g, 0);
551  if (asp && ((GD_comp(g).size > 1)||(GD_n_cluster(g) > 0))) {
552  asp->badGraph = 1;
553  asp = NULL;
554  }
555  acyclic(g);
556  if (minmax_edges2(g, p))
557  decompose(g, 0);
558 #ifdef ALLOW_LEVELS
559  if ((N_level = agattr(g,AGNODE,"level",NULL)))
560  setRanks(g, N_level);
561  else
562 #endif
563 
564  if (asp)
565  rank3(g, asp);
566  else
567  rank1(g);
568 
569  expand_ranksets(g, asp);
570  cleanup1(g);
571 }
572 
573 void dot_rank(graph_t * g, aspect_t* asp)
574 {
575  if (agget (g, "newrank")) {
576  GD_flags(g) |= NEW_RANK;
577  dot2_rank (g, asp);
578  }
579  else
580  dot1_rank (g, asp);
581  if (Verbose)
582  fprintf (stderr, "Maxrank = %d, minrank = %d\n", GD_maxrank(g), GD_minrank(g));
583 }
584 
586 {
587  return (strncmp(agnameof(g), "cluster", 7) == 0);
588 }
589 
590 #ifdef OBSOLETE
591 static node_t*
592 merge_leaves(graph_t * g, node_t * cur, node_t * new)
593 {
594  node_t *rv;
595 
596  if (cur == NULL)
597  rv = new;
598  else {
599  rv = UF_union(cur, new);
600  ND_ht(rv) = MAX(ND_ht(cur), ND_ht(new));
601  ND_lw(rv) = ND_lw(cur) + ND_lw(new) + GD_nodesep(g) / 2;
602  ND_rw(rv) = ND_rw(cur) + ND_rw(new) + GD_nodesep(g) / 2;
603  }
604  return rv;
605 }
606 
607 static void
608 potential_leaf(graph_t * g, edge_t * e, node_t * leaf)
609 {
610  node_t *par;
611 
612  if ((ED_tail_port(e).p.x) || (ED_head_port(e).p.x))
613  return;
614  if ((ED_minlen(e) != 1) || (ND_order(agtail(e)) > 0))
615  return;
616  par = ((leaf != aghead(e)) ? aghead(e) : agtail(e));
617  ND_ranktype(leaf) = LEAFSET;
618  if (par == agtail(e))
619  GD_outleaf(par) = merge_leaves(g, GD_outleaf(par), leaf);
620  else
621  GD_inleaf(par) = merge_leaves(g, GD_inleaf(par), leaf);
622 }
623 
624 static void
625 collapse_leaves(graph_t * g)
626 {
627  node_t *n;
628  edge_t *e;
629 
630  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
631 
632  /* consider n as a potential leaf of some other node. */
633  if ((ND_ranktype(n) != NOCMD) || (ND_order(n)))
634  continue;
635  if (agfstout(g, n) == NULL) {
636  if ((e = agfstin(g, n)) && (agnxtin(g, e) == NULL)) {
637  potential_leaf(g, AGMKOUT(e), n);
638  continue;
639  }
640  }
641  if (agfstin(g, n) == NULL) {
642  if ((e = agfstout(g, n)) && (agnxtout(g, e) == NULL)) {
643  potential_leaf(g, e, n);
644  continue;
645  }
646  }
647  }
648 }
649 #endif
650 
651 /* new ranking code:
652  * Allows more constraints
653  * Copy of level.c in dotgen2
654  * Many of the utility functions are simpler or gone with
655  * cgraph library.
656  */
657 #define BACKWARD_PENALTY 1000
658 #define STRONG_CLUSTER_WEIGHT 1000
659 #define NORANK 6
660 #define ROOT "\177root"
661 #define TOPNODE "\177top"
662 #define BOTNODE "\177bot"
663 
664 /* hops is not used in dot, so we overload it to
665  * contain the index of the connected component
666  */
667 #define ND_comp(n) ND_hops(n)
668 
669 extern int rank2(Agraph_t *, int, int, int);
670 
671 static void set_parent(graph_t* g, graph_t* p)
672 {
673  GD_parent(g) = p;
674  make_new_cluster(p, g);
675  node_induce(p, g);
676 }
677 
678 static int is_empty(graph_t * g)
679 {
680  return (!agfstnode(g));
681 }
682 
683 static int is_a_strong_cluster(graph_t * g)
684 {
685  int rv;
686  char *str = agget(g, "compact");
687  /* rv = mapBool((str), TRUE); */
688  rv = mapBool((str), FALSE);
689  return rv;
690 }
691 
692 static int rankset_kind(graph_t * g)
693 {
694  char *str = agget(g, "rank");
695 
696  if (str && str[0]) {
697  if (!strcmp(str, "min"))
698  return MINRANK;
699  if (!strcmp(str, "source"))
700  return SOURCERANK;
701  if (!strcmp(str, "max"))
702  return MAXRANK;
703  if (!strcmp(str, "sink"))
704  return SINKRANK;
705  if (!strcmp(str, "same"))
706  return SAMERANK;
707  }
708  return NORANK;
709 }
710 
711 static int is_nonconstraint(edge_t * e)
712 {
713  char *constr;
714 
715  if (E_constr && (constr = agxget(e, E_constr))) {
716  if (constr[0] && mapbool(constr) == FALSE)
717  return TRUE;
718  }
719  return FALSE;
720 }
721 
722 static node_t *find(node_t * n)
723 {
724  node_t *set;
725  if ((set = ND_set(n))) {
726  if (set != n)
727  set = ND_set(n) = find(set);
728  } else
729  set = ND_set(n) = n;
730  return set;
731 }
732 
733 static node_t *union_one(node_t * leader, node_t * n)
734 {
735  if (n)
736  return (ND_set(find(n)) = find(leader));
737  else
738  return leader;
739 }
740 
741 static node_t *union_all(graph_t * g)
742 {
743  node_t *n, *leader;
744 
745  n = agfstnode(g);
746  if (!n)
747  return n;
748  leader = find(n);
749  while ((n = agnxtnode(g, n)))
750  union_one(leader, n);
751  return leader;
752 }
753 
754 static void compile_samerank(graph_t * ug, graph_t * parent_clust)
755 {
756  graph_t *s; /* subgraph being scanned */
757  graph_t *clust; /* cluster that contains the rankset */
758  node_t *n, *leader;
759 
760  if (is_empty(ug))
761  return;
762  if (is_a_cluster(ug)) {
763  clust = ug;
764  if (parent_clust) {
765  GD_level(ug) = GD_level(parent_clust) + 1;
766  set_parent(ug, parent_clust);
767  }
768  else
769  GD_level(ug) = 0;
770  } else
771  clust = parent_clust;
772 
773  /* process subgraphs of this subgraph */
774  for (s = agfstsubg(ug); s; s = agnxtsubg(s))
775  compile_samerank(s, clust);
776 
777  /* process this subgraph as a cluster */
778  if (is_a_cluster(ug)) {
779  for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
780  if (ND_clust(n) == 0)
781  ND_clust(n) = ug;
782 #ifdef DEBUG
783  fprintf(stderr, "(%s) %s %p\n", agnameof(ug), agnameof(n),
784  ND_clust(n));
785 #endif
786  }
787  }
788 
789  /* process this subgraph as a rankset */
790  switch (rankset_kind(ug)) {
791  case SOURCERANK:
792  GD_has_sourcerank(clust) = TRUE; /* fall through */
793  case MINRANK:
794  leader = union_all(ug);
795  GD_minrep(clust) = union_one(leader, GD_minrep(clust));
796  break;
797  case SINKRANK:
798  GD_has_sinkrank(clust) = TRUE; /* fall through */
799  case MAXRANK:
800  leader = union_all(ug);
801  GD_maxrep(clust) = union_one(leader, GD_maxrep(clust));
802  break;
803  case SAMERANK:
804  leader = union_all(ug);
805  /* do we need to record these ranksets? */
806  break;
807  case NORANK:
808  break;
809  default: /* unrecognized - warn and do nothing */
810  agerr(AGWARN, "%s has unrecognized rank=%s", agnameof(ug),
811  agget(ug, "rank"));
812  }
813 
814  /* a cluster may become degenerate */
815  if (is_a_cluster(ug) && GD_minrep(ug)) {
816  if (GD_minrep(ug) == GD_maxrep(ug)) {
817  node_t *up = union_all(ug);
818  GD_minrep(ug) = up;
819  GD_maxrep(ug) = up;
820  }
821  }
822 }
823 
824 static graph_t *dot_lca(graph_t * c0, graph_t * c1)
825 {
826  while (c0 != c1) {
827  if (GD_level(c0) >= GD_level(c1))
828  c0 = GD_parent(c0);
829  else
830  c1 = GD_parent(c1);
831  }
832  return c0;
833 }
834 
835 static int is_internal_to_cluster(edge_t * e)
836 {
837  graph_t *par, *ct, *ch;
838  ct = ND_clust(agtail(e));
839  ch = ND_clust(aghead(e));
840  if (ct == ch)
841  return TRUE;
842  par = dot_lca(ct, ch);
843  /* if (par == agroot(par)) */
844  /* return FALSE; */
845  if ((par == ct) || (par == ch))
846  return TRUE;
847  return FALSE;
848 }
849 
850 static node_t* Last_node;
851 static node_t* makeXnode (graph_t* G, char* name)
852 {
853  node_t *n = agnode(G, name, 1);
854  alloc_elist(4, ND_in(n));
855  alloc_elist(4, ND_out(n));
856  if (Last_node) {
857  ND_prev(n) = Last_node;
858  ND_next(Last_node) = n;
859  } else {
860  ND_prev(n) = NULL;
861  GD_nlist(G) = n;
862  }
863  Last_node = n;
864  ND_next(n) = NULL;
865 
866  return n;
867 }
868 
869 static void compile_nodes(graph_t * g, graph_t * Xg)
870 {
871  /* build variables */
872  node_t *n;
873 
874  Last_node = NULL;
875  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
876  if (find(n) == n)
877  ND_rep(n) = makeXnode (Xg, agnameof(n));
878  }
879  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
880  if (ND_rep(n) == 0)
881  ND_rep(n) = ND_rep(find(n));
882  }
883 }
884 
885 static void merge(edge_t * e, int minlen, int weight)
886 {
887  ED_minlen(e) = MAX(ED_minlen(e), minlen);
888  ED_weight(e) += weight;
889 }
890 
891 static void strong(graph_t * g, node_t * t, node_t * h, edge_t * orig)
892 {
893  edge_t *e;
894  if ((e = agfindedge(g, t, h)) ||
895  (e = agfindedge(g, h, t)) || (e = agedge(g, t, h, 0, 1)))
896  merge(e, ED_minlen(orig), ED_weight(orig));
897  else
898  agerr(AGERR, "ranking: failure to create strong constraint edge between nodes %s and %s\n",
899  agnameof(t), agnameof(h));
900 }
901 
902 static void weak(graph_t * g, node_t * t, node_t * h, edge_t * orig)
903 {
904  node_t *v;
905  edge_t *e, *f;
906  static int id;
907  char buf[100];
908 
909  for (e = agfstin(g, t); e; e = agnxtin(g, e)) {
910  /* merge with existing weak edge (e,f) */
911  v = agtail(e);
912  if ((f = agfstout(g, v)) && (aghead(f) == h)) {
913  return;
914  }
915  }
916  if (!e) {
917  sprintf (buf, "_weak_%d", id++);
918  v = makeXnode(g, buf);
919  e = agedge(g, v, t, 0, 1);
920  f = agedge(g, v, h, 0, 1);
921  }
922  ED_minlen(e) = MAX(ED_minlen(e), 0); /* effectively a nop */
923  ED_weight(e) += ED_weight(orig) * BACKWARD_PENALTY;
924  ED_minlen(f) = MAX(ED_minlen(f), ED_minlen(orig));
925  ED_weight(f) += ED_weight(orig);
926 }
927 
928 static void compile_edges(graph_t * ug, graph_t * Xg)
929 {
930  node_t *n;
931  edge_t *e;
932  node_t *Xt, *Xh;
933  graph_t *tc, *hc;
934 
935  /* build edge constraints */
936  for (n = agfstnode(ug); n; n = agnxtnode(ug, n)) {
937  Xt = ND_rep(n);
938  for (e = agfstout(ug, n); e; e = agnxtout(ug, e)) {
939  if (is_nonconstraint(e))
940  continue;
941  Xh = ND_rep(find(aghead(e)));
942  if (Xt == Xh)
943  continue;
944 
945  tc = ND_clust(agtail(e));
946  hc = ND_clust(aghead(e));
947 
948  if (is_internal_to_cluster(e)) {
949  /* determine if graph requires reversed edge */
950  if ((find(agtail(e)) == GD_maxrep(ND_clust(agtail(e))))
951  || (find(aghead(e)) == GD_minrep(ND_clust(aghead(e))))) {
952  node_t *temp = Xt;
953  Xt = Xh;
954  Xh = temp;
955  }
956  strong(Xg, Xt, Xh, e);
957  } else {
958  if (is_a_strong_cluster(tc) || is_a_strong_cluster(hc))
959  weak(Xg, Xt, Xh, e);
960  else
961  strong(Xg, Xt, Xh, e);
962  }
963  }
964  }
965 }
966 
967 static void compile_clusters(graph_t* g, graph_t* Xg, node_t* top, node_t* bot)
968 {
969  node_t *n;
970  node_t *rep;
971  edge_t *e;
972  graph_t *sub;
973 
974  if (is_a_cluster(g) && is_a_strong_cluster(g)) {
975  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
976  if (agfstin(g, n) == 0) {
977  rep = ND_rep(find(n));
978  if (!top) top = makeXnode(Xg,TOPNODE);
979  agedge(Xg, top, rep, 0, 1);
980  }
981  if (agfstout(g, n) == 0) {
982  rep = ND_rep(find(n));
983  if (!bot) bot = makeXnode(Xg,BOTNODE);
984  agedge(Xg, rep, bot, 0, 1);
985  }
986  }
987  if (top && bot) {
988  e = agedge(Xg, top, bot, 0, 1);
989  merge(e, 0, STRONG_CLUSTER_WEIGHT);
990  }
991  }
992  for (sub = agfstsubg(g); sub; sub = agnxtsubg(sub))
993  compile_clusters(sub, Xg, top, bot);
994 }
995 
996 static void reverse_edge2(graph_t * g, edge_t * e)
997 {
998  edge_t *rev;
999 
1000  rev = agfindedge(g, aghead(e), agtail(e));
1001  if (!rev)
1002  rev = agedge(g, aghead(e), agtail(e), 0, 1);
1003  merge(rev, ED_minlen(e), ED_weight(e));
1004  agdelete(g, e);
1005 }
1006 
1007 static void dfs(graph_t * g, node_t * v)
1008 {
1009  edge_t *e, *f;
1010  node_t *w;
1011 
1012  if (ND_mark(v))
1013  return;
1014  ND_mark(v) = TRUE;
1015  ND_onstack(v) = TRUE;
1016  for (e = agfstout(g, v); e; e = f) {
1017  f = agnxtout(g, e);
1018  w = aghead(e);
1019  if (ND_onstack(w))
1020  reverse_edge2(g, e);
1021  else {
1022  if (ND_mark(w) == FALSE)
1023  dfs(g, w);
1024  }
1025  }
1026  ND_onstack(v) = FALSE;
1027 }
1028 
1029 static void break_cycles(graph_t * g)
1030 {
1031  node_t *n;
1032 
1033  for (n = agfstnode(g); n; n = agnxtnode(g, n))
1034  ND_mark(n) = ND_onstack(n) = FALSE;
1035  for (n = agfstnode(g); n; n = agnxtnode(g, n))
1036  dfs(g, n);
1037 }
1038 /* setMinMax:
1039  * This will only be called with the root graph or a cluster
1040  * which are guaranteed to contain nodes. Thus, leader will be
1041  * set.
1042  */
1043 static void setMinMax (graph_t* g, int doRoot)
1044 {
1045  int c, v;
1046  node_t *n;
1047  node_t* leader = NULL;
1048 
1049  /* Do child clusters */
1050  for (c = 1; c <= GD_n_cluster(g); c++)
1051  setMinMax(GD_clust(g)[c], 0);
1052 
1053  if (!GD_parent(g) && !doRoot) // root graph
1054  return;
1055 
1056  GD_minrank(g) = MAXSHORT;
1057  GD_maxrank(g) = -1;
1058  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1059  v = ND_rank(n);
1060  if (GD_maxrank(g) < v)
1061  GD_maxrank(g) = v;
1062  if (GD_minrank(g) > v) {
1063  GD_minrank(g) = v;
1064  leader = n;
1065  }
1066  }
1067  GD_leader(g) = leader;
1068 }
1069 
1070 /* readout_levels:
1071  * Store node rank information in original graph.
1072  * Set rank bounds in graph and clusters
1073  * Free added data structures.
1074  *
1075  * rank2 is called with balance=1, which ensures that minrank=0
1076  */
1077 static void readout_levels(graph_t * g, graph_t * Xg, int ncc)
1078 {
1079  node_t *n;
1080  node_t *xn;
1081  int* minrk = NULL;
1082  int doRoot = 0;
1083 
1084  GD_minrank(g) = MAXSHORT;
1085  GD_maxrank(g) = -1;
1086  if (ncc > 1) {
1087  int i;
1088  minrk = N_NEW(ncc+1,int);
1089  for (i = 1; i <= ncc; i++)
1090  minrk[i] = MAXSHORT;
1091  }
1092  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1093  xn = ND_rep(find(n));
1094  ND_rank(n) = ND_rank(xn);
1095  if (GD_maxrank(g) < ND_rank(n))
1096  GD_maxrank(g) = ND_rank(n);
1097  if (GD_minrank(g) > ND_rank(n))
1098  GD_minrank(g) = ND_rank(n);
1099  if (minrk) {
1100  ND_comp(n) = ND_comp(xn);
1101  minrk[ND_comp(n)] = MIN(minrk[ND_comp(n)],ND_rank(n));
1102  }
1103  }
1104  if (minrk) {
1105  for (n = agfstnode(g); n; n = agnxtnode(g, n))
1106  ND_rank(n) -= minrk[ND_comp(n)];
1107  /* Non-uniform shifting, so recompute maxrank/minrank of root graph */
1108  doRoot = 1;
1109  }
1110  else if (GD_minrank(g) > 0) { /* should never happen */
1111  int delta = GD_minrank(g);
1112  for (n = agfstnode(g); n; n = agnxtnode(g, n))
1113  ND_rank(n) -= delta;
1114  GD_minrank(g) -= delta;
1115  GD_maxrank(g) -= delta;
1116  }
1117 
1118  setMinMax(g, doRoot);
1119 
1120  /* release fastgraph memory from Xg */
1121  for (n = agfstnode(Xg); n; n = agnxtnode(Xg, n)) {
1122  free_list(ND_in(n));
1123  free_list(ND_out(n));
1124  }
1125 
1126  free(ND_alg(agfstnode(g)));
1127  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1128  ND_alg(n) = NULL;
1129  }
1130  if (minrk)
1131  free (minrk);
1132 }
1133 
1134 static void dfscc(graph_t * g, node_t * n, int cc)
1135 {
1136  edge_t *e;
1137  if (ND_comp(n) == 0) {
1138  ND_comp(n) = cc;
1139  for (e = agfstout(g, n); e; e = agnxtout(g, e))
1140  dfscc(g, aghead(e), cc);
1141  for (e = agfstin(g, n); e; e = agnxtin(g, e))
1142  dfscc(g, agtail(e), cc);
1143  }
1144 }
1145 
1146 static int connect_components(graph_t * g)
1147 {
1148  int cc = 0;
1149  node_t *n;
1150 
1151  for (n = agfstnode(g); n; n = agnxtnode(g, n))
1152  ND_comp(n) = 0;
1153  for (n = agfstnode(g); n; n = agnxtnode(g, n))
1154  if (ND_comp(n) == 0)
1155  dfscc(g, n, ++cc);
1156  if (cc > 1) {
1157  node_t *root = makeXnode(g, ROOT);
1158  int ncc = 1;
1159  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1160  if (ND_comp(n) == ncc) {
1161  (void) agedge(g, root, n, 0, 1);
1162  ncc++;
1163  }
1164  }
1165  }
1166  return (cc);
1167 }
1168 
1169 static void add_fast_edges (graph_t * g)
1170 {
1171  node_t *n;
1172  edge_t *e;
1173  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1174  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
1175  elist_append(e, ND_out(n));
1176  elist_append(e, ND_in(aghead(e)));
1177  }
1178  }
1179 }
1180 
1181 static void my_init_graph(Agraph_t *g, Agobj_t *graph, void *arg)
1182 { int *sz = arg; agbindrec(graph,"level graph rec",sz[0],TRUE); }
1183 static void my_init_node(Agraph_t *g, Agobj_t *node, void *arg)
1184 { int *sz = arg; agbindrec(node,"level node rec",sz[1],TRUE); }
1185 static void my_init_edge(Agraph_t *g, Agobj_t *edge, void *arg)
1186 { int *sz = arg; agbindrec(edge,"level edge rec",sz[2],TRUE); }
1187 static Agcbdisc_t mydisc = { {my_init_graph,0,0}, {my_init_node,0,0}, {my_init_edge,0,0} };
1188 
1189 int infosizes[] = {
1190  sizeof(Agraphinfo_t),
1191  sizeof(Agnodeinfo_t),
1192  sizeof(Agedgeinfo_t)
1193 };
1194 
1195 void dot2_rank(graph_t * g, aspect_t* asp)
1196 {
1197  int ssize;
1198  int ncc, maxiter = INT_MAX;
1199  char *s;
1200  graph_t *Xg;
1201 
1202  Last_node = NULL;
1203  Xg = agopen("level assignment constraints", Agstrictdirected, 0);
1204  agbindrec(Xg,"level graph rec",sizeof(Agraphinfo_t),TRUE);
1205  agpushdisc(Xg,&mydisc,infosizes);
1206 
1207  edgelabel_ranks(g);
1208 
1209  if ((s = agget(g, "nslimit1")))
1210  maxiter = atof(s) * agnnodes(g);
1211  else
1212  maxiter = INT_MAX;
1213 
1214  compile_samerank(g, 0);
1215  compile_nodes(g, Xg);
1216  compile_edges(g, Xg);
1217  compile_clusters(g, Xg, 0, 0);
1218  break_cycles(Xg);
1219  ncc = connect_components(Xg);
1220  add_fast_edges (Xg);
1221 
1222  if (asp) {
1223  init_UF_size(Xg);
1224  initEdgeTypes(Xg);
1225  }
1226 
1227  if ((s = agget(g, "searchsize")))
1228  ssize = atoi(s);
1229  else
1230  ssize = -1;
1231  rank2(Xg, 1, maxiter, ssize);
1232 /* fastgr(Xg); */
1233  readout_levels(g, Xg, ncc);
1234 #ifdef DEBUG
1235  fprintf (stderr, "Xg %d nodes %d edges\n", agnnodes(Xg), agnedges(Xg));
1236 #endif
1237  agclose(Xg);
1238 }
#define MAX(a, b)
Definition: agerror.c:17
#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 MAXRANK
Definition: const.h:40
#define GD_has_labels(g)
Definition: types.h:372
#define GD_nlist(g)
Definition: types.h:401
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
#define N_NEW(n, t)
Definition: memory.h:36
#define elist_append(item, L)
Definition: types.h:272
#define ND_rep(n)
Definition: types.h:502
#define GD_leader(g)
Definition: types.h:382
void acyclic(graph_t *g)
Definition: acyclic.c:57
#define MIN(a, b)
Definition: arith.h:35
#define GD_n_cluster(g)
Definition: types.h:396
#define BOTNODE
Definition: rank.c:662
void class1(graph_t *g)
Definition: class1.c:66
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 ED_head_port(e)
Definition: types.h:591
void dot_scan_ranks(graph_t *g)
Definition: rank.c:204
#define GD_has_sinkrank(g)
Definition: types.h:376
#define assert(x)
Definition: cghdr.h:47
void decompose(graph_t *g, int pass)
Definition: decomp.c:200
#define ND_UF_size(n)
Definition: types.h:493
#define ED_to_orig(e)
Definition: types.h:601
CGRAPH_API void agpushdisc(Agraph_t *g, Agcbdisc_t *disc, void *state)
Definition: obj.c:202
#define ED_weight(e)
Definition: types.h:606
#define GD_flags(g)
Definition: types.h:369
CGRAPH_API int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
#define GD_maxset(g)
Definition: types.h:390
#define GD_parent(g)
Definition: types.h:354
void initEdgeTypes(graph_t *g)
Definition: aspect.c:1595
void do_graph_label(graph_t *sg)
Definition: input.c:892
#define alloc_elist(n, L)
Definition: types.h:273
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
#define GD_outleaf(g)
Definition: types.h:403
#define ROOT
Definition: rank.c:660
CGRAPH_API Agraph_t * agfstsubg(Agraph_t *g)
Definition: subg.c:72
CGRAPH_API int agcontains(Agraph_t *, void *)
Definition: obj.c:245
EXTERN Agsym_t * E_constr
Definition: globals.h:107
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
#define SOURCERANK
Definition: const.h:39
#define ND_mark(n)
Definition: types.h:514
int x
Definition: geom.h:26
void rank1(graph_t *g)
Definition: rank.c:386
int node_induce(Agraph_t *g, Agraph_t *eg)
Definition: ccomps.c:500
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:199
#define GD_ranksep(g)
Definition: types.h:406
int is_cluster(Agraph_t *)
Definition: rank.c:585
#define ZALLOC(size, ptr, type, osize)
Definition: memory.h:43
#define ND_clust(n)
Definition: types.h:495
Definition: cgraph.h:388
char * agget(void *obj, char *name)
Definition: attr.c:428
node_t * UF_find(node_t *n)
Definition: utils.c:146
#define GD_inleaf(g)
Definition: types.h:379
CGRAPH_API Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
#define MINRANK
Definition: const.h:38
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
CGRAPH_API Agdesc_t Agstrictdirected
Definition: cgraph.h:419
#define NEW_RANK
Definition: const.h:279
#define GD_set_type(g)
Definition: types.h:408
#define ED_tail_port(e)
Definition: types.h:600
int rank(graph_t *g, int balance, int maxiter)
Definition: ns.c:866
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 SINKRANK
Definition: const.h:41
#define ND_order(n)
Definition: types.h:520
#define TOPNODE
Definition: rank.c:661
#define SAMERANK
Definition: const.h:37
CGRAPH_API int agclose(Agraph_t *g)
Definition: graph.c:93
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define NOCMD
Definition: const.h:36
#define VIRTUAL
Definition: const.h:28
#define GD_maxrank(g)
Definition: types.h:389
void dot_rank(Agraph_t *, aspect_t *)
Definition: rank.c:573
int badGraph
Definition: aspect.h:24
int infosizes[]
Definition: rank.c:1189
#define LEAFSET
Definition: const.h:42
#define ND_rw(n)
Definition: types.h:531
CGRAPH_API Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition: edge.c:378
edge_t ** list
Definition: types.h:262
#define ND_comp(n)
Definition: rank.c:667
#define AGMKOUT(e)
Definition: cgraph.h:404
EXTERN int CL_type
Definition: globals.h:75
boolean mapBool(char *p, boolean dflt)
Definition: utils.c:454
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Definition: grammar.c:79
#define GD_clust(g)
Definition: types.h:364
Agraph_t * graph(char *name)
Definition: gv.cpp:38
#define AGNODE
Definition: cgraph.h:101
#define STRONG_CLUSTER_WEIGHT
Definition: rank.c:658
Agobj_t base
Definition: cgraph.h:140
Agraph_t * dot_root(void *p)
Definition: dotinit.c:513
void UF_singleton(node_t *u)
Definition: utils.c:188
#define MAXSHORT
Definition: arith.h:60
#define sub(h, i)
Definition: closest.c:75
#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
#define CLUSTER
Definition: const.h:43
#define ND_onstack(n)
Definition: types.h:519
#define GD_level(g)
Definition: types.h:355
Definition: geom.h:26
#define GD_has_sourcerank(g)
Definition: types.h:375
#define ND_in(n)
Definition: types.h:507
#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
void init_UF_size(graph_t *g)
Definition: aspect.c:1969
int is_a_cluster(Agraph_t *g)
Definition: utils.c:915
boolean mapbool(char *p)
Definition: utils.c:472
Agrec_t * data
Definition: cgraph.h:109
Agnode_t * node(Agraph_t *g, char *name)
Definition: gv.cpp:103
#define ND_out(n)
Definition: types.h:522
struct Agedgeinfo_t Agedgeinfo_t
int rank2(graph_t *g, int balance, int maxiter, int search_size)
Definition: ns.c:794
CGRAPH_API Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
int size
Definition: types.h:263
struct Agraphinfo_t Agraphinfo_t
void reverse_edge(edge_t *e)
Definition: acyclic.c:21
#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
CGRAPH_API Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition: edge.c:70
#define agfindedge(g, t, h)
Definition: types.h:610
#define GD_minset(g)
Definition: types.h:392
#define GD_maxrep(g)
Definition: types.h:394
CGRAPH_API int agnedges(Agraph_t *g)
Definition: graph.c:167
#define GD_nodesep(g)
Definition: types.h:402
#define GD_minrank(g)
Definition: types.h:391
#define NORANK
Definition: rank.c:659
agxbuf * str
Definition: htmlparse.c:85
Agraph_t * root
Definition: cgraph.h:247
#define LOCAL
Definition: const.h:46
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define NORMAL
Definition: const.h:27
#define EDGE_LABEL
Definition: const.h:184
#define BACKWARD_PENALTY
Definition: rank.c:657
int y
Definition: geom.h:26
int maptoken(char *p, char **name, int *val)
Definition: utils.c:443
#define ND_prev(n)
Definition: types.h:527
#define ED_edge_type(e)
Definition: types.h:585
void rank3(graph_t *g, aspect_t *asp)
Definition: aspect.c:1786
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:35
node_t * UF_union(node_t *u, node_t *v)
Definition: utils.c:156
#define free_list(L)
Definition: types.h:274
#define GD_minrep(g)
Definition: types.h:393
#define ED_minlen(e)
Definition: types.h:595
#define INT_MAX
Definition: arith.h:52
Agedge_t * edge(Agraph_t *g, Agnode_t *t, Agnode_t *h)
Definition: gv.cpp:110
#define ND_set(n)
Definition: types.h:492
#define TRUE
Definition: cgraph.h:38