Graphviz  2.41.20170921.2350
ns.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  * Network Simplex Algorithm for Ranking Nodes of a DAG
17  */
18 
19 #include "render.h"
20 #include <setjmp.h>
21 
22 static int init_graph(graph_t *);
23 static void dfs_cutval(node_t * v, edge_t * par);
24 static int dfs_range(node_t * v, edge_t * par, int low);
25 static int x_val(edge_t * e, node_t * v, int dir);
26 #ifdef DEBUG
27 static void check_cycles(graph_t * g);
28 #endif
29 
30 #define LENGTH(e) (ND_rank(aghead(e)) - ND_rank(agtail(e)))
31 #define SLACK(e) (LENGTH(e) - ED_minlen(e))
32 #define SEQ(a,b,c) (((a) <= (b)) && ((b) <= (c)))
33 #define TREE_EDGE(e) (ED_tree_index(e) >= 0)
34 
35 static jmp_buf jbuf;
36 static graph_t *G;
37 static int N_nodes, N_edges;
38 static int Minrank, Maxrank;
39 static int S_i; /* search index for enter_edge */
40 static int Search_size;
41 #define SEARCHSIZE 30
42 static nlist_t Tree_node;
43 static elist Tree_edge;
44 
45 static void add_tree_edge(edge_t * e)
46 {
47  node_t *n;
48  //fprintf(stderr,"add tree edge %p %s ", (void*)e, agnameof(agtail(e))) ; fprintf(stderr,"%s\n", agnameof(aghead(e))) ;
49  if (TREE_EDGE(e)) {
50  agerr(AGERR, "add_tree_edge: missing tree edge\n");
51  longjmp (jbuf, 1);
52  }
53  ED_tree_index(e) = Tree_edge.size;
54  Tree_edge.list[Tree_edge.size++] = e;
55  if (ND_mark(agtail(e)) == FALSE)
56  Tree_node.list[Tree_node.size++] = agtail(e);
57  if (ND_mark(aghead(e)) == FALSE)
58  Tree_node.list[Tree_node.size++] = aghead(e);
59  n = agtail(e);
60  ND_mark(n) = TRUE;
61  ND_tree_out(n).list[ND_tree_out(n).size++] = e;
62  ND_tree_out(n).list[ND_tree_out(n).size] = NULL;
63  if (ND_out(n).list[ND_tree_out(n).size - 1] == 0) {
64  agerr(AGERR, "add_tree_edge: empty outedge list\n");
65  longjmp (jbuf, 1);
66  }
67  n = aghead(e);
68  ND_mark(n) = TRUE;
69  ND_tree_in(n).list[ND_tree_in(n).size++] = e;
70  ND_tree_in(n).list[ND_tree_in(n).size] = NULL;
71  if (ND_in(n).list[ND_tree_in(n).size - 1] == 0) {
72  agerr(AGERR, "add_tree_edge: empty inedge list\n");
73  longjmp (jbuf, 1);
74  }
75 }
76 
77 static void exchange_tree_edges(edge_t * e, edge_t * f)
78 {
79  int i, j;
80  node_t *n;
81 
83  Tree_edge.list[ED_tree_index(e)] = f;
84  ED_tree_index(e) = -1;
85 
86  n = agtail(e);
87  i = --(ND_tree_out(n).size);
88  for (j = 0; j <= i; j++)
89  if (ND_tree_out(n).list[j] == e)
90  break;
91  ND_tree_out(n).list[j] = ND_tree_out(n).list[i];
92  ND_tree_out(n).list[i] = NULL;
93  n = aghead(e);
94  i = --(ND_tree_in(n).size);
95  for (j = 0; j <= i; j++)
96  if (ND_tree_in(n).list[j] == e)
97  break;
98  ND_tree_in(n).list[j] = ND_tree_in(n).list[i];
99  ND_tree_in(n).list[i] = NULL;
100 
101  n = agtail(f);
102  ND_tree_out(n).list[ND_tree_out(n).size++] = f;
103  ND_tree_out(n).list[ND_tree_out(n).size] = NULL;
104  n = aghead(f);
105  ND_tree_in(n).list[ND_tree_in(n).size++] = f;
106  ND_tree_in(n).list[ND_tree_in(n).size] = NULL;
107 }
108 
109 static
110 void init_rank(void)
111 {
112  int i, ctr;
113  nodequeue *Q;
114  node_t *v;
115  edge_t *e;
116 
117  Q = new_queue(N_nodes);
118  ctr = 0;
119 
120  for (v = GD_nlist(G); v; v = ND_next(v)) {
121  if (ND_priority(v) == 0)
122  enqueue(Q, v);
123  }
124 
125  while ((v = dequeue(Q))) {
126  ND_rank(v) = 0;
127  ctr++;
128  for (i = 0; (e = ND_in(v).list[i]); i++)
129  ND_rank(v) = MAX(ND_rank(v), ND_rank(agtail(e)) + ED_minlen(e));
130  for (i = 0; (e = ND_out(v).list[i]); i++) {
131  if (--(ND_priority(aghead(e))) <= 0)
132  enqueue(Q, aghead(e));
133  }
134  }
135  if (ctr != N_nodes) {
136  agerr(AGERR, "trouble in init_rank\n");
137  for (v = GD_nlist(G); v; v = ND_next(v))
138  if (ND_priority(v))
139  agerr(AGPREV, "\t%s %d\n", agnameof(v), ND_priority(v));
140  }
141  free_queue(Q);
142 }
143 
144 static edge_t *leave_edge(void)
145 {
146  edge_t *f, *rv = NULL;
147  int j, cnt = 0;
148 
149  j = S_i;
150  while (S_i < Tree_edge.size) {
151  if (ED_cutvalue(f = Tree_edge.list[S_i]) < 0) {
152  if (rv) {
153  if (ED_cutvalue(rv) > ED_cutvalue(f))
154  rv = f;
155  } else
156  rv = Tree_edge.list[S_i];
157  if (++cnt >= Search_size)
158  return rv;
159  }
160  S_i++;
161  }
162  if (j > 0) {
163  S_i = 0;
164  while (S_i < j) {
165  if (ED_cutvalue(f = Tree_edge.list[S_i]) < 0) {
166  if (rv) {
167  if (ED_cutvalue(rv) > ED_cutvalue(f))
168  rv = f;
169  } else
170  rv = Tree_edge.list[S_i];
171  if (++cnt >= Search_size)
172  return rv;
173  }
174  S_i++;
175  }
176  }
177  return rv;
178 }
179 
180 static edge_t *Enter;
181 static int Low, Lim, Slack;
182 
183 static void dfs_enter_outedge(node_t * v)
184 {
185  int i, slack;
186  edge_t *e;
187 
188  for (i = 0; (e = ND_out(v).list[i]); i++) {
189  if (TREE_EDGE(e) == FALSE) {
190  if (!SEQ(Low, ND_lim(aghead(e)), Lim)) {
191  slack = SLACK(e);
192  if ((slack < Slack) || (Enter == NULL)) {
193  Enter = e;
194  Slack = slack;
195  }
196  }
197  } else if (ND_lim(aghead(e)) < ND_lim(v))
198  dfs_enter_outedge(aghead(e));
199  }
200  for (i = 0; (e = ND_tree_in(v).list[i]) && (Slack > 0); i++)
201  if (ND_lim(agtail(e)) < ND_lim(v))
202  dfs_enter_outedge(agtail(e));
203 }
204 
205 static void dfs_enter_inedge(node_t * v)
206 {
207  int i, slack;
208  edge_t *e;
209 
210  for (i = 0; (e = ND_in(v).list[i]); i++) {
211  if (TREE_EDGE(e) == FALSE) {
212  if (!SEQ(Low, ND_lim(agtail(e)), Lim)) {
213  slack = SLACK(e);
214  if ((slack < Slack) || (Enter == NULL)) {
215  Enter = e;
216  Slack = slack;
217  }
218  }
219  } else if (ND_lim(agtail(e)) < ND_lim(v))
220  dfs_enter_inedge(agtail(e));
221  }
222  for (i = 0; (e = ND_tree_out(v).list[i]) && (Slack > 0); i++)
223  if (ND_lim(aghead(e)) < ND_lim(v))
224  dfs_enter_inedge(aghead(e));
225 }
226 
227 static edge_t *enter_edge(edge_t * e)
228 {
229  node_t *v;
230  int outsearch;
231 
232  /* v is the down node */
233  if (ND_lim(agtail(e)) < ND_lim(aghead(e))) {
234  v = agtail(e);
235  outsearch = FALSE;
236  } else {
237  v = aghead(e);
238  outsearch = TRUE;
239  }
240  Enter = NULL;
241  Slack = INT_MAX;
242  Low = ND_low(v);
243  Lim = ND_lim(v);
244  if (outsearch)
245  dfs_enter_outedge(v);
246  else
247  dfs_enter_inedge(v);
248  return Enter;
249 }
250 
251 static void init_cutvalues(void)
252 {
253  dfs_range(GD_nlist(G), NULL, 1);
254  dfs_cutval(GD_nlist(G), NULL);
255 }
256 
257 /* functions for initial tight tree construction */
258 // borrow field from network simplex - overwritten in init_cutvalues() forgive me
259 #define ND_subtree(n) (subtree_t*)ND_par(n)
260 #define ND_subtree_set(n,value) (ND_par(n) = (edge_t*)value)
261 
262 typedef struct subtree_s {
263  node_t *rep; /* some node in the tree */
264  int size; /* total tight tree size */
265  int heap_index; /* required to find non-min elts when merged */
266  struct subtree_s *par; /* union find */
267 } subtree_t;
268 
269 /* find initial tight subtrees */
270 static int tight_subtree_search(Agnode_t *v, subtree_t *st)
271 {
272  Agedge_t *e;
273  int i;
274  int rv;
275 
276  rv = 1;
277  ND_subtree_set(v,st);
278  for (i = 0; (e = ND_in(v).list[i]); i++) {
279  if (TREE_EDGE(e)) continue;
280  if ((ND_subtree(agtail(e)) == 0) && (SLACK(e) == 0)) {
281  add_tree_edge(e);
282  rv += tight_subtree_search(agtail(e),st);
283  }
284  }
285  for (i = 0; (e = ND_out(v).list[i]); i++) {
286  if (TREE_EDGE(e)) continue;
287  if ((ND_subtree(aghead(e)) == 0) && (SLACK(e) == 0)) {
288  add_tree_edge(e);
289  rv += tight_subtree_search(aghead(e),st);
290  }
291  }
292  return rv;
293 }
294 
295 static subtree_t *find_tight_subtree(Agnode_t *v)
296 {
297  subtree_t *rv;
298  rv = NEW(subtree_t);
299  rv->rep = v;
300  rv->size = tight_subtree_search(v,rv);
301  rv->par = rv;
302  return rv;
303 }
304 
305 typedef struct STheap_s {
307  int size;
308 } STheap_t;
309 
310 static subtree_t *STsetFind(Agnode_t *n0)
311 {
312  subtree_t *s0 = ND_subtree(n0);
313  while (s0->par && (s0->par != s0)) {
314  if (s0->par->par) {s0->par = s0->par->par;} /* path compression for the code weary */
315  s0 = s0->par;
316  }
317  return s0;
318 }
319 
320 static subtree_t *STsetUnion(subtree_t *s0, subtree_t *s1)
321 {
322  subtree_t *r0, *r1, *r;
323 
324  for (r0 = s0; r0->par && (r0->par != r0); r0 = r0->par);
325  for (r1 = s1; r1->par && (r1->par != r1); r1 = r1->par);
326  if (r0 == r1) return r0; /* safety code but shouldn't happen */
327  assert((r0->heap_index > -1) || (r1->heap_index > -1));
328  if (r1->heap_index == -1) r = r0;
329  else if (r0->heap_index == -1) r = r1;
330  else if (r1->size < r0->size) r = r0;
331  else r = r1;
332 
333  r0->par = r1->par = r;
334  r->size = r0->size + r1->size;
335  assert(r->heap_index >= 0);
336  return r;
337 }
338 
339 #define INCIDENT(e,treeset) ((STsetFind(agtail(e),treeset)) != STsetFind(aghead(e),treeset))
340 
341 /* find tightest edge to another tree incident on the given tree */
342 static Agedge_t *inter_tree_edge_search(Agnode_t *v, Agnode_t *from, Agedge_t *best)
343 {
344  int i;
345  Agedge_t *e;
346  subtree_t *ts = STsetFind(v);
347  if (best && SLACK(best) == 0) return best;
348  for (i = 0; (e = ND_out(v).list[i]); i++) {
349  if (TREE_EDGE(e)) {
350  if (aghead(e) == from) continue; // do not search back in tree
351  best = inter_tree_edge_search(aghead(e),v,best); // search forward in tree
352  }
353  else {
354  if (STsetFind(aghead(e)) != ts) { // encountered candidate edge
355  if ((best == 0) || (SLACK(e) < SLACK(best))) best = e;
356  }
357  /* else ignore non-tree edge between nodes in the same tree */
358  }
359  }
360  /* the following code must mirror the above, but for in-edges */
361  for (i = 0; (e = ND_in(v).list[i]); i++) {
362  if (TREE_EDGE(e)) {
363  if (agtail(e) == from) continue;
364  best = inter_tree_edge_search(agtail(e),v,best);
365  }
366  else {
367  if (STsetFind(agtail(e)) != ts) {
368  if ((best == 0) || (SLACK(e) < SLACK(best))) best = e;
369  }
370  }
371  }
372  return best;
373 }
374 
375 static Agedge_t *inter_tree_edge(subtree_t *tree)
376 {
377  Agedge_t *rv;
378  rv = inter_tree_edge_search(tree->rep, (Agnode_t *)0, (Agedge_t *)0);
379  return rv;
380 }
381 
382 static
383 int STheapsize(STheap_t *heap) { return heap->size; }
384 
385 static
386 void STheapify(STheap_t *heap, int i)
387 {
388  int left, right, smallest;
389  subtree_t **elt = heap->elt;
390  do {
391  left = 2*(i+1)-1;
392  right = 2*(i+1);
393  if ((left < heap->size) && (elt[left]->size < elt[i]->size)) smallest = left;
394  else smallest = i;
395  if ((right < heap->size) && (elt[right]->size < elt[smallest]->size)) smallest = right;
396  else smallest = i;
397  if (smallest != i) {
398  subtree_t *temp;
399  temp = elt[i];
400  elt[i] = elt[smallest];
401  elt[smallest] = temp;
402  elt[i]->heap_index = i;
403  elt[smallest]->heap_index = smallest;
404  i = smallest;
405  }
406  else break;
407  } while (i < heap->size);
408 }
409 
410 static
411 STheap_t *STbuildheap(subtree_t **elt, int size)
412 {
413  int i;
414  STheap_t *heap;
415  heap = NEW(STheap_t);
416  heap->elt = elt;
417  heap->size = size;
418  for (i = 0; i < heap->size; i++) heap->elt[i]->heap_index = i;
419  for (i = heap->size/2; i >= 0; i--)
420  STheapify(heap,i);
421  return heap;
422 }
423 
424 static
425 subtree_t *STextractmin(STheap_t *heap)
426 {
427  subtree_t *rv;
428  rv = heap->elt[0];
429  rv->heap_index = -1;
430  heap->elt[0] = heap->elt[heap->size - 1];
431  heap->elt[0]->heap_index = 0;
432  heap->elt[heap->size -1] = rv; /* needed to free storage later */
433  heap->size--;
434  STheapify(heap,0);
435  return rv;
436 }
437 
438 static
439 void tree_adjust(Agnode_t *v, Agnode_t *from, int delta)
440 {
441  int i;
442  Agedge_t *e;
443  Agnode_t *w;
444  ND_rank(v) = ND_rank(v) + delta;
445  for (i = 0; (e = ND_tree_in(v).list[i]); i++) {
446  w = agtail(e);
447  if (w != from)
448  tree_adjust(w, v, delta);
449  }
450  for (i = 0; (e = ND_tree_out(v).list[i]); i++) {
451  w = aghead(e);
452  if (w != from)
453  tree_adjust(w, v, delta);
454  }
455 }
456 
457 static
458 subtree_t *merge_trees(Agedge_t *e) /* entering tree edge */
459 {
460  int delta;
461  subtree_t *t0, *t1, *rv;
462 
463  assert(!TREE_EDGE(e));
464 
465  t0 = STsetFind(agtail(e));
466  t1 = STsetFind(aghead(e));
467 
468  //fprintf(stderr,"merge trees of %d %d of %d, delta %d\n",t0->size,t1->size,N_nodes,delta);
469 
470  if (t0->heap_index == -1) { // move t0
471  delta = SLACK(e);
472  tree_adjust(t0->rep,(Agnode_t*)0,delta);
473  }
474  else { // move t1
475  delta = -SLACK(e);
476  tree_adjust(t1->rep,0,delta);
477  }
478  add_tree_edge(e);
479  rv = STsetUnion(t0,t1);
480 
481  return rv;
482 }
483 
484 /* Construct initial tight tree. Graph must be connected, feasible.
485  * Adjust ND_rank(v) as needed. add_tree_edge() on tight tree edges.
486  * trees are basically lists of nodes stored in nodequeues.
487  * Return 1 if input graph is not connected; 0 on success.
488  */
489 static
490 int feasible_tree(void)
491 {
492  Agnode_t *n;
493  Agedge_t *ee;
494  subtree_t **tree, *tree0, *tree1;
495  int i, subtree_count = 0;
496  STheap_t *heap;
497  int error = 0;
498 
499  /* initialization */
500  for (n = GD_nlist(G); n; n = ND_next(n)) {
501  ND_subtree_set(n,0);
502  }
503 
504  tree = N_NEW(N_nodes,subtree_t*);
505  /* given init_rank, find all tight subtrees */
506  for (n = GD_nlist(G); n; n = ND_next(n)) {
507  if (ND_subtree(n) == 0) {
508  tree[subtree_count] = find_tight_subtree(n);
509  subtree_count++;
510  }
511  }
512 
513  /* incrementally merge subtrees */
514  heap = STbuildheap(tree,subtree_count);
515  while (STheapsize(heap) > 1) {
516  tree0 = STextractmin(heap);
517  if (!(ee = inter_tree_edge(tree0))) {
518  error = 1;
519  break;
520  }
521  tree1 = merge_trees(ee);
522  STheapify(heap,tree1->heap_index);
523  }
524 
525  free(heap);
526  for (i = 0; i < subtree_count; i++) free(tree[i]);
527  free(tree);
528  if (error) return 1;
529  assert(Tree_edge.size == N_nodes - 1);
530  init_cutvalues();
531  return 0;
532 }
533 
534 /* utility functions for debugging */
535 static subtree_t *nd_subtree(Agnode_t *n) {return ND_subtree(n);}
536 static int nd_priority(Agnode_t *n) {return ND_priority(n);}
537 static int nd_rank(Agnode_t *n) {return ND_rank(n);}
538 static int ed_minlen(Agedge_t *e) {return ED_minlen(e);}
539 
540 /* walk up from v to LCA(v,w), setting new cutvalues. */
541 static Agnode_t *treeupdate(Agnode_t * v, Agnode_t * w, int cutvalue, int dir)
542 {
543  edge_t *e;
544  int d;
545 
546  while (!SEQ(ND_low(v), ND_lim(w), ND_lim(v))) {
547  e = ND_par(v);
548  if (v == agtail(e))
549  d = dir;
550  else
551  d = NOT(dir);
552  if (d)
553  ED_cutvalue(e) += cutvalue;
554  else
555  ED_cutvalue(e) -= cutvalue;
556  if (ND_lim(agtail(e)) > ND_lim(aghead(e)))
557  v = agtail(e);
558  else
559  v = aghead(e);
560  }
561  return v;
562 }
563 
564 static void rerank(Agnode_t * v, int delta)
565 {
566  int i;
567  edge_t *e;
568 
569  ND_rank(v) -= delta;
570  for (i = 0; (e = ND_tree_out(v).list[i]); i++)
571  if (e != ND_par(v))
572  rerank(aghead(e), delta);
573  for (i = 0; (e = ND_tree_in(v).list[i]); i++)
574  if (e != ND_par(v))
575  rerank(agtail(e), delta);
576 }
577 
578 /* e is the tree edge that is leaving and f is the nontree edge that
579  * is entering. compute new cut values, ranks, and exchange e and f.
580  */
581 static void
582 update(edge_t * e, edge_t * f)
583 {
584  int cutvalue, delta;
585  Agnode_t *lca;
586 
587  delta = SLACK(f);
588  /* "for (v = in nodes in tail side of e) do ND_rank(v) -= delta;" */
589  if (delta > 0) {
590  int s;
591  s = ND_tree_in(agtail(e)).size + ND_tree_out(agtail(e)).size;
592  if (s == 1)
593  rerank(agtail(e), delta);
594  else {
595  s = ND_tree_in(aghead(e)).size + ND_tree_out(aghead(e)).size;
596  if (s == 1)
597  rerank(aghead(e), -delta);
598  else {
599  if (ND_lim(agtail(e)) < ND_lim(aghead(e)))
600  rerank(agtail(e), delta);
601  else
602  rerank(aghead(e), -delta);
603  }
604  }
605  }
606 
607  cutvalue = ED_cutvalue(e);
608  lca = treeupdate(agtail(f), aghead(f), cutvalue, 1);
609  if (treeupdate(aghead(f), agtail(f), cutvalue, 0) != lca) {
610  agerr(AGERR, "update: mismatched lca in treeupdates\n");
611  longjmp (jbuf, 1);
612  }
613  ED_cutvalue(f) = -cutvalue;
614  ED_cutvalue(e) = 0;
615  exchange_tree_edges(e, f);
616  dfs_range(lca, ND_par(lca), ND_low(lca));
617 }
618 
619 static void scan_and_normalize(void)
620 {
621  node_t *n;
622 
623  Minrank = INT_MAX;
624  Maxrank = -INT_MAX;
625  for (n = GD_nlist(G); n; n = ND_next(n)) {
626  if (ND_node_type(n) == NORMAL) {
627  Minrank = MIN(Minrank, ND_rank(n));
628  Maxrank = MAX(Maxrank, ND_rank(n));
629  }
630  }
631  if (Minrank != 0) {
632  for (n = GD_nlist(G); n; n = ND_next(n))
633  ND_rank(n) -= Minrank;
634  Maxrank -= Minrank;
635  Minrank = 0;
636  }
637 }
638 
639 static void
640 freeTreeList (graph_t* g)
641 {
642  node_t *n;
643  for (n = GD_nlist(G); n; n = ND_next(n)) {
644  free_list(ND_tree_in(n));
646  ND_mark(n) = FALSE;
647  }
648 }
649 
650 static void LR_balance(void)
651 {
652  int i, delta;
653  edge_t *e, *f;
654 
655  for (i = 0; i < Tree_edge.size; i++) {
656  e = Tree_edge.list[i];
657  if (ED_cutvalue(e) == 0) {
658  f = enter_edge(e);
659  if (f == NULL)
660  continue;
661  delta = SLACK(f);
662  if (delta <= 1)
663  continue;
664  if (ND_lim(agtail(e)) < ND_lim(aghead(e)))
665  rerank(agtail(e), delta / 2);
666  else
667  rerank(aghead(e), -delta / 2);
668  }
669  }
670  freeTreeList (G);
671 }
672 
673 static void TB_balance(void)
674 {
675  node_t *n;
676  edge_t *e;
677  int i, low, high, choice, *nrank;
678  int inweight, outweight;
679 
680  scan_and_normalize();
681 
682  /* find nodes that are not tight and move to less populated ranks */
683  nrank = N_NEW(Maxrank + 1, int);
684  for (i = 0; i <= Maxrank; i++)
685  nrank[i] = 0;
686  for (n = GD_nlist(G); n; n = ND_next(n))
687  if (ND_node_type(n) == NORMAL)
688  nrank[ND_rank(n)]++;
689  for (n = GD_nlist(G); n; n = ND_next(n)) {
690  if (ND_node_type(n) != NORMAL)
691  continue;
692  inweight = outweight = 0;
693  low = 0;
694  high = Maxrank;
695  for (i = 0; (e = ND_in(n).list[i]); i++) {
696  inweight += ED_weight(e);
697  low = MAX(low, ND_rank(agtail(e)) + ED_minlen(e));
698  }
699  for (i = 0; (e = ND_out(n).list[i]); i++) {
700  outweight += ED_weight(e);
701  high = MIN(high, ND_rank(aghead(e)) - ED_minlen(e));
702  }
703  if (low < 0)
704  low = 0; /* vnodes can have ranks < 0 */
705  if (inweight == outweight) {
706  choice = low;
707  for (i = low + 1; i <= high; i++)
708  if (nrank[i] < nrank[choice])
709  choice = i;
710  nrank[ND_rank(n)]--;
711  nrank[choice]++;
712  ND_rank(n) = choice;
713  }
714  free_list(ND_tree_in(n));
716  ND_mark(n) = FALSE;
717  }
718  free(nrank);
719 }
720 
721 static int init_graph(graph_t * g)
722 {
723  int i, feasible;
724  node_t *n;
725  edge_t *e;
726 
727  G = g;
728  N_nodes = N_edges = S_i = 0;
729  for (n = GD_nlist(g); n; n = ND_next(n)) {
730  ND_mark(n) = FALSE;
731  N_nodes++;
732  for (i = 0; (e = ND_out(n).list[i]); i++)
733  N_edges++;
734  }
735 
736  Tree_node.list = ALLOC(N_nodes, Tree_node.list, node_t *);
737  Tree_node.size = 0;
738  Tree_edge.list = ALLOC(N_nodes, Tree_edge.list, edge_t *);
739  Tree_edge.size = 0;
740 
741  feasible = TRUE;
742  for (n = GD_nlist(g); n; n = ND_next(n)) {
743  ND_priority(n) = 0;
744  for (i = 0; (e = ND_in(n).list[i]); i++) {
745  ND_priority(n)++;
746  ED_cutvalue(e) = 0;
747  ED_tree_index(e) = -1;
748  if (feasible
749  && (ND_rank(aghead(e)) - ND_rank(agtail(e)) < ED_minlen(e)))
750  feasible = FALSE;
751  }
752  ND_tree_in(n).list = N_NEW(i + 1, edge_t *);
753  ND_tree_in(n).size = 0;
754  for (i = 0; (e = ND_out(n).list[i]); i++);
755  ND_tree_out(n).list = N_NEW(i + 1, edge_t *);
756  ND_tree_out(n).size = 0;
757  }
758  return feasible;
759 }
760 
761 /* graphSize:
762  * Compute no. of nodes and edges in the graph
763  */
764 static void
765 graphSize (graph_t * g, int* nn, int* ne)
766 {
767  int i, nnodes, nedges;
768  node_t *n;
769  edge_t *e;
770 
771  nnodes = nedges = 0;
772  for (n = GD_nlist(g); n; n = ND_next(n)) {
773  nnodes++;
774  for (i = 0; (e = ND_out(n).list[i]); i++) {
775  nedges++;
776  }
777  }
778  *nn = nnodes;
779  *ne = nedges;
780 }
781 
782 /* rank:
783  * Apply network simplex to rank the nodes in a graph.
784  * Uses ED_minlen as the internode constraint: if a->b with minlen=ml,
785  * rank b - rank a >= ml.
786  * Assumes the graph has the following additional structure:
787  * A list of all nodes, starting at GD_nlist, and linked using ND_next.
788  * Out and in edges lists stored in ND_out and ND_in, even if the node
789  * doesn't have any out or in edges.
790  * The node rank values are stored in ND_rank.
791  * Returns 0 if successful; returns 1 if the graph was not connected;
792  * returns 2 if something seriously wrong;
793  */
794 int rank2(graph_t * g, int balance, int maxiter, int search_size)
795 {
796  int iter = 0, feasible;
797  char *ns = "network simplex: ";
798  edge_t *e, *f;
799 
800 #ifdef DEBUG
801  check_cycles(g);
802 #endif
803  if (Verbose) {
804  int nn, ne;
805  graphSize (g, &nn, &ne);
806  fprintf(stderr, "%s %d nodes %d edges maxiter=%d balance=%d\n", ns,
807  nn, ne, maxiter, balance);
808  start_timer();
809  }
810  feasible = init_graph(g);
811  if (!feasible)
812  init_rank();
813  if (maxiter <= 0) {
814  freeTreeList (g);
815  return 0;
816  }
817 
818  if (search_size >= 0)
819  Search_size = search_size;
820  else
821  Search_size = SEARCHSIZE;
822 
823  if (setjmp (jbuf)) {
824  return 2;
825  }
826 
827  if (feasible_tree()) {
828  freeTreeList (g);
829  return 1;
830  }
831  while ((e = leave_edge())) {
832  f = enter_edge(e);
833  update(e, f);
834  iter++;
835  if (Verbose && (iter % 100 == 0)) {
836  if (iter % 1000 == 100)
837  fputs(ns, stderr);
838  fprintf(stderr, "%d ", iter);
839  if (iter % 1000 == 0)
840  fputc('\n', stderr);
841  }
842  if (iter >= maxiter)
843  break;
844  }
845  switch (balance) {
846  case 1:
847  TB_balance();
848  break;
849  case 2:
850  LR_balance();
851  break;
852  default:
853  scan_and_normalize();
854  freeTreeList (G);
855  break;
856  }
857  if (Verbose) {
858  if (iter >= 100)
859  fputc('\n', stderr);
860  fprintf(stderr, "%s%d nodes %d edges %d iter %.2f sec\n",
861  ns, N_nodes, N_edges, iter, elapsed_sec());
862  }
863  return 0;
864 }
865 
866 int rank(graph_t * g, int balance, int maxiter)
867 {
868  char *s;
869  int search_size;
870 
871  if ((s = agget(g, "searchsize")))
872  search_size = atoi(s);
873  else
874  search_size = SEARCHSIZE;
875 
876  return rank2 (g, balance, maxiter, search_size);
877 }
878 
879 /* set cut value of f, assuming values of edges on one side were already set */
880 static void x_cutval(edge_t * f)
881 {
882  node_t *v;
883  edge_t *e;
884  int i, sum, dir;
885 
886  /* set v to the node on the side of the edge already searched */
887  if (ND_par(agtail(f)) == f) {
888  v = agtail(f);
889  dir = 1;
890  } else {
891  v = aghead(f);
892  dir = -1;
893  }
894 
895  sum = 0;
896  for (i = 0; (e = ND_out(v).list[i]); i++)
897  sum += x_val(e, v, dir);
898  for (i = 0; (e = ND_in(v).list[i]); i++)
899  sum += x_val(e, v, dir);
900  ED_cutvalue(f) = sum;
901 }
902 
903 static int x_val(edge_t * e, node_t * v, int dir)
904 {
905  node_t *other;
906  int d, rv, f;
907 
908  if (agtail(e) == v)
909  other = aghead(e);
910  else
911  other = agtail(e);
912  if (!(SEQ(ND_low(v), ND_lim(other), ND_lim(v)))) {
913  f = 1;
914  rv = ED_weight(e);
915  } else {
916  f = 0;
917  if (TREE_EDGE(e))
918  rv = ED_cutvalue(e);
919  else
920  rv = 0;
921  rv -= ED_weight(e);
922  }
923  if (dir > 0) {
924  if (aghead(e) == v)
925  d = 1;
926  else
927  d = -1;
928  } else {
929  if (agtail(e) == v)
930  d = 1;
931  else
932  d = -1;
933  }
934  if (f)
935  d = -d;
936  if (d < 0)
937  rv = -rv;
938  return rv;
939 }
940 
941 static void dfs_cutval(node_t * v, edge_t * par)
942 {
943  int i;
944  edge_t *e;
945 
946  for (i = 0; (e = ND_tree_out(v).list[i]); i++)
947  if (e != par)
948  dfs_cutval(aghead(e), e);
949  for (i = 0; (e = ND_tree_in(v).list[i]); i++)
950  if (e != par)
951  dfs_cutval(agtail(e), e);
952  if (par)
953  x_cutval(par);
954 }
955 
956 static int dfs_range(node_t * v, edge_t * par, int low)
957 {
958  edge_t *e;
959  int i, lim;
960 
961  lim = low;
962  ND_par(v) = par;
963  ND_low(v) = low;
964  for (i = 0; (e = ND_tree_out(v).list[i]); i++)
965  if (e != par)
966  lim = dfs_range(aghead(e), e, lim);
967  for (i = 0; (e = ND_tree_in(v).list[i]); i++)
968  if (e != par)
969  lim = dfs_range(agtail(e), e, lim);
970  ND_lim(v) = lim;
971  return lim + 1;
972 }
973 
974 #ifdef DEBUG
975 void tchk(void)
976 {
977  int i, n_cnt, e_cnt;
978  node_t *n;
979  edge_t *e;
980 
981  n_cnt = 0;
982  e_cnt = 0;
983  for (n = agfstnode(G); n; n = agnxtnode(G, n)) {
984  n_cnt++;
985  for (i = 0; (e = ND_tree_out(n).list[i]); i++) {
986  e_cnt++;
987  if (SLACK(e) > 0)
988  fprintf(stderr, "not a tight tree %p", e);
989  }
990  }
991  if ((n_cnt != Tree_node.size) || (e_cnt != Tree_edge.size))
992  fprintf(stderr, "something missing\n");
993 }
994 
995 void check_cutvalues(void)
996 {
997  node_t *v;
998  edge_t *e;
999  int i, save;
1000 
1001  for (v = agfstnode(G); v; v = agnxtnode(G, v)) {
1002  for (i = 0; (e = ND_tree_out(v).list[i]); i++) {
1003  save = ED_cutvalue(e);
1004  x_cutval(e);
1005  if (save != ED_cutvalue(e))
1006  abort();
1007  }
1008  }
1009 }
1010 
1011 int check_ranks(void)
1012 {
1013  int cost = 0;
1014  node_t *n;
1015  edge_t *e;
1016 
1017  for (n = agfstnode(G); n; n = agnxtnode(G, n)) {
1018  for (e = agfstout(G, n); e; e = agnxtout(G, e)) {
1019  cost += (ED_weight(e)) * abs(LENGTH(e));
1020  if (ND_rank(aghead(e)) - ND_rank(agtail(e)) - ED_minlen(e) < 0)
1021  abort();
1022  }
1023  }
1024  fprintf(stderr, "rank cost %d\n", cost);
1025  return cost;
1026 }
1027 
1028 void checktree(void)
1029 {
1030  int i, n = 0, m = 0;
1031  node_t *v;
1032  edge_t *e;
1033 
1034  for (v = agfstnode(G); v; v = agnxtnode(G, v)) {
1035  for (i = 0; (e = ND_tree_out(v).list[i]); i++)
1036  n++;
1037  if (i != ND_tree_out(v).size)
1038  abort();
1039  for (i = 0; (e = ND_tree_in(v).list[i]); i++)
1040  m++;
1041  if (i != ND_tree_in(v).size)
1042  abort();
1043  }
1044  fprintf(stderr, "%d %d %d\n", Tree_edge.size, n, m);
1045 }
1046 
1047 void check_fast_node(node_t * n)
1048 {
1049  node_t *nptr;
1050  nptr = GD_nlist(agraphof(n));
1051  while (nptr && nptr != n)
1052  nptr = ND_next(nptr);
1053  assert(nptr != NULL);
1054 }
1055 
1056 static char* dump_node (node_t* n)
1057 {
1058  static char buf[50];
1059 
1060  if (ND_node_type(n)) {
1061  sprintf(buf, "%p", n);
1062  return buf;
1063  }
1064  else
1065  return agnameof(n);
1066 }
1067 
1068 static void dump_graph (graph_t* g)
1069 {
1070  int i;
1071  edge_t *e;
1072  node_t *n,*w;
1073  FILE* fp = fopen ("ns.gv", "w");
1074  fprintf (fp, "digraph \"%s\" {\n", agnameof(g));
1075  for (n = GD_nlist(g); n; n = ND_next(n)) {
1076  fprintf (fp, " \"%s\"\n", dump_node(n));
1077  }
1078  for (n = GD_nlist(g); n; n = ND_next(n)) {
1079  for (i = 0; (e = ND_out(n).list[i]); i++) {
1080  fprintf (fp, " \"%s\"", dump_node(n));
1081  w = aghead(e);
1082  fprintf (fp, " -> \"%s\"\n", dump_node(w));
1083  }
1084  }
1085 
1086  fprintf (fp, "}\n");
1087  fclose (fp);
1088 }
1089 
1090 static node_t *checkdfs(graph_t* g, node_t * n)
1091 {
1092  edge_t *e;
1093  node_t *w,*x;
1094  int i;
1095 
1096  if (ND_mark(n))
1097  return 0;
1098  ND_mark(n) = TRUE;
1099  ND_onstack(n) = TRUE;
1100  for (i = 0; (e = ND_out(n).list[i]); i++) {
1101  w = aghead(e);
1102  if (ND_onstack(w)) {
1103  dump_graph (g);
1104  fprintf(stderr, "cycle: last edge %lx %s(%lx) %s(%lx)\n",
1105  (uint64_t)e,
1106  agnameof(n), (uint64_t)n,
1107  agnameof(w), (uint64_t)w);
1108  return w;
1109  }
1110  else {
1111  if (ND_mark(w) == FALSE) {
1112  x = checkdfs(g, w);
1113  if (x) {
1114  fprintf(stderr,"unwind %lx %s(%lx)\n",
1115  (uint64_t)e,
1116  agnameof(n), (uint64_t)n);
1117  if (x != n) return x;
1118  fprintf(stderr,"unwound to root\n");
1119  fflush(stderr);
1120  abort();
1121  return 0;
1122  }
1123  }
1124  }
1125  }
1126  ND_onstack(n) = FALSE;
1127  return 0;
1128 }
1129 
1130 void check_cycles(graph_t * g)
1131 {
1132  node_t *n;
1133  for (n = GD_nlist(g); n; n = ND_next(n))
1134  ND_mark(n) = ND_onstack(n) = FALSE;
1135  for (n = GD_nlist(g); n; n = ND_next(n))
1136  checkdfs(g, n);
1137 }
1138 #endif /* DEBUG */
void s1(graph_t *, node_t *)
Definition: stuff.c:686
#define MAX(a, b)
Definition: agerror.c:17
#define ND_rank(n)
Definition: types.h:529
Definition: cgraph.h:388
int heap_index
Definition: ns.c:265
#define GD_nlist(g)
Definition: types.h:401
#define ND_subtree(n)
Definition: ns.c:259
void start_timer(void)
Definition: timing.c:45
#define N_NEW(n, t)
Definition: memory.h:36
#define MIN(a, b)
Definition: arith.h:35
int size
Definition: ns.c:307
#define ND_node_type(n)
Definition: types.h:518
#define ALLOC(size, ptr, type)
Definition: memory.h:41
#define assert(x)
Definition: cghdr.h:47
#define ED_tree_index(e)
Definition: types.h:603
#define ED_cutvalue(e)
Definition: types.h:584
#define ND_tree_out(n)
Definition: types.h:540
#define ED_weight(e)
Definition: types.h:606
node_t ** list
Definition: types.h:257
#define SEQ(a, b, c)
Definition: ns.c:32
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
#define SLACK(e)
Definition: ns.c:31
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
void enqueue(nodequeue *q, node_t *n)
Definition: utils.c:51
#define ND_mark(n)
Definition: types.h:514
char * agget(void *obj, char *name)
Definition: attr.c:428
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
nodequeue * new_queue(int sz)
Definition: utils.c:34
#define ND_tree_in(n)
Definition: types.h:539
int size
Definition: ns.c:264
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
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
#define TREE_EDGE(e)
Definition: ns.c:33
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
struct STheap_s STheap_t
#define ND_subtree_set(n, value)
Definition: ns.c:260
Definition: ns.c:262
struct subtree_s subtree_t
#define ND_par(n)
Definition: types.h:524
edge_t ** list
Definition: types.h:262
node_t * dequeue(nodequeue *q)
Definition: utils.c:58
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define SEARCHSIZE
Definition: ns.c:41
Definition: grammar.c:79
subtree_t ** elt
Definition: ns.c:306
#define ND_lim(n)
Definition: types.h:511
Definition: ns.c:305
void free_queue(nodequeue *q)
Definition: utils.c:45
#define NULL
Definition: logic.h:39
#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
#define right(i)
Definition: closest.c:87
#define ND_next(n)
Definition: types.h:517
EXTERN unsigned char Verbose
Definition: globals.h:64
node_t * rep
Definition: ns.c:263
for(;;)
Definition: grammar.c:1846
#define ND_priority(n)
Definition: types.h:528
Definition: dijkstra.c:54
#define ND_out(n)
Definition: types.h:522
int rank2(graph_t *g, int balance, int maxiter, int search_size)
Definition: ns.c:794
int size
Definition: types.h:258
int size
Definition: types.h:263
Definition: types.h:256
#define left
Definition: dthdr.h:16
struct subtree_s * par
Definition: ns.c:266
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define NORMAL
Definition: const.h:27
Definition: cgraph.h:388
#define FALSE
Definition: cgraph.h:35
#define ND_low(n)
Definition: types.h:512
#define free_list(L)
Definition: types.h:274
#define ED_minlen(e)
Definition: types.h:595
#define INT_MAX
Definition: arith.h:52
#define LENGTH(e)
Definition: ns.c:30
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:38