graphalgorithm.java

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

import java.awt.*;

public class GraphAlgorithm extends java.applet.Applet {

    GraphCanvas graphcanvas = new GraphCanvas(this);
    Options options = new Options(this);   
    Documentation documentation = new Documentation();

    public void init() {
	setLayout(new BorderLayout(10, 10));
	add("Center", graphcanvas);
	add("North", documentation);
	add("East", options);
    }

    public Insets insets() {
	return new Insets(10, 10, 10, 10);
    }

    public void lock() {
	graphcanvas.lock();
	options.lock();
    } 

    public void unlock() {
	graphcanvas.unlock();
	options.unlock();
    } 
}


class Options extends Panel {
// set of options at the right of the screen
    Button b1 = new Button("clear");
    Button b2 = new Button("run");
    Button b3 = new Button("step");
    Button b4 = new Button("reset");
    Button b5 = new Button("example");
    Button b6 = new Button("exit");
    GraphAlgorithm parent;   
    boolean Locked=false;
  
    Options(GraphAlgorithm myparent) {
	parent = myparent;
	setLayout(new GridLayout(6, 1, 0, 10));
	add(b1);
	add(b2);
	add(b3);
	add(b4);
	add(b5); 
	add(b6);
    }

    public boolean action(Event evt, Object arg) {
	if (evt.target instanceof Button) {
	  if (((String)arg).equals("step")) {
	     if (!Locked) {
	        b3.setLabel("next step");
	        parent.graphcanvas.stepalg();
	     }
	     else parent.documentation.doctext.showline("locked");
	  }
	  if (((String)arg).equals("next step")) 
	     parent.graphcanvas.nextstep();
	  if (((String)arg).equals("reset")) { 
	     parent.graphcanvas.reset();
	     b3.setLabel("step");
	     parent.documentation.doctext.showline("all items");
	  }
	  if (((String)arg).equals("clear")) { 
	     parent.graphcanvas.clear();
	     b3.setLabel("step");
	     parent.documentation.doctext.showline("all items");
	  }
	  if (((String)arg).equals("run")) {
	     if (!Locked)  
	        parent.graphcanvas.runalg();
	     else parent.documentation.doctext.showline("locked");
	  }
	  if (((String)arg).equals("example")) {
	     if (!Locked)   
	        parent.graphcanvas.showexample();
	     else parent.documentation.doctext.showline("locked");
	  } 
	  if (((String)arg).equals("exit")) { 
	     System.exit(0);
	  } 
	}                   
	return true; 
    }
    
    public void lock() {
	Locked=true;
    }

    public void unlock() {
	Locked=false;
	b3.setLabel("step"); 
    } 
}    


class Documentation extends Panel {
// Documentation on top of the screen
    DocOptions docopt = new DocOptions(this);
    DocText doctext = new DocText();

    Documentation() {
	setLayout(new BorderLayout(10, 10));
	add("West", docopt);
	add("Center", doctext);
    }
}


class DocOptions extends Panel {
    Choice doc = new Choice();
    Documentation parent;   
   
    DocOptions(Documentation myparent) {
	setLayout(new GridLayout(2, 1, 5, 0));
	parent = myparent;
	add(new Label("DOCUMENTATION:"));
	doc.addItem("draw nodes");
	doc.addItem("remove nodes"); 
	doc.addItem("move nodes");
	doc.addItem("the startnode");
	doc.addItem("draw arrows"); 
	doc.addItem("change weights");
	doc.addItem("remove arrows");
	doc.addItem("clear / reset"); 
	doc.addItem("run algorithm");
	doc.addItem("step through");
	doc.addItem("example"); 
	doc.addItem("exit"); 
	doc.addItem("all items");
	add(doc);
    }
  
    public boolean action(Event evt, Object arg) {
        if (evt.target instanceof Choice) {
	    String str=new String(doc.getSelectedItem());
	    parent.doctext.showline(str);  
        }             
       	return true;
    }
}


class DocText extends TextArea {
    final String drawnodes = new String("DRAWING NODES:\n"+
	  "Draw a node by clicking the mouse.\n\n");
    final String rmvnodes = new String("REMOVE NODES:\n"+
	  "To remove a node press <ctrl> and click on the node.\n"+
	  "You can not remove the startnode.\n"+
	  "Select another startnode, then you can remove the node.\n\n");
    final String mvnodes = new String("MOVING NODES\n"+
	  "To move a node press <Shift>, click on the node,\nand drag it to"+
	  " its new position.\n\n");
    final String startnode = new String("STARTNODE:\n"+
	  "The startnode is blue, other nodes are grey.\n"+ 
	  "The first node you draw on the screen will be the startnode.\n"+
	  "To select another startnode press <ctrl>, click on the startnode,\n"+
	  "and drag the mouse to another node.\n"+
	  "To delete the startnode, first select another startnode, and then"+
	  "\nremove the node the usual way.\n\n"); 
    final String drawarrows = new String("DRAWING ARROWS:\n"+
	  "To draw an arrow click mouse in a node,"+
	  "and drag it to another node.\n\n");
    final String weight = new String("CHANGING WEIGHTS:\n"+
	  "To change the weight of an arrow, click on the arrowhead and drag\n"+
	  "it along the arrow.\n\n");
    final String rmvarrows = new String("REMOVE ARROWS:\n"+
	  "To remove an arrow, change its weight to 0.\n\n");
    final String clrreset = new String("<CLEAR> BUTTON: "+
	  "Remove the current graph from the screen.\n"+
	  "<RESET> BUTTON: "+
	  "Remove the results of the algorithm from the graph,\n"+
	  " and unlock screen.\n\n");
    final String runalg = new String("<RUN> BUTTON: "+
	  "Run the algorithm on the graph, there will be a time\n" +
	  "delay of +/- 1 second between steps.\n"+
	  "To run the algorithm slower, use <STEP>.\n");
    final String step = new String("<STEP> BUTTON: " +
	  "An opportunity to step through the algorithm.\n");
    final String example = new String("<EXAMPLE> BUTTON: "+
	  "Displays a graph on the screen for you.\n"+
	  "You can then use <STEP> or <RUN>\n");
    final String exitbutton = new String("<EXIT> BUTTON: " +
	  "Only works if applet is run with appletviewer.\n");
    final String toclose = new String("ERROR: "+
	  "This position is to close to another node/arrow.\n");
    final String done = new String("Algorithm has finished, " +
	  "follow orange arrows from startnode to any node "+
	  "to get\nthe shortest path to " +
	  "the node. The length of the path is written in the node.\n" +
          "press <RESET> to reset the graph, and unlock the screen.");
    final String some = new String("Algorithm has finished, " +
	  "follow orange arrows from startnode to any node "+
	  "to get\nthe shortest path to " +
	  "the node. The length of the path is written in the node.\n" +
          "There are no paths from the startnode to any gray node.\n" +
          "press <RESET> to reset the graph, and unlock the screen.");
    final String none = new String("Algorithm has finished, " +
	  "there are no nodes reachable from the start node.\n"+
	  "press <RESET> to reset the graph, and unlock the screen.");
  
    final String maxnodes = new String("ERROR: "+ 
	  "Maximum number of nodes reached!\n\n");
    final String info = new String("DOCUMENTATION:\n"+
	  "You can scroll through the documentation or get documentation\n"+
	  "on a specific "+
	  "item by selecting the item on the left.\nSelecting <All items> "+
	  "brings you back "+
	  " to the scrolling text.\n\n"); 
    final String locked = new String("ERROR: "+
	  "Keyboard/mouse locked for this action.\n"+
	  "Either press <NEXT STEP> or <RESET>.\n"); 

    final String doc = info + drawnodes + rmvnodes + mvnodes + 
		       startnode + drawarrows + weight + rmvarrows + 
		       clrreset + runalg + step + example + exitbutton;

    DocText() {
	super(5, 2);
	setText(doc);
    }
    
    public void showline(String str) {
	if (str.equals("draw nodes"))              setText(drawnodes);
	else if (str.equals("remove nodes"))       setText(rmvnodes);
	else if (str.equals("move nodes"))         setText(mvnodes);
	else if (str.equals("the startnode"))      setText(startnode);
	else if (str.equals("draw arrows"))        setText(drawarrows);
	else if (str.equals("change weights"))     setText(weight);
	else if (str.equals("remove arrows"))      setText(rmvarrows);
	else if (str.equals("clear / reset"))      setText(clrreset);
	else if (str.equals("run algorithm"))      setText(runalg);
	else if (str.equals("step through"))       setText(step);
	else if (str.equals("example"))            setText(example); 
        else if (str.equals("exit"))               setText(exitbutton);
	else if (str.equals("all items"))          setText(doc);
	else if (str.equals("toclose"))            setText(toclose); 
	else if (str.equals("done"))               setText(done);   
	else if (str.equals("locked"))             setText(locked);
	else if (str.equals("maxnodes"))           setText(maxnodes);       
        else if (str.equals("none"))               setText(none);   
        else if (str.equals("some"))               setText(some);   
	else setText(str);
    }
}


class GraphCanvas extends Canvas implements Runnable {
// drawing area for the graph
    
    final int MAXNODES = 20;
    final int MAX = MAXNODES+1;
    final int NODESIZE = 26;
    final int NODERADIX = 13;
    final int DIJKSTRA = 1;
 
    // basic graph information
    Point node[] = new Point[MAX];          // node
    int weight[][] = new int[MAX][MAX];     // weight of arrow
    Point arrow[][] = new Point[MAX][MAX];  // current position of arrowhead
    Point startp[][] = new Point[MAX][MAX]; // start and
    Point endp[][] = new Point[MAX][MAX];   // endpoint of arrow
    float dir_x[][] = new float[MAX][MAX];  // direction of arrow
    float dir_y[][] = new float[MAX][MAX];  // direction of arrow
   
    // graph information while running algorithm
    boolean algedge[][] = new boolean[MAX][MAX];
    int dist[] = new int[MAX];
    int finaldist[] = new int[MAX];
    Color colornode[] = new Color[MAX];
    boolean changed[] = new boolean[MAX];   // indicates distance change during algorithm   
    int numchanged =0; 
    int neighbours=0;
    
    int step=0;
    
    // information used by the algorithm to find the next 
    // node with minimum distance
    int mindist, minnode, minstart, minend;

    int numnodes=0;      // number of nodes
    int emptyspots=0;    // empty spots in array node[] (due to node deletion)
    int startgraph=0;    // start of graph
    int hitnode;         // mouse clicked on or close to this node
    int node1, node2;    // numbers of nodes involved in current action

    Point thispoint=new Point(0,0); // current mouseposition
    Point oldpoint=new Point(0, 0); // previous position of node being moved

    // current action
    boolean newarrow = false;
    boolean movearrow = false;
    boolean movestart = false;
    boolean deletenode = false;
    boolean movenode = false;
    boolean performalg = false;
    boolean clicked = false;

    // fonts
    Font roman= new Font("TimesRoman", Font.BOLD, 12);
    Font helvetica= new Font("Helvetica", Font.BOLD, 15);
    FontMetrics fmetrics = getFontMetrics(roman);
    int h = (int)fmetrics.getHeight()/3;

    // for double buffering
    private Image offScreenImage;
    private Graphics offScreenGraphics;
    private Dimension offScreenSize;


    // for run option
    Thread algrthm;

    // current algorithm, (in case more algorithms are added)
    int algorithm;

    // algorithm information to be displayed in documetation panel
    String showstring = new String("");

    boolean stepthrough=false;

    // locking the screen while running the algorithm
    boolean Locked = false;

    GraphAlgorithm parent;

    GraphCanvas(GraphAlgorithm myparent) {
	parent = myparent;
	init();
	algorithm=DIJKSTRA;
	setBackground(Color.white);
    }

    public void lock() {
    // lock screen while running an algorithm
	Locked=true;
    }

    public void unlock() {
	Locked=false;
    }

    public void start() {
	if (algrthm != null) algrthm.resume();
    }

    public void init() {
	for (int i=0;i<MAXNODES;i++) {
	  colornode[i]=Color.gray;