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