37static void check_cycles(
graph_t * g);
40#define LENGTH(e) (ND_rank(aghead(e)) - ND_rank(agtail(e)))
41#define SLACK(e) (LENGTH(e) - ED_minlen(e))
42#define SEQ(a,b,c) ((a) <= (b) && (b) <= (c))
43#define TREE_EDGE(e) (ED_tree_index(e) >= 0)
49 size_t N_edges, N_nodes;
58 agerrorf(
"add_tree_edge: missing tree edge\n");
61 assert(
LIST_SIZE(&ctx->Tree_edge) <= INT_MAX);
69 agerrorf(
"add_tree_edge: empty outedge list\n");
77 agerrorf(
"add_tree_edge: empty inedge list\n");
101 agerrorf(
"invalidate_path: skipped over LCA\n");
122 for (j = 0; j <= i; j++)
129 for (j = 0; j <= i; j++)
161 for (
int i = 0; (e =
ND_in(v).list[i]); i++)
163 for (
int i = 0; (e =
ND_out(v).list[i]); i++) {
168 if (ctr != ctx->N_nodes) {
183 while (ctx->S_i <
LIST_SIZE(&ctx->Tree_edge)) {
189 rv =
LIST_GET(&ctx->Tree_edge, ctx->S_i);
190 if (++
cnt >= ctx->Search_size)
197 while (ctx->S_i < j) {
203 rv =
LIST_GET(&ctx->Tree_edge, ctx->S_i);
204 if (++
cnt >= ctx->Search_size)
224 for (
int i = 0; (e =
ND_out(v).list[i]); i++) {
227 const int slack =
SLACK(e);
228 if (slack < Slack || Enter ==
NULL) {
236 for (
int i = 0; (e =
ND_tree_in(v).list[i]) && Slack > 0; i++)
258 for (
int i = 0; (e =
ND_in(v).list[i]); i++) {
261 const int slack =
SLACK(e);
262 if (slack < Slack || Enter ==
NULL) {
270 for (
int i = 0; (e =
ND_tree_out(v).list[i]) && Slack > 0; i++)
305#define ND_subtree(n) (subtree_t*)ND_par(n)
306#define ND_subtree_set(n,value) (ND_par(n) = (edge_t*)value)
340 bool updated =
false;
423 while (s0->
par && s0->
par != s0) {
434 for (r0 = s0; r0->
par && r0->
par != r0; r0 = r0->
par);
435 for (r1 =
s1; r1->
par && r1->
par != r1; r1 = r1->
par);
436 if (r0 == r1)
return r0;
440 else if (r1->
size < r0->
size) r = r0;
454 if (best &&
SLACK(best) == 0)
return best;
455 for (
int i = 0; (e =
ND_out(v).list[i]); i++) {
457 if (
aghead(e) == from)
continue;
462 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
468 for (
int i = 0; (e =
ND_in(v).list[i]); i++) {
470 if (
agtail(e) == from)
continue;
475 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
492 const size_t left = 2 * (i + 1) - 1;
493 const size_t right = 2 * (i + 1);
495 if (left < heap->size && elt[
left]->size < elt[smallest]->size) smallest =
left;
496 if (right < heap->size && elt[
right]->size < elt[smallest]->size) smallest =
right;
498 SWAP(&elt[i], &elt[smallest]);
504 }
while (i < heap->size);
511 for (
size_t i = 0; i <
heap->size; i++)
heap->elt[i]->heap_index = i;
524 heap->elt[0]->heap_index = 0;
536 for (
int i = 0; (e =
ND_tree_in(v).list[i]); i++) {
541 for (
int i = 0; (e =
ND_tree_out(v).list[i]); i++) {
581 size_t subtree_count = 0;
621 for (
size_t i = 0; i < subtree_count; i++)
free(
tree[i]);
624 assert(
LIST_SIZE(&ctx->Tree_edge) == ctx->N_nodes - 1);
633 const bool d = v ==
agtail(e) ? dir : !dir;
654 for (
int i = 0; (e =
ND_tree_in(v).list[i]); i++)
687 agerrorf(
"update: mismatched lca in treeupdates\n");
692 int lca_low =
ND_low(lca);
704 int Minrank = INT_MAX;
705 int Maxrank = INT_MIN;
735 for (
size_t i = 0; i <
LIST_SIZE(&ctx->Tree_edge); i++) {
778 assert(Maxrank >= 0);
779 int *nrank =
gv_calloc((
size_t)Maxrank + 1,
sizeof(
int));
780 if ( (
s =
agget(ctx->
G,
"TBbalance")) ) {
781 if (
streq(
s,
"min")) adj = 1;
782 else if (
streq(
s,
"max")) adj = 2;
785 if (
ND_in(n).size == 0 && adj == 1) {
788 if (
ND_out(n).size == 0 && adj == 2) {
799 for (
size_t i = 0; i <
LIST_SIZE(&Tree_node); i++) {
804 for (
size_t ii = 0; ii <
LIST_SIZE(&Tree_node); ii++) {
812 for (
size_t i = 0; (e =
ND_in(n).list[i]); i++) {
816 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++) {
823 if (inweight == outweight)
824 ND_rank(n) = adj == 1 ? low : high;
827 if (inweight == outweight) {
829 for (
int i = low + 1; i <= high; i++)
830 if (nrank[i] < nrank[choice])
852 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++)
858 bool feasible =
true;
862 for (i = 0; (e =
ND_in(n).list[i]); i++) {
871 for (i = 0; (e =
ND_out(n).list[i]); i++);
888 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++) {
911 char ns[] =
"network simplex: ";
922 " edges maxiter=%d balance=%d\n", ns, nn, ne, maxiter, balance);
929 if (search_size >= 0)
930 ctx.Search_size = search_size;
954 if (
Verbose && iter % 100 == 0) {
955 if (iter % 1000 == 100)
957 fprintf(stderr,
"%d ", iter);
958 if (iter % 1000 == 0)
981 ns, ctx.N_nodes, ctx.N_edges, iter,
elapsed_sec());
991 if ((
s =
agget(g,
"searchsize")))
992 search_size = atoi(
s);
996 return rank2 (g, balance, maxiter, search_size);
1016 for (
int i = 0; (e =
ND_out(v).list[i]); i++)
1018 agerrorf(
"overflow when computing edge weight sum\n");
1021 for (
int i = 0; (e =
ND_in(v).list[i]); i++)
1023 agerrorf(
"overflow when computing edge weight sum\n");
1071 for (
int i = 0; (e =
ND_tree_out(v).list[i]); i++)
1074 for (
int i = 0; (e =
ND_tree_in(v).list[i]); i++)
1107 bool pushed_new =
false;
1174 const dfs_state_t root = {.
v = v, .par = par, .lim = low};
1178 bool processed_child =
false;
1194 processed_child =
true;
1198 if (processed_child) {
1215 processed_child =
true;
1219 if (processed_child) {
1247 for (
int i = 0; (e =
ND_tree_out(n).list[i]); i++) {
1250 fprintf(stderr,
"not a tight tree %p", e);
1253 if (e_cnt !=
LIST_SIZE(&ctx->Tree_edge))
1254 fprintf(stderr,
"something missing\n");
1257void check_fast_node(
node_t * n)
1260 while (nptr && nptr != n)
1262 assert(nptr !=
NULL);
1265static void dump_node(FILE *sink,
node_t *n) {
1267 fprintf(sink,
"%p", n);
1273static void dump_graph (
graph_t* g)
1276 FILE *
const fp = fopen (
"ns.gv",
"w");
1277 fprintf (fp,
"digraph \"%s\" {\n",
agnameof(g));
1284 for (
int i = 0; (e =
ND_out(n).list[i]); i++) {
1289 fputs(
" -> \"", fp);
1295 fprintf (fp,
"}\n");
1307 for (
int i = 0; (e =
ND_out(n).list[i]); i++) {
1311 fprintf(stderr,
"cycle: last edge %p %s(%p) %s(%p)\n", e,
agnameof(n), n,
1317 node_t *
const x = checkdfs(g, w);
1319 fprintf(stderr,
"unwind %p %s(%p)\n", e,
agnameof(n), n);
1320 if (x != n)
return x;
1321 fprintf(stderr,
"unwound to root\n");
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.
Arithmetic helper functions.
static Agedge_t * top(edge_stack_t *sp)
type-generic dynamically expanding list
#define LIST_POP_FRONT(list)
#define LIST_APPEND(list, item)
#define LIST_RESERVE(list, capacity)
#define LIST_POP_BACK(list)
#define LIST_SORT(list, cmp)
#define LIST_SET(list, index, item)
#define LIST_IS_EMPTY(list)
#define LIST_PUSH_BACK(list, item)
#define LIST_GET(list, index)
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)
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 edge_t * dfs_enter_outedge(node_t *v, int Low, int Lim)
static size_t STheapsize(const STheap_t *heap)
static Agnode_t * treeupdate(Agnode_t *v, Agnode_t *w, int cutvalue, bool dir)
static void init_cutvalues(network_simplex_ctx_t *ctx)
static STheap_t * STbuildheap(subtree_t **elt, size_t size)
static edge_t * enter_edge(edge_t *e)
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 exchange_tree_edges(network_simplex_ctx_t *ctx, edge_t *e, edge_t *f)
static int feasible_tree(network_simplex_ctx_t *ctx)
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 STheapify(STheap_t *heap, size_t i)
static void graphSize(graph_t *g, size_t *nn, size_t *ne)
static edge_t * dfs_enter_inedge(node_t *v, int Low, int Lim)
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