import java.util.*;
import java.awt.*;
import java.applet.Applet;

class Node {
    double x;
    double y;

    double dx;
    double dy;

    boolean fixed;

    String lbl;
}

class Edge {
    int from;
    int to;

    double len;
}

class MapPanel extends Panel implements Runnable {
    Map map;
    int nnodes;
    boolean frozen=false;
    boolean stretchy=false;
    boolean happy=false;
    boolean names=false;
    Node nodes[] = new Node[100];

    int nedges;
    Edge edges[] = new Edge[200];

    Thread relaxer;
    boolean stress;
    boolean random;

    MapPanel(Map map) {
	this.map = map;
    }

    int findNode(String lbl) {
	for (int i = 0 ; i < nnodes ; i++) {
	    if (nodes[i].lbl.equals(lbl)) {
		return i;
	    }
	}
	return addNode(lbl);
    }
    int addNode(String lbl) {
       Dimension d = map.size();
       Node n = new Node();
       n.x = 10 + (d.width-20)*Math.random();
       n.y = 10 + (d.height-20)*Math.random();
       n.lbl = lbl;
       nodes[nnodes] = n;
       return nnodes++;
    }
    void addEdge(String from, String to, int len) {
	Edge e = new Edge();
	e.from = findNode(from);
	e.to = findNode(to);
	e.len = len;
	edges[nedges++] = e;
    }

    public void run() {
	while (true) {
	    relax();
	    if (random && (Math.random() < 0.03)) {
		Node n = nodes[(int)(Math.random() * nnodes)];
		if (!n.fixed) {
		    n.x += 100*Math.random() - 50;
		    n.y += 100*Math.random() - 50;
		}
	    }
	    try {
		Thread.sleep(100);
	    } catch (InterruptedException e) {
		break;
	    }
	}
    }

    synchronized void relax() {
        if(frozen) { repaint(); return; }
	for (int i = 0 ; i < nedges ; i++) {
	    Edge e = edges[i];
	    double vx = nodes[e.to].x - nodes[e.from].x;
	    double vy = nodes[e.to].y - nodes[e.from].y;
	    double len = Math.sqrt(vx * vx + vy * vy);
	    double f = (edges[i].len - len) / (len * 3) ;
	    double dx = f * vx;
	    double dy = f * vy;

	    if(stretchy) edges[i].len = edges[i].len-((f*edges[i].len)/10);
	    

	    nodes[e.to].dx += dx;
	    nodes[e.to].dy += dy;
	    nodes[e.from].dx += -dx;
	    nodes[e.from].dy += -dy;
	}

	if(!happy){
	  for (int i = 0 ; i < nnodes ; i++) {
	    Node n1 = nodes[i];
	    double dx = 0;
	    double dy = 0;

	    for (int j = 0 ; j < nnodes ; j++) {
		if (i == j) {
		    continue;
		}
		Node n2 = nodes[j];
		double vx = n1.x - n2.x;
		double vy = n1.y - n2.y;
		double len = vx * vx + vy * vy;
		if (len == 0) {
		    dx += Math.random();
		    dy += Math.random();
		} else if (len < 100*100) {
		    dx += vx / len;
		    dy += vy / len;
		}
	    }
	    double dlen = dx * dx + dy * dy;
	    if (dlen > 0) {
		dlen = Math.sqrt(dlen) / 2;
		n1.dx += dx / dlen;
		n1.dy += dy / dlen;
	    }
	  }
	}

	Dimension d = size();
	for (int i = 0 ; i < nnodes ; i++) {
	    Node n = nodes[i];
	    if (!n.fixed) {
		n.x += Math.max(-5, Math.min(5, n.dx));
		n.y += Math.max(-5, Math.min(5, n.dy));
		//System.out.println("v= " + n.dx + "," + n.dy);
		if (n.x < 10) {
		    n.x = 10;
		} else if (n.x > (d.width-10)) {
		    n.x = d.width-10;
		}
		if (n.y < 10) {
		    n.y = 10;
		} else if (n.y > (d.height-10)) {
		    n.y = d.height-10;
		}
	    }
	    n.dx /= 2;
	    n.dy /= 2;
	}
	repaint();
    }

    Node pick;
    boolean pickfixed;
    Image offscreen;
    Dimension offscreensize;
    Graphics offgraphics;
    

    final Color fixedColor = Color.white;
    final Color selectColor = Color.gray;
    final Color edgeColor = Color.black;
    final Color nodeColor = new Color(250, 220, 100);
    final Color stressColor = Color.gray;
    final Color arcColor1 = Color.black;
    final Color arcColor2 = Color.yellow;
    final Color arcColor3 = Color.red;

    public void paintNode(Graphics g, Node n, FontMetrics fm) {
	int x = (int)n.x;
	int y = (int)n.y;
	char cc = n.lbl.charAt(0);
	Color qColor = ((cc=='R') ? Color.red :
			((cc=='G') ? Color.green :
			 ((cc=='B') ? Color.blue :
			  ((cc=='C') ? Color.cyan :
			   ((cc=='M') ? Color.magenta :
			    ((cc=='Y') ? Color.yellow :
			     ((cc=='O') ? Color.orange :
			      nodeColor)))))));
	g.setColor((n == pick)? selectColor : (n.fixed ? fixedColor : qColor));
	if (names) {
	   int w = fm.stringWidth(n.lbl) + 10;
	   int h = fm.getHeight() + 4;
	   g.fillRect(x - w/2, y - h / 2, w-1, h-1);
	   g.setColor(Color.black);
	   g.drawRect(x - w/2, y - h / 2, w-1, h-1);
	   g.drawString(n.lbl, x - (w-10)/2, (y - (h-4)/2) + fm.getAscent());
	} else {
	   g.fillOval(x - 6, y - 6, 11, 11);
	   g.setColor(Color.black);
	   g.drawOval(x - 6, y - 6, 11, 11);
	}
    }

    public synchronized void update(Graphics g) {
	Dimension d = size();
	if ((offscreen == null) || (d.width != offscreensize.width) || (d.height != offscreensize.height)) {
	    offscreen = createImage(d.width, d.height);
	    offscreensize = d;
	    offgraphics = offscreen.getGraphics();
	    offgraphics.setFont(getFont());
	}

	offgraphics.setColor(getBackground());
	offgraphics.fillRect(0, 0, d.width, d.height);
	for (int i = 0 ; i < nedges ; i++) {
	    Edge e = edges[i];
	    int x1 = (int)nodes[e.from].x;
	    int y1 = (int)nodes[e.from].y;
	    int x2 = (int)nodes[e.to].x;
	    int y2 = (int)nodes[e.to].y;
	    int len = (int)Math.abs(Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) - e.len);
	    offgraphics.setColor((len < 10) ? arcColor1 : (len < 20 ? arcColor2 : arcColor3)) ;
	    offgraphics.drawLine(x1, y1, x2, y2);
	    if (stress) {
		String lbl = String.valueOf(len);
		offgraphics.setColor(stressColor);
		offgraphics.drawString(lbl, x1 + (x2-x1)/2, y1 + (y2-y1)/2);
		offgraphics.setColor(edgeColor);
	    }
	}

	FontMetrics fm = offgraphics.getFontMetrics();
	for (int i = 0 ; i < nnodes ; i++) {
	    paintNode(offgraphics, nodes[i], fm);
	}

	g.drawImage(offscreen, 0, 0, null);
    }

    public synchronized boolean mouseDown(Event evt, int x, int y) {
	double bestdist = Double.MAX_VALUE;
	for (int i = 0 ; i < nnodes ; i++) {
	    Node n = nodes[i];
	    double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y);
	    if (dist < bestdist) {
		pick = n;
		bestdist = dist;
	    }
	}
	pickfixed = pick.fixed;
	pick.fixed = true;
	pick.x = x;
	pick.y = y;
	repaint();
	return true;
    }

    public synchronized boolean mouseDrag(Event evt, int x, int y) {
	pick.x = x;
	pick.y = y;
	repaint();
	return true;
    }

    public synchronized boolean mouseUp(Event evt, int x, int y) {
	pick.x = x;
	pick.y = y;
	pick.fixed = pickfixed;
	pick = null;
	
	repaint();
	return true;
    }

    public void start() {
	relaxer = new Thread(this);
	relaxer.start();
    }
    public void stop() {
	relaxer.stop();
    }
}

public class Map extends Applet {
    MapPanel panel;

    public void init() {
	setLayout(new BorderLayout());

	panel = new MapPanel(this);
	add("Center", panel);

	Panel p = new Panel();
	add("South", p);
	p.setLayout(new BorderLayout());

	Panel ctl = new Panel();
	Panel dsp = new Panel();
	p.add("North", ctl);
	p.add("South", dsp);

	GridBagLayout gbl = new GridBagLayout();
	GridBagConstraints gbc = new GridBagConstraints();
	ctl.setLayout(gbl);
	dsp.setLayout(gbl);

	gbc.weightx = 0.0;
	gbc.anchor = GridBagConstraints.WEST;
	gbl.setConstraints(ctl.add(new Button("Scramble")),gbc);
	gbl.setConstraints(ctl.add(new Button("Shake")),gbc);
	gbl.setConstraints(ctl.add(new Button("Set Lengths")),gbc);
	gbc.gridwidth = GridBagConstraints.REMAINDER;
	gbc.weightx = 1.0;
	gbc.insets.left = 20;
	gbl.setConstraints(ctl.add(new Checkbox("Frozen")),gbc);
	gbc.insets.left = 0;

	gbc.gridwidth = 1;
	gbc.weightx = 0.0;
	gbl.setConstraints(dsp.add(new Checkbox("Random")),gbc);
	gbl.setConstraints(dsp.add(new Checkbox("Stretchy")),gbc);
	gbl.setConstraints(dsp.add(new Checkbox("Happy")),gbc);
	gbc.weightx = 1.0;
	gbc.anchor = GridBagConstraints.EAST;
	gbl.setConstraints(dsp.add(new Checkbox("Names")),gbc);
	gbc.weightx = 0.0;
	gbc.gridwidth = GridBagConstraints.REMAINDER;
	gbl.setConstraints(dsp.add(new Checkbox("Stress")),gbc);

	String edges = getParameter("edges");
	for (StringTokenizer t = new StringTokenizer(edges, ",\n") ;
	     t.hasMoreTokens() ; ) {
	    String str = t.nextToken();
	    String last = null;
	    for (StringTokenizer tt = new StringTokenizer(str, "-") ;
		 tt.hasMoreTokens() ; ) {
	       String elem = tt.nextToken();
	       int len = 50;
	       int j = elem.indexOf('/');
	       if (j > 0) {
		  len = Integer.valueOf(elem.substring(j+1)).intValue();
		  elem = elem.substring(0, j);
	       }
	       if (last != null){
		  panel.addEdge(last, elem, len);
	       }
	       last = elem;
	    }
	}
	Dimension d = size();
	String center = getParameter("center");
	if (center != null){
	    Node n = panel.nodes[panel.findNode(center)];
	    n.x = d.width / 2;
	    n.y = d.height / 2;
	    n.fixed = true;
	}
    }

    public void start() {
	panel.start();
    }
    public void stop() {
	panel.stop();
    }
    public boolean action(Event evt, Object arg) {
      if (arg instanceof Boolean) {
	if (((Checkbox)evt.target).getLabel().equals("Stress")) {
	  panel.stress = ((Boolean)arg).booleanValue();
	  panel.repaint();
	} 
	else if (((Checkbox)evt.target).getLabel().equals("Names")){
	  panel.names = ((Boolean)arg).booleanValue();
	  panel.repaint();
	}
	else if (((Checkbox)evt.target).getLabel().equals("Stretchy")){
	  panel.stretchy = ((Boolean)arg).booleanValue();	
	}
	else if (((Checkbox)evt.target).getLabel().equals("Happy")){
	  panel.happy = ((Boolean)arg).booleanValue();
	}
	else if (((Checkbox)evt.target).getLabel().equals("Random")){
	  panel.random = ((Boolean)arg).booleanValue();
	}
	else {
	  panel.frozen = ((Boolean)arg).booleanValue();
	}
	return true;
      } 
      if ("Scramble".equals(arg)) {
	Dimension d = size();
	for (int i = 0 ; i < panel.nnodes ; i++) {
	  Node n = panel.nodes[i];
	  if (!n.fixed) {
	    n.x = 10 + (d.width-20)*Math.random();
	    n.y = 10 + (d.height-20)*Math.random();
	  }
	}
	panel.repaint();
	return true;
      }
      if ("Shake".equals(arg)) {
	Dimension d = size();
	for (int i = 0 ; i < panel.nnodes ; i++) {
	  Node n = panel.nodes[i];
	  if (!n.fixed) {
	    n.x += 80*Math.random() - 40;
	    n.y += 80*Math.random() - 40;
	  }
	}
	panel.repaint();
	return true;
      }
      if("Set Lengths".equals(arg)){
	for (int i=0;i<panel.nedges;i++){
	  Edge e = panel.edges[i];
	  double vx = panel.nodes[e.to].x - panel.nodes[e.from].x;
	  double vy = panel.nodes[e.to].y - panel.nodes[e.from].y;
	  double len = Math.sqrt(vx * vx + vy * vy);
	  double f = (panel.edges[i].len - len) / (len * 3) ;

	  panel.edges[i].len = len;
	}
	for(int i = 0;i<panel.nnodes;i++){
	  panel.nodes[i].dx=0;
	  panel.nodes[i].dy=0;
	}
	panel.repaint();
	return true;
      }
      panel.repaint();
      System.out.println("EVENT: " + arg);
      return false;
    }
}