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