bangnaga

Dijkstra.java

May 1st, 2012
166
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /********************************************/
  2. /* Dijkstra.java                            */
  3. /* Copyright (C) 1997, 1998, 2000  K. Ikeda */
  4. /********************************************/
  5.  
  6. import java.applet.*;
  7. import java.awt.*;
  8. import java.awt.event.*;
  9. import java.util.*;
  10. import java.io.*;
  11. import java.net.URL;
  12.  
  13. class Node {
  14.     int x;
  15.     int y;
  16.     int delta_plus; /* edge starts from this node */
  17.     int delta_minus;    /* edge terminates at this node */
  18.     int dist;       /* distance from the start node */
  19.     int prev;       /* previous node of the shortest path */
  20.     int succ,pred;  /* node in Sbar with finite dist. */
  21.     int w;
  22.     int h;
  23.     int pw;
  24.     int dx;
  25.     int dy;
  26.     String  name;
  27. }
  28.  
  29. class Edge {
  30.     int rndd_plus;  /* initial vertex of this edge */
  31.     int rndd_minus; /* terminal vertex of this edge */
  32.     int delta_plus; /* edge starts from rndd_plus */
  33.     int delta_minus;    /* edge terminates at rndd_minus */
  34.     int len;        /* length */
  35.     String  name;
  36. }
  37.  
  38. public class Dijkstra extends Applet implements MouseListener {
  39.     int n,m;
  40.     int u,snode;    /* start node */
  41.     int pre_s_first, pre_s_last;
  42.     boolean isdigraph;
  43.     int iteration, step;
  44.     Node    v[] = new Node[100];
  45.     Edge    e[] = new Edge[200];
  46.  
  47.     int findNode(String name) {
  48.         for (int i=0; i<n; i++)
  49.             if (v[i].name.equals(name))
  50.                 return i;
  51.         return -1;
  52.     }
  53.  
  54.     void input_graph(InputStream is) throws IOException {
  55.         int x,y,l;
  56.         String  s;
  57.  
  58.         Reader r = new BufferedReader(new InputStreamReader(is));
  59.         StreamTokenizer st = new StreamTokenizer(r);
  60.         st.commentChar('#');
  61.         st.nextToken(); n = (int)st.nval;
  62.         st.nextToken(); m = (int)st.nval;
  63.         st.nextToken(); s = st.sval;
  64.         isdigraph = "digraph".equals(s);
  65.         for (int i = 0; i<n; i++) {
  66.             Node node = new Node();
  67.             st.nextToken(); node.name = st.sval;
  68.             st.nextToken(); node.x = (int)st.nval;
  69.             st.nextToken(); node.y = (int)st.nval;
  70.             v[i] = node;
  71.         }
  72.         for (int i = 0; i<m; i++) {
  73.             Edge edge = new Edge();
  74.             st.nextToken(); edge.name = st.sval;
  75.             switch (st.nextToken()) {
  76.             case StreamTokenizer.TT_NUMBER:
  77.                 edge.rndd_plus = (int)st.nval;
  78.                 break;
  79.             case StreamTokenizer.TT_WORD:
  80.                 edge.rndd_plus = findNode(st.sval);
  81.                 break;
  82.             default:
  83.                 break;
  84.             }
  85.             switch (st.nextToken()) {
  86.             case StreamTokenizer.TT_NUMBER:
  87.                 edge.rndd_minus = (int)st.nval;
  88.                 break;
  89.             case StreamTokenizer.TT_WORD:
  90.                 edge.rndd_minus = findNode(st.sval);
  91.                 break;
  92.             default:
  93.                 break;
  94.             }
  95.             st.nextToken(); edge.len = (int)st.nval;
  96.             e[i] = edge;
  97.         }
  98.         for (int i=0; i<n; i++) {
  99.             v[i].succ = v[i].pred = -2;
  100.             v[i].prev = v[i].dist = -1;
  101.             v[i].pw = 0;
  102.         }
  103.         iteration = step = 0;
  104.     }
  105.  
  106.     void rdb() {
  107.         int i,k;
  108.  
  109.         for (i=0; i<n; i++)
  110.             v[i].delta_plus = v[i].delta_minus = -1;
  111.         for (i=0; i<m; i++)
  112.             e[i].delta_plus = e[i].delta_minus = -1;
  113.         for (i=0; i<m; i++) {
  114.             k = e[i].rndd_plus;
  115.             if (v[k].delta_plus == -1)
  116.                 v[k].delta_plus = i;
  117.             else {
  118.                 k = v[k].delta_plus;
  119.                 while(e[k].delta_plus >= 0)
  120.                     k = e[k].delta_plus;
  121.                 e[k].delta_plus = i;
  122.             }
  123.             k = e[i].rndd_minus;
  124.             if (v[k].delta_minus == -1)
  125.                 v[k].delta_minus = i;
  126.             else {
  127.                 k = v[k].delta_minus;
  128.                 while(e[k].delta_minus >= 0)
  129.                     k = e[k].delta_minus;
  130.                 e[k].delta_minus = i;
  131.             }
  132.         }
  133.     }
  134.  
  135.     void append_pre_s(int i) {
  136.         v[i].succ = v[i].pred = -1;
  137.         if (pre_s_first<0)
  138.             pre_s_first = i;
  139.         else
  140.             v[pre_s_last].succ = i;
  141.         v[i].pred = pre_s_last;
  142.         pre_s_last = i;
  143.     }
  144.  
  145.     void remove_pre_s(int i) {
  146.         int succ = v[i].succ;
  147.         int pred = v[i].pred;
  148.  
  149.         if (succ>=0)
  150.             v[succ].pred = pred;
  151.         else
  152.             pre_s_last = pred;
  153.         if (pred>=0)
  154.             v[pred].succ = succ;
  155.         else
  156.             pre_s_first = succ;
  157.     }
  158.  
  159.     void step1() {      /* initialize */
  160.         u = snode;
  161.         for (int i=0; i<n; i++) {
  162.             v[i].succ = v[i].pred = -2;
  163.             v[i].prev = v[i].dist = -1;
  164.         }
  165.         v[u].succ = -3;
  166.         v[u].dist = 0;
  167.         pre_s_first = pre_s_last = -1;
  168.     }
  169.  
  170.     void step2() {      /* replace labels */
  171.         int i,j;
  172.  
  173.         j = v[u].delta_plus;
  174.         while (j>=0) {
  175.             i = e[j].rndd_minus;
  176.             if ((v[i].succ>=-2)&&((v[i].dist<0)||
  177.                 (v[i].dist>v[u].dist+e[j].len))) {
  178.                 if (v[i].dist<0)
  179.                     append_pre_s(i);
  180.                 v[i].dist = v[u].dist + e[j].len;
  181.                 v[i].prev = u;    /* label */
  182.             }
  183.             j = e[j].delta_plus;
  184.         }
  185.         if (!isdigraph) {
  186.         j = v[u].delta_minus;
  187.         while (j>=0) {
  188.             i = e[j].rndd_plus;
  189.             if ((v[i].succ>=-2)&&((v[i].dist<0)||
  190.                 (v[i].dist>v[u].dist+e[j].len))) {
  191.                 if (v[i].dist<0)
  192.                     append_pre_s(i);
  193.                 v[i].dist = v[u].dist + e[j].len;
  194.                 v[i].prev = u;    /* label */
  195.             }
  196.             j = e[j].delta_minus;
  197.         }
  198.         }
  199.         v[u].succ = -4;
  200.     }
  201.  
  202.     void step3() {      /* find the shortest node in Sbar */
  203.         int i,rho;
  204.  
  205.         rho = -1;
  206.         for (i = pre_s_first; i>=0; i = v[i].succ) {
  207.             if ((rho < 0)||(rho>v[i].dist)) {
  208.                 rho = v[i].dist;
  209.                 u = i;
  210.             }
  211.         }
  212.         remove_pre_s(u);
  213.         v[u].succ = -3;
  214.     }
  215.  
  216.     void step4() {
  217.         v[u].succ = -4;
  218.     }
  219.  
  220.     double weight(Node n, double x, double y) {
  221.         double  w,z,xx,yy;
  222.  
  223.         w = 0;
  224.         for (int j = n.delta_plus; j>=0; j=e[j].delta_plus) {
  225.             xx = (double)(v[e[j].rndd_minus].x - n.x);
  226.             yy = (double)(v[e[j].rndd_minus].y - n.y);
  227.             z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+1.0;
  228.             w += z*z*z*z;
  229.         }
  230.         for (int j = n.delta_minus; j>=0; j=e[j].delta_minus) {
  231.             xx = (double)(v[e[j].rndd_plus].x - n.x);
  232.             yy = (double)(v[e[j].rndd_plus].y - n.y);
  233.             z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+1.0;
  234.             w += z*z*z*z;
  235.         }
  236.         return w;
  237.     }
  238.  
  239.     void init_sub() {
  240.         int x[] = {1, 0, -1, 1, 0, -1};
  241.         int y[] = {1, 1, 1, -1, -1, -1};
  242.         int     i,j,k;
  243.         double  w,z;
  244.  
  245.         for (i=0; i<n; i++) {
  246.             k=0;
  247.             w=weight(v[i],(double)x[0],(double)y[0]);
  248.             for (j=1; j<6; j++) {
  249.                 z=weight(v[i],(double)x[j],(double)y[j]);
  250.                 if (z<w) {
  251.                     w = z;
  252.                     k = j;
  253.                 }
  254.             }
  255.             v[i].dx = x[k];
  256.             v[i].dy = y[k];
  257.         }
  258.     }
  259.  
  260.     public void init() {
  261.         String mdname = getParameter("inputfile");
  262.         try {
  263.             InputStream is;
  264.  
  265.             is = new URL(getDocumentBase(),mdname).openStream();
  266.             input_graph(is);
  267.             try {
  268.                 if (is != null)
  269.                     is.close();
  270.                 } catch(Exception e) {
  271.             }
  272.         } catch (FileNotFoundException e) {
  273.             System.err.println("File not found.");
  274.         } catch (IOException e) {
  275.             System.err.println("Cannot access file.");
  276.         }
  277.  
  278.         String s = getParameter("start");
  279.         if (s != null)
  280.             snode = Integer.parseInt(s);
  281.         else
  282.             snode = 0;
  283.  
  284.         setBackground(Color.white);
  285.         rdb();
  286.         init_sub();
  287.         addMouseListener(this);
  288.     }
  289.  
  290.     public void paintNode(Graphics g, Node n, FontMetrics fm) {
  291.         String s;
  292.         int x = n.x;
  293.         int y = n.y;
  294.         int w = fm.stringWidth(n.name) + 10;
  295.         int h = fm.getHeight() + 4;
  296.         n.w = w;
  297.         n.h = h;
  298.  
  299.         if (n.succ<-2)
  300.             g.setColor(Color.blue);
  301.         else if (n.succ==-2)
  302.             g.setColor(Color.gray);
  303.         else
  304.             g.setColor(Color.red);
  305.  
  306.         g.drawRect(x-w/2,y-h/2,w,h);
  307.  
  308.         if (n.succ==-4)
  309.             g.setColor(Color.cyan);
  310.         else if (n.succ==-3)
  311.             g.setColor(Color.pink);
  312.         else if (n.succ>-2)
  313.             g.setColor(Color.yellow);
  314.         else
  315.             g.setColor(getBackground());
  316.  
  317.         g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);
  318.  
  319.         g.setColor(Color.black);
  320.         g.drawString(n.name,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent());
  321.  
  322.  
  323.         if (n.dist<0)
  324.             s = "";
  325.         else
  326.             s = ""+n.dist;
  327.         w = fm.stringWidth(s) + 10;
  328.         x += (h+1)*n.dx; y += (h+1)*n.dy;
  329.         g.setColor(getBackground());
  330.         g.fillRect(x-n.pw/2,y-h/2,n.pw,h);
  331.         n.pw = w;
  332.         if (n.succ<-2)
  333.             g.setColor(Color.blue);
  334.         else
  335.             g.setColor(Color.red);
  336.         g.drawString(s,x-(w-10)/2,y-(h-4)/2+fm.getAscent());
  337.     }
  338.  
  339.     int [] xy(int a, int b, int w, int h) {
  340.         int x[] = new int[2];
  341.  
  342.         if (Math.abs(w*b)>=Math.abs(h*a)) {
  343.             x[0] = ((b>=0)?1:-1)*a*h/b/2;
  344.             x[1] = ((b>=0)?1:-1)*h/2;
  345.         } else {
  346.             x[0] = ((a>=0)?1:-1)*w/2;
  347.             x[1] = ((a>=0)?1:-1)*b*w/a/2;
  348.         }
  349.         return x;
  350.     }
  351.  
  352.     void drawArrow(Graphics g,int x1,int y1,int x2,int y2) {
  353.         int a = x1-x2;
  354.         int b = y1-y2;
  355.  
  356.         if (isdigraph) {
  357.         double  aa = Math.sqrt(a*a+b*b)/16.0;
  358.         double  bb = b/aa;
  359.             aa = a/aa;
  360.         g.drawLine(x2,y2,x2+(int)((aa*12+bb*5)/13),y2+(int)((-aa*5+bb*12)/13));
  361.         g.drawLine(x2,y2,x2+(int)((aa*12-bb*5)/13),y2+(int)((aa*5+bb*12)/13));
  362.         }
  363.         g.drawLine(x1,y1,x2,y2);
  364.     }
  365.  
  366.     public void paintEdge(Graphics g, Edge e, FontMetrics fm) {
  367.         Node v1 = v[e.rndd_plus];
  368.         Node v2 = v[e.rndd_minus];
  369.  
  370.         int a = v1.x-v2.x;
  371.         int b = v1.y-v2.y;
  372.  
  373.         int x1[] = xy(-a,-b,v1.w,v1.h);
  374.         int x2[] = xy(a,b,v2.w,v2.h);
  375.  
  376.         if (v2.prev == e.rndd_plus) {
  377.             if ((v1.succ<-2)&&(v2.succ>=-2))
  378.                 g.setColor(Color.red);
  379.             else
  380.                 g.setColor(Color.blue);
  381.         } else {
  382.             g.setColor(Color.lightGray);
  383.         }
  384.         if ((!isdigraph)&&(v1.prev == e.rndd_minus)) {
  385.             if ((v2.succ<-2)&&(v1.succ>=-2))
  386.                 g.setColor(Color.red);
  387.             else
  388.                 g.setColor(Color.blue);
  389.         }
  390.         drawArrow(g,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1]);
  391.  
  392.         int w = fm.stringWidth("" + e.len);
  393.         int h = fm.getHeight();
  394.  
  395.         g.setColor(getBackground());
  396.         g.fillRect((v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2,w,h);
  397.  
  398.         if ((v2.prev == e.rndd_plus)||
  399.             ((!isdigraph)&&(v1.prev == e.rndd_minus)))
  400.             g.setColor(Color.black);
  401.         else
  402.             g.setColor(Color.lightGray);
  403.         g.drawString("" + e.len,(v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2+fm.getAscent());
  404.     }
  405.  
  406.     public void paint(Graphics g) {
  407.         FontMetrics fm = g.getFontMetrics();
  408.         for (int i=0; i<n; i++)
  409.             paintNode(g,v[i],fm);
  410.         for (int i=0; i<m; i++)
  411.             paintEdge(g,e[i],fm);
  412.     }
  413.  
  414.     public void update(Graphics g) {
  415.         paint(g);
  416.     }
  417.  
  418.     public void mousePressed(MouseEvent ev) {
  419.         if (iteration==0) {
  420.             step1();
  421.             iteration++;
  422.             step = 2;
  423.         } else if (iteration>=n) {
  424.             step4();
  425.             iteration = 0;
  426.         } else {
  427.             if (step == 2) {
  428.                 step2();
  429.                 step = 3;
  430.             } else {
  431.                 step3();
  432.                 iteration++;
  433.                 step = 2;
  434.             }
  435.         }
  436.         repaint();
  437.     }
  438.     public void mouseClicked(MouseEvent event) {}
  439.     public void mouseReleased(MouseEvent event) {}
  440.     public void mouseEntered(MouseEvent event) {}
  441.     public void mouseExited(MouseEvent event) {}
  442. }
RAW Paste Data