/****************************************//* File: Maxflow.java			*//* based on Ford-Fulkerson Method	*//* Copyright (C) 1997, 1998 K. Ikeda	*//****************************************/import java.applet.*;import java.awt.*;import java.io.*;import java.net.URL;class Node {	int	x;	int	y;	int	delta_plus;	/* edge starts from this node */	int	delta_minus;	/* edge terminates at this node */	int	dist;		/* distance from the start node */	int	prev;		/* previous node of the shortest path */	int	p_edge;	int	l;	int	w;	int	h;	String	name;}class Edge {	int	rndd_plus;	/* initial vertex of this edge */	int	rndd_minus;	/* terminal vertex of this edge */	int	delta_plus;	/* edge starts from rndd_plus */	int	delta_minus;	/* edge terminates at rndd_minus */	int	capacity;	/* capacity */	int	flow;		/* flow */	int	st;	String	name;}public class Maxflow extends Applet {	int	n,m;	int	snode,tnode;	/* start node, terminate node */	int	step;	Node	v[] = new Node[100];	Edge	e[] = new Edge[200];	int findNode(String name) {		for (int i=0; i<n; i++)			if (v[i].name.equals(name))				return i;		return -1;	}	void input_graph(InputStream is) throws IOException {		int x,y,l;		String	s;		StreamTokenizer st = new StreamTokenizer(is);		st.commentChar('#');		st.nextToken();	n = (int)st.nval;		st.nextToken();	m = (int)st.nval;		st.nextToken();	s = st.sval;		for (int i = 0; i<n; i++) {			Node node = new Node();			st.nextToken();	node.name = st.sval;			st.nextToken();	node.x = (int)st.nval;			st.nextToken();	node.y = (int)st.nval;			v[i] = node;		}		for (int i = 0; i<m; i++) {			Edge edge = new Edge();			st.nextToken();	edge.name = st.sval;			switch (st.nextToken()) {			case StreamTokenizer.TT_NUMBER:				edge.rndd_plus = (int)st.nval;				break;			case StreamTokenizer.TT_WORD:				edge.rndd_plus = findNode(st.sval);				break;			default:				break;			}			switch (st.nextToken()) {			case StreamTokenizer.TT_NUMBER:				edge.rndd_minus = (int)st.nval;				break;			case StreamTokenizer.TT_WORD:				edge.rndd_minus = findNode(st.sval);				break;			default:				break;			}			st.nextToken();	edge.capacity = (int)st.nval;			edge.flow = 0;			e[i] = edge;		}		step = 1;	}	void rdb() {		int	i,k;		for (i=0; i<n; i++)			v[i].delta_plus = v[i].delta_minus = -1;		for (i=0; i<m; i++)			e[i].delta_plus = e[i].delta_minus = -1;		for (i=0; i<m; i++) {			k = e[i].rndd_plus;			if (v[k].delta_plus == -1)				v[k].delta_plus = i;			else {				k = v[k].delta_plus;				while(e[k].delta_plus >= 0)					k = e[k].delta_plus;				e[k].delta_plus = i;			}			k = e[i].rndd_minus;			if (v[k].delta_minus == -1)				v[k].delta_minus = i;			else {				k = v[k].delta_minus;				while(e[k].delta_minus >= 0)					k = e[k].delta_minus;				e[k].delta_minus = i;			}		}	}	void stpath() {		/* find an s-t path */		int	u[] = new int[100], ni, no;		int	i,j,d;		for (i=0; i<n; i++) {			v[i].prev = v[i].dist = -1;			v[i].l = 0;		}		for (i=0; i<m; i++)			e[i].st = -1;		ni = no = 0;		d = 0;		u[ni] = snode;		v[snode].dist = 0;		j = v[snode].delta_plus;		i = 0;		while (j>=0) {			if (i<e[j].capacity)				i = e[j].capacity;			j = e[j].delta_plus;		}		v[snode].l = i;		for (; no<=ni; no++) {			d = v[u[no]].dist;			for (j=v[u[no]].delta_plus; j>=0; j=e[j].delta_plus) {				if (e[j].capacity-e[j].flow == 0)					continue;				i = e[j].rndd_minus;				if (v[i].dist<0) {					v[i].dist = d+1;					v[i].prev = u[no];					v[i].p_edge = j;					v[i].l = Math.min(v[u[no]].l,						e[j].capacity-e[j].flow);					e[j].st++;					u[++ni] = i;				}			}			for (j=v[u[no]].delta_minus; j>=0; j=e[j].delta_minus) {				if (e[j].flow == 0)					continue;				i = e[j].rndd_plus;				if (v[i].dist<0) {					v[i].dist = d+1;					v[i].prev = u[no];					v[i].p_edge = j;					v[i].l = Math.min(v[u[no]].l,e[j].flow);					e[j].st++;					u[++ni] = i;				}			}		}	}	void step0() {	/* initialize */		for (int i=0; i<m; i++)			e[i].flow = 0;		stpath();	}	void step1() {		/* mark an s-t path */		int	i;		if (v[tnode].dist<0)			return;		for (i = tnode; v[i].prev>=0; i=v[i].prev )			e[v[i].p_edge].st++;	}	void step2() {		/* augment the flow */		int	i,j,a,f;		f = v[tnode].l;		for (i = tnode; (j=v[i].prev)>=0; i = j) {			a = v[i].p_edge;			if (e[a].rndd_minus==i)				e[a].flow += f;			else if (e[a].rndd_plus==i)				e[a].flow -= f;		}		stpath();	}	public void init() {		String mdname = getParameter("inputfile");		try {			InputStream is;			is = new URL(getDocumentBase(),mdname).openStream();			input_graph(is);			try {				if (is != null)					is.close();				} catch(Exception e) {			}		} catch (FileNotFoundException e) {			System.err.println("File not found.");		} catch (IOException e) {			System.err.println("Cannot access file.");		}		String s = getParameter("s");		if (s != null)			snode = Integer.parseInt(s);		else			snode = 0;		s = getParameter("t");		if (s != null)			tnode = Integer.parseInt(s);		else			tnode = n-1;		setBackground(Color.white);		rdb();		step0();	}	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	x[] = new int[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;		}		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(x2,y2,x2+(int)((aa*12-bb*5)/13),				 y2+(int)((aa*5+bb*12)/13));		g.drawLine(x1,y1,x2,y2);	}	public void paintEdge(Graphics g, Edge e, FontMetrics fm) {		Node v1 = v[e.rndd_plus];		Node v2 = v[e.rndd_minus];		Color	c;		int a = v1.x-v2.x;		int b = v1.y-v2.y;		int x1[] = xy(-a,-b,v1.w,v1.h);		int x2[] = xy(a,b,v2.w,v2.h);		if (e.st>0)			c = Color.red;		else if ((v1.dist>=0)&&(v2.dist>=0))			c = Color.blue;		else			c = Color.gray;		g.setColor(c);		drawArrow(g,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1]);		int w = fm.stringWidth(""+e.flow+"/"+e.capacity);		int h = fm.getHeight();		g.setColor(getBackground());		g.fillRect((v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2,w,h);		g.setColor(Color.black);		g.drawString(""+e.flow+"/"+e.capacity,			(v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2+fm.getAscent());	}	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);		Residue p = (Residue)getAppletContext().getApplet("residue");		if (p!=null)			p.set(1,n,m,snode,tnode,v,e);	}	public void update(Graphics g) {		paint(g);	}	public boolean mouseDown(Event ev, int x, int y)	{		if (step==1) {			step1();			if (v[tnode].dist<0)				step = 0;			else				step = 2;		} else if (step==2){			step2();			step = 1;		} else {			step0();			step = 1;		}		repaint();		return true;	}}