API tools faq
paste
Advertisement
bangnaga

Dijkstra.java

bangnaga
May 1st, 2012
230
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 9.80 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!