graphalgorithm.java

一个java 编写的最短路径算法实现

	    else if (y>hbound) { arrow[node1][node2].y=hbound; }
	    else arrow[node1][node2].y=y;
	    arrow[node1][node2].x=
		(arrow[node1][node2].y-startp[node1][node2].y) *
		    (endp[node1][node2].x-startp[node1][node2].x)/
			(endp[node1][node2].y-startp[node1][node2].y) + 
		startp[node1][node2].x;

	    weight[node1][node2]=
		Math.abs(arrow[node1][node2].y-startp[node1][node2].y-diff_y)*
			100/(hbound-lbound);
	}
    }

    public void arrowupdate(int p1, int p2, int w) {
    // make a new arrow from node p1 to p2 with weight w, or change
    // the weight of the existing arrow to w, calculate the resulting 
    // position of the arrowhead
	int dx, dy;
	float l;
	weight[p1][p2]=w;

	// direction line between p1 and p2
	dx = node[p2].x-node[p1].x;
	dy = node[p2].y-node[p1].y;

	// distance between p1 and p2
	l = (float)( Math.sqrt((float)(dx*dx + dy*dy)));
	dir_x[p1][p2]=dx/l;
	dir_y[p1][p2]=dy/l;

	// calculate the start and endpoints of the arrow,
	// adjust startpoints if there also is an arrow from p2 to p1
	if (weight[p2][p1]>0) {
	   startp[p1][p2] = new Point((int)(node[p1].x-5*dir_y[p1][p2]), 
				      (int)(node[p1].y+5*dir_x[p1][p2]));
	   endp[p1][p2] = new Point((int)(node[p2].x-5*dir_y[p1][p2]), 
				    (int)(node[p2].y+5*dir_x[p1][p2]));
	}
	else {
	   startp[p1][p2] = new Point(node[p1].x, node[p1].y);
	   endp[p1][p2] = new Point(node[p2].x, node[p2].y);
	}

	// range for arrowhead is not all the way to the start/endpoints
	int diff_x = (int)(Math.abs(20*dir_x[p1][p2]));
	int diff_y = (int)(Math.abs(20*dir_y[p1][p2]));

	// calculate new x-position arrowhead
	if (startp[p1][p2].x>endp[p1][p2].x) {
	   arrow[p1][p2] = new Point(endp[p1][p2].x + diff_x +
		(Math.abs(endp[p1][p2].x-startp[p1][p2].x) - 2*diff_x )*
			(100-w)/100 , 0);
	}
	else {
	   arrow[p1][p2] = new Point(startp[p1][p2].x + diff_x +
		(Math.abs(endp[p1][p2].x-startp[p1][p2].x) - 2*diff_x )*
			w/100, 0);
	}

	// calculate new y-position arrowhead
	if (startp[p1][p2].y>endp[p1][p2].y) {
	   arrow[p1][p2].y=endp[p1][p2].y + diff_y +
		(Math.abs(endp[p1][p2].y-startp[p1][p2].y) - 2*diff_y )*
			(100-w)/100;
	}
	else {
	   arrow[p1][p2].y=startp[p1][p2].y + diff_y +
		(Math.abs(endp[p1][p2].y-startp[p1][p2].y) - 2*diff_y )*
			w/100;
	}
    }


    public String intToString(int i) {
	char c=(char)((int)'a'+i);
	return ""+c;
    }

    public final synchronized void update(Graphics g) {
    // prepare new image offscreen
	Dimension d=size();
	if ((offScreenImage == null) || (d.width != offScreenSize.width) ||
			(d.height != offScreenSize.height)) {
	    offScreenImage = createImage(d.width, d.height);
	    offScreenSize = d;
	    offScreenGraphics = offScreenImage.getGraphics();
	}
	offScreenGraphics.setColor(Color.white);
	offScreenGraphics.fillRect(0, 0, d.width, d.height);
	paint(offScreenGraphics);
	g.drawImage(offScreenImage, 0, 0, null);
    }

    public void drawarrow(Graphics g, int i, int j) {
    // draw arrow between node i and node j
	int x1, x2, x3, y1, y2, y3;

	// calculate arrowhead
	x1= (int)(arrow[i][j].x - 3*dir_x[i][j] + 6*dir_y[i][j]);
	x2= (int)(arrow[i][j].x - 3*dir_x[i][j] - 6*dir_y[i][j]);
	x3= (int)(arrow[i][j].x + 6*dir_x[i][j]);

	y1= (int)(arrow[i][j].y - 3*dir_y[i][j] - 6*dir_x[i][j]);
	y2= (int)(arrow[i][j].y - 3*dir_y[i][j] + 6*dir_x[i][j]);
	y3= (int)(arrow[i][j].y + 6*dir_y[i][j]);

	int arrowhead_x[] = { x1, x2, x3, x1 };
	int arrowhead_y[] = { y1, y2, y3, y1 };

	// if edge already chosen by algorithm change color
	if (algedge[i][j]) g.setColor(Color.orange);
	// draw arrow
	g.drawLine(startp[i][j].x, startp[i][j].y, endp[i][j].x, endp[i][j].y);
	g.fillPolygon(arrowhead_x, arrowhead_y, 4);

	// write weight of arrow at an appropriate position
	int dx = (int)(Math.abs(7*dir_y[i][j]));
	int dy = (int)(Math.abs(7*dir_x[i][j]));
	String str = new String("" + weight[i][j]);
	g.setColor(Color.black);
	if ((startp[i][j].x>endp[i][j].x) && (startp[i][j].y>=endp[i][j].y))
	  g.drawString( str, arrow[i][j].x + dx, arrow[i][j].y - dy);
	if ((startp[i][j].x>=endp[i][j].x) && (startp[i][j].y<endp[i][j].y))
	  g.drawString( str, arrow[i][j].x - fmetrics.stringWidth(str) - dx , 
			     arrow[i][j].y - dy);
	if ((startp[i][j].x<endp[i][j].x) && (startp[i][j].y<=endp[i][j].y))
	  g.drawString( str, arrow[i][j].x - fmetrics.stringWidth(str) , 
			     arrow[i][j].y + fmetrics.getHeight());
	if ((startp[i][j].x<=endp[i][j].x) && (startp[i][j].y>endp[i][j].y))
	    g.drawString( str, arrow[i][j].x + dx, 
			       arrow[i][j].y + fmetrics.getHeight() );
    }


    public void detailsDijkstra(Graphics g, int i, int j) {
    // check arrow between node i and node j is amongst the arrows to
    // choose from during this step of the algorithm
    // check if node j has the next minimal distance to the startnode
	if ( (finaldist[i]!=-1) && (finaldist[j]==-1) ) {
	  g.setColor(Color.red);
	  if ( (dist[j]==-1) || (dist[j]>=(dist[i]+weight[i][j])) ) {
             if ( (dist[i]+weight[i][j])<dist[j] ) {
                 changed[j]=true;
                 numchanged++;
             }
	     dist[j] = dist[i]+weight[i][j];
	     colornode[j]=Color.red;             
	     if ( (mindist==0) || (dist[j]<mindist) ) {
	        mindist=dist[j];
	        minstart=i;
	        minend=j;
	     }
	  }
	}
	else g.setColor(Color.gray);
    }

    public void endstepDijkstra(Graphics g) {
    // displays current and final distances of nodes, sets the final distance
    // for the node that had minimal distance in this step
    // explains algorithm on documentation panel
        for (int i=0; i<numnodes; i++)
	  if ( (node[i].x>0) && (dist[i]!=-1) ) {
	     String str = new String(""+dist[i]);
	     g.drawString(str, node[i].x - (int)fmetrics.stringWidth(str)/2 -1, 
			       node[i].y + h);
	     // string to distance to nodes on the documentation panel
	     if (finaldist[i]==-1) {
	        neighbours++;  
	        if (neighbours!=1)
	           showstring = showstring + ", ";
	        showstring = showstring + intToString(i) +"=" + dist[i];
	     } 
	  }
        showstring = showstring + ". ";
       
        if ( (step>1) && (numchanged>0) ) {
           if (numchanged>1)
              showstring = showstring + "Notice that the distances to ";
           else showstring = showstring + "Notice that the distance to ";
           for (int i=0; i<numnodes; i++)
              if ( changed[i] )
                 showstring = showstring + intToString(i) +", ";
           if (numchanged>1)
              showstring = showstring + "have changed!\n";
           else showstring = showstring + "has changed!\n";
        }
        else showstring = showstring + " "; 
	if (neighbours>1) { 
	// if there where more canditates explain why this node is taken  
 	  showstring = showstring + "Node " + intToString(minend) + 
				    " has the minimum distance.\n";
	  //check if there are other paths to minend. 
	  int newpaths=0;
	  for (int i=0; i<numnodes; i++) 
	     if ( (node[i].x>0) && (weight[i][minend]>0) && ( finaldist[i] == -1 ) )
	        newpaths++; 
	  if (newpaths>0) 
	     showstring = showstring + "Any other path to " + intToString(minend) + 
                   " visits another red node, and will be longer than " +  mindist + ".\n";
          else showstring = showstring + 
			     "There are no other arrows coming in to "+
			     intToString(minend) + ".\n";
	}
	else {
           boolean morenodes=false;
           for (int i=0; i<numnodes; i++) 
	     if ( ( node[i].x>0 ) && ( finaldist[i] == -1 ) && ( weight[i][minend]>0 ) )
	        morenodes=true; 
           boolean bridge=false;
           for (int i=0; i<numnodes; i++) 
	     if ( ( node[i].x>0 ) && ( finaldist[i] == -1 ) && ( weight[minend][i]>0 ) )
	        bridge=true; 
           if ( morenodes && bridge ) 
              showstring = showstring + "Since this node forms a 'bridge' to "+
               "the remaining nodes,\nall other paths to this node will be longer.\n";     
           else if ( morenodes && (!bridge) ) 
              showstring = showstring + "Remaining gray nodes are not reachable.\n";
           else showstring = showstring + "There are no other arrows coming in to "+
	       intToString(minend) + ".\n"; 
        }
	showstring = showstring + "Node " + intToString(minend) + 
	   " will be colored orange to indicate " + mindist + 
	   " is the length of the shortest path to " + intToString(minend) +"."; 
	parent.documentation.doctext.showline(showstring);       
    }

    public void detailsalg(Graphics g, int i, int j) {
    // more algorithms can be added later
	if (algorithm==DIJKSTRA)
	    detailsDijkstra(g, i, j);
    }

    public void endstepalg(Graphics g) {
    // more algorithms can be added later
	if (algorithm==DIJKSTRA)
	    endstepDijkstra(g);
	if ( ( performalg ) && (mindist==0) ) {
	   if (algrthm != null) algrthm.stop();
	   int nreachable = 0;
	   for (int i=0; i<numnodes; i++)
	      if (finaldist[i] > 0)
		 nreachable++;
	   if (nreachable == 0)
	      parent.documentation.doctext.showline("none");
           else if (nreachable< (numnodes-emptyspots-1))
	      parent.documentation.doctext.showline("some");
	   else
	      parent.documentation.doctext.showline("done");
	} 
    }

    public void paint(Graphics g) {
        mindist=0;
	minnode=MAXNODES;
	minstart=MAXNODES;
	minend=MAXNODES;
        for(int i=0; i<MAXNODES; i++) 
           changed[i]=false;
        numchanged=0;
        neighbours=0;
	g.setFont(roman);
	g.setColor(Color.black);
        if (step==1)
           showstring="Algorithm running: red arrows point to nodes reachable from " +
                   " the startnode.\nThe distance to: ";
        else 
           showstring="Step " + step + ": Red arrows point to nodes reachable from " +
                   "nodes that already have a final distance." +
                   "\nThe distance to: ";

	// draw a new arrow upto current mouse position
	if (newarrow)
	  g.drawLine(node[node1].x, node[node1].y, thispoint.x, thispoint.y);

	// draw all arrows
	for (int i=0; i<numnodes; i++)
	  for (int j=0; j<numnodes; j++)
	     if (weight [i][j]>0) {
	        // if algorithm is running then perform next step for this arrow
	        if (performalg)
	           detailsalg(g, i, j);
	        drawarrow(g, i, j);
	     }

	// if arrowhead has been dragged to 0, draw it anyway, so the user
	// will have the option to make it positive again
	if (movearrow && weight[node1][node2]==0) {
	  drawarrow(g, node1, node2);
	  g.drawLine(startp[node1][node2].x, startp[node1][node2].y, 
		     endp[node1][node2].x, endp[node1][node2].y);
	}

	// draw the nodes
	for (int i=0; i<numnodes; i++)
	  if (node[i].x>0) {
	     g.setColor(colornode[i]);
	     g.fillOval(node[i].x-NODERADIX, node[i].y-NODERADIX, 
			NODESIZE, NODESIZE);
	  }

	// reflect the startnode being moved
	g.setColor(Color.blue);
	if (movestart)
	  g.fillOval(thispoint.x-NODERADIX, thispoint.y-NODERADIX, 
			NODESIZE, NODESIZE);


	g.setColor(Color.black);
	// finish this step of the algorithm
	if (performalg) endstepalg(g);

	// draw black circles around nodes, write their names to the screen
	g.setFont(helvetica);
	for (int i=0; i<numnodes; i++)
	  if (node[i].x>0) {
	     g.setColor(Color.black);
	     g.drawOval(node[i].x-NODERADIX, node[i].y-NODERADIX, 
			NODESIZE, NODESIZE);
	     g.setColor(Color.blue);
	     g.drawString(intToString(i), node[i].x-14, node[i].y-14);
	  }
    }
}