ns.c   [plain text]

/*
    This software may only be used by you under license from AT&T Corp.
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
    AT&T's Internet website having the URL:
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
    If you received this software without first entering into a license
    with AT&T, you have an infringing copy of this software and cannot use
    it without violating AT&T's intellectual property rights.
*/
#pragma prototyped

/* 
 * Network Simplex Algorithm for Ranking Nodes of a DAG
 */

#include "dot.h"


static int init_graph(graph_t *);

#define LENGTH(e)		(ND_rank(e->head) - ND_rank(e->tail))
#define SLACK(e)		(LENGTH(e) - ED_minlen(e))
#define SEQ(a,b,c)		(((a) <= (b)) && ((b) <= (c)))
#define TREE_EDGE(e)	(ED_tree_index(e) >= 0)

static graph_t	*G;
static int		N_nodes,N_edges;
static int		Minrank,Maxrank;
static int		S_i;		/* search index for enter_edge */
static int		Search_size;
#define SEARCHSIZE 30
static nlist_t	Tree_node;
static elist	Tree_edge;

void add_tree_edge(edge_t* e)
{
	node_t	*n;
	if (TREE_EDGE(e)) abort();
	ED_tree_index(e) = Tree_edge.size;
	Tree_edge.list[Tree_edge.size++] = e;
	if (ND_mark(e->tail) == FALSE) Tree_node.list[Tree_node.size++] = e->tail;
	if (ND_mark(e->head) == FALSE) Tree_node.list[Tree_node.size++] = e->head;
	n = e->tail;
	ND_mark(n) = TRUE;
	ND_tree_out(n).list[ND_tree_out(n).size++] = e;
	ND_tree_out(n).list[ND_tree_out(n).size] = NULL;
	if (ND_out(n).list[ND_tree_out(n).size-1] == 0) abort();
	n = e->head;
	ND_mark(n) = TRUE;
	ND_tree_in(n).list[ND_tree_in(n).size++] = e;
	ND_tree_in(n).list[ND_tree_in(n).size] = NULL;
	if (ND_in(n).list[ND_tree_in(n).size-1] == 0) abort();
}

void exchange_tree_edges(edge_t *e,edge_t *f)
{
	int		i,j;
	node_t	*n;

	ED_tree_index(f) = ED_tree_index(e);
	Tree_edge.list[ED_tree_index(e)] = f;
	ED_tree_index(e) = -1;

	n = e->tail;
	i = --(ND_tree_out(n).size);
	for (j = 0; j <= i; j++) if (ND_tree_out(n).list[j] == e) break;
	ND_tree_out(n).list[j] = ND_tree_out(n).list[i];
	ND_tree_out(n).list[i] = NULL;
	n = e->head;
	i = --(ND_tree_in(n).size);
	for (j = 0; j <= i; j++) if (ND_tree_in(n).list[j] == e) break;
	ND_tree_in(n).list[j] = ND_tree_in(n).list[i];
	ND_tree_in(n).list[i] = NULL;

	n = f->tail;
	ND_tree_out(n).list[ND_tree_out(n).size++] = f;
	ND_tree_out(n).list[ND_tree_out(n).size] = NULL;
	n = f->head;
	ND_tree_in(n).list[ND_tree_in(n).size++] = f;
	ND_tree_in(n).list[ND_tree_in(n).size] = NULL;
}

void init_rank(void)
{
	int			i,ctr;
	queue		*Q;
	node_t		*v;
	edge_t		*e;

	Q = new_queue(N_nodes);
	ctr = 0;

	for (v = GD_nlist(G); v; v = ND_next(v)) {
		if (ND_priority(v) == 0) enqueue(Q,v);
	}

	while ((v = dequeue(Q))) {
		ND_rank(v) = 0;
		ctr++;
		for (i = 0; (e = ND_in(v).list[i]); i++)
			ND_rank(v) = MAX(ND_rank(v),ND_rank(e->tail) + ED_minlen(e));
		for (i = 0; (e = ND_out(v).list[i]); i++) {
			if (--(ND_priority(e->head)) <= 0) enqueue(Q,e->head);
		}
	}
	if (ctr != N_nodes) {
		agerr(AGERR, "trouble in init_rank\n");
		for (v = GD_nlist(G); v; v = ND_next(v))
			if (ND_priority(v))
				agerr(AGPREV, "\t%s %d\n",v->name,ND_priority(v));
	}
	free_queue(Q);
}

node_t *
incident(edge_t* e)
{
	if (ND_mark(e->tail)) {
		if (ND_mark(e->head) == FALSE)
			return e->tail;
	}
	else {
		if (ND_mark(e->head))
			return e->head;
	}
	return NULL;
}

edge_t *
leave_edge (void)
{
	edge_t			*f,*rv = NULL;
	int				j,cnt = 0;

	j = S_i;
	while (S_i < Tree_edge.size) {
		if ((f = Tree_edge.list[S_i])->u.cutvalue < 0) {
			if (rv) {
				if (ED_cutvalue(rv) > ED_cutvalue(f)) rv = f;
			}
			else rv = Tree_edge.list[S_i];
			if (++cnt >= Search_size) return rv;
		}
		S_i++;
	}
	if (j > 0) {
		S_i = 0;
		while (S_i < j) {
			if ((f = Tree_edge.list[S_i])->u.cutvalue < 0) {
				if (rv) {
					if (ED_cutvalue(rv) > ED_cutvalue(f)) rv = f;
				}
				else rv = Tree_edge.list[S_i];
				if (++cnt >= Search_size) return rv;
			}
			S_i++;
		}
	}
	return rv;
}

static edge_t	*Enter;
static int		Low,Lim,Slack;

void dfs_enter_outedge(node_t* v)
{
	int		i,slack;
	edge_t	*e;

	for (i = 0; (e = ND_out(v).list[i]); i++) {
		if (TREE_EDGE(e) == FALSE) {
			if (!SEQ(Low,ND_lim(e->head),Lim)) {
				slack = SLACK(e);
				if ((slack < Slack) || (Enter == NULL)) {
					Enter = e;
					Slack = slack;
				}
			}
		}
		else if (ND_lim(e->head) < ND_lim(v)) dfs_enter_outedge(e->head);
	}
	for (i = 0; (e = ND_tree_in(v).list[i]) && (Slack > 0); i++)
		if (ND_lim(e->tail) < ND_lim(v)) dfs_enter_outedge(e->tail);
}

void dfs_enter_inedge(node_t* v)
{
	int		i,slack;
	edge_t	*e;

	for (i = 0; (e = ND_in(v).list[i]); i++) {
		if (TREE_EDGE(e) == FALSE) {
			if (!SEQ(Low,ND_lim(e->tail),Lim)) {
				slack = SLACK(e);
				if ((slack < Slack) || (Enter == NULL)) {
					Enter = e;
					Slack = slack;
				}
			}
		}
		else if (ND_lim(e->tail) < ND_lim(v)) dfs_enter_inedge(e->tail);
	}
	for (i = 0; (e = ND_tree_out(v).list[i]) && (Slack > 0); i++)
		if (ND_lim(e->head) < ND_lim(v)) dfs_enter_inedge(e->head);
}

edge_t *
enter_edge(edge_t* e)
{
	node_t	*v;
	int		outsearch;

	/* v is the down node */
	if (ND_lim(e->tail) < ND_lim(e->head)) {v = e->tail; outsearch = FALSE;}
	else {v = e->head;outsearch = TRUE;}
	Enter = NULL;
	Slack = MAXINT;
	Low = ND_low(v);
	Lim = ND_lim(v);
	if (outsearch) dfs_enter_outedge(v);
	else dfs_enter_inedge(v);
	return Enter;
}

int treesearch(node_t* v)
{
	int		i;
	edge_t	*e;

	for (i = 0; (e = ND_out(v).list[i]); i++) {
		if ((ND_mark(e->head) == FALSE) && (SLACK(e) == 0)) {
			add_tree_edge(e);
			if ((Tree_edge.size == N_nodes-1) || treesearch(e->head)) return TRUE;
		}
	}
	for (i = 0; (e = ND_in(v).list[i]); i++) {
		if ((ND_mark(e->tail) == FALSE) && (SLACK(e) == 0)) {
			add_tree_edge(e);
			if ((Tree_edge.size == N_nodes-1) || treesearch(e->tail)) return TRUE;
		}
	}
	return FALSE;
}

int
tight_tree(void)
{
	int		i;
	node_t	*n;

	for (n = GD_nlist(G); n; n = ND_next(n)) {
		ND_mark(n) = FALSE;
		ND_tree_in(n).list[0] = ND_tree_out(n).list[0] = NULL;
		ND_tree_in(n).size = ND_tree_out(n).size = 0;
	}
	for (i = 0; i < Tree_edge.size; i++) Tree_edge.list[i]->u.tree_index = -1;

	Tree_node.size = Tree_edge.size = 0;
	for (n = GD_nlist(G); n && (Tree_edge.size == 0); n = ND_next(n)) treesearch(n);
	return Tree_node.size;
}

void init_cutvalues(void)
{
	dfs_range(GD_nlist(G),NULL,1);
	dfs_cutval(GD_nlist(G),NULL);
}

void feasible_tree(void)
{
	int			i,delta;
	node_t		*n;
	edge_t		*e,*f;

	if (N_nodes <= 1) return;
	while (tight_tree() < N_nodes) {
		e = NULL;
		for (n = GD_nlist(G); n; n = ND_next(n)) {
			for (i = 0; (f = ND_out(n).list[i]); i++) {
				if ((TREE_EDGE(f) == FALSE) && incident(f) && ((e == NULL)
					|| (SLACK(f) < SLACK(e)))) e = f;
			}
		}
		if (e) {
			delta = SLACK(e);
			if (delta) {
				if (incident(e) == e->head) delta = -delta;
				for (i = 0; i < Tree_node.size; i++)
					Tree_node.list[i]->u.rank += delta;
			}
		}
		else {
#ifdef DEBUG
			fprintf(stderr,"not in tight tree:\n");
			for (n = GD_nlist(G); n; n = ND_next(n)) {
				for (i = 0; i < Tree_node.size; i++)
					if (Tree_node.list[i] == n) break;
				if (i >= Tree_node.size) fprintf(stderr,"\t%s\n",n->name);
			}
#endif
			abort();
		}
	}
	init_cutvalues();
}

/* walk up from v to LCA(v,w), setting new cutvalues. */
node_t *
treeupdate(node_t *v, node_t *w, int cutvalue, int dir)
{
	edge_t	*e;
	int		d;

	while (!SEQ(ND_low(v),ND_lim(w),ND_lim(v))) {
		e = ND_par(v);
		if (v == e->tail) d = dir; else d = NOT(dir);
		if (d) ED_cutvalue(e) += cutvalue; else ED_cutvalue(e) -= cutvalue;
		if (ND_lim(e->tail) > ND_lim(e->head)) v = e->tail; else v = e->head;
	}
	return v;
}

void rerank(node_t* v, int delta)
{
	int		i;
	edge_t	*e;

	ND_rank(v) -= delta;
	for (i = 0; (e = ND_tree_out(v).list[i]); i++) 
		if (e != ND_par(v)) rerank(e->head,delta);
	for (i = 0; (e = ND_tree_in(v).list[i]); i++) 
		if (e != ND_par(v)) rerank(e->tail,delta);
}

/* e is the tree edge that is leaving and f is the nontree edge that
 * is entering.  compute new cut values, ranks, and exchange e and f.
 */
void update(edge_t *e, edge_t *f)
{
	int		cutvalue,delta;
	node_t	*lca;

	delta = SLACK(f);
	/* "for (v = in nodes in tail side of e) do ND_rank(v) -= delta;" */
	if (delta > 0) {
		int s;
		s = ND_tree_in(e->tail).size + ND_tree_out(e->tail).size;
		if (s == 1) rerank(e->tail,delta);
		else {
			s = ND_tree_in(e->head).size + ND_tree_out(e->head).size;
			if (s == 1) rerank(e->head,-delta);
			else {
				if (ND_lim(e->tail) < ND_lim(e->head)) rerank(e->tail,delta);
				else rerank(e->head,-delta);
			}
		}
	}

	cutvalue = ED_cutvalue(e);
	lca = treeupdate(f->tail,f->head,cutvalue,1);
	if (treeupdate(f->head,f->tail,cutvalue,0) != lca) abort();
	ED_cutvalue(f) = -cutvalue;
	ED_cutvalue(e) = 0;
	exchange_tree_edges(e,f);
	dfs_range(lca,ND_par(lca),ND_low(lca));
}

void scan_and_normalize(void)
{
	node_t	*n;

	Minrank = MAXINT;
	Maxrank = -MAXINT;
	for (n = GD_nlist(G); n; n = ND_next(n)) {
		if (ND_node_type(n) == NORMAL) {
			Minrank = MIN(Minrank,ND_rank(n));
			Maxrank = MAX(Maxrank,ND_rank(n));
		}
	}
	if (Minrank != 0) {
		for (n = GD_nlist(G); n; n = ND_next(n)) ND_rank(n) -= Minrank;
		Maxrank -= Minrank;
		Minrank = 0;
	}
}

void LR_balance(void)
{
	int		i,delta;
	node_t	*n;
	edge_t	*e,*f;

	for (i = 0; i < Tree_edge.size; i++) {
		e = Tree_edge.list[i];
		if (ED_cutvalue(e) == 0) {
			f = enter_edge(e);
			if (f == NULL) continue;
			delta = SLACK(f);
			if (delta <= 1) continue;
			if (ND_lim(e->tail) < ND_lim(e->head)) rerank(e->tail,delta/2);
			else rerank(e->head,-delta/2);
		}
	}
	for (n = GD_nlist(G); n; n = ND_next(n)) {
		free_list(ND_tree_in(n));
		free_list(ND_tree_out(n));
		ND_mark(n) = FALSE;
	}
}

void TB_balance(void)
{
	node_t	*n;
	edge_t	*e;
	int		i,low,high,choice,*nrank;
	int		inweight,outweight;

	scan_and_normalize();

	/* find nodes that are not tight and move to less populated ranks */
	nrank = N_NEW(Maxrank+1,int);
	for (i = 0; i <= Maxrank; i++) nrank[i] = 0;
	for (n = GD_nlist(G); n; n = ND_next(n))
		if (ND_node_type(n) == NORMAL) nrank[ND_rank(n)]++;
	for (n = GD_nlist(G); n; n = ND_next(n)) {
		if (ND_node_type(n) != NORMAL) continue;
		inweight = outweight = 0;
		low = 0;
		high = Maxrank;
		for (i = 0; (e = ND_in(n).list[i]); i++) {
			inweight += ED_weight(e);
			low = MAX(low,ND_rank(e->tail) + ED_minlen(e));
		}
		for (i = 0; (e = ND_out(n).list[i]); i++) {
			outweight += ED_weight(e);
			high = MIN(high,ND_rank(e->head) - ED_minlen(e));
		}
		if (low < 0) low = 0;	/* vnodes can have ranks < 0 */
		if (inweight == outweight) {
			choice = low;
			for (i = low + 1; i <= high; i++)
				if (nrank[i] < nrank[choice]) choice = i;
			nrank[ND_rank(n)]--; nrank[choice]++;
			ND_rank(n) = choice;
		}
		free_list(ND_tree_in(n));
		free_list(ND_tree_out(n));
		ND_mark(n) = FALSE;
	}
	free(nrank);
}

static int
init_graph(graph_t* g)
{
	int		i,feasible;
	node_t	*n;
	edge_t	*e;

	G = g;
	N_nodes = N_edges = S_i = 0;
	for (n = GD_nlist(g); n; n = ND_next(n)) {
		ND_mark(n) = FALSE;
		N_nodes++;
		for (i = 0; (e = ND_out(n).list[i]); i++) N_edges++;
	}

	Tree_node.list = ALLOC(N_nodes,Tree_node.list,node_t*);
	Tree_node.size = 0;
	Tree_edge.list = ALLOC(N_nodes,Tree_edge.list,edge_t*);
	Tree_edge.size = 0;

	feasible = TRUE;
	for (n = GD_nlist(g); n; n = ND_next(n)) {
		ND_priority(n) = 0;
		for (i = 0; (e = ND_in(n).list[i]); i++) {
			ND_priority(n)++;
			ED_cutvalue(e) = 0;
			ED_tree_index(e) = -1;
			if (feasible && (ND_rank(e->head) - ND_rank(e->tail) < ED_minlen(e)))
				feasible = FALSE;
		}
		ND_tree_in(n).list = N_NEW(i+1,edge_t*);
		ND_tree_in(n).size = 0;
		for (i = 0; (e = ND_out(n).list[i]); i++);
		ND_tree_out(n).list = N_NEW(i+1,edge_t*);
		ND_tree_out(n).size = 0;
	}
	return feasible;
}

void rank(graph_t *g, int balance, int maxiter)
{
	int	iter = 0,feasible;
	char	*s,*ns = "network simplex: ";
	edge_t	*e,*f;

	if (Verbose) start_timer();
	feasible = init_graph(g);
	if (!feasible) init_rank();
	if (maxiter <= 0) return;

	if ((s = agget(g,"searchsize"))) Search_size = atoi(s);
	else Search_size = SEARCHSIZE;

	feasible_tree();
	while ((e = leave_edge())) {
		f = enter_edge(e);
		update(e,f);
		iter++;
		if (Verbose && (iter % 100 == 0)) {
			if (iter % 1000 == 100) fputs(ns,stderr);
			fprintf(stderr,"%d ",iter);
			if (iter % 1000 == 0) fputc('\n',stderr);
		}
		if (iter >= maxiter) break;
	}
	switch(balance){
	case 1: TB_balance(); break;
	case 2: LR_balance(); break;
	default: scan_and_normalize(); break;
	}
	if (Verbose) {
		if (iter >= 100) fputc('\n',stderr);
		fprintf(stderr,"%s%d nodes %d edges %d iter %.2f sec\n",
			ns,N_nodes,N_edges,iter,elapsed_sec());
	}
}

/* set cut value of f, assuming values of edges on one side were already set */
void x_cutval(edge_t* f)
{
	node_t	*v;
	edge_t	*e;
	int		i,sum,dir;

	/* set v to the node on the side of the edge already searched */
	if (ND_par(f->tail) == f) { v = f->tail; dir = 1; }
	else { v = f->head; dir = -1; }

	sum = 0;
	for (i = 0; (e = ND_out(v).list[i]); i++) sum += x_val(e,v,dir);
	for (i = 0; (e = ND_in(v).list[i]); i++) sum += x_val(e,v,dir);
	ED_cutvalue(f) = sum;
}

int x_val(edge_t* e, node_t* v, int dir)
{
	node_t	*other;
	int		d,rv,f;

	if (e->tail == v) other = e->head; else other = e->tail;
	if (!(SEQ(ND_low(v),ND_lim(other),ND_lim(v)))) {f = 1; rv = ED_weight(e);}
	else {
		f = 0;
		if (TREE_EDGE(e)) rv = ED_cutvalue(e);
		else rv = 0;
		rv -= ED_weight(e);
	}
	if (dir > 0) {if (e->head == v) d = 1; else d = -1;}
	else {if (e->tail == v) d = 1; else d = -1; }
	if (f) d = -d;
	if (d < 0) rv = -rv;
	return rv;
}

void dfs_cutval(node_t* v, edge_t* par)
{
	int		i;
	edge_t	*e;

	for (i = 0; (e = ND_tree_out(v).list[i]); i++)
		if (e != par) dfs_cutval(e->head,e);
	for (i = 0; (e = ND_tree_in(v).list[i]); i++)
		if (e != par) dfs_cutval(e->tail,e);
	if (par) x_cutval(par);
}

int dfs_range(node_t* v, edge_t* par, int low)
{
	edge_t	*e;
	int		i,lim;

	lim = low;
	ND_par(v) = par;
	ND_low(v) = low;
	for (i = 0; (e = ND_tree_out(v).list[i]); i++)
		if (e != par) lim = dfs_range(e->head,e,lim);
	for (i = 0; (e = ND_tree_in(v).list[i]); i++)
		if (e != par) lim = dfs_range(e->tail,e,lim);
	ND_lim(v) = lim;
	return lim + 1;
}

#ifdef DEBUG
void tchk(void)
{
	int		i,n_cnt,e_cnt;
	node_t	*n;
	edge_t	*e;

	n_cnt = 0;
	e_cnt = 0;
	for (n = GD_nlist(G); n; n = ND_next(n)) {
		n_cnt++;
		for (i = 0; e = ND_tree_out(n).list[i]; i++) {
			e_cnt++;
			if (SLACK(e) > 0)
				printf("not a tight tree %x",e);
		}
	}
	if ((n_cnt != Tree_node.size)  || (e_cnt != Tree_edge.size))
		printf("something missing\n");
}

void check_cutvalues(void)
{
	node_t	*v;
	edge_t	*e;
	int		i,save;

	for (v = GD_nlist(G); v; v = ND_next(v)) {
		for (i = 0; (e = ND_tree_out(v).list[i]); i++) {
			save = ED_cutvalue(e);
			x_cutval(e);
			if (save != ED_cutvalue(e)) abort();
		}
	}
}

int
check_ranks(void)
{
	int		i, cost = 0;
	node_t	*n;
	edge_t	*e;

	for (n = GD_nlist(G); n; n = ND_next(n)) {
		for (i = 0; (e = ND_out(n).list[i]); i++) {
			cost += (ED_weight(e))*abs(LENGTH(e));
	if (ND_rank(e->head) - ND_rank(e->tail) - ED_minlen(e) < 0) abort();
		}
	}
	fprintf(stderr,"rank cost %d\n",cost);
	return cost;
}

void checktree(void)
{
	int		i,n = 0,m = 0;
	node_t	*v;
	edge_t	*e;

	for (v = GD_nlist(G); v; v = ND_next(v)) {
		for (i = 0; (e = ND_tree_out(v).list[i]); i++) n++;
		if (i != ND_tree_out(v).size) abort();
		for (i = 0; (e = ND_tree_in(v).list[i]); i++) m++;
		if (i != ND_tree_in(v).size) abort();
	}
	printf("%d %d %d\n",Tree_edge.size,n,m);
}

void check_fast_node(node_t* n)
{
	node_t	*nptr;
	nptr = GD_nlist(n->graph);
	while (nptr && nptr != n) nptr = ND_next(nptr);
	assert (nptr != NULL);
}

void checkdfs(node_t* n)
{
	int		i;
	edge_t	*e;
	node_t	*w;

	if (ND_mark(n)) return;
	ND_mark(n) = TRUE;
	ND_onstack(n) = TRUE;
	for (i = 0; (e = ND_out(n).list[i]); i++) {
		w = e->head;
		if (ND_onstack(w))
			fprintf(stderr,"cycle involving %s %s\n",n->name,w->name);
		else {
			if (ND_mark(w) == FALSE) checkdfs(w);
		}
	}
	ND_onstack(n) = FALSE;
}

void check_cycles(graph_t* g)
{
	node_t	*n;
	for (n = GD_nlist(g); n; n = ND_next(n)) ND_mark(n) = ND_onstack(n) = FALSE;
	for (n = GD_nlist(g); n; n = ND_next(n)) checkdfs(n);
}
#endif /* DEBUG */