Dijkstra's For Node Mapping Calculation.java

gistfile1.java

import java.util.PriorityQueue;
import java.util.ArrayList; 
import java.util.Scanner;
import java.util.List; 
import java.io.*; 

class Edge {
	public Node dest_node;	// Destination when you travel along this node
	public int distance; 	// How far to get to destination node along this edge

	public Edge(Node dest_node, int distance) {
		this.distance = distance;
		this.dest_node = dest_node; 
	} 
	public int getDistance() { return distance; }
	public Node getDestination() { return dest_node; }
}

class Node implements Comparable<Node> {
	public int id;	// Nodes have natural numbers as ids; source is 0
	public int min_distance = Integer.MAX_VALUE;  // Treat max int as infinity
	public Node predecessor; 	// Keeps track of who precedes this node on min path
	public Edge[] neighbors;  // Tracks distances to nodes I'm connected to

	public Node(int id) { this.id = id; }
	public String toString() { return id + "," + min_distance; }

	// Define compare method so that I can know who has 'shorter' path from src
	public int compareTo(Node alt_node) {
		int dist_compare = Integer.compare(min_distance, alt_node.min_distance);
		if (dist_compare == 0) return Integer.compare(id, alt_node.id);
		else return dist_compare;
	}
	public Edge[] getNeighbors() { return neighbors; }
	public int getMinDistance() { return min_distance; }
	public Node getPredecessor() { return predecessor; }
	public void setNeighbors(Edge[] neighbors) { this.neighbors = neighbors; }
	public void setPredecessor(Node p) { predecessor = p; }
	public void setMinDistance(int i) { min_distance = i; }
}

class LinkState {
	static int NUM_NODES = 0; // Track how many nodes there are
	static int NUM_VISITED = 0;  // Track how many nodes I've visited

	public static void main(String[] args) {
		int[][] int_array = generate_mapping(args[0]);
		ArrayList<Node> nodes = create_nodes(int_array);
		findPath(nodes); // Find path, starting at source node 1
	}

	public static void findPath(ArrayList<Node> nodes) {
		Node source = nodes.get(0);
		source.setMinDistance(0); // Since we start at source, min distance is 0
		// Using p_queue allows it to compare for me based off Comparable<Node>
		PriorityQueue<Node> node_queue = new PriorityQueue<Node>();
		node_queue.add(source); // init queue with source node
		int step = 0; 
		String path = ""; 
		String d_str = ""; 
		for (int i = 1; i < NUM_NODES; i++) {
			d_str += ("D(" + (i+1) + "),p(" + (i+1) + ")\t");
		}

		System.out.println("-----------------------------------------------------------------------------------------------------");
		System.out.println("Step\tN\'\t" + d_str);
		System.out.println("-----------------------------------------------------------------------------------------------------");

		// When this queue is empty, it means we've found the min distance to all nodes
		while (!node_queue.isEmpty()) {
			Node closest_node = node_queue.poll(); // Grabs closest node

			// See if new minimum distance to neighbor node found
			for (Edge edge : closest_node.getNeighbors()) {
				int distance_to = edge.getDistance();
				Node destination = edge.getDestination();
				int min_d_from_curr = closest_node.getMinDistance() + distance_to;
				if (destination.getMinDistance() > min_d_from_curr && min_d_from_curr > 0) {
					// If we have a new minimum distance, we have to take it out 
					// of the queue and re-add it after updating the distance.
					// That way it gets stored according to new distance 'priority'
					node_queue.remove(destination);
					destination.setPredecessor(closest_node);
					destination.setMinDistance(min_d_from_curr);
					node_queue.add(destination);
				}
			} 

			// Print out info about each of my nodes
			if (step > 0) path += ",";	
			path += closest_node.id; 
			step++; 
			String distances = "";
			for (int i = 1; i < NUM_NODES; i++) {
				Node current_node = nodes.get(i);
				int d = (current_node.getMinDistance() == Integer.MAX_VALUE) ? -1 : current_node.getMinDistance();
				int idn = (current_node.getPredecessor() == null) ? 1 : current_node.getPredecessor().id;
				distances += (d + "," + idn + "\t");
			}
			System.out.println(step + "\t" + path + "\t" + distances);	
			System.out.println("-----------------------------------------------------------------------------------------------------");	
		}
	}

	public static ArrayList<Node> create_nodes(int[][] int_array) {
		ArrayList<Node> node_list = new ArrayList<Node>(); 
		for (int a = 0; a < NUM_NODES; a++) { node_list.add(new Node(a+1)); }

		for (int i = 0; i < NUM_NODES; i++) {
			Node current_node = node_list.get(i);
			Edge[] edges = new Edge[NUM_NODES];
			for (int j = 0; j < NUM_NODES; j++) {
				edges[j] = new Edge(node_list.get(j), int_array[i][j]);
			}
			current_node.setNeighbors(edges); 
		}
		return node_list;
	}

	public static int[][] generate_mapping(String in) {
		int[][] mapping_from_file = null; 
		int node_num = 0;

		// Hook Scanner into file
		Scanner file_scanner = null;
		try { file_scanner = new Scanner(new File(in)); }
		catch (FileNotFoundException fnfe) { System.out.println(fnfe.toString()); }
		 
		// Parse file using String.split() and store into int[][]
		while (file_scanner.hasNextLine()) {
			String scan_line = file_scanner.nextLine(); 
			if (scan_line.charAt(0) == 'E') { break; }  // EOF
			String[] nodes_row = scan_line.split(",");  // Split up based on commas
			if (NUM_NODES == 0) {	// Init array once I know how many nodes
				NUM_NODES = nodes_row.length;
				mapping_from_file = new int[NUM_NODES][NUM_NODES];
			} 
			for (int i = 0; i < nodes_row.length; i++) {
				if (i == nodes_row.length-1) { nodes_row[i] = nodes_row[i].charAt(0) + ""; }
				if (nodes_row[i].equals("N")) mapping_from_file[node_num][i] = Integer.MAX_VALUE;
				else mapping_from_file[node_num][i] = Integer.parseInt(nodes_row[i]);
			} 
			node_num++;	// Increment node counter
		}
		return mapping_from_file; 
	}
}