graphalgorithm.java

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

	  for (int j=0; j<MAXNODES;j++)
	      algedge[i][j]=false;
	}
	colornode[startgraph]=Color.blue;
	performalg = false;
    }

    public void clear() {
    // removes graph from screen
	startgraph=0;
	numnodes=0;
	emptyspots=0;
	init();
	for(int i=0; i<MAXNODES; i++) {
	  node[i]=new Point(0, 0);
	  for (int j=0; j<MAXNODES;j++)
	      weight[i][j]=0;
	}
	if (algrthm != null) algrthm.stop();
	parent.unlock();
	repaint();
    }

    public void reset() {
    // resets a graph after running an algorithm
	init();
	if (algrthm != null) algrthm.stop();
	parent.unlock();
	repaint();
    }

    public void runalg() {
    // gives an animation of the algorithm
	parent.lock();
	initalg();
	performalg = true;
	algrthm = new Thread(this);
	algrthm.start();
    }

    public void stepalg() {
    // lets you step through the algorithm
	parent.lock();
	initalg();
	performalg = true;
	nextstep();
    }

    public void initalg() {
	init();
	for(int i=0; i<MAXNODES; i++) {
	  dist[i]=-1;
	  finaldist[i]=-1;
	  for (int j=0; j<MAXNODES;j++)
              algedge[i][j]=false;
	}
        dist[startgraph]=0;
	finaldist[startgraph]=0;
	step=0;
    }

    public void nextstep() {
    // calculates a step in the algorithm (finds a shortest 
    // path to a next node).
        finaldist[minend]=mindist;
	algedge[minstart][minend]=true;
	colornode[minend]=Color.orange;
        // build more information to display on documentation panel
	step++;
	repaint();
    }

    public void stop() {
	if (algrthm != null) algrthm.suspend();
    }

    public void run() {
	for(int i=0; i<(numnodes-emptyspots); i++){
	  nextstep();
	  try { algrthm.sleep(2000); }
	  catch (InterruptedException e) {}
	}
	algrthm = null;
    }

    public void showexample() {
    // draws a graph on the screen
	int w, h;
	clear();
	init();
	numnodes=10;
	emptyspots=0;
	for(int i=0; i<MAXNODES; i++) {
	  node[i]=new Point(0, 0);
	  for (int j=0; j<MAXNODES;j++)
	      weight[i][j]=0;
	}
	w=this.size().width/8;
	h=this.size().height/8;
	node[0]=new Point(w, h);     node[1]=new Point(3*w, h);   
	node[2]=new Point(5*w, h);   node[3]=new Point(w, 4*h); 
	node[4]=new Point(3*w, 4*h); node[5]=new Point(5*w, 4*h);
	node[6]=new Point(w, 7*h);   node[7]=new Point(3*w, 7*h); 
	node[8]=new Point(5*w, 7*h); node[9]=new Point(7*w, 4*h);

	weight[0][1]=4;  weight[0][3]=85;
	weight[1][0]=74; weight[1][2]=18; weight[1][4]=12;
	weight[2][5]=74; weight[2][1]=12; weight[2][9]=12;
	weight[3][4]=32; weight[3][6]=38;
	weight[4][3]=66; weight[4][5]=76; weight[4][7]=33;
	weight[5][8]=11; weight[5][9]=21;
	weight[6][7]=10; weight[6][3]=12;
	weight[7][6]=2;  weight[7][8]=72;
	weight[8][5]=31; weight[8][9]=78; weight[8][7]=18;
	weight[9][5]=8;

	for (int i=0;i<numnodes;i++)
	   for (int j=0;j<numnodes;j++)
	      if (weight[i][j]>0)
	         arrowupdate(i, j, weight[i][j]);

	repaint();
    }

    public boolean mouseDown(Event evt, int x, int y) {
	
	if (Locked)
	    parent.documentation.doctext.showline("locked");
	else {
	  clicked = true;
	  if (evt.shiftDown()) {
	  // move a node
	     if (nodehit(x, y, NODESIZE)) {
	        oldpoint = node[hitnode];
	        node1 = hitnode;
	        movenode=true;
	     }
	  }
	  else if (evt.controlDown()) {
	  // delete a node
	     if (nodehit(x, y, NODESIZE)) {
	        node1 = hitnode;
	        if (startgraph==node1) {
	           movestart=true;
	           thispoint = new Point(x,y);
                   colornode[startgraph]=Color.gray;
	        }
	        else
	           deletenode= true;
	     }
	  }
	  else if (arrowhit(x, y, 5)) {
	  // change weihgt of an edge
	     movearrow = true;
	     repaint();
	  }
	  else if (nodehit(x, y, NODESIZE)) {
	  // draw a new arrow
	     if (!newarrow) {
	        newarrow = true;
	        thispoint = new Point(x, y);
	        node1 = hitnode;
	     }
	   }
	   else if ( !nodehit(x, y, 50) && !arrowhit(x, y, 50) )  {
	   // draw new node
	      if (emptyspots==0) {
	      // take the next available spot in the array
	         if (numnodes < MAXNODES)
	            node[numnodes++]=new Point(x, y);
	         else  parent.documentation.doctext.showline("maxnodes");
	      }
	      else {
	      // take an empty spot in the array (from previously deleted node)
	         int i;
	         for (i=0;i<numnodes;i++)
	            if (node[i].x==-100) break;
	         node[i]=new Point(x, y);
	         emptyspots--;
	      }
	   }
	   else
	   // mouseclick to close to a point or arrowhead, so probably an error
	      parent.documentation.doctext.showline("toclose");
	   repaint();
	}
	return true;
    }

    public boolean mouseDrag(Event evt, int x, int y) {
	if ( (!Locked) && clicked ) {
	   if (movenode) {
	   // move node and adjust arrows coming into/outof the node
	      node[node1]=new Point(x, y);
	      for (int i=0;i<numnodes;i++) {
	         if (weight[i][node1]>0) {
	            arrowupdate(i, node1, weight[i][node1]);
	         }
	         if (weight[node1][i]>0) {
	            arrowupdate(node1, i, weight[node1][i]);
	         }
	      }
	      repaint();
	   }
	   else if (movestart || newarrow) {
	      thispoint = new Point(x, y);
	      repaint();
	   }
	   else if (movearrow) {
	      changeweight(x, y);
	      repaint();
	   }
	}
	return true;
    }


    public boolean mouseUp(Event evt, int x, int y) {
	if ( (!Locked) && clicked ) {
	   if (movenode) {
	   // move the node if the new position is not to close to 
	   // another node or outside of the panel
	      node[node1]=new Point(0, 0);
	      if ( nodehit(x, y, 50) || (x<0) || (x>this.size().width) || 
					  (y<0) || (y>this.size().height) ) {
	         node[node1]=oldpoint;
	         parent.documentation.doctext.showline("toclose");
	      }
	      else node[node1]=new Point(x, y);
	      for (int i=0;i<numnodes;i++) {
	         if (weight[i][node1]>0)
	            arrowupdate(i, node1, weight[i][node1]);
	         if (weight[node1][i]>0) 
	            arrowupdate(node1, i, weight[node1][i]);
	      }
	      movenode=false;
	   }
	   else if (deletenode) {
	      nodedelete();
	      deletenode=false;
	   }
	   else if (newarrow) {
	      newarrow = false;
	      if (nodehit(x, y, NODESIZE)) {
	         node2=hitnode;
	         if (node1!=node2) {
	            arrowupdate(node1, node2, 50);
	            if (weight[node2][node1]>0) {
	               arrowupdate(node2, node1, weight[node2][node1]);
	            }
	            parent.documentation.doctext.showline("change weights");
	         }
	         else System.out.println("zelfde");
	      }
	   }
	   else if (movearrow) {
	      movearrow = false;
	      if (weight[node1][node2]>0)
	         changeweight(x, y);
	   }
	   else if (movestart) {
	   // if new position is a node, this node becomes the startnode
	      if (nodehit(x, y, NODESIZE))
	         startgraph=hitnode;
	      colornode[startgraph]=Color.blue;
	      movestart=false;
	   }
	   repaint();
	}
	return true;
    }

    public boolean nodehit(int x, int y, int dist) {
    // checks if you hit a node with your mouseclick
	for (int i=0; i<numnodes; i++)
	  if ( (x-node[i].x)*(x-node[i].x) + 
				(y-node[i].y)*(y-node[i].y) < dist*dist ) {
	     hitnode = i;
	     return true;
	  }
	return false;
    }

    public boolean arrowhit(int x, int y, int dist) {
    // checks if you hit an arrow with your mouseclick
	for (int i=0; i<numnodes; i++)
	  for (int j=0; j<numnodes; j++) {
	     if ( ( weight[i][j]>0 ) && 
			(Math.pow(x-arrow[i][j].x, 2) + 
			 Math.pow(y-arrow[i][j].y, 2) < Math.pow(dist, 2) ) ) {
	        node1 = i;
	        node2 = j;
	        return true;
	     }
	  }
	return false;
    }

    public void nodedelete() {
    // delete a node and the arrows coming into/outof the node
	node[node1]=new Point(-100, -100);
	for (int j=0;j<numnodes;j++) {
	   weight[node1][j]=0;
	   weight[j][node1]=0;
	}
	emptyspots++;
    }

    public void changeweight(int x, int y) {
    // changes the weight of an arrow (edge in the graph), when a user drags 
    // the arrowhead over the edge connecting node node1 and node2.

	// direction of the arrow
	int diff_x = (int)(20*dir_x[node1][node2]);
	int diff_y = (int)(20*dir_y[node1][node2]);

	// depending on the arrow direction, follow the x, or the y
	// position of the mouse while the arrowhead is being dragged
	boolean follow_x=false;
	   if (Math.abs(endp[node1][node2].x-startp[node1][node2].x) >
		     Math.abs(endp[node1][node2].y-startp[node1][node2].y) ) {
	   follow_x = true;
	}

	// find the new position of the arrowhead, and calculate 
	// the corresponding weight
	if (follow_x) {
	    int hbound = Math.max(startp[node1][node2].x, 
				  endp[node1][node2].x)-Math.abs(diff_x);
	    int lbound = Math.min(startp[node1][node2].x, 
				  endp[node1][node2].x)+Math.abs(diff_x);

	    // arrow must stay between the nodes
	    if (x<lbound) { arrow[node1][node2].x=lbound; }
	    else if (x>hbound) { arrow[node1][node2].x=hbound; }
	    else arrow[node1][node2].x=x;

	    arrow[node1][node2].y=
		(arrow[node1][node2].x-startp[node1][node2].x) *
		    (endp[node1][node2].y-startp[node1][node2].y)/
		        (endp[node1][node2].x-startp[node1][node2].x) + 
		startp[node1][node2].y;

	    // new weight
	    weight[node1][node2]=
		Math.abs(arrow[node1][node2].x-startp[node1][node2].x-diff_x)*
			100/(hbound-lbound);
	}
	// do the same if you follow y
	else {
	    int hbound = Math.max(startp[node1][node2].y, 
			 	  endp[node1][node2].y)-Math.abs(diff_y);
	    int lbound = Math.min(startp[node1][node2].y, 
			 	  endp[node1][node2].y)+Math.abs(diff_y);

	    if (y<lbound) { arrow[node1][node2].y=lbound; }