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)
64 agerrorf(
"add_tree_edge: missing tree edge\n");
67 assert(edge_list_size(&ctx->
Tree_edge) <= INT_MAX);
75 agerrorf(
"add_tree_edge: empty outedge list\n");
83 agerrorf(
"add_tree_edge: empty inedge list\n");
107 agerrorf(
"invalidate_path: skipped over LCA\n");
130 for (j = 0; j <= i; j++)
137 for (j = 0; j <= i; j++)
160 node_queue_t Q = {0};
161 node_queue_reserve(&Q, ctx->
N_nodes);
166 node_queue_push_back(&Q, v);
169 while (!node_queue_is_empty(&Q)) {
170 v = node_queue_pop_front(&Q);
173 for (i = 0; (e =
ND_in(v).list[i]); i++)
175 for (i = 0; (e =
ND_out(v).list[i]); i++) {
177 node_queue_push_back(&Q,
aghead(e));
209 while (ctx->
S_i < j) {
230 for (i = 0; (e =
ND_out(v).list[i]); i++) {
234 if (slack < ctx->Slack || ctx->
Enter ==
NULL) {
252 for (i = 0; (e =
ND_in(v).list[i]); i++) {
256 if (slack < ctx->Slack || ctx->
Enter ==
NULL) {
283 ctx->
Slack = INT_MAX;
301#define ND_subtree(n) (subtree_t*)ND_par(n)
302#define ND_subtree_set(n,value) (ND_par(n) = (edge_t*)value)
337 tsts_push_back(&todo, (
tst_t){.v = v, .rv = 1});
339 while (!tsts_is_empty(&todo)) {
340 bool updated =
false;
347 (void)tsts_pop_back(&todo);
348 if (tsts_is_empty(&todo)) {
351 --tsts_back(&todo)->rv;
356 tsts_push_back(&todo, next);
370 (void)tsts_pop_back(&todo);
371 if (tsts_is_empty(&todo)) {
374 --tsts_back(&todo)->rv;
379 tsts_push_back(&todo, next);
390 if (tsts_is_empty(&todo)) {
393 tsts_back(&todo)->rv +=
last.rv;
424 while (s0->
par && s0->
par != s0) {
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;
441 else if (r1->
size < r0->
size) r = r0;
456 if (best &&
SLACK(best) == 0)
return best;
457 for (i = 0; (e =
ND_out(v).list[i]); i++) {
459 if (
aghead(e) == from)
continue;
464 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
470 for (i = 0; (e =
ND_in(v).list[i]); i++) {
472 if (
agtail(e) == from)
continue;
477 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
496 const size_t left = 2 * (i + 1) - 1;
497 const size_t right = 2 * (i + 1);
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;
504 elt[i] = elt[smallest];
505 elt[smallest] = temp;
511 }
while (i < heap->size);
518 for (
size_t i = 0; i <
heap->size; i++)
heap->elt[i]->heap_index = i;
532 heap->elt[0]->heap_index = 0;
546 for (i = 0; (e =
ND_tree_in(v).list[i]); i++) {
596 size_t subtree_count = 0;
636 for (
size_t i = 0; i < subtree_count; i++)
free(
tree[i]);
713 agerrorf(
"update: mismatched lca in treeupdates\n");
718 int lca_low =
ND_low(lca);
732 int Minrank = INT_MAX;
733 int Maxrank = INT_MIN;
767 for (
size_t i = 0; i < edge_list_size(&ctx->
Tree_edge); i++) {
790#pragma GCC diagnostic push
791#pragma GCC diagnostic ignored "-Wcast-qual"
796#pragma GCC diagnostic pop
815 int low, high, choice;
816 int inweight, outweight;
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;
830 if (
ND_in(n).size == 0 && adj == 1) {
833 if (
ND_out(n).size == 0 && adj == 2) {
838 node_list_t Tree_node = {0};
839 node_list_reserve(&Tree_node, ctx->
N_nodes);
841 node_list_append(&Tree_node, n);
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);
850 for (
size_t ii = 0; ii < node_list_size(&Tree_node); ii++) {
851 n = node_list_get(&Tree_node, ii);
854 inweight = outweight = 0;
857 for (
size_t i = 0; (e =
ND_in(n).list[i]); i++) {
861 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++) {
868 if (inweight == outweight)
869 ND_rank(n) = (adj == 1? low : high);
872 if (inweight == outweight) {
874 for (
int i = low + 1; i <= high; i++)
875 if (nrank[i] < nrank[choice])
886 node_list_free(&Tree_node);
899 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++)
905 bool feasible =
true;
909 for (i = 0; (e =
ND_in(n).list[i]); i++) {
918 for (i = 0; (e =
ND_out(n).list[i]); i++);
938 for (i = 0; (e =
ND_out(n).list[i]); i++) {
961 char *ns =
"network simplex: ";
971 fprintf(stderr,
"%s %d nodes %d edges maxiter=%d balance=%d\n", ns,
972 nn, ne, maxiter, balance);
979 if (search_size >= 0)
1005 if (
Verbose && iter % 100 == 0) {
1006 if (iter % 1000 == 100)
1008 fprintf(stderr,
"%d ", iter);
1009 if (iter % 1000 == 0)
1010 fputc(
'\n', stderr);
1012 if (iter >= maxiter)
1030 fputc(
'\n', stderr);
1042 if ((
s =
agget(g,
"searchsize")))
1043 search_size = atoi(
s);
1047 return rank2 (g, balance, maxiter, search_size);
1067 for (i = 0; (e =
ND_out(v).list[i]); i++)
1069 agerrorf(
"overflow when computing edge weight sum\n");
1072 for (i = 0; (e =
ND_in(v).list[i]); i++)
1074 agerrorf(
"overflow when computing edge weight sum\n");
1126 for (i = 0; (e =
ND_tree_in(v).list[i]); i++)
1153 dfs_stack_t todo = {0};
1158 dfs_stack_push_back(&todo, root);
1160 while (!dfs_stack_is_empty(&todo)) {
1161 bool pushed_new =
false;
1172 dfs_stack_push_back(&todo, next);
1189 dfs_stack_push_back(&todo, next);
1201 (void)dfs_stack_pop_back(&todo);
1203 if (!dfs_stack_is_empty(&todo)) {
1204 dfs_stack_back(&todo)->lim = lim + 1;
1208 dfs_stack_free(&todo);
1224 dfs_stack_t todo = {0};
1228 const dfs_state_t root = {.
v = v, .par = par, .lim = low};
1229 dfs_stack_push_back(&todo, root);
1231 while (!dfs_stack_is_empty(&todo)) {
1232 bool processed_child =
false;
1246 dfs_stack_push_back(&todo, next);
1248 processed_child =
true;
1252 if (processed_child) {
1267 dfs_stack_push_back(&todo, next);
1269 processed_child =
true;
1273 if (processed_child) {
1280 (void)dfs_stack_pop_back(&todo);
1282 if (!dfs_stack_is_empty(&todo)) {
1283 dfs_stack_back(&todo)->lim = lim + 1;
1287 dfs_stack_free(&todo);
1306 fprintf(stderr,
"not a tight tree %p", e);
1309 if (e_cnt != edge_list_size(&ctx->
Tree_edge))
1310 fprintf(stderr,
"something missing\n");
1313void check_fast_node(
node_t * n)
1317 while (nptr && nptr != n)
1319 assert(nptr !=
NULL);
1322static void dump_node(FILE *sink,
node_t *n) {
1324 fprintf(sink,
"%p", n);
1330static void dump_graph (
graph_t* g)
1335 FILE* fp = fopen (
"ns.gv",
"w");
1336 fprintf (fp,
"digraph \"%s\" {\n",
agnameof(g));
1343 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1348 fputs(
" -> \"", fp);
1354 fprintf (fp,
"}\n");
1368 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1372 fprintf(stderr,
"cycle: last edge %lx %s(%lx) %s(%lx)\n",
1382 fprintf(stderr,
"unwind %lx %s(%lx)\n",
1385 if (x != n)
return x;
1386 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 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)
#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 int increasingrankcmpf(const node_t **x, const node_t **y)
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 int decreasingrankcmpf(const node_t **x, const node_t **y)
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