/****************************************//* File: Residue.java			*//* based on Ford-Fulkerson Method	*//* Copyright (C) 1997, 1998 K. Ikeda	*//****************************************/import java.applet.*;import java.awt.*;public class Residue extends Applet implements Runnable {	Thread	th;	int	n=0,m=0;	int	snode=0,tnode=0;	/* start node, terminate node */	int	flag = -1;	Node	v[];	Edge	e[];	public void set(int flag, int n, int m,			int snode, int tnode, Node v[], Edge e[])  {		this.flag = flag;		this.n = n;		this.m = m;		this.snode = snode;		this.tnode = tnode;		this.v = v;		this.e = e;		setBackground(Color.white);	}	public void paintNode(Graphics g, Node n, FontMetrics fm) {		String s;		int x = n.x;		int y = n.y;		int w = fm.stringWidth(n.name) + 10;		int h = fm.getHeight() + 4;		n.w = w;		n.h = h;		Color	c;		if (n.dist<0)			c = Color.gray;		else			c = Color.blue;		g.setColor(c);		g.drawRect(x-w/2,y-h/2,w,h);		g.setColor(getBackground());		g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);		g.setColor(c);		g.drawString(n.name,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent());	}	int [] xy(int a, int b, int w, int h, int dx, int dy) {		int	x[] = new int[2];		w -= ((a>=0)?2:-2)*dx-3;		h -= ((b>=0)?2:-2)*dy-2;		if (Math.abs(w*b)>=Math.abs(h*a)) {			x[0] = ((b>=0)?1:-1)*a*h/b/2;			x[1] = ((b>=0)?1:-1)*h/2;		} else {			x[0] = ((a>=0)?1:-1)*w/2;			x[1] = ((a>=0)?1:-1)*b*w/a/2;		}		x[0] += dx;		x[1] += dy;		return x;	}	void drawArrow(Graphics g,int x1,int y1,int x2,int y2) {		int	a = x1-x2;		int	b = y1-y2;		double	aa = Math.sqrt(a*a+b*b)/16.0;		double	bb = b/aa;			aa = a/aa;		g.drawLine(x2,y2,x2+(int)((aa*12-bb*5)/13),				 y2+(int)((aa*5+bb*12)/13));		g.drawLine(x1,y1,x2,y2);	}	void drawEdge(Graphics g, FontMetrics fm,			int x1, int y1, int x2, int y2, int c) {		int a = x1-x2;		int b = y1-y2;		drawArrow(g,x1,y1,x2,y2);		int w = fm.stringWidth("" + c);		int h = fm.getHeight();		int x = (x1+x2)/2;		int y = (y1+y2)/2;		if ((b<0)||((b==0)&&(a<0))) x += fm.stringWidth(" ");		else x -= w+fm.stringWidth(" ");		if ((a>0)||((a==0)&&(b<0))) y += 1;		else	y -= h;		g.setColor(getBackground());		g.fillRect(x,y,w,h);		if (c!=0) {			g.setColor(Color.black);			g.drawString("" + c,x,y+fm.getAscent());		}	}	public void paintEdge(Graphics g, Edge e, FontMetrics fm) {		Node v1 = v[e.rndd_plus];		Node v2 = v[e.rndd_minus];		Color	c;		if ((e.st>0)&&(v1.dist<v2.dist))			c = Color.red;		else if ((e.st==0)&&(v1.dist<v2.dist))			c = Color.blue;		else			c = Color.gray;		int a = v1.x-v2.x;		int b = v1.y-v2.y;		double	aa = Math.sqrt(a*a+b*b)/2.0;		double	bb = -b/aa;			aa = a/aa;		int x1[] = xy(-a,-b,v1.w,v1.h,(int)bb,(int)aa);		int x2[] = xy(a,b,v2.w,v2.h,(int)bb,(int)aa);		if (e.capacity-e.flow==0)			g.setColor(getBackground());		else			g.setColor(c);		drawEdge(g,fm,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1],				e.capacity-e.flow);		if ((e.st>0)&&(v1.dist>v2.dist))			c = Color.red;		else if ((e.st==0)&&(v1.dist>v2.dist))			c = Color.blue;		else			c = Color.gray;		x1 = xy(a,b,v2.w,v2.h,-(int)bb,-(int)aa);		x2 = xy(-a,-b,v1.w,v1.h,-(int)bb,-(int)aa);		if (e.flow==0)			g.setColor(getBackground());		else			g.setColor(c);		drawEdge(g,fm,v2.x+x1[0],v2.y+x1[1],v1.x+x2[0],v1.y+x2[1],				e.flow);	}	public void paint(Graphics g) {		FontMetrics fm = g.getFontMetrics();		for (int i=0; i<n; i++)			paintNode(g,v[i],fm);		for (int i=0; i<m; i++)			paintEdge(g,e[i],fm);	}	public void update(Graphics g) {		paint(g);	}	public void start() {		if (th==null) {			th = new Thread(this);			th.start();		}	}	public void run() {		while (true) {			try {				th.sleep(100);			}			catch (InterruptedException e) {}			if (flag-- > 0)				repaint();		}	}}