ars.java

The task in this assignment is to implement an airline routing system. Your system should be able t

import java.util.*;
import java.io.*;

public class ARS extends Graph
{
	/**This integer is used to store the sum of the weight of all inputed edges.
		*In my system, the initial distance of the vertex is replaced by this integer.
	*/
	protected int max;

	/*The constructor without an inputed file as an airline routine system.*/
	public ARS()
	{
		super();
		max = 1;
	}

	/*The constructor with an inputed file as an airline routine system.*/
	public ARS(String file)
	{
		this();

		//Read in the graph in the file.
		try
		{
			String line = "";
			BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file)));
			while ((line = reader.readLine()) != null)
			{
				StringTokenizer st = new StringTokenizer(line, " ");

				if (st.nextToken().equals("VERTEX"))
					insertVertex(st.nextToken());
				else
					insertEdge(st.nextToken(), st.nextToken(), st.nextToken());
			}
			reader.close();
		}
		catch(Exception e)
		{
			e.printStackTrace();
		}

	}

	/*This overwritten method is used to insert a new edge.*/
	public void insertEdge(String s, String d, String w)
	{
		//Check whether both of the vertices exit in the graph.
		if (! (vertex.contains(s) && vertex.contains(d)))
		{
			System.out.println("At least one of the vertices you input does not exist!");
			return;
		}
		
		//Update the max integer.
		max += Integer.parseInt(w);
		
		//Insert the edge in both directions.
		ArrayList<String> es = new ArrayList<String>();
		es.add(d);
		es.add(w);
		edge.get(s).add(es);

		ArrayList<String> ed = new ArrayList<String>();
		ed.add(s);
		ed.add(w);
		edge.get(d).add(ed);
	}

	/*This overwritten method is used to remove a vertex.*/
	public void removeVertex(String v)
	{
		//Check whether the vertex exists.
		if (! vertex.contains(v))
		{
			System.out.println("The vertex you input does not exist in the graph!");
			return;
		}

		//Output the deleted edge because of the deletion of the vertex
		ArrayList<ArrayList<String>> ev = edge.get(v);
		for (ArrayList<String> e : ev)
			System.out.println("The filght from " + v + " to " + e.get(0) + " has been removed.");
		
		//Remove the vertex and its edges.
		vertex.remove(v);
		edge.remove(v);
		
		for (String t : vertex)
		{
			ArrayList<ArrayList<String>> et = edge.get(t);
			for (int k = 0; k < et.size(); k ++)
				if (et.get(k).get(0).equals(v))
					et.remove(k);
		}
	}

	/*This overwritten method is used to remove an edge*/
	public void removeEdge(String s, String d)
	{
		//Check whether the edge exists.
		if (! (vertex.contains(s) && vertex.contains(d)))
		{
			System.out.println("The edge you input does not exist.");
			return;
		}

		//Remove the edge in both directions.
		ArrayList<ArrayList<String>> es = edge.get(s);
		for (ArrayList<String> e : es)
			if (e.get(0).equals(d))
			{
				es.remove(e);
				break;
			}

		ArrayList<ArrayList<String>> ed = edge.get(d);
		for (ArrayList<String> e : ed)
			if (e.get(0).equals(s))
			{
				ed.remove(e);
				break;
			}

		//Output the no longer reachable vertex because of the deletion of the edge.
		if (edge.get(s).size() == 0)
			System.out.println("The airport " + s + " is no longer reachable.");
		if (edge.get(d).size() == 0)
			System.out.println("The airport " + d + " is no longer reachable.");
	}

	/*The Dijkstra's algorithm*/
	public void dijkstra(String s, String d)
	{
		//This hashtable stores the distance and the past vertex of every vertex.
		HashMap<String, ArrayList<String>> status = new HashMap<String, ArrayList<String>>();
		for (String v : vertex)
		{
			ArrayList<String> sv = new ArrayList<String>();
			sv.add("" + max);
			sv.add("null");
			status.put(v, sv);
		}

		//This queue stores all the vertices that are out of the "cloud".
		LinkedList<String> queue = new LinkedList<String>();
		for (String v : vertex)
			queue.add(v);

		//Set the status of the starting vertex.
		status.get(s).set(0, "0");
		queue.remove(s);

		//The Dijkstra's algorithm
		//String v stores the vertex that has just been put into the "cloud".
		String v = s;
		while (queue.size() != 0)
		{
			//Update the distance of the adjacent vertices of v if necessary.
			for (ArrayList<String> evw : edge.get(v))
			{
				String w = evw.get(0);
				int dw = Integer.parseInt(status.get(v).get(0)) + Integer.parseInt(evw.get(1));
				int pdw = Integer.parseInt(status.get(w).get(0));
				if (queue.contains(w) && dw < pdw)
				{
					ArrayList<String> sw = status.get(w);
					sw.set(0, "" + dw);
					sw.set(1, v);
				}
			}

			//Find the vertex with the smallest distance outside the "cloud".
			String w = queue.get(0);
			int dw = Integer.parseInt(status.get(w).get(0));
			for (String t : queue)
			{
				int dt = Integer.parseInt(status.get(t).get(0));
				if (dt < dw)
				{
					w = t;
					dw = dt;
				}
			}

			//Update the string v and the queue.
			v = w;
			queue.remove(w);
		}

		//Output the result.
		System.out.println("The shortest distance from " + s + " to " + d + " is: " + status.get(d).get(0));
		System.out.print("The shortest path from " + s + " to " + d + " is: ");
		LinkedList<String> sp = new LinkedList<String>();
		showPath(d, status, sp);
		while (sp.size() != 0)
			System.out.print(sp.pop() + " ");
		System.out.print(d + "\n");
	}

	/*This method is used to get the path from the starting vertex to the ending vertex.*/
	private void showPath(String d, HashMap<String, ArrayList<String>> status, LinkedList<String> sp)
	{
		String p = status.get(d).get(1);
		if (p.equals("null"))
			return;
		sp.push(p);
		showPath(p, status, sp);
	}
}