36static void check_cycles(
graph_t * g);
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)
62 agerrorf(
"add_tree_edge: missing tree edge\n");
77 agerrorf(
"add_tree_edge: empty outedge list\n");
85 agerrorf(
"add_tree_edge: empty inedge list\n");
109 agerrorf(
"invalidate_path: skipped over LCA\n");
131 for (j = 0; j <= i; j++)
138 for (j = 0; j <= i; j++)
161 node_queue_t Q = {0};
162 node_queue_reserve(&Q, ctx->
N_nodes);
167 node_queue_push_back(&Q, v);
170 while (!node_queue_is_empty(&Q)) {
171 v = node_queue_pop_front(&Q);
174 for (i = 0; (e =
ND_in(v).list[i]); i++)
176 for (i = 0; (e =
ND_out(v).list[i]); i++) {
178 node_queue_push_back(&Q,
aghead(e));
210 while (ctx->
S_i < j) {
231 for (i = 0; (e =
ND_out(v).list[i]); i++) {
235 if (slack < ctx->Slack || ctx->
Enter ==
NULL) {
253 for (i = 0; (e =
ND_in(v).list[i]); i++) {
257 if (slack < ctx->Slack || ctx->
Enter ==
NULL) {
284 ctx->
Slack = INT_MAX;
302#define ND_subtree(n) (subtree_t*)ND_par(n)
303#define ND_subtree_set(n,value) (ND_par(n) = (edge_t*)value)
338 tsts_push_back(&todo, (
tst_t){.v = v, .rv = 1});
340 while (!tsts_is_empty(&todo)) {
341 bool updated =
false;
348 (void)tsts_pop_back(&todo);
349 if (tsts_is_empty(&todo)) {
352 --tsts_back(&todo)->rv;
357 tsts_push_back(&todo, next);
371 (void)tsts_pop_back(&todo);
372 if (tsts_is_empty(&todo)) {
375 --tsts_back(&todo)->rv;
380 tsts_push_back(&todo, next);
391 if (tsts_is_empty(&todo)) {
394 tsts_back(&todo)->rv +=
last.rv;
425 while (s0->
par && s0->
par != s0) {
436 for (r0 = s0; r0->
par && r0->
par != r0; r0 = r0->
par);
437 for (r1 =
s1; r1->
par && r1->
par != r1; r1 = r1->
par);
438 if (r0 == r1)
return r0;
442 else if (r1->
size < r0->
size) r = r0;
457 if (best &&
SLACK(best) == 0)
return best;
458 for (i = 0; (e =
ND_out(v).list[i]); i++) {
460 if (
aghead(e) == from)
continue;
465 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
471 for (i = 0; (e =
ND_in(v).list[i]); i++) {
473 if (
agtail(e) == from)
continue;
478 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
497 const size_t left = 2 * (i + 1) - 1;
498 const size_t right = 2 * (i + 1);
500 if (left < heap->size && elt[
left]->size < elt[smallest]->size) smallest =
left;
501 if (right < heap->size && elt[
right]->size < elt[smallest]->size) smallest =
right;
505 elt[i] = elt[smallest];
506 elt[smallest] = temp;
512 }
while (i < heap->size);
519 for (
size_t i = 0; i <
heap->size; i++)
heap->elt[i]->heap_index = i;
533 heap->elt[0]->heap_index = 0;
547 for (i = 0; (e =
ND_tree_in(v).list[i]); i++) {
597 size_t subtree_count = 0;
637 for (
size_t i = 0; i < subtree_count; i++)
free(
tree[i]);
714 agerrorf(
"update: mismatched lca in treeupdates\n");
719 int lca_low =
ND_low(lca);
733 int Minrank = INT_MAX;
734 int Maxrank = INT_MIN;
796#pragma GCC diagnostic push
797#pragma GCC diagnostic ignored "-Wcast-qual"
802#pragma GCC diagnostic pop
818#pragma GCC diagnostic push
819#pragma GCC diagnostic ignored "-Wcast-qual"
824#pragma GCC diagnostic pop
839 int low, high, choice;
840 int inweight, outweight;
847 assert(Maxrank >= 0);
848 int *nrank =
gv_calloc((
size_t)Maxrank + 1,
sizeof(
int));
849 if ( (
s =
agget(ctx->
G,
"TBbalance")) ) {
850 if (
streq(
s,
"min")) adj = 1;
851 else if (
streq(
s,
"max")) adj = 2;
854 if (
ND_in(n).size == 0 && adj == 1) {
857 if (
ND_out(n).size == 0 && adj == 2) {
878 inweight = outweight = 0;
881 for (
size_t i = 0; (e =
ND_in(n).list[i]); i++) {
885 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++) {
892 if (inweight == outweight)
893 ND_rank(n) = (adj == 1? low : high);
896 if (inweight == outweight) {
898 for (
int i = low + 1; i <= high; i++)
899 if (nrank[i] < nrank[choice])
922 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++)
929 bool feasible =
true;
933 for (i = 0; (e =
ND_in(n).list[i]); i++) {
942 for (i = 0; (e =
ND_out(n).list[i]); i++);
962 for (i = 0; (e =
ND_out(n).list[i]); i++) {
985 char *ns =
"network simplex: ";
995 fprintf(stderr,
"%s %d nodes %d edges maxiter=%d balance=%d\n", ns,
996 nn, ne, maxiter, balance);
1003 if (search_size >= 0)
1029 if (
Verbose && iter % 100 == 0) {
1030 if (iter % 1000 == 100)
1032 fprintf(stderr,
"%d ", iter);
1033 if (iter % 1000 == 0)
1034 fputc(
'\n', stderr);
1036 if (iter >= maxiter)
1054 fputc(
'\n', stderr);
1066 if ((
s =
agget(g,
"searchsize")))
1067 search_size = atoi(
s);
1071 return rank2 (g, balance, maxiter, search_size);
1091 for (i = 0; (e =
ND_out(v).list[i]); i++)
1093 agerrorf(
"overflow when computing edge weight sum\n");
1096 for (i = 0; (e =
ND_in(v).list[i]); i++)
1098 agerrorf(
"overflow when computing edge weight sum\n");
1150 for (i = 0; (e =
ND_tree_in(v).list[i]); i++)
1177 dfs_stack_t todo = {0};
1182 dfs_stack_push_back(&todo, root);
1184 while (!dfs_stack_is_empty(&todo)) {
1185 bool pushed_new =
false;
1196 dfs_stack_push_back(&todo, next);
1213 dfs_stack_push_back(&todo, next);
1225 (void)dfs_stack_pop_back(&todo);
1227 if (!dfs_stack_is_empty(&todo)) {
1228 dfs_stack_back(&todo)->lim = lim + 1;
1232 dfs_stack_free(&todo);
1248 dfs_stack_t todo = {0};
1252 const dfs_state_t root = {.
v = v, .par = par, .lim = low};
1253 dfs_stack_push_back(&todo, root);
1255 while (!dfs_stack_is_empty(&todo)) {
1256 bool processed_child =
false;
1270 dfs_stack_push_back(&todo, next);
1272 processed_child =
true;
1276 if (processed_child) {
1291 dfs_stack_push_back(&todo, next);
1293 processed_child =
true;
1297 if (processed_child) {
1304 (void)dfs_stack_pop_back(&todo);
1306 if (!dfs_stack_is_empty(&todo)) {
1307 dfs_stack_back(&todo)->lim = lim + 1;
1311 dfs_stack_free(&todo);
1330 fprintf(stderr,
"not a tight tree %p", e);
1334 fprintf(stderr,
"something missing\n");
1337void check_fast_node(
node_t * n)
1341 while (nptr && nptr != n)
1343 assert(nptr !=
NULL);
1346static void dump_node(FILE *sink,
node_t *n) {
1348 fprintf(sink,
"%p", n);
1354static void dump_graph (
graph_t* g)
1359 FILE* fp = fopen (
"ns.gv",
"w");
1360 fprintf (fp,
"digraph \"%s\" {\n",
agnameof(g));
1367 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1372 fputs(
" -> \"", fp);
1378 fprintf (fp,
"}\n");
1392 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1396 fprintf(stderr,
"cycle: last edge %lx %s(%lx) %s(%lx)\n",
1406 fprintf(stderr,
"unwind %lx %s(%lx)\n",
1409 if (x != n)
return x;
1410 fprintf(stderr,
"unwound to root\n");
static agxbuf last
last message
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
static NORETURN void graphviz_exit(int status)
static int cnt(Dict_t *d, Dtlink_t **set)
char * agget(void *obj, char *name)
void agerrorf(const char *fmt,...)
int agerr(agerrlevel_t level, const char *fmt,...)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
Agraph_t * agraphof(void *obj)
char * agnameof(void *)
returns a string descriptor for the object.
static Agedge_t * top(edge_stack_t *sp)
#define DEFINE_LIST(name, type)
NEATOPROCS_API void s1(graph_t *, node_t *)
static void TB_balance(network_simplex_ctx_t *ctx)
static subtree_t * merge_trees(network_simplex_ctx_t *ctx, Agedge_t *e)
static int x_val(edge_t *e, node_t *v, int dir)
static void freeTreeList(network_simplex_ctx_t *ctx, graph_t *g)
static void reset_lists(network_simplex_ctx_t *ctx)
static subtree_t * STextractmin(STheap_t *heap)
int rank(graph_t *g, int balance, int maxiter)
static int dfs_range(node_t *v, edge_t *par, int low)
static int update(network_simplex_ctx_t *ctx, edge_t *e, edge_t *f)
static void LR_balance(network_simplex_ctx_t *ctx)
static int increasingrankcmpf(const void *x, const void *y)
static int tight_subtree_search(network_simplex_ctx_t *ctx, Agnode_t *v, subtree_t *st)
a stack of states
static void dfs_cutval(node_t *v, edge_t *par)
static bool on_heap(const subtree_t *tree)
is this subtree stored in an STheap?
static size_t STheapsize(const STheap_t *heap)
static void init_cutvalues(network_simplex_ctx_t *ctx)
static STheap_t * STbuildheap(subtree_t **elt, size_t size)
static int decreasingrankcmpf(const void *x, const void *y)
#define ND_subtree_set(n, value)
static void init_rank(network_simplex_ctx_t *ctx)
static void dfs_enter_inedge(network_simplex_ctx_t *ctx, node_t *v)
static void exchange_tree_edges(network_simplex_ctx_t *ctx, edge_t *e, edge_t *f)
static int feasible_tree(network_simplex_ctx_t *ctx)
static edge_t * enter_edge(network_simplex_ctx_t *ctx, edge_t *e)
static Agnode_t * treeupdate(Agnode_t *v, Agnode_t *w, int cutvalue, int dir)
static void graphSize(graph_t *g, int *nn, int *ne)
static subtree_t * STsetFind(Agnode_t *n0)
static void rerank(Agnode_t *v, int delta)
static int dfs_range_init(node_t *v)
struct subtree_s subtree_t
static void x_cutval(edge_t *f)
static int scan_and_normalize(network_simplex_ctx_t *ctx)
static int add_tree_edge(network_simplex_ctx_t *ctx, edge_t *e)
static Agedge_t * inter_tree_edge_search(Agnode_t *v, Agnode_t *from, Agedge_t *best)
static void invalidate_path(node_t *lca, node_t *to_node)
static edge_t * leave_edge(network_simplex_ctx_t *ctx)
static subtree_t * find_tight_subtree(network_simplex_ctx_t *ctx, Agnode_t *v)
static void tree_adjust(Agnode_t *v, Agnode_t *from, int delta)
static bool init_graph(network_simplex_ctx_t *ctx, graph_t *g)
static subtree_t * STsetUnion(subtree_t *s0, subtree_t *s1)
static void dfs_enter_outedge(network_simplex_ctx_t *ctx, node_t *v)
static void STheapify(STheap_t *heap, size_t i)
int rank2(graph_t *g, int balance, int maxiter, int search_size)
static Agedge_t * inter_tree_edge(subtree_t *tree)
arithmetic overflow helpers
static bool sadd_overflow(int a, int b, int *res)
static int nedges
total no. of edges used in routing
static bool streq(const char *a, const char *b)
are a and b equal?
local state used by dfs_range*
size_t heap_index
required to find non-min elts when merged
state for use in tight_subtree_search
int out_i
iteration counter through ND_out(v).list
int in_i
iteration counter through ND_in(v).list