Graphviz 13.0.0~dev.20250424.1043
Loading...
Searching...
No Matches
ns.c
Go to the documentation of this file.
1
7/*************************************************************************
8 * Copyright (c) 2011 AT&T Intellectual Property
9 * All rights reserved. This program and the accompanying materials
10 * are made available under the terms of the Eclipse Public License v1.0
11 * which accompanies this distribution, and is available at
12 * https://www.eclipse.org/legal/epl-v10.html
13 *
14 * Contributors: Details at https://graphviz.org
15 *************************************************************************/
16
17#include <assert.h>
18#include <common/render.h>
19#include <limits.h>
20#include <stdbool.h>
21#include <stddef.h>
22#include <stdint.h>
23#include <stdio.h>
24#include <util/alloc.h>
25#include <util/exit.h>
26#include <util/list.h>
27#include <util/overflow.h>
28#include <util/prisize_t.h>
29#include <util/streq.h>
30
31static void dfs_cutval(node_t * v, edge_t * par);
32static int dfs_range_init(node_t *v);
33static int dfs_range(node_t * v, edge_t * par, int low);
34static int x_val(edge_t * e, node_t * v, int dir);
35#ifdef DEBUG
36static void check_cycles(graph_t * g);
37#endif
38
39#define LENGTH(e) (ND_rank(aghead(e)) - ND_rank(agtail(e)))
40#define SLACK(e) (LENGTH(e) - ED_minlen(e))
41#define SEQ(a,b,c) ((a) <= (b) && (b) <= (c))
42#define TREE_EDGE(e) (ED_tree_index(e) >= 0)
43
44typedef struct {
48 size_t S_i; /* search index for enter_edge */
49 size_t N_edges, N_nodes;
51
53 int Low, Lim, Slack;
55
56#define SEARCHSIZE 30
57
59{
60 node_t *n;
61 if (TREE_EDGE(e)) {
62 agerrorf("add_tree_edge: missing tree edge\n");
63 return -1;
64 }
65 assert(ctx->Tree_edge.size <= INT_MAX);
66 ED_tree_index(e) = (int)ctx->Tree_edge.size;
67 ctx->Tree_edge.list[ctx->Tree_edge.size++] = e;
68 if (!ND_mark(agtail(e)))
69 ctx->Tree_node.list[ctx->Tree_node.size++] = agtail(e);
70 if (!ND_mark(aghead(e)))
71 ctx->Tree_node.list[ctx->Tree_node.size++] = aghead(e);
72 n = agtail(e);
73 ND_mark(n) = true;
74 ND_tree_out(n).list[ND_tree_out(n).size++] = e;
75 ND_tree_out(n).list[ND_tree_out(n).size] = NULL;
76 if (ND_out(n).list[ND_tree_out(n).size - 1] == 0) {
77 agerrorf("add_tree_edge: empty outedge list\n");
78 return -1;
79 }
80 n = aghead(e);
81 ND_mark(n) = true;
82 ND_tree_in(n).list[ND_tree_in(n).size++] = e;
83 ND_tree_in(n).list[ND_tree_in(n).size] = NULL;
84 if (ND_in(n).list[ND_tree_in(n).size - 1] == 0) {
85 agerrorf("add_tree_edge: empty inedge list\n");
86 return -1;
87 }
88 return 0;
89}
90
96static void invalidate_path(node_t *lca, node_t *to_node) {
97 while (true) {
98 if (ND_low(to_node) == -1)
99 break;
100
101 ND_low(to_node) = -1;
102
103 edge_t *e = ND_par(to_node);
104 if (e == NULL)
105 break;
106
107 if (ND_lim(to_node) >= ND_lim(lca)) {
108 if (to_node != lca)
109 agerrorf("invalidate_path: skipped over LCA\n");
110 break;
111 }
112
113 if (ND_lim(agtail(e)) > ND_lim(aghead(e)))
114 to_node = agtail(e);
115 else
116 to_node = aghead(e);
117 }
118}
119
121{
122 node_t *n;
123
125 ctx->Tree_edge.list[ED_tree_index(e)] = f;
126 ED_tree_index(e) = -1;
127
128 n = agtail(e);
129 size_t i = --ND_tree_out(n).size;
130 size_t j;
131 for (j = 0; j <= i; j++)
132 if (ND_tree_out(n).list[j] == e)
133 break;
134 ND_tree_out(n).list[j] = ND_tree_out(n).list[i];
135 ND_tree_out(n).list[i] = NULL;
136 n = aghead(e);
137 i = --ND_tree_in(n).size;
138 for (j = 0; j <= i; j++)
139 if (ND_tree_in(n).list[j] == e)
140 break;
141 ND_tree_in(n).list[j] = ND_tree_in(n).list[i];
142 ND_tree_in(n).list[i] = NULL;
143
144 n = agtail(f);
145 ND_tree_out(n).list[ND_tree_out(n).size++] = f;
146 ND_tree_out(n).list[ND_tree_out(n).size] = NULL;
147 n = aghead(f);
148 ND_tree_in(n).list[ND_tree_in(n).size++] = f;
149 ND_tree_in(n).list[ND_tree_in(n).size] = NULL;
150}
151
152DEFINE_LIST(node_queue, node_t *)
153
154static
156{
157 int i;
158 node_t *v;
159 edge_t *e;
160
161 node_queue_t Q = {0};
162 node_queue_reserve(&Q, ctx->N_nodes);
163 size_t ctr = 0;
164
165 for (v = GD_nlist(ctx->G); v; v = ND_next(v)) {
166 if (ND_priority(v) == 0)
167 node_queue_push_back(&Q, v);
168 }
169
170 while (!node_queue_is_empty(&Q)) {
171 v = node_queue_pop_front(&Q);
172 ND_rank(v) = 0;
173 ctr++;
174 for (i = 0; (e = ND_in(v).list[i]); i++)
175 ND_rank(v) = MAX(ND_rank(v), ND_rank(agtail(e)) + ED_minlen(e));
176 for (i = 0; (e = ND_out(v).list[i]); i++) {
177 if (--ND_priority(aghead(e)) <= 0)
178 node_queue_push_back(&Q, aghead(e));
179 }
180 }
181 if (ctr != ctx->N_nodes) {
182 agerrorf("trouble in init_rank\n");
183 for (v = GD_nlist(ctx->G); v; v = ND_next(v))
184 if (ND_priority(v))
185 agerr(AGPREV, "\t%s %d\n", agnameof(v), ND_priority(v));
186 }
187 node_queue_free(&Q);
188}
189
191{
192 edge_t *f, *rv = NULL;
193 int cnt = 0;
194
195 size_t j = ctx->S_i;
196 while (ctx->S_i < ctx->Tree_edge.size) {
197 if (ED_cutvalue(f = ctx->Tree_edge.list[ctx->S_i]) < 0) {
198 if (rv) {
199 if (ED_cutvalue(rv) > ED_cutvalue(f))
200 rv = f;
201 } else
202 rv = ctx->Tree_edge.list[ctx->S_i];
203 if (++cnt >= ctx->Search_size)
204 return rv;
205 }
206 ctx->S_i++;
207 }
208 if (j > 0) {
209 ctx->S_i = 0;
210 while (ctx->S_i < j) {
211 if (ED_cutvalue(f = ctx->Tree_edge.list[ctx->S_i]) < 0) {
212 if (rv) {
213 if (ED_cutvalue(rv) > ED_cutvalue(f))
214 rv = f;
215 } else
216 rv = ctx->Tree_edge.list[ctx->S_i];
217 if (++cnt >= ctx->Search_size)
218 return rv;
219 }
220 ctx->S_i++;
221 }
222 }
223 return rv;
224}
225
227{
228 int i, slack;
229 edge_t *e;
230
231 for (i = 0; (e = ND_out(v).list[i]); i++) {
232 if (!TREE_EDGE(e)) {
233 if (!SEQ(ctx->Low, ND_lim(aghead(e)), ctx->Lim)) {
234 slack = SLACK(e);
235 if (slack < ctx->Slack || ctx->Enter == NULL) {
236 ctx->Enter = e;
237 ctx->Slack = slack;
238 }
239 }
240 } else if (ND_lim(aghead(e)) < ND_lim(v))
241 dfs_enter_outedge(ctx, aghead(e));
242 }
243 for (i = 0; (e = ND_tree_in(v).list[i]) && (ctx->Slack > 0); i++)
244 if (ND_lim(agtail(e)) < ND_lim(v))
245 dfs_enter_outedge(ctx, agtail(e));
246}
247
249{
250 int i, slack;
251 edge_t *e;
252
253 for (i = 0; (e = ND_in(v).list[i]); i++) {
254 if (!TREE_EDGE(e)) {
255 if (!SEQ(ctx->Low, ND_lim(agtail(e)), ctx->Lim)) {
256 slack = SLACK(e);
257 if (slack < ctx->Slack || ctx->Enter == NULL) {
258 ctx->Enter = e;
259 ctx->Slack = slack;
260 }
261 }
262 } else if (ND_lim(agtail(e)) < ND_lim(v))
263 dfs_enter_inedge(ctx, agtail(e));
264 }
265 for (i = 0; (e = ND_tree_out(v).list[i]) && ctx->Slack > 0; i++)
266 if (ND_lim(aghead(e)) < ND_lim(v))
267 dfs_enter_inedge(ctx, aghead(e));
268}
269
271{
272 node_t *v;
273 bool outsearch;
274
275 /* v is the down node */
276 if (ND_lim(agtail(e)) < ND_lim(aghead(e))) {
277 v = agtail(e);
278 outsearch = false;
279 } else {
280 v = aghead(e);
281 outsearch = true;
282 }
283 ctx->Enter = NULL;
284 ctx->Slack = INT_MAX;
285 ctx->Low = ND_low(v);
286 ctx->Lim = ND_lim(v);
287 if (outsearch)
288 dfs_enter_outedge(ctx, v);
289 else
290 dfs_enter_inedge(ctx, v);
291 return ctx->Enter;
292}
293
295{
297 dfs_cutval(GD_nlist(ctx->G), NULL);
298}
299
300/* functions for initial tight tree construction */
301// borrow field from network simplex - overwritten in init_cutvalues() forgive me
302#define ND_subtree(n) (subtree_t*)ND_par(n)
303#define ND_subtree_set(n,value) (ND_par(n) = (edge_t*)value)
304
305typedef struct subtree_s {
306 node_t *rep; /* some node in the tree */
307 int size; /* total tight tree size */
308 size_t heap_index;
309 struct subtree_s *par; /* union find */
311
313static bool on_heap(const subtree_t *tree) {
314 return tree->heap_index != SIZE_MAX;
315}
316
318typedef struct {
320 int in_i;
321 int out_i;
322 int rv;
323} tst_t;
324
326DEFINE_LIST(tsts, tst_t)
327
328/* find initial tight subtrees */
330{
331 Agedge_t *e;
332 int rv;
333
334 rv = 1;
335 ND_subtree_set(v,st);
336
337 tsts_t todo = {0};
338 tsts_push_back(&todo, (tst_t){.v = v, .rv = 1});
339
340 while (!tsts_is_empty(&todo)) {
341 bool updated = false;
342 tst_t *top = tsts_back(&todo);
343
344 for (; (e = ND_in(top->v).list[top->in_i]); top->in_i++) {
345 if (TREE_EDGE(e)) continue;
346 if (ND_subtree(agtail(e)) == 0 && SLACK(e) == 0) {
347 if (add_tree_edge(ctx, e) != 0) {
348 (void)tsts_pop_back(&todo);
349 if (tsts_is_empty(&todo)) {
350 rv = -1;
351 } else {
352 --tsts_back(&todo)->rv;
353 }
354 } else {
355 ND_subtree_set(agtail(e), st);
356 const tst_t next = {.v = agtail(e), .rv = 1};
357 tsts_push_back(&todo, next);
358 }
359 updated = true;
360 break;
361 }
362 }
363 if (updated) {
364 continue;
365 }
366
367 for (; (e = ND_out(top->v).list[top->out_i]); top->out_i++) {
368 if (TREE_EDGE(e)) continue;
369 if (ND_subtree(aghead(e)) == 0 && SLACK(e) == 0) {
370 if (add_tree_edge(ctx, e) != 0) {
371 (void)tsts_pop_back(&todo);
372 if (tsts_is_empty(&todo)) {
373 rv = -1;
374 } else {
375 --tsts_back(&todo)->rv;
376 }
377 } else {
378 ND_subtree_set(aghead(e), st);
379 const tst_t next = {.v = aghead(e), .rv = 1};
380 tsts_push_back(&todo, next);
381 }
382 updated = true;
383 break;
384 }
385 }
386 if (updated) {
387 continue;
388 }
389
390 const tst_t last = tsts_pop_back(&todo);
391 if (tsts_is_empty(&todo)) {
392 rv = last.rv;
393 } else {
394 tsts_back(&todo)->rv += last.rv;
395 }
396 }
397
398 tsts_free(&todo);
399
400 return rv;
401}
402
404{
405 subtree_t *rv;
406 rv = gv_alloc(sizeof(subtree_t));
407 rv->rep = v;
408 rv->size = tight_subtree_search(ctx,v,rv);
409 if (rv->size < 0) {
410 free(rv);
411 return NULL;
412 }
413 rv->par = rv;
414 return rv;
415}
416
417typedef struct STheap_s {
419 size_t size;
421
423{
424 subtree_t *s0 = ND_subtree(n0);
425 while (s0->par && s0->par != s0) {
426 if (s0->par->par) {s0->par = s0->par->par;} /* path compression for the code weary */
427 s0 = s0->par;
428 }
429 return s0;
430}
431
433{
434 subtree_t *r0, *r1, *r;
435
436 for (r0 = s0; r0->par && r0->par != r0; r0 = r0->par);
437 for (r1 = s1; r1->par && r1->par != r1; r1 = r1->par);
438 if (r0 == r1) return r0; /* safety code but shouldn't happen */
439 assert(on_heap(r0) || on_heap(r1));
440 if (!on_heap(r1)) r = r0;
441 else if (!on_heap(r0)) r = r1;
442 else if (r1->size < r0->size) r = r0;
443 else r = r1;
444
445 r0->par = r1->par = r;
446 r->size = r0->size + r1->size;
447 assert(on_heap(r));
448 return r;
449}
450
451/* find tightest edge to another tree incident on the given tree */
453{
454 int i;
455 Agedge_t *e;
456 subtree_t *ts = STsetFind(v);
457 if (best && SLACK(best) == 0) return best;
458 for (i = 0; (e = ND_out(v).list[i]); i++) {
459 if (TREE_EDGE(e)) {
460 if (aghead(e) == from) continue; // do not search back in tree
461 best = inter_tree_edge_search(aghead(e),v,best); // search forward in tree
462 }
463 else {
464 if (STsetFind(aghead(e)) != ts) { // encountered candidate edge
465 if (best == 0 || SLACK(e) < SLACK(best)) best = e;
466 }
467 /* else ignore non-tree edge between nodes in the same tree */
468 }
469 }
470 /* the following code must mirror the above, but for in-edges */
471 for (i = 0; (e = ND_in(v).list[i]); i++) {
472 if (TREE_EDGE(e)) {
473 if (agtail(e) == from) continue;
474 best = inter_tree_edge_search(agtail(e),v,best);
475 }
476 else {
477 if (STsetFind(agtail(e)) != ts) {
478 if (best == 0 || SLACK(e) < SLACK(best)) best = e;
479 }
480 }
481 }
482 return best;
483}
484
486{
487 Agedge_t *rv;
489 return rv;
490}
491
492static size_t STheapsize(const STheap_t *heap) { return heap->size; }
493
494static void STheapify(STheap_t *heap, size_t i) {
495 subtree_t **elt = heap->elt;
496 do {
497 const size_t left = 2 * (i + 1) - 1;
498 const size_t right = 2 * (i + 1);
499 size_t smallest = i;
500 if (left < heap->size && elt[left]->size < elt[smallest]->size) smallest = left;
501 if (right < heap->size && elt[right]->size < elt[smallest]->size) smallest = right;
502 if (smallest != i) {
503 subtree_t *temp;
504 temp = elt[i];
505 elt[i] = elt[smallest];
506 elt[smallest] = temp;
507 elt[i]->heap_index = i;
508 elt[smallest]->heap_index = smallest;
509 i = smallest;
510 }
511 else break;
512 } while (i < heap->size);
513}
514
515static STheap_t *STbuildheap(subtree_t **elt, size_t size) {
516 STheap_t *heap = gv_alloc(sizeof(STheap_t));
517 heap->elt = elt;
518 heap->size = size;
519 for (size_t i = 0; i < heap->size; i++) heap->elt[i]->heap_index = i;
520 for (size_t i = heap->size / 2; i != SIZE_MAX; i--)
521 STheapify(heap,i);
522 return heap;
523}
524
525static
527{
528 subtree_t *rv;
529 rv = heap->elt[0];
530 rv->heap_index = SIZE_MAX;
531 // mark this as not participating in the heap anymore
532 heap->elt[0] = heap->elt[heap->size - 1];
533 heap->elt[0]->heap_index = 0;
534 heap->elt[heap->size -1] = rv; /* needed to free storage later */
535 heap->size--;
536 STheapify(heap,0);
537 return rv;
538}
539
540static
541void tree_adjust(Agnode_t *v, Agnode_t *from, int delta)
542{
543 int i;
544 Agedge_t *e;
545 Agnode_t *w;
546 ND_rank(v) = ND_rank(v) + delta;
547 for (i = 0; (e = ND_tree_in(v).list[i]); i++) {
548 w = agtail(e);
549 if (w != from)
550 tree_adjust(w, v, delta);
551 }
552 for (i = 0; (e = ND_tree_out(v).list[i]); i++) {
553 w = aghead(e);
554 if (w != from)
555 tree_adjust(w, v, delta);
556 }
557}
558
559static
560subtree_t *merge_trees(network_simplex_ctx_t *ctx, Agedge_t *e) /* entering tree edge */
561{
562 int delta;
563 subtree_t *t0, *t1, *rv;
564
565 assert(!TREE_EDGE(e));
566
567 t0 = STsetFind(agtail(e));
568 t1 = STsetFind(aghead(e));
569
570 if (!on_heap(t0)) { // move t0
571 delta = SLACK(e);
572 if (delta != 0)
574 }
575 else { // move t1
576 delta = -SLACK(e);
577 if (delta != 0)
579 }
580 if (add_tree_edge(ctx, e) != 0) {
581 return NULL;
582 }
583 rv = STsetUnion(t0,t1);
584
585 return rv;
586}
587
588/* Construct initial tight tree. Graph must be connected, feasible.
589 * Adjust ND_rank(v) as needed. add_tree_edge() on tight tree edges.
590 * trees are basically lists of nodes stored in `node_queue_t`s.
591 * Return 1 if input graph is not connected; 0 on success.
592 */
593static
595{
596 Agedge_t *ee;
597 size_t subtree_count = 0;
598 STheap_t *heap = NULL;
599 int error = 0;
600
601 /* initialization */
602 for (Agnode_t *n = GD_nlist(ctx->G); n != NULL; n = ND_next(n)) {
603 ND_subtree_set(n,0);
604 }
605
606 subtree_t **tree = gv_calloc(ctx->N_nodes, sizeof(subtree_t *));
607 /* given init_rank, find all tight subtrees */
608 for (Agnode_t *n = GD_nlist(ctx->G); n != NULL; n = ND_next(n)) {
609 if (ND_subtree(n) == 0) {
610 tree[subtree_count] = find_tight_subtree(ctx, n);
611 if (tree[subtree_count] == NULL) {
612 error = 2;
613 goto end;
614 }
615 subtree_count++;
616 }
617 }
618
619 /* incrementally merge subtrees */
620 heap = STbuildheap(tree,subtree_count);
621 while (STheapsize(heap) > 1) {
622 subtree_t *tree0 = STextractmin(heap);
623 if (!(ee = inter_tree_edge(tree0))) {
624 error = 1;
625 break;
626 }
627 subtree_t *tree1 = merge_trees(ctx, ee);
628 if (tree1 == NULL) {
629 error = 2;
630 break;
631 }
632 STheapify(heap,tree1->heap_index);
633 }
634
635end:
636 free(heap);
637 for (size_t i = 0; i < subtree_count; i++) free(tree[i]);
638 free(tree);
639 if (error) return error;
640 assert(ctx->Tree_edge.size == ctx->N_nodes - 1);
641 init_cutvalues(ctx);
642 return 0;
643}
644
645/* walk up from v to LCA(v,w), setting new cutvalues. */
646static Agnode_t *treeupdate(Agnode_t * v, Agnode_t * w, int cutvalue, int dir)
647{
648 edge_t *e;
649 int d;
650
651 while (!SEQ(ND_low(v), ND_lim(w), ND_lim(v))) {
652 e = ND_par(v);
653 if (v == agtail(e))
654 d = dir;
655 else
656 d = !dir;
657 if (d)
658 ED_cutvalue(e) += cutvalue;
659 else
660 ED_cutvalue(e) -= cutvalue;
661 if (ND_lim(agtail(e)) > ND_lim(aghead(e)))
662 v = agtail(e);
663 else
664 v = aghead(e);
665 }
666 return v;
667}
668
669static void rerank(Agnode_t * v, int delta)
670{
671 int i;
672 edge_t *e;
673
674 ND_rank(v) -= delta;
675 for (i = 0; (e = ND_tree_out(v).list[i]); i++)
676 if (e != ND_par(v))
677 rerank(aghead(e), delta);
678 for (i = 0; (e = ND_tree_in(v).list[i]); i++)
679 if (e != ND_par(v))
680 rerank(agtail(e), delta);
681}
682
683/* e is the tree edge that is leaving and f is the nontree edge that
684 * is entering. compute new cut values, ranks, and exchange e and f.
685 */
686static int
688{
689 int cutvalue, delta;
690 Agnode_t *lca;
691
692 delta = SLACK(f);
693 /* "for (v = in nodes in tail side of e) do ND_rank(v) -= delta;" */
694 if (delta > 0) {
695 size_t s = ND_tree_in(agtail(e)).size + ND_tree_out(agtail(e)).size;
696 if (s == 1)
697 rerank(agtail(e), delta);
698 else {
699 s = ND_tree_in(aghead(e)).size + ND_tree_out(aghead(e)).size;
700 if (s == 1)
701 rerank(aghead(e), -delta);
702 else {
703 if (ND_lim(agtail(e)) < ND_lim(aghead(e)))
704 rerank(agtail(e), delta);
705 else
706 rerank(aghead(e), -delta);
707 }
708 }
709 }
710
711 cutvalue = ED_cutvalue(e);
712 lca = treeupdate(agtail(f), aghead(f), cutvalue, 1);
713 if (treeupdate(aghead(f), agtail(f), cutvalue, 0) != lca) {
714 agerrorf("update: mismatched lca in treeupdates\n");
715 return 2;
716 }
717
718 // invalidate paths from LCA till affected nodes:
719 int lca_low = ND_low(lca);
720 invalidate_path(lca, aghead(f));
721 invalidate_path(lca, agtail(f));
722
723 ED_cutvalue(f) = -cutvalue;
724 ED_cutvalue(e) = 0;
725 exchange_tree_edges(ctx, e, f);
726 dfs_range(lca, ND_par(lca), lca_low);
727 return 0;
728}
729
731 node_t *n;
732
733 int Minrank = INT_MAX;
734 int Maxrank = INT_MIN;
735 for (n = GD_nlist(ctx->G); n; n = ND_next(n)) {
736 if (ND_node_type(n) == NORMAL) {
737 Minrank = MIN(Minrank, ND_rank(n));
738 Maxrank = MAX(Maxrank, ND_rank(n));
739 }
740 }
741 for (n = GD_nlist(ctx->G); n; n = ND_next(n))
742 ND_rank(n) -= Minrank;
743 Maxrank -= Minrank;
744 return Maxrank;
745}
746
748
749 free(ctx->Tree_node.list);
750 ctx->Tree_node = (nlist_t){0};
751
752 free(ctx->Tree_edge.list);
753 ctx->Tree_edge = (elist){0};
754}
755
756static void
758{
759 node_t *n;
760 for (n = GD_nlist(g); n; n = ND_next(n)) {
763 ND_mark(n) = false;
764 }
765 reset_lists(ctx);
766}
767
769{
770 int delta;
771 edge_t *e, *f;
772
773 for (size_t i = 0; i < ctx->Tree_edge.size; i++) {
774 e = ctx->Tree_edge.list[i];
775 if (ED_cutvalue(e) == 0) {
776 f = enter_edge(ctx,e);
777 if (f == NULL)
778 continue;
779 delta = SLACK(f);
780 if (delta <= 1)
781 continue;
782 if (ND_lim(agtail(e)) < ND_lim(aghead(e)))
783 rerank(agtail(e), delta / 2);
784 else
785 rerank(aghead(e), -delta / 2);
786 }
787 }
788 freeTreeList(ctx, ctx->G);
789}
790
791static int decreasingrankcmpf(const void *x, const void *y) {
792// Suppress Clang/GCC -Wcast-qual warning. Casting away const here is acceptable
793// as the later usage is const. We need the cast because the macros use
794// non-const pointers for genericity.
795#ifdef __GNUC__
796#pragma GCC diagnostic push
797#pragma GCC diagnostic ignored "-Wcast-qual"
798#endif
799 node_t **n0 = (node_t**)x;
800 node_t **n1 = (node_t**)y;
801#ifdef __GNUC__
802#pragma GCC diagnostic pop
803#endif
804 if (ND_rank(*n1) < ND_rank(*n0)) {
805 return -1;
806 }
807 if (ND_rank(*n1) > ND_rank(*n0)) {
808 return 1;
809 }
810 return 0;
811}
812
813static int increasingrankcmpf(const void *x, const void *y) {
814// Suppress Clang/GCC -Wcast-qual warning. Casting away const here is acceptable
815// as the later usage is const. We need the cast because the macros use
816// non-const pointers for genericity.
817#ifdef __GNUC__
818#pragma GCC diagnostic push
819#pragma GCC diagnostic ignored "-Wcast-qual"
820#endif
821 node_t **n0 = (node_t **)x;
822 node_t **n1 = (node_t **)y;
823#ifdef __GNUC__
824#pragma GCC diagnostic pop
825#endif
826 if (ND_rank(*n0) < ND_rank(*n1)) {
827 return -1;
828 }
829 if (ND_rank(*n0) > ND_rank(*n1)) {
830 return 1;
831 }
832 return 0;
833}
834
836{
837 node_t *n;
838 edge_t *e;
839 int low, high, choice;
840 int inweight, outweight;
841 int adj = 0;
842 char *s;
843
844 const int Maxrank = scan_and_normalize(ctx);
845
846 /* find nodes that are not tight and move to less populated ranks */
847 assert(Maxrank >= 0);
848 int *nrank = gv_calloc((size_t)Maxrank + 1, sizeof(int));
849 if ( (s = agget(ctx->G,"TBbalance")) ) {
850 if (streq(s,"min")) adj = 1;
851 else if (streq(s,"max")) adj = 2;
852 if (adj) for (n = GD_nlist(ctx->G); n; n = ND_next(n))
853 if (ND_node_type(n) == NORMAL) {
854 if (ND_in(n).size == 0 && adj == 1) {
855 ND_rank(n) = 0;
856 }
857 if (ND_out(n).size == 0 && adj == 2) {
858 ND_rank(n) = Maxrank;
859 }
860 }
861 }
862 size_t ii;
863 for (ii = 0, n = GD_nlist(ctx->G); n; ii++, n = ND_next(n)) {
864 ctx->Tree_node.list[ii] = n;
865 }
866 ctx->Tree_node.size = ii;
867 qsort(ctx->Tree_node.list, ctx->Tree_node.size, sizeof(ctx->Tree_node.list[0]),
869 for (size_t i = 0; i < ctx->Tree_node.size; i++) {
870 n = ctx->Tree_node.list[i];
871 if (ND_node_type(n) == NORMAL)
872 nrank[ND_rank(n)]++;
873 }
874 for (ii = 0; ii < ctx->Tree_node.size; ii++) {
875 n = ctx->Tree_node.list[ii];
876 if (ND_node_type(n) != NORMAL)
877 continue;
878 inweight = outweight = 0;
879 low = 0;
880 high = Maxrank;
881 for (size_t i = 0; (e = ND_in(n).list[i]); i++) {
882 inweight += ED_weight(e);
883 low = MAX(low, ND_rank(agtail(e)) + ED_minlen(e));
884 }
885 for (size_t i = 0; (e = ND_out(n).list[i]); i++) {
886 outweight += ED_weight(e);
887 high = MIN(high, ND_rank(aghead(e)) - ED_minlen(e));
888 }
889 if (low < 0)
890 low = 0; /* vnodes can have ranks < 0 */
891 if (adj) {
892 if (inweight == outweight)
893 ND_rank(n) = (adj == 1? low : high);
894 }
895 else {
896 if (inweight == outweight) {
897 choice = low;
898 for (int i = low + 1; i <= high; i++)
899 if (nrank[i] < nrank[choice])
900 choice = i;
901 nrank[ND_rank(n)]--;
902 nrank[choice]++;
903 ND_rank(n) = choice;
904 }
905 }
908 ND_mark(n) = false;
909 }
910 free(nrank);
911}
912
914 node_t *n;
915 edge_t *e;
916
917 ctx->G = g;
918 ctx->N_nodes = ctx->N_edges = ctx->S_i = 0;
919 for (n = GD_nlist(g); n; n = ND_next(n)) {
920 ND_mark(n) = false;
921 ctx->N_nodes++;
922 for (size_t i = 0; (e = ND_out(n).list[i]); i++)
923 ctx->N_edges++;
924 }
925
926 ctx->Tree_node.list = gv_calloc(ctx->N_nodes, sizeof(node_t *));
927 ctx->Tree_edge.list = gv_calloc(ctx->N_nodes, sizeof(edge_t *));
928
929 bool feasible = true;
930 for (n = GD_nlist(g); n; n = ND_next(n)) {
931 ND_priority(n) = 0;
932 size_t i;
933 for (i = 0; (e = ND_in(n).list[i]); i++) {
934 ND_priority(n)++;
935 ED_cutvalue(e) = 0;
936 ED_tree_index(e) = -1;
937 if (ND_rank(aghead(e)) - ND_rank(agtail(e)) < ED_minlen(e))
938 feasible = false;
939 }
940 ND_tree_in(n).list = gv_calloc(i + 1, sizeof(edge_t *));
941 ND_tree_in(n).size = 0;
942 for (i = 0; (e = ND_out(n).list[i]); i++);
943 ND_tree_out(n).list = gv_calloc(i + 1, sizeof(edge_t *));
944 ND_tree_out(n).size = 0;
945 }
946 return feasible;
947}
948
949/* graphSize:
950 * Compute no. of nodes and edges in the graph
951 */
952static void
953graphSize (graph_t * g, int* nn, int* ne)
954{
955 int i, nnodes, nedges;
956 node_t *n;
957 edge_t *e;
958
959 nnodes = nedges = 0;
960 for (n = GD_nlist(g); n; n = ND_next(n)) {
961 nnodes++;
962 for (i = 0; (e = ND_out(n).list[i]); i++) {
963 nedges++;
964 }
965 }
966 *nn = nnodes;
967 *ne = nedges;
968}
969
970/* rank:
971 * Apply network simplex to rank the nodes in a graph.
972 * Uses ED_minlen as the internode constraint: if a->b with minlen=ml,
973 * rank b - rank a >= ml.
974 * Assumes the graph has the following additional structure:
975 * A list of all nodes, starting at GD_nlist, and linked using ND_next.
976 * Out and in edges lists stored in ND_out and ND_in, even if the node
977 * doesn't have any out or in edges.
978 * The node rank values are stored in ND_rank.
979 * Returns 0 if successful; returns 1 if the graph was not connected;
980 * returns 2 if something seriously wrong;
981 */
982int rank2(graph_t * g, int balance, int maxiter, int search_size)
983{
984 int iter = 0;
985 char *ns = "network simplex: ";
986 edge_t *e, *f;
987 network_simplex_ctx_t ctx = {0};
988
989#ifdef DEBUG
990 check_cycles(g);
991#endif
992 if (Verbose) {
993 int nn, ne;
994 graphSize (g, &nn, &ne);
995 fprintf(stderr, "%s %d nodes %d edges maxiter=%d balance=%d\n", ns,
996 nn, ne, maxiter, balance);
997 start_timer();
998 }
999 bool feasible = init_graph(&ctx, g);
1000 if (!feasible)
1001 init_rank(&ctx);
1002
1003 if (search_size >= 0)
1004 ctx.Search_size = search_size;
1005 else
1006 ctx.Search_size = SEARCHSIZE;
1007
1008 {
1009 int err = feasible_tree(&ctx);
1010 if (err != 0) {
1011 freeTreeList(&ctx, g);
1012 return err;
1013 }
1014 }
1015 if (maxiter <= 0) {
1016 freeTreeList(&ctx, g);
1017 return 0;
1018 }
1019
1020 while ((e = leave_edge(&ctx))) {
1021 int err;
1022 f = enter_edge(&ctx, e);
1023 err = update(&ctx, e, f);
1024 if (err != 0) {
1025 freeTreeList(&ctx, g);
1026 return err;
1027 }
1028 iter++;
1029 if (Verbose && iter % 100 == 0) {
1030 if (iter % 1000 == 100)
1031 fputs(ns, stderr);
1032 fprintf(stderr, "%d ", iter);
1033 if (iter % 1000 == 0)
1034 fputc('\n', stderr);
1035 }
1036 if (iter >= maxiter)
1037 break;
1038 }
1039 switch (balance) {
1040 case 1:
1041 TB_balance(&ctx);
1042 reset_lists(&ctx);
1043 break;
1044 case 2:
1045 LR_balance(&ctx);
1046 break;
1047 default:
1048 (void)scan_and_normalize(&ctx);
1049 freeTreeList (&ctx, ctx.G);
1050 break;
1051 }
1052 if (Verbose) {
1053 if (iter >= 100)
1054 fputc('\n', stderr);
1055 fprintf(stderr, "%s%" PRISIZE_T " nodes %" PRISIZE_T " edges %d iter %.2f sec\n",
1056 ns, ctx.N_nodes, ctx.N_edges, iter, elapsed_sec());
1057 }
1058 return 0;
1059}
1060
1061int rank(graph_t * g, int balance, int maxiter)
1062{
1063 char *s;
1064 int search_size;
1065
1066 if ((s = agget(g, "searchsize")))
1067 search_size = atoi(s);
1068 else
1069 search_size = SEARCHSIZE;
1070
1071 return rank2 (g, balance, maxiter, search_size);
1072}
1073
1074/* set cut value of f, assuming values of edges on one side were already set */
1075static void x_cutval(edge_t * f)
1076{
1077 node_t *v;
1078 edge_t *e;
1079 int i, sum, dir;
1080
1081 /* set v to the node on the side of the edge already searched */
1082 if (ND_par(agtail(f)) == f) {
1083 v = agtail(f);
1084 dir = 1;
1085 } else {
1086 v = aghead(f);
1087 dir = -1;
1088 }
1089
1090 sum = 0;
1091 for (i = 0; (e = ND_out(v).list[i]); i++)
1092 if (sadd_overflow(sum, x_val(e, v, dir), &sum)) {
1093 agerrorf("overflow when computing edge weight sum\n");
1094 graphviz_exit(EXIT_FAILURE);
1095 }
1096 for (i = 0; (e = ND_in(v).list[i]); i++)
1097 if (sadd_overflow(sum, x_val(e, v, dir), &sum)) {
1098 agerrorf("overflow when computing edge weight sum\n");
1099 graphviz_exit(EXIT_FAILURE);
1100 }
1101 ED_cutvalue(f) = sum;
1102}
1103
1104static int x_val(edge_t * e, node_t * v, int dir)
1105{
1106 node_t *other;
1107 int d, rv, f;
1108
1109 if (agtail(e) == v)
1110 other = aghead(e);
1111 else
1112 other = agtail(e);
1113 if (!(SEQ(ND_low(v), ND_lim(other), ND_lim(v)))) {
1114 f = 1;
1115 rv = ED_weight(e);
1116 } else {
1117 f = 0;
1118 if (TREE_EDGE(e))
1119 rv = ED_cutvalue(e);
1120 else
1121 rv = 0;
1122 rv -= ED_weight(e);
1123 }
1124 if (dir > 0) {
1125 if (aghead(e) == v)
1126 d = 1;
1127 else
1128 d = -1;
1129 } else {
1130 if (agtail(e) == v)
1131 d = 1;
1132 else
1133 d = -1;
1134 }
1135 if (f)
1136 d = -d;
1137 if (d < 0)
1138 rv = -rv;
1139 return rv;
1140}
1141
1142static void dfs_cutval(node_t * v, edge_t * par)
1143{
1144 int i;
1145 edge_t *e;
1146
1147 for (i = 0; (e = ND_tree_out(v).list[i]); i++)
1148 if (e != par)
1149 dfs_cutval(aghead(e), e);
1150 for (i = 0; (e = ND_tree_in(v).list[i]); i++)
1151 if (e != par)
1152 dfs_cutval(agtail(e), e);
1153 if (par)
1154 x_cutval(par);
1155}
1156
1165
1166DEFINE_LIST(dfs_stack, dfs_state_t)
1167
1168/*
1169* Initializes DFS range attributes (par, low, lim) over tree nodes such that:
1170* ND_par(n) - parent tree edge
1171* ND_low(n) - min DFS index for nodes in sub-tree (>= 1)
1172* ND_lim(n) - max DFS index for nodes in sub-tree
1173*/
1174static int dfs_range_init(node_t *v) {
1175 int lim = 0;
1176
1177 dfs_stack_t todo = {0};
1178
1179 ND_par(v) = NULL;
1180 ND_low(v) = 1;
1181 const dfs_state_t root = {.v = v, .par = NULL, .lim = 1};
1182 dfs_stack_push_back(&todo, root);
1183
1184 while (!dfs_stack_is_empty(&todo)) {
1185 bool pushed_new = false;
1186 dfs_state_t *const s = dfs_stack_back(&todo);
1187
1188 while (ND_tree_out(s->v).list[s->tree_out_i]) {
1189 edge_t *const e = ND_tree_out(s->v).list[s->tree_out_i];
1190 ++s->tree_out_i;
1191 if (e != s->par) {
1192 node_t *const n = aghead(e);
1193 ND_par(n) = e;
1194 ND_low(n) = s->lim;
1195 const dfs_state_t next = {.v = n, .par = e, .lim = s->lim};
1196 dfs_stack_push_back(&todo, next);
1197 pushed_new = true;
1198 break;
1199 }
1200 }
1201 if (pushed_new) {
1202 continue;
1203 }
1204
1205 while (ND_tree_in(s->v).list[s->tree_in_i]) {
1206 edge_t *const e = ND_tree_in(s->v).list[s->tree_in_i];
1207 ++s->tree_in_i;
1208 if (e != s->par) {
1209 node_t *const n = agtail(e);
1210 ND_par(n) = e;
1211 ND_low(n) = s->lim;
1212 const dfs_state_t next = {.v = n, .par = e, .lim = s->lim};
1213 dfs_stack_push_back(&todo, next);
1214 pushed_new = true;
1215 break;
1216 }
1217 }
1218 if (pushed_new) {
1219 continue;
1220 }
1221
1222 ND_lim(s->v) = s->lim;
1223
1224 lim = s->lim;
1225 (void)dfs_stack_pop_back(&todo);
1226
1227 if (!dfs_stack_is_empty(&todo)) {
1228 dfs_stack_back(&todo)->lim = lim + 1;
1229 }
1230 }
1231
1232 dfs_stack_free(&todo);
1233
1234 return lim + 1;
1235}
1236
1237/*
1238 * Incrementally updates DFS range attributes
1239 */
1240static int dfs_range(node_t * v, edge_t * par, int low)
1241{
1242 int lim = 0;
1243
1244 if (ND_par(v) == par && ND_low(v) == low) {
1245 return ND_lim(v) + 1;
1246 }
1247
1248 dfs_stack_t todo = {0};
1249
1250 ND_par(v) = par;
1251 ND_low(v) = low;
1252 const dfs_state_t root = {.v = v, .par = par, .lim = low};
1253 dfs_stack_push_back(&todo, root);
1254
1255 while (!dfs_stack_is_empty(&todo)) {
1256 bool processed_child = false;
1257 dfs_state_t *const s = dfs_stack_back(&todo);
1258
1259 while (ND_tree_out(s->v).list[s->tree_out_i]) {
1260 edge_t *const e = ND_tree_out(s->v).list[s->tree_out_i];
1261 ++s->tree_out_i;
1262 if (e != s->par) {
1263 node_t *const n = aghead(e);
1264 if (ND_par(n) == e && ND_low(n) == s->lim) {
1265 s->lim = ND_lim(n) + 1;
1266 } else {
1267 ND_par(n) = e;
1268 ND_low(n) = s->lim;
1269 const dfs_state_t next = {.v = n, .par = e, .lim = s->lim};
1270 dfs_stack_push_back(&todo, next);
1271 }
1272 processed_child = true;
1273 break;
1274 }
1275 }
1276 if (processed_child) {
1277 continue;
1278 }
1279
1280 while (ND_tree_in(s->v).list[s->tree_in_i]) {
1281 edge_t *const e = ND_tree_in(s->v).list[s->tree_in_i];
1282 ++s->tree_in_i;
1283 if (e != s->par) {
1284 node_t *const n = agtail(e);
1285 if (ND_par(n) == e && ND_low(n) == s->lim) {
1286 s->lim = ND_lim(n) + 1;
1287 } else {
1288 ND_par(n) = e;
1289 ND_low(n) = s->lim;
1290 const dfs_state_t next = {.v = n, .par = e, .lim = s->lim};
1291 dfs_stack_push_back(&todo, next);
1292 }
1293 processed_child = true;
1294 break;
1295 }
1296 }
1297 if (processed_child) {
1298 continue;
1299 }
1300
1301 ND_lim(s->v) = s->lim;
1302
1303 lim = s->lim;
1304 (void)dfs_stack_pop_back(&todo);
1305
1306 if (!dfs_stack_is_empty(&todo)) {
1307 dfs_stack_back(&todo)->lim = lim + 1;
1308 }
1309 }
1310
1311 dfs_stack_free(&todo);
1312
1313 return lim + 1;
1314}
1315
1316#ifdef DEBUG
1317void tchk(network_simplex_ctx_t *ctx)
1318{
1319 int i;
1320 node_t *n;
1321 edge_t *e;
1322
1323 size_t n_cnt = 0;
1324 size_t e_cnt = 0;
1325 for (n = agfstnode(ctx->G); n; n = agnxtnode(ctx->G, n)) {
1326 n_cnt++;
1327 for (i = 0; (e = ND_tree_out(n).list[i]); i++) {
1328 e_cnt++;
1329 if (SLACK(e) > 0)
1330 fprintf(stderr, "not a tight tree %p", e);
1331 }
1332 }
1333 if (n_cnt != ctx->Tree_node.size || e_cnt != ctx->Tree_edge.size)
1334 fprintf(stderr, "something missing\n");
1335}
1336
1337void check_fast_node(node_t * n)
1338{
1339 node_t *nptr;
1340 nptr = GD_nlist(agraphof(n));
1341 while (nptr && nptr != n)
1342 nptr = ND_next(nptr);
1343 assert(nptr != NULL);
1344}
1345
1346static void dump_node(FILE *sink, node_t *n) {
1347 if (ND_node_type(n)) {
1348 fprintf(sink, "%p", n);
1349 }
1350 else
1351 fputs(agnameof(n), sink);
1352}
1353
1354static void dump_graph (graph_t* g)
1355{
1356 int i;
1357 edge_t *e;
1358 node_t *n,*w;
1359 FILE* fp = fopen ("ns.gv", "w");
1360 fprintf (fp, "digraph \"%s\" {\n", agnameof(g));
1361 for (n = GD_nlist(g); n; n = ND_next(n)) {
1362 fputs(" \"", fp);
1363 dump_node(fp, n);
1364 fputs("\"\n", fp);
1365 }
1366 for (n = GD_nlist(g); n; n = ND_next(n)) {
1367 for (i = 0; (e = ND_out(n).list[i]); i++) {
1368 fputs(" \"", fp);
1369 dump_node(fp, n);
1370 fputs("\"", fp);
1371 w = aghead(e);
1372 fputs(" -> \"", fp);
1373 dump_node(fp, w);
1374 fputs("\"\n", fp);
1375 }
1376 }
1377
1378 fprintf (fp, "}\n");
1379 fclose (fp);
1380}
1381
1382static node_t *checkdfs(graph_t* g, node_t * n)
1383{
1384 edge_t *e;
1385 node_t *w,*x;
1386 int i;
1387
1388 if (ND_mark(n))
1389 return 0;
1390 ND_mark(n) = true;
1391 ND_onstack(n) = true;
1392 for (i = 0; (e = ND_out(n).list[i]); i++) {
1393 w = aghead(e);
1394 if (ND_onstack(w)) {
1395 dump_graph (g);
1396 fprintf(stderr, "cycle: last edge %lx %s(%lx) %s(%lx)\n",
1397 (uint64_t)e,
1398 agnameof(n), (uint64_t)n,
1399 agnameof(w), (uint64_t)w);
1400 return w;
1401 }
1402 else {
1403 if (!ND_mark(w)) {
1404 x = checkdfs(g, w);
1405 if (x) {
1406 fprintf(stderr,"unwind %lx %s(%lx)\n",
1407 (uint64_t)e,
1408 agnameof(n), (uint64_t)n);
1409 if (x != n) return x;
1410 fprintf(stderr,"unwound to root\n");
1411 fflush(stderr);
1412 abort();
1413 return 0;
1414 }
1415 }
1416 }
1417 }
1418 ND_onstack(n) = false;
1419 return 0;
1420}
1421
1422void check_cycles(graph_t * g)
1423{
1424 node_t *n;
1425 for (n = GD_nlist(g); n; n = ND_next(n)) {
1426 ND_mark(n) = false;
1427 ND_onstack(n) = false;
1428 }
1429 for (n = GD_nlist(g); n; n = ND_next(n))
1430 checkdfs(g, n);
1431}
1432#endif /* DEBUG */
static agxbuf last
last message
Definition agerror.c:29
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define MIN(a, b)
Definition arith.h:28
#define Low(n)
Definition bcomps.c:56
#define right(i)
Definition closest.c:79
#define NORMAL
Definition const.h:24
static char * err
Definition delaunay.c:696
#define left
Definition dthdr.h:12
static NORETURN void graphviz_exit(int status)
Definition exit.h:23
static tctype tchk[][2]
Definition gdefs.h:87
static bool Verbose
Definition gml2gv.c:23
void free(void *)
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:163
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:200
char * agget(void *obj, char *name)
Definition attr.c:472
#define ED_tree_index(e)
Definition types.h:600
#define ED_minlen(e)
Definition types.h:592
#define agtail(e)
Definition cgraph.h:986
#define ED_weight(e)
Definition types.h:603
#define ED_cutvalue(e)
Definition types.h:581
#define aghead(e)
Definition cgraph.h:987
void agerrorf(const char *fmt,...)
Definition agerror.c:165
int agerr(agerrlevel_t level, const char *fmt,...)
Definition agerror.c:155
@ AGPREV
Definition cgraph.h:955
#define GD_nlist(g)
Definition types.h:393
#define ND_tree_in(n)
Definition types.h:533
#define ND_rank(n)
Definition types.h:523
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:47
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:40
#define ND_lim(n)
Definition types.h:504
#define ND_next(n)
Definition types.h:510
#define ND_par(n)
Definition types.h:518
#define ND_node_type(n)
Definition types.h:511
#define ND_tree_out(n)
Definition types.h:534
#define ND_low(n)
Definition types.h:505
#define ND_in(n)
Definition types.h:501
#define ND_out(n)
Definition types.h:515
#define ND_priority(n)
Definition types.h:522
Agraph_t * agraphof(void *obj)
Definition obj.c:185
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
@ tree
Definition gvgen.c:34
table Syntax error
Definition htmlparse.y:294
#define ND_onstack(n)
Definition acyclic.c:29
#define ND_mark(n)
Definition acyclic.c:28
static Agedge_t * top(edge_stack_t *sp)
Definition tred.c:73
#define DEFINE_LIST(name, type)
Definition list.h:22
#define delta
Definition maze.c:136
NEATOPROCS_API void s1(graph_t *, node_t *)
Definition stuff.c:671
static void TB_balance(network_simplex_ctx_t *ctx)
Definition ns.c:835
static subtree_t * merge_trees(network_simplex_ctx_t *ctx, Agedge_t *e)
Definition ns.c:560
static int x_val(edge_t *e, node_t *v, int dir)
Definition ns.c:1104
static void freeTreeList(network_simplex_ctx_t *ctx, graph_t *g)
Definition ns.c:757
static void reset_lists(network_simplex_ctx_t *ctx)
Definition ns.c:747
static subtree_t * STextractmin(STheap_t *heap)
Definition ns.c:526
int rank(graph_t *g, int balance, int maxiter)
Definition ns.c:1061
#define SEARCHSIZE
Definition ns.c:56
static int dfs_range(node_t *v, edge_t *par, int low)
Definition ns.c:1240
static int update(network_simplex_ctx_t *ctx, edge_t *e, edge_t *f)
Definition ns.c:687
static void LR_balance(network_simplex_ctx_t *ctx)
Definition ns.c:768
static int increasingrankcmpf(const void *x, const void *y)
Definition ns.c:813
static int tight_subtree_search(network_simplex_ctx_t *ctx, Agnode_t *v, subtree_t *st)
a stack of states
Definition ns.c:329
static void dfs_cutval(node_t *v, edge_t *par)
Definition ns.c:1142
static bool on_heap(const subtree_t *tree)
is this subtree stored in an STheap?
Definition ns.c:313
struct STheap_s STheap_t
static size_t STheapsize(const STheap_t *heap)
Definition ns.c:492
static void init_cutvalues(network_simplex_ctx_t *ctx)
Definition ns.c:294
static STheap_t * STbuildheap(subtree_t **elt, size_t size)
Definition ns.c:515
static int decreasingrankcmpf(const void *x, const void *y)
Definition ns.c:791
#define SEQ(a, b, c)
Definition ns.c:41
#define ND_subtree_set(n, value)
Definition ns.c:303
static void init_rank(network_simplex_ctx_t *ctx)
Definition ns.c:155
static void dfs_enter_inedge(network_simplex_ctx_t *ctx, node_t *v)
Definition ns.c:248
#define TREE_EDGE(e)
Definition ns.c:42
static void exchange_tree_edges(network_simplex_ctx_t *ctx, edge_t *e, edge_t *f)
Definition ns.c:120
static int feasible_tree(network_simplex_ctx_t *ctx)
Definition ns.c:594
static edge_t * enter_edge(network_simplex_ctx_t *ctx, edge_t *e)
Definition ns.c:270
static Agnode_t * treeupdate(Agnode_t *v, Agnode_t *w, int cutvalue, int dir)
Definition ns.c:646
static void graphSize(graph_t *g, int *nn, int *ne)
Definition ns.c:953
#define ND_subtree(n)
Definition ns.c:302
static subtree_t * STsetFind(Agnode_t *n0)
Definition ns.c:422
static void rerank(Agnode_t *v, int delta)
Definition ns.c:669
static int dfs_range_init(node_t *v)
Definition ns.c:1174
struct subtree_s subtree_t
static void x_cutval(edge_t *f)
Definition ns.c:1075
static int scan_and_normalize(network_simplex_ctx_t *ctx)
Definition ns.c:730
static int add_tree_edge(network_simplex_ctx_t *ctx, edge_t *e)
Definition ns.c:58
static Agedge_t * inter_tree_edge_search(Agnode_t *v, Agnode_t *from, Agedge_t *best)
Definition ns.c:452
static void invalidate_path(node_t *lca, node_t *to_node)
Definition ns.c:96
static edge_t * leave_edge(network_simplex_ctx_t *ctx)
Definition ns.c:190
static subtree_t * find_tight_subtree(network_simplex_ctx_t *ctx, Agnode_t *v)
Definition ns.c:403
static void tree_adjust(Agnode_t *v, Agnode_t *from, int delta)
Definition ns.c:541
static bool init_graph(network_simplex_ctx_t *ctx, graph_t *g)
Definition ns.c:913
#define SLACK(e)
Definition ns.c:40
static subtree_t * STsetUnion(subtree_t *s0, subtree_t *s1)
Definition ns.c:432
static void dfs_enter_outedge(network_simplex_ctx_t *ctx, node_t *v)
Definition ns.c:226
static void STheapify(STheap_t *heap, size_t i)
Definition ns.c:494
int rank2(graph_t *g, int balance, int maxiter, int search_size)
Definition ns.c:982
static Agedge_t * inter_tree_edge(subtree_t *tree)
Definition ns.c:485
arithmetic overflow helpers
static bool sadd_overflow(int a, int b, int *res)
Definition overflow.h:22
#define PRISIZE_T
Definition prisize_t.h:25
static int nedges
total no. of edges used in routing
Definition routespl.c:31
static bool streq(const char *a, const char *b)
are a and b equal?
Definition streq.h:11
graph or subgraph
Definition cgraph.h:424
Definition ns.c:417
size_t size
Definition ns.c:419
subtree_t ** elt
Definition ns.c:418
local state used by dfs_range*
Definition ns.c:1158
int lim
Definition ns.c:1161
node_t * v
Definition ns.c:1159
int tree_out_i
Definition ns.c:1162
int tree_in_i
Definition ns.c:1163
edge_t * par
Definition ns.c:1160
Definition types.h:251
edge_t ** list
Definition types.h:252
size_t size
Definition types.h:253
elist Tree_edge
Definition ns.c:47
size_t N_edges
Definition ns.c:49
nlist_t Tree_node
Definition ns.c:46
graph_t * G
Definition ns.c:45
edge_t * Enter
Definition ns.c:52
size_t N_nodes
Definition ns.c:49
node_t ** list
Definition types.h:247
size_t size
Definition types.h:248
node_t * rep
Definition ns.c:306
struct subtree_s * par
Definition ns.c:309
size_t heap_index
required to find non-min elts when merged
Definition ns.c:308
int size
Definition ns.c:307
state for use in tight_subtree_search
Definition ns.c:318
Agnode_t * v
Definition ns.c:319
int out_i
iteration counter through ND_out(v).list
Definition ns.c:321
int in_i
iteration counter through ND_in(v).list
Definition ns.c:320
int rv
result value
Definition ns.c:322
double elapsed_sec(void)
Definition timing.c:48
void start_timer(void)
Definition timing.c:43
#define free_list(L)
Definition types.h:272
Definition grammar.c:93
#define MAX(a, b)
Definition write.c:31