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)
56 agerrorf(
"add_tree_edge: missing tree edge\n");
71 agerrorf(
"add_tree_edge: empty outedge list\n");
79 agerrorf(
"add_tree_edge: empty inedge list\n");
103 agerrorf(
"invalidate_path: skipped over LCA\n");
125 for (j = 0; j <= i; j++)
132 for (j = 0; j <= i; j++)
155 node_queue_t Q = {0};
156 node_queue_reserve(&Q,
N_nodes);
161 node_queue_push_back(&Q, v);
164 while (!node_queue_is_empty(&Q)) {
165 v = node_queue_pop_front(&Q);
168 for (i = 0; (e =
ND_in(v).list[i]); i++)
170 for (i = 0; (e =
ND_out(v).list[i]); i++) {
172 node_queue_push_back(&Q,
aghead(e));
228 for (i = 0; (e =
ND_out(v).list[i]); i++) {
250 for (i = 0; (e =
ND_in(v).list[i]); i++) {
299#define ND_subtree(n) (subtree_t*)ND_par(n)
300#define ND_subtree_set(n,value) (ND_par(n) = (edge_t*)value)
335 tsts_push_back(&todo, (
tst_t){.v = v, .rv = 1});
337 while (!tsts_is_empty(&todo)) {
338 bool updated =
false;
345 (void)tsts_pop_back(&todo);
346 if (tsts_is_empty(&todo)) {
349 --tsts_back(&todo)->rv;
354 tsts_push_back(&todo, next);
368 (void)tsts_pop_back(&todo);
369 if (tsts_is_empty(&todo)) {
372 --tsts_back(&todo)->rv;
377 tsts_push_back(&todo, next);
388 if (tsts_is_empty(&todo)) {
391 tsts_back(&todo)->rv +=
last.rv;
422 while (s0->
par && s0->
par != s0) {
433 for (r0 = s0; r0->
par && r0->
par != r0; r0 = r0->
par);
434 for (r1 =
s1; r1->
par && r1->
par != r1; r1 = r1->
par);
435 if (r0 == r1)
return r0;
439 else if (r1->
size < r0->
size) r = r0;
454 if (best &&
SLACK(best) == 0)
return best;
455 for (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 (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;
494 const size_t left = 2 * (i + 1) - 1;
495 const size_t right = 2 * (i + 1);
497 if (left < heap->size && elt[
left]->size < elt[smallest]->size) smallest =
left;
498 if (right < heap->size && elt[
right]->size < elt[smallest]->size) smallest =
right;
502 elt[i] = elt[smallest];
503 elt[smallest] = temp;
509 }
while (i < heap->size);
516 for (
size_t i = 0; i <
heap->size; i++)
heap->elt[i]->heap_index = i;
530 heap->elt[0]->heap_index = 0;
544 for (i = 0; (e =
ND_tree_in(v).list[i]); i++) {
594 size_t subtree_count = 0;
634 for (
size_t i = 0; i < subtree_count; i++)
free(
tree[i]);
711 agerrorf(
"update: mismatched lca in treeupdates\n");
716 int lca_low =
ND_low(lca);
730 int Minrank = INT_MAX;
731 int Maxrank = INT_MIN;
793#pragma GCC diagnostic push
794#pragma GCC diagnostic ignored "-Wcast-qual"
799#pragma GCC diagnostic pop
815#pragma GCC diagnostic push
816#pragma GCC diagnostic ignored "-Wcast-qual"
821#pragma GCC diagnostic pop
836 int low, high, choice;
837 int inweight, outweight;
844 assert(Maxrank >= 0);
845 int *nrank =
gv_calloc((
size_t)Maxrank + 1,
sizeof(
int));
846 if ( (
s =
agget(
G,
"TBbalance")) ) {
847 if (
streq(
s,
"min")) adj = 1;
848 else if (
streq(
s,
"max")) adj = 2;
851 if (
ND_in(n).size == 0 && adj == 1) {
854 if (
ND_out(n).size == 0 && adj == 2) {
875 inweight = outweight = 0;
878 for (
size_t i = 0; (e =
ND_in(n).list[i]); i++) {
882 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++) {
889 if (inweight == outweight)
890 ND_rank(n) = (adj == 1? low : high);
893 if (inweight == outweight) {
895 for (
int i = low + 1; i <= high; i++)
896 if (nrank[i] < nrank[choice])
919 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++)
926 bool feasible =
true;
930 for (i = 0; (e =
ND_in(n).list[i]); i++) {
939 for (i = 0; (e =
ND_out(n).list[i]); i++);
959 for (i = 0; (e =
ND_out(n).list[i]); i++) {
982 char *ns =
"network simplex: ";
991 fprintf(stderr,
"%s %d nodes %d edges maxiter=%d balance=%d\n", ns,
992 nn, ne, maxiter, balance);
999 if (search_size >= 0)
1025 if (
Verbose && iter % 100 == 0) {
1026 if (iter % 1000 == 100)
1028 fprintf(stderr,
"%d ", iter);
1029 if (iter % 1000 == 0)
1030 fputc(
'\n', stderr);
1032 if (iter >= maxiter)
1050 fputc(
'\n', stderr);
1062 if ((
s =
agget(g,
"searchsize")))
1063 search_size = atoi(
s);
1067 return rank2 (g, balance, maxiter, search_size);
1087 for (i = 0; (e =
ND_out(v).list[i]); i++)
1089 agerrorf(
"overflow when computing edge weight sum\n");
1092 for (i = 0; (e =
ND_in(v).list[i]); i++)
1094 agerrorf(
"overflow when computing edge weight sum\n");
1146 for (i = 0; (e =
ND_tree_in(v).list[i]); i++)
1173 dfs_stack_t todo = {0};
1178 dfs_stack_push_back(&todo, root);
1180 while (!dfs_stack_is_empty(&todo)) {
1181 bool pushed_new =
false;
1192 dfs_stack_push_back(&todo, next);
1209 dfs_stack_push_back(&todo, next);
1221 (void)dfs_stack_pop_back(&todo);
1223 if (!dfs_stack_is_empty(&todo)) {
1224 dfs_stack_back(&todo)->lim = lim + 1;
1228 dfs_stack_free(&todo);
1244 dfs_stack_t todo = {0};
1248 const dfs_state_t root = {.
v = v, .par = par, .lim = low};
1249 dfs_stack_push_back(&todo, root);
1251 while (!dfs_stack_is_empty(&todo)) {
1252 bool processed_child =
false;
1266 dfs_stack_push_back(&todo, next);
1268 processed_child =
true;
1272 if (processed_child) {
1287 dfs_stack_push_back(&todo, next);
1289 processed_child =
true;
1293 if (processed_child) {
1300 (void)dfs_stack_pop_back(&todo);
1302 if (!dfs_stack_is_empty(&todo)) {
1303 dfs_stack_back(&todo)->lim = lim + 1;
1307 dfs_stack_free(&todo);
1326 fprintf(stderr,
"not a tight tree %p", e);
1330 fprintf(stderr,
"something missing\n");
1333void check_fast_node(
node_t * n)
1337 while (nptr && nptr != n)
1339 assert(nptr !=
NULL);
1342static void dump_node(FILE *sink,
node_t *n) {
1344 fprintf(sink,
"%p", n);
1350static void dump_graph (
graph_t* g)
1355 FILE* fp = fopen (
"ns.gv",
"w");
1356 fprintf (fp,
"digraph \"%s\" {\n",
agnameof(g));
1363 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1368 fputs(
" -> \"", fp);
1374 fprintf (fp,
"}\n");
1388 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1392 fprintf(stderr,
"cycle: last edge %lx %s(%lx) %s(%lx)\n",
1402 fprintf(stderr,
"unwind %lx %s(%lx)\n",
1405 if (x != n)
return x;
1406 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 freeTreeList(graph_t *g)
static int update(edge_t *e, edge_t *f)
static int x_val(edge_t *e, node_t *v, int dir)
static void init_cutvalues(void)
static subtree_t * STextractmin(STheap_t *heap)
static int feasible_tree(void)
int rank(graph_t *g, int balance, int maxiter)
static subtree_t * merge_trees(Agedge_t *e)
static int dfs_range(node_t *v, edge_t *par, int low)
static void reset_lists(void)
static void TB_balance(void)
static void dfs_enter_inedge(node_t *v)
static int increasingrankcmpf(const void *x, const void *y)
static subtree_t * find_tight_subtree(Agnode_t *v)
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 bool init_graph(graph_t *g)
static size_t STheapsize(const STheap_t *heap)
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)
static void init_rank(void)
static int scan_and_normalize(void)
#define ND_subtree_set(n, value)
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 void LR_balance(void)
static int dfs_range_init(node_t *v)
struct subtree_s subtree_t
static void x_cutval(edge_t *f)
static int add_tree_edge(edge_t *e)
static Agedge_t * inter_tree_edge_search(Agnode_t *v, Agnode_t *from, Agedge_t *best)
static void exchange_tree_edges(edge_t *e, edge_t *f)
static edge_t * leave_edge(void)
static void invalidate_path(node_t *lca, node_t *to_node)
static void tree_adjust(Agnode_t *v, Agnode_t *from, int delta)
static subtree_t * STsetUnion(subtree_t *s0, subtree_t *s1)
static int tight_subtree_search(Agnode_t *v, subtree_t *st)
a stack of states
static void STheapify(STheap_t *heap, size_t i)
int rank2(graph_t *g, int balance, int maxiter, int search_size)
static void dfs_enter_outedge(node_t *v)
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