graphcanvas.java

dijkstra algorithm, need complile and building to jar file and run it.

package dijkstra;

import java.awt.Canvas;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Event;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.Point;

import static dijkstra.Constants.MAXNODES;
import static dijkstra.Constants.DIJKSTRA_ALGORITHM;
import static dijkstra.Constants.NODERADIX;
import static dijkstra.Constants.NODESIZE;

public class GraphCanvas extends Canvas {
	private Graph graph = new Graph();

	private int step = 0;

	// information used by the dijkstra algorithm to find the next node with
	// minimum distance
	private int minDistance, minNode, minStart, minEnd;

	// the node index used for brute force algorithm to find out next node.
	private int nodeIndex = -1;

	private int numOfNodes = 0; // number of nodes

	private int hitnode; // mouse clicked on or close to this node

	private int node1, node2; // numbers of nodes involved in current action

	private Point currPoint = new Point(0, 0); // current mouse position

	private Point prevPoint = new Point(0, 0); // previous position of node

	private boolean newarrow = false;

	private boolean movearrow = false;

	private boolean movestart = false;

	private boolean movenode = false;

	private boolean performalg = false;

	private boolean clicked = false;

	private boolean inPrint = false;
	// fonts

	private Font roman = new Font("TimesRoman", Font.BOLD, 12);

	private Font helvetica = new Font("Helvetica", Font.BOLD, 15);

	private FontMetrics fmetrics = getFontMetrics(roman);

	private int h = (int) fmetrics.getHeight() / 3;

	// for double buffering

	private Image offScreenImage;

	private Graphics offScreenGraphics;

	private Dimension offScreenSize;

	private int algorithm = DIJKSTRA_ALGORITHM;

	// for algorithm information to be displayed in log panel
	private DijkstraApplet parent;

	public GraphCanvas(DijkstraApplet myparent) {

		parent = myparent;

		init();

		setBackground(Color.white);

	}

	public void init() {

		graph.init();

		performalg = false;

	}

	public void clear() {
		// System.out.println("****** clear******");
		numOfNodes = 0;

		init();

		// removes graph from screen
		graph.clear();

		if (algorithm != DIJKSTRA_ALGORITHM) {
			nodeIndex = -1;
		}

		repaint();

	}

	public void reset() {
		// System.out.println("****** reset******");
		// resets a graph after running an algorithm

		init();

		if (algorithm != DIJKSTRA_ALGORITHM) {
			nodeIndex = -1;
		}

		repaint();

	}

	public void runAlgorithm() {

		// gives an animation of the algorithm

		initAlgorithm();

		performalg = true;
		nodeIndex = 0;
		run();
	}

	public void stepAlgorithm() {
		// System.out.println("****** StepAlgorithem******");
		// lets you step through the algorithm

		initAlgorithm();

		performalg = true;

		if (algorithm != DIJKSTRA_ALGORITHM) {
			nodeIndex = -1;
		}
		nextstep();

	}

	public void setAlgprithm(int algorithm) {
		this.algorithm = algorithm;
		if (algorithm == DIJKSTRA_ALGORITHM) {
			parent.getLogPanel().log("--- Applying Dijkstra Algorithm ---");
		} else {
			parent.getLogPanel().log("--- Applying Brute Force ---");
		}
	}

	public void initAlgorithm() {
		// System.out.println("****** initAlgorithm******");
		init();

		graph.initAlgorithmGraph();
		step = 0;

	}

	public boolean nextstep() {
		// System.out.println("****** nextstep******");
		// calculates a step in the algorithm (finds a shortest
		// path to a next node).

		boolean hasNextStep = true;
		if (algorithm == DIJKSTRA_ALGORITHM) {
			graph.finalDist[minEnd] = minDistance;
			graph.algorithmEdge[minStart][minEnd] = true;

			graph.colorNode[minEnd] = Color.orange;

		} else {
			if (nodeIndex < numOfNodes) {
				nodeIndex++;
			}
		}
		// build more information to display on documentation panel

		step++;
		parent.getLogPanel().log("Step " + step);
		update();
		return hasNextStep;
	}

	public void run() {
		// System.out.println("****** run******");
		String logMsg = "";
		long totalTime = 0;
		if (algorithm == DIJKSTRA_ALGORITHM) {
			logMsg = "============ Using Dijkstra's  Algorithm, ";
			for (int i = 0; i < numOfNodes; i++) {
				long starttime = System.currentTimeMillis();
				nextstep();
				long stoptime = System.currentTimeMillis();
				totalTime += (stoptime - starttime);

				try {
					Thread.sleep(300);
				} catch (InterruptedException e) {
				}

			}
		} else {
			logMsg = "============ Using Brute Force Algorithm, ";
			nodeIndex = -1;
			while (nodeIndex < numOfNodes) {
				long starttime = System.currentTimeMillis();
				nextstep();
				long stoptime = System.currentTimeMillis();
				totalTime += (stoptime - starttime);
				try {
					Thread.sleep(300);
				} catch (InterruptedException e) {
				}
			}
		}
		logMsg += "total time used " + totalTime + " millisec and ";
		logMsg += "total steps are " + step;
		parent.getLogPanel().log(logMsg);
	}

	public void drawExample() {
		// draws a example graph on the screen

		clear();

		init();

		numOfNodes = 10;

		int w = this.getSize().width / 8;

		int h = this.getSize().height / 8;

		graph.initSampleData(w, h, numOfNodes);

		repaint();

	}

	public String findNodeName(int i) {

		char c = (char) ((int) 'a' + i);

		return "" + c;

	}

	public void clearAlgorithmEdge(int j) {
		for (int i = 0; i < numOfNodes; i++) {
			graph.algorithmEdge[i][j] = false;
		}
	}

	public void applyBruteForce(Graphics g, int i, int j) {
		if (i == nodeIndex) { // current working node

			if (i != graph.startgraph) {
				graph.colorNode[nodeIndex] = Color.orange;
			}
			if (graph.finalDist[i] != -1) {
				String logMsg = "work on the line " + findNodeName(i) + " --> "
						+ findNodeName(j) + " now. ";
				if ((graph.finalDist[j] == -1)) { // new node
					graph.algorithmEdge[i][j] = true;
					graph.dist[j] = graph.dist[i] + graph.weight[i][j];
					graph.finalDist[j] = graph.dist[j];

					graph.colorNode[j] = Color.red;

				} else if ((graph.finalDist[j] != -1)) {
					if ((graph.dist[i] + graph.weight[i][j]) < graph.dist[j]) {
						graph.dist[j] = graph.dist[i] + graph.weight[i][j];
						graph.finalDist[j] = graph.dist[j];
						graph.colorNode[j] = Color.red;
						clearAlgorithmEdge(j);
						graph.algorithmEdge[i][j] = true;
						if (j < i) {// the changed node already passed, then
							// need to
							// come back and reverify
							logMsg += "the updated node " + findNodeName(j)
									+ " already passed and need to revisit.";
							nodeIndex = j - 1;
						}
					}
				}
				if (!inPrint)
					parent.getLogPanel().log(logMsg);
			}
		} else {
			g.setColor(Color.gray);
		}
	}

	public void applyDijkstra(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 start node

		if ((graph.finalDist[i] != -1) && (graph.finalDist[j] == -1)) { // leave
			// node
			if (!inPrint)
				parent.getLogPanel().log(
						"work on the line " + findNodeName(i) + " --> "
								+ findNodeName(j) + " now");
			g.setColor(Color.red);
			if ((graph.dist[j] == -1)
					|| (graph.dist[j] >= (graph.dist[i] + graph.weight[i][j]))) {
				
				graph.dist[j] = graph.dist[i] + graph.weight[i][j];

				graph.colorNode[j] = Color.red;

				if ((minDistance == 0) || (graph.dist[j] < minDistance)) {

					minDistance = graph.dist[j];

					minStart = i;

					minEnd = j;

				}
			}

		} else {
			g.setColor(Color.gray);
		}

	}

	public void displayAndSetFinalDistance(Graphics g) {
		// displays current and final distances of nodes, sets the final
		// distance

		// for the node that had minimal distance in this step

		for (int i = 0; i < numOfNodes; i++) {

			if ((graph.node[i].x > 0) && (graph.dist[i] != -1)) {
				String str = Integer.toString(graph.dist[i]);
				if (!inPrint)
					parent.getLogPanel().log(
							"The current distance for node " + findNodeName(i)
									+ " = " + str);
				g.drawString(str, graph.node[i].x
						- (int) fmetrics.stringWidth(str) / 2 - 1,
						graph.node[i].y + h);

			}
		}
	}

	public void applyAlgorithm(Graphics g, int i, int j) {

		// more algorithms can be added later

		if (algorithm == DIJKSTRA_ALGORITHM) {
			applyDijkstra(g, i, j);
		} else {
			applyBruteForce(g, i, j);
		}

	}

	public void endStepAlgorithm(Graphics g) {

		// more algorithms can be added later
		displayAndSetFinalDistance(g);

		if (algorithm == DIJKSTRA_ALGORITHM && !inPrint) {
			parent.getLogPanel().log(
					"The leave node " + findNodeName(minEnd)
							+ " has the minimum distance " + minDistance);
		}