In this project we will model the connections between some fictional cities. The data is available on graph.txt (at the end) Our weighted graph will represent this by edge-weights equal to a fictional distance value among some fictional cities. Remember that the city names are String. So, you need to use a hashtable to map the city names into graph vertices: converting strings to integers as vertex numbers. More explanation on Hashing: Implement a method or a piece of code using hashing techniques which stores some strings as names (e.g., ece, araz, ali, sara, ) in an array after generating a hashcode (index) for each name. For example, if hashcode (sara) = 8, it should be stored in index 8. If index 8 is already full, collision management techniques should be used. The length of hash table (array) is up to you, but do not choose it too big. The initial list of names should be read from an input file that contains 353 lines. In this file, each line contains two names as vertices, and an integer value as edge weight between two vertices. Your program should also be able to search a given string in the array in constant time using hashing techniques (not linear search) and return the index of array containing this name, or -1 if the name does not exist in the array. Note: We will not use a different input file to test your code but we will enter different input values as parameters of the methods that you are asked to implement (given below). ReadGraphFromFile(): loads graph data a from the file into an adjacency matrix. Before constructing this matrix, a hash table should be also created. IsThereAPath(String v1, String v2): Returns true if there is a path between vertex v1 and vertex v2 or false, otherwise. BFSfromTo(String v1, String v2): prints the sequence of vertices (names of the vertices) and edges (weights of the edges) between the vertices while starting a BFS from v1 until reaching v2. DFSfromTo(String v1, String v2): prints the sequence of vertices (names of the vertices) and edges (weights of the edges) between while starting a DFS from v1 until reaching v2. WhatIsShortestPathLength(String v1, String v2): returns the length of shortest path from vertex v1 to vertex v2. It prints v1 --x-- v2 if there is no path from v1 to v2. NumberOfSimplePaths(String v1, String v2): returns the number of paths from v1 to v2. Neighbors(String v1): returns the names of the neighbor vertices of v1. HighestDegree(): returns the name of the vertex with the highest degree. If there is more then one, it returns the names of all. IsDirected(): returns true if the graph is directed, otherwise false. AreTheyAdjacent(String v1, String v2): returns true if v1 and v2 are adjacent, otherwise false. IsThereACycle(String v1): returns true if there is a cycle path which starts and ends on v1, otherwise false. NumberOfVerticesInComponent(String v1): prints the number of vertices that exist in the component that contains name1. Main method: in this method, prepare a menu to select any of the methods mentioned above. For each method, the input parameters should be received from the user interactively and the result of the method must be printed to the console. NOTE 1: In all the methods mentioned above, no vertex can be repeated in the same path. NOTE 2: In BFS, the edge order while visiting the children of a vertex, starts from edge with minimum weight and continues to the edge with maximum weight NOTE 3: For the graph representation and algorithms of this project, use your own implementations and ideas. Any usages of premade-classes, libraries or known algorithms will be graded as 0. For example, if you use any graph related class in Java, your grade will be 0. Another example, for the solution of WhatIsShortestPathLength method, if you use any known solution such as Djisktra's algorithm, your grade will be 0. Please use your own ideas, solutions and implementations. For your overall project, this rule is not applied only for the DFS and BFS functions. NOTE 4: File structure is different than what you saw in the lecture. The number of the vertices and the edges are not specified in the file. You can calculate them if you think that you need them. The content of the file is similar to the adjacency list representation. Each row of the file defines the edges for a single vertex. For example, the first for of the file defines the edges of vertex A. In each row, after the "->" sign, edges are listed and separated with ",". Each edge definition consists of two elements, separated with ":". The first elements is the end-point and the second element is the weight of the edge. Feel free to modify that code or to implement your ownidea. Please note that you are not allowed to use anything other than basic string operations such as split. (For the string operations you are allowed to use basic methods of the String class in Java)

graph.txt:

A -> B: 3, C: 2, D: 1, E: 4 B -> C: 1, D: 4, G: 5 C -> D: 5, E: 2, H: 3 D -> E: 1, F: 2, I: 4 E -> A: 2, B: 3, F: 1 F -> G: 3, H: 4, J: 2 G -> H: 2, I: 1, K: 5 H -> I: 3, J: 2, L: 4 I -> J: 1, K: 3, M: 2 J -> K: 3, L: 4, N: 1 K -> L: 5, M: 2, O: 3 L -> M: 4, N: 2, P: 1 M -> N: 5, O: 3, Q: 4 N -> O: 2, P: 3, R: 1 O -> P: 4, Q: 2, S: 5 P -> Q: 1, R: 3, T: 4 Q -> R: 2, S: 1, U: 5 R -> S: 3, T: 2, V: 4 S -> T: 4, U: 1, W: 2 T -> U: 3, V: 5, X: 1 U -> V: 2, W: 4, Y: 3 V -> W: 1, X: 2, Z: 5 W -> X: 3, Y: 4, A1: 1 X -> Y: 2, Z: 3, B1: 4 Y -> Z: 1, A1: 5, C1: 2 Z -> A1: 4, B1: 3, D1: 1 A1 -> B1: 2, C1: 3, E1: 4 B1 -> C1: 1, D1: 2, F1: 5 C1 -> D1: 3, E1: 1, G1: 4 D1 -> E1: 2, F1: 3, H1: 5 E1 -> F1: 1, G1: 2, I1: 4 F1 -> G1: 3, H1: 4, J1: 1 G1 -> H1: 2, I1: 3, K1: 5 H1 -> I1: 4, J1: 1, L1: 2 I1 -> J1: 3, K1: 4, M1: 1 J1 -> K1: 2, L1: 3, N1: 5 K1 -> L1: 1, M1: 4, O1: 2 L1 -> M1: 3, N1: 1, P1: 4 M1 -> N1: 5, O1: 2, Q1: 3 N1 -> O1: 1, P1: 4, R1: 2 O1 -> P1: 3, Q1: 5, S1: 1 P1 -> Q1: 4, R1: 1, T1: 3 Q1 -> R1: 2, S1: 5, U1: 4 R1 -> S1: 1, T1: 3, V1: 2 S1 -> T1: 4, U1: 1, W1: 3 T1 -> U1: 2, V1: 4, X1: 1 U1 -> V1: 3, W1: 2, Y1: 4 V1 -> W1: 1, X1: 2, Z1: 3 W1 -> X1: 4, Y1: 1, A2: 3 X1 -> Y1: 2, Z1: 3, B2: 1 Y1 -> Z1: 1, A2: 5, C2: 2 Z1 -> A2: 4, B2: 3, D2: 1 A2 -> B2: 2, C2: 3, E2: 4