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