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++)
164 for (i = 0; (e =
ND_in(v).list[i]); i++)
166 for (i = 0; (e =
ND_out(v).list[i]); i++) {
224 for (i = 0; (e =
ND_out(v).list[i]); i++) {
246 for (i = 0; (e =
ND_in(v).list[i]); i++) {
295#define ND_subtree(n) (subtree_t*)ND_par(n)
296#define ND_subtree_set(n,value) (ND_par(n) = (edge_t*)value)
319 for (i = 0; (e =
ND_in(v).list[i]); i++) {
328 for (i = 0; (e =
ND_out(v).list[i]); i++) {
362 while (s0->
par && s0->
par != s0) {
373 for (r0 = s0; r0->
par && r0->
par != r0; r0 = r0->
par);
374 for (r1 =
s1; r1->
par && r1->
par != r1; r1 = r1->
par);
375 if (r0 == r1)
return r0;
379 else if (r1->
size < r0->
size) r = r0;
394 if (best &&
SLACK(best) == 0)
return best;
395 for (i = 0; (e =
ND_out(v).list[i]); i++) {
397 if (
aghead(e) == from)
continue;
402 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
408 for (i = 0; (e =
ND_in(v).list[i]); i++) {
410 if (
agtail(e) == from)
continue;
415 if (best == 0 ||
SLACK(e) <
SLACK(best)) best = e;
434 const size_t left = 2 * (i + 1) - 1;
435 const size_t right = 2 * (i + 1);
437 if (left < heap->size && elt[
left]->size < elt[smallest]->size) smallest =
left;
438 if (right < heap->size && elt[
right]->size < elt[smallest]->size) smallest =
right;
442 elt[i] = elt[smallest];
443 elt[smallest] = temp;
449 }
while (i < heap->size);
456 for (
size_t i = 0; i <
heap->size; i++)
heap->elt[i]->heap_index = i;
470 heap->elt[0]->heap_index = 0;
484 for (i = 0; (e =
ND_tree_in(v).list[i]); i++) {
534 size_t subtree_count = 0;
574 for (
size_t i = 0; i < subtree_count; i++)
free(
tree[i]);
651 agerrorf(
"update: mismatched lca in treeupdates\n");
656 int lca_low =
ND_low(lca);
670 int Minrank = INT_MAX;
671 int Maxrank = INT_MIN;
733#pragma GCC diagnostic push
734#pragma GCC diagnostic ignored "-Wcast-qual"
739#pragma GCC diagnostic pop
755#pragma GCC diagnostic push
756#pragma GCC diagnostic ignored "-Wcast-qual"
761#pragma GCC diagnostic pop
776 int low, high, choice;
777 int inweight, outweight;
784 assert(Maxrank >= 0);
785 int *nrank =
gv_calloc((
size_t)Maxrank + 1,
sizeof(
int));
786 if ( (
s =
agget(
G,
"TBbalance")) ) {
787 if (
streq(
s,
"min")) adj = 1;
788 else if (
streq(
s,
"max")) adj = 2;
791 if (
ND_in(n).size == 0 && adj == 1) {
794 if (
ND_out(n).size == 0 && adj == 2) {
815 inweight = outweight = 0;
818 for (
size_t i = 0; (e =
ND_in(n).list[i]); i++) {
822 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++) {
829 if (inweight == outweight)
830 ND_rank(n) = (adj == 1? low : high);
833 if (inweight == outweight) {
835 for (
int i = low + 1; i <= high; i++)
836 if (nrank[i] < nrank[choice])
859 for (
size_t i = 0; (e =
ND_out(n).list[i]); i++)
866 bool feasible =
true;
870 for (i = 0; (e =
ND_in(n).list[i]); i++) {
879 for (i = 0; (e =
ND_out(n).list[i]); i++);
899 for (i = 0; (e =
ND_out(n).list[i]); i++) {
922 char *ns =
"network simplex: ";
931 fprintf(stderr,
"%s %d nodes %d edges maxiter=%d balance=%d\n", ns,
932 nn, ne, maxiter, balance);
939 if (search_size >= 0)
965 if (
Verbose && iter % 100 == 0) {
966 if (iter % 1000 == 100)
968 fprintf(stderr,
"%d ", iter);
969 if (iter % 1000 == 0)
1002 if ((
s =
agget(g,
"searchsize")))
1003 search_size = atoi(
s);
1007 return rank2 (g, balance, maxiter, search_size);
1027 for (i = 0; (e =
ND_out(v).list[i]); i++)
1029 agerrorf(
"overflow when computing edge weight sum\n");
1032 for (i = 0; (e =
ND_in(v).list[i]); i++)
1034 agerrorf(
"overflow when computing edge weight sum\n");
1086 for (i = 0; (e =
ND_tree_in(v).list[i]); i++)
1143 for (i = 0; (e =
ND_tree_in(v).list[i]); i++)
1164 fprintf(stderr,
"not a tight tree %p", e);
1168 fprintf(stderr,
"something missing\n");
1171void check_fast_node(
node_t * n)
1175 while (nptr && nptr != n)
1177 assert(nptr !=
NULL);
1180static void dump_node(FILE *sink,
node_t *n) {
1182 fprintf(sink,
"%p", n);
1188static void dump_graph (
graph_t* g)
1193 FILE* fp = fopen (
"ns.gv",
"w");
1194 fprintf (fp,
"digraph \"%s\" {\n",
agnameof(g));
1201 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1206 fputs(
" -> \"", fp);
1212 fprintf (fp,
"}\n");
1226 for (i = 0; (e =
ND_out(n).list[i]); i++) {
1230 fprintf(stderr,
"cycle: last edge %lx %s(%lx) %s(%lx)\n",
1240 fprintf(stderr,
"unwind %lx %s(%lx)\n",
1243 if (x != n)
return x;
1244 fprintf(stderr,
"unwound to root\n");
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
void error(int level, const char *s,...)
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.
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 int dfs_range_init(node_t *v, edge_t *par, int low)
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)
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)
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)
#define PRISIZE_T
PRIu64 alike for printing size_t
generic first-in-first-out buffer (queue)
static queue_t queue_new(size_t hint)
static void queue_free(queue_t *q)
static void queue_push(queue_t *q, void *item)
static void * queue_pop(queue_t *q)
static int nedges
total no. of edges used in routing
static bool streq(const char *a, const char *b)
are a and b equal?
size_t heap_index
required to find non-min elts when merged