class Node { int x; int y; int set; int first; int next; 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 len; /* length */ int select; String name; }
public class Kruskal extends Applet implements MouseListener { int n,m; int num,den; int u, usel, step; Node v[] = new Node[100]; Edge e[] = new Edge[200]; int idx[] = new int[200];
int findNode(String name) { for (int i=0; i<n; i++) if (v.name.equals(name)) return i; return -1; }
void input_graph(InputStream is) throws IOException { int x,y,l; String s;
Reader r = new BufferedReader(new InputStreamReader(is)); StreamTokenizer st = new StreamTokenizer(r); 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 = 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.len = (int)st.nval; e = edge; } for (int i=0; i<m; i++) e.select = -1; den = 0; num = 128; for (int i=0; i<m; i++) if (e.len>den) den = e.len; step1(); Krsub p = (Krsub)getAppletContext().getApplet("krsub"); if (p!=null) p.set(1,n,m,num,den,v,e,idx); step = 2; }
void swap(int i, int j) { int k = idx;
idx = idx[j]; idx[j] = k; }
int partition(int left, int right) { int pivot = e[idx[(int)((left+right)/2)]].len;
while (left<=right) { while (e[idx[left]].len < pivot) left++; while (e[idx[right]].len > pivot) right--; if (left <= right) swap(left++,right--); } return left; }
void qsort(int left, int right) { int i;
if (left >= right) return; i = partition(left,right); qsort(left,i-1); qsort(i,right); }
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;
if (e.select == -1 ) g.setColor(Color.black); else if (e.select == -2) g.setColor(Color.lightGray); else if (e.select == 1) g.setColor(Color.orange); else g.setColor(Color.red); g.drawString("" + e.len,(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,fm); for (int i=0; i<m; i++) paintEdge(g,e,fm); Krsub p = (Krsub)getAppletContext().getApplet("krsub"); if (p!=null) p.set(1,n,m,num,den,v,e,idx); }
public void update(Graphics g) { paint(g); }
public void mousePressed(MouseEvent e) { if (step == 1) { step1(); step = 2; } else if (usel >= n-1) { step4(); step = 1; } else { if (step == 3) { step3(); step = 2; } else { step2(); step = 3; } } repaint(); } public void mouseClicked(MouseEvent event) {} public void mouseReleased(MouseEvent event) {} public void mouseEntered(MouseEvent event) {} public void mouseExited(MouseEvent event) {} }
The original post was about an applet, but you'll see later on down the thread where I added the capability to run it as either an applet or application.
Previous Topic
