Introduction
In this project, you will determine all possible flight plans for a person wishing to travel between two cities serviced by an airline (assuming a path exists). You will also calculate the total cost incurred for all parts of the trip. For this project, you will use information from two different input files in order to calculate the trip plan and total cost.
Origination and Destination Data – This file will contain a sequence of city pairs representing different legs of flights that can be considered in preparing a flight plan. The file will also contain a dollar cost for that leg and a time to travel. For each pair in the file, you can assume that it is possible to fly in both directions.
Requested Flights – This file will contain a sequence of origin/destination city pairs. Your program will determine if the flight is or is not possible for each pair. If possible, it will output to a file the flight plan with the total cost for the flight. If it is impossible, a suitable message will be written to the output file.
The names of the input and output files will be provided via command line arguments.
Flight Data:
Here is an example of a flight data input file (it does not go with Figure 1):
4
Dallas|Austin|98|47
Austin|Houston|95|39
Dallas|Houston|101|51
Austin|Chicago|144|192
The first line of the file will contain an integer indicating how many rows of data will be in the file. Each subsequent row will contain two city names, the flight's cost, and the flight's number of minutes. Each field will be separated with a pipe (shift-\ on most keyboards).
Requested Flight Plans:
A sample input file for the requested flight plans is shown below. The first line will contain an integer indicating the requested flight plans. The subsequent lines will contain a pipe-delimited list of city pairs with a trailing character to indicate sorting the output of flights by time (T) or cost (C). Your solution will find all flight paths between these two cities (if any exist) and calculate the total cost of the flights and the total time in the air.
2
Dallas|Houston|T
Chicago|Dallas|C
Output File:
For each flight in the Requested Flight Plans file, your program will print the three most efficient flight plans available based on whether the request was to order by time or cost. If there are at most three possible plans, output all of the possible plans. An error message should be output if no flight plan can be created. Here is an example:
Flight 1: Dallas, Houston (Time)
Path 1: Dallas -> Houston. Time: 51 Cost: 101.00
Path 2: Dallas -> Austin -> Houston. Time: 86 Cost: 193.00
Flight 2: Chicago, Dallas (Cost)
Path 1: Chicago -> Austin -> Dallas. Time: 237 Cost: 242.00
Path 2: Chicago -> Austin -> Houston -> Dallas. Time: 282 Cost: 340.00
Flight Planning (Traveling Salesman) Problem Implementation in Java:
Dijkstra Priority Queue In Java code.
DijkstraPriorityQueue.java file:
| import java.io.BufferedReader; | |
| import java.io.FileNotFoundException; | |
| import java.io.FileReader; | |
| import java.io.PrintWriter; | |
| import java.util.ArrayList; | |
| import java.util.HashMap; | |
| import java.util.HashSet; | |
| import java.util.List; | |
| import java.util.PriorityQueue; | |
| import java.util.Set; | |
| import java.util.StringTokenizer; | |
| public class DijkstraPriorityQueue | |
| { | |
| private HashMap<String, Integer> optimalDistances; | |
| private HashMap<String, Integer> distances; | |
| private Set<String> settled; | |
| private List<Path> visitedNodesList; | |
| private PriorityQueue<Node> priorityQueue; | |
| private int optType,otherType; | |
| private String pathCostTime[][], Source, Destination; | |
| private List<String> nodeList; | |
| public DijkstraPriorityQueue(List<String> nodeList) | |
| { | |
| this.nodeList = nodeList; | |
| optimalDistances = new HashMap<String,Integer>(); | |
| distances = new HashMap<String,Integer>(); | |
| settled = new HashSet<String>(); | |
| visitedNodesList = new ArrayList<Path>(); | |
| priorityQueue = new PriorityQueue<Node>(new Node()); | |
| } | |
| public void dijkstra_algorithm(String pathCostTime[][], String requestedPath[]) | |
| { | |
| String evaluationNode; | |
| Source = requestedPath[0]; | |
| Destination = requestedPath[1]; | |
| if(requestedPath[2].equalsIgnoreCase("C")) | |
| { | |
| optType = 2; | |
| otherType = 3; | |
| } | |
| else | |
| { | |
| optType = 3; | |
| otherType = 2; | |
| } | |
| this.pathCostTime = pathCostTime; | |
| for (String node:nodeList) | |
| { | |
| optimalDistances.put(node, Integer.MAX_VALUE); | |
| distances.put(node, Integer.MAX_VALUE); | |
| } | |
| priorityQueue.add(new Node(Source, 0)); | |
| optimalDistances.replace(Source,0); | |
| distances.replace(Source, 0); | |
| while (!priorityQueue.isEmpty()) | |
| { | |
| evaluationNode = getNodeWithMinimumDistanceFromPriorityQueue(); | |
| Path evaluationNodeList = new Path(); | |
| evaluationNodeList.setNode(evaluationNode); | |
| settled.add(evaluationNode); | |
| evaluateNeighbours(evaluationNode, evaluationNodeList); | |
| if(!nodeExists(visitedNodesList, evaluationNode)) | |
| visitedNodesList.add(evaluationNodeList); | |
| } | |
| } | |
| private boolean nodeExists(List<Path> visitedNodesList2, String evaluationNode) | |
| { | |
| for (Path path : visitedNodesList) | |
| { | |
| if(path.getNode().equals(evaluationNode)) | |
| return true; | |
| } | |
| return false; | |
| } | |
| // definition of the method getNodeWithMinimumDistanceFromPriorityQueue() | |
| private String getNodeWithMinimumDistanceFromPriorityQueue() | |
| { | |
| String node = priorityQueue.remove().node; | |
| return node; | |
| } | |
| // definition of the method evaluateNeighbours() | |
| private void evaluateNeighbours(String evaluationNode, Path evaluationNodeList) | |
| { | |
| int edgeDistance = -1; | |
| int newDistance = -1; | |
| for (int i = 0; i<pathCostTime.length; i++) | |
| { | |
| if(!pathCostTime[i][0].equals(evaluationNode)) | |
| continue; | |
| String destinationNode; | |
| for (int j = 0; j < nodeList.size(); j++) | |
| { | |
| destinationNode = nodeList.get(j); | |
| if(!pathCostTime[i][1].equals(destinationNode)) | |
| continue; | |
| if (!settled.contains(destinationNode)) | |
| { | |
| edgeDistance = Integer.parseInt(pathCostTime[i][optType]); | |
| newDistance = optimalDistances.get(evaluationNode) + edgeDistance; | |
| if (newDistance < optimalDistances.get(destinationNode)) | |
| { | |
| optimalDistances.replace(destinationNode,newDistance); | |
| distances.replace(destinationNode,distances.get(evaluationNode) + | |
| Integer.parseInt(pathCostTime[i][otherType])); | |
| for (Path path : visitedNodesList) | |
| { | |
| if(path.exists(destinationNode)) | |
| path.delete(destinationNode); | |
| break; | |
| } | |
| evaluationNodeList.add(destinationNode); | |
| } | |
| priorityQueue.add(new Node(destinationNode,optimalDistances.get(destinationNode))); | |
| } | |
| } | |
| } | |
| } | |
| // definition of the method main() | |
| //takes the names of the two input files as well as the output file as arguments. | |
| public static void main(String args[]) throws FileNotFoundException | |
| { | |
| //Declare the variables. | |
| String pathCostTime[][],requsetedPathList[][]; | |
| BufferedReader flightData, requestedFlightData; | |
| List<String> nodesList; | |
| String infile1 = args[0]; | |
| String infile2 = args[1]; | |
| String outFile = args[2]; | |
| PrintWriter out = new PrintWriter(outFile); | |
| try | |
| { | |
| flightData = new BufferedReader(new FileReader(infile1)); | |
| requestedFlightData = new BufferedReader(new FileReader(infile2)); | |
| String str; | |
| nodesList = new ArrayList<String>(); | |
| pathCostTime = new String[Integer.parseInt(flightData.readLine())][4]; | |
| requsetedPathList = new String[Integer.parseInt(requestedFlightData.readLine())][3]; | |
| int i=0,j; String _node; | |
| // Make tokens of the data of the flightData file | |
| while((str = flightData.readLine()) != null) | |
| { | |
| j=0; | |
| StringTokenizer data = new StringTokenizer(str,"|"); | |
| int k = 1; | |
| while(k<=2) | |
| { | |
| if(!nodesList.contains(_node = data.nextToken())) | |
| { | |
| pathCostTime[i][j++] = _node; | |
| nodesList.add(_node); | |
| } | |
| else | |
| pathCostTime[i][j++] = _node; | |
| k++; | |
| } | |
| while(data.hasMoreTokens()) | |
| { | |
| pathCostTime[i][j++] = data.nextToken(); | |
| } | |
| i++; | |
| } | |
| i=0; | |
| // Make tokens of the data of the requestedFlightData file | |
| while((str = requestedFlightData.readLine()) != null) | |
| { | |
| j=0; | |
| StringTokenizer data = new StringTokenizer(str,"|"); | |
| while(data.hasMoreTokens()) | |
| requsetedPathList[i][j++] = data.nextToken(); | |
| i++; | |
| } | |
| i=1; | |
| // Check the type of the cost | |
| for(String requsetedPath[] : requsetedPathList) | |
| { | |
| if(!(nodesList.contains(requsetedPath[0])&& nodesList.contains(requsetedPath[1]))) | |
| { | |
| out.println("Path can not be find !!!!!"); | |
| continue; | |
| } | |
| String _type,_otherType; | |
| if(requsetedPath[2].equals("T")) | |
| { | |
| _type = "Time"; | |
| _otherType = "Cost"; | |
| } | |
| else | |
| { | |
| _type = "Cost"; | |
| _otherType = "Time"; | |
| } | |
| // Call the DijkstraPriorityQueue to make the priority queue. | |
| DijkstraPriorityQueue dijkstrasPriorityQueue = new DijkstraPriorityQueue(nodesList); | |
| // Call the dijkstra_algorithm method to run the Dijkstra's algorithm | |
| dijkstrasPriorityQueue.dijkstra_algorithm(pathCostTime, requsetedPath); | |
| out.println("Flight "+i+": "+dijkstrasPriorityQueue.Source+", "+ | |
| dijkstrasPriorityQueue.Destination+" ("+_type+")"); | |
| for (String node:nodesList) | |
| { | |
| if(!node.equals(dijkstrasPriorityQueue.Destination)) | |
| continue; | |
| List<String> completePath = findPath(dijkstrasPriorityQueue.visitedNodesList, | |
| dijkstrasPriorityQueue.Destination); | |
| for (int k = 0; k < completePath.size(); k++) | |
| { | |
| if(k == completePath.size()-1 ) | |
| out.print(completePath.get(k)+". "); | |
| else | |
| out.print(completePath.get(k)+" --> "); | |
| } | |
| out.println(_type+": " + dijkstrasPriorityQueue.optimalDistances.get(node)+" " | |
| +_otherType+": "+dijkstrasPriorityQueue.distances.get(node)); | |
| break; | |
| } | |
| i++; | |
| } | |
| } catch (Exception e) | |
| { | |
| System.out.println("Exception has occured:" + e.toString()); | |
| } | |
| out.close(); | |
| } | |
| // definition of the method findPath() | |
| private static List<String> findPath(List<Path> visitedNodesList, String Destination) | |
| { | |
| List<String> completePath = new ArrayList<String>(); | |
| for( Path path : visitedNodesList) | |
| { | |
| if(!path.exists(Destination)) | |
| continue; | |
| completePath = findPath(visitedNodesList, path.getNode()); | |
| completePath.add(Destination); | |
| return completePath; | |
| } | |
| completePath.add(Destination); | |
| return completePath; | |
| } | |
| } |
City.java file:
| import java.util.Comparator; | |
| // Class | |
| class City implements Comparator<City> | |
| { | |
| public String city; | |
| public int cost; | |
| public City() | |
| { | |
| } | |
| // Compare the nodes. | |
| @Override | |
| public int compare(City node1, City node2) | |
| { | |
| if (node1.cost < node2.cost) | |
| return -1;if (node1.cost > node2.cost) | |
| return 1; | |
| return 0; | |
| } | |
| public City(String city, int cost) | |
| { | |
| this.city = city; | |
| this.cost = cost; | |
| } | |
| } |
Node.java file:
| import java.util.Comparator; | |
| // Class | |
| class Node implements Comparator<Node> | |
| { | |
| public String node; | |
| public int CostTime; | |
| public Node() | |
| { | |
| } | |
| // Set the node and their cost | |
| public Node(String node, int CostTime) | |
| { | |
| this.node = node; | |
| this.CostTime = CostTime; | |
| } | |
| // Compare the nodes. | |
| @Override | |
| public int compare(Node node1, Node node2) | |
| { | |
| if (node1.CostTime < node2.CostTime) | |
| return -1; | |
| if (node1.CostTime > node2.CostTime) | |
| return 1; | |
| return 0; | |
| } | |
| } |
Path.java file:
| import java.util.ArrayList; | |
| import java.util.List; | |
| // Create the class | |
| class Path | |
| { | |
| private List<String> path; | |
| private String Node; | |
| //Create the arrayList | |
| public Path() | |
| { | |
| path = new ArrayList<String>(); | |
| } | |
| // Set the node | |
| public void setNode(String Node) | |
| { | |
| this.Node = Node; | |
| } | |
| // Get the node | |
| public String getNode() | |
| { | |
| return this.Node; | |
| } | |
| // Check if the node exist or not | |
| public Boolean exists(String node) | |
| { | |
| if(path.contains(node)) | |
| return true; | |
| return false; | |
| } | |
| // Add the node in the array List | |
| public void add(String node) | |
| { | |
| path.add(node); | |
| } | |
| //Delete the node from the list | |
| public void delete(String node) | |
| { | |
| path.remove(node); | |
| } | |
| } |
Root.java file:
| import java.util.ArrayList; | |
| import java.util.List; | |
| // Create the class | |
| class Root | |
| { | |
| private List<String> root; | |
| private String city; | |
| // Get the node | |
| public String getNode() | |
| { | |
| return this.city; | |
| } | |
| // Add the node in the array List | |
| public void add(String city) | |
| { | |
| root.add(city); | |
| } | |
| //Delete the node from the list | |
| public void delete(String city) | |
| { | |
| root.remove(city); | |
| } | |
| // Check if the node exist or not | |
| public Boolean exists(String city) | |
| { | |
| if(root.contains(city)) | |
| return true; | |
| return false; | |
| } | |
| //Create the arrayList | |
| public Root() | |
| { | |
| root = new ArrayList<String>(); | |
| } | |
| // Set the node | |
| public void setNode(String Node) | |
| { | |
| this.city = Node; | |
| } | |
| } |
You must have the following .txt file in your project directory:
- flightData.txt
- outFile.txt
- requestedFlightData.txt
The flightData.txt file will contain flight information as follows.
The outFile.txt is the output directory where the program output will be saved.
The requestesFlightData.txt file is the query file as user input as follows.
Output file
 |
| Traveling Salesman Problem Using Dynamic Programming in Java [Flight Planning] |
Please feel free to comment. Java projects with source code.
where the data
ReplyDeletePost a Comment