public static String dfs (CityRoadMap map, HashMap indexMap, String cityName) throws Exception { String result = ""; // Message to return // Call the bfs method of the AbstractGraph.Tree class // passing in the index of the City in the vertices array // code goes here // Retrieve the City search order into an ArrayList of indexes // code goes here // Output the number of Cities found // code goes here // Loop through the search order ArrayList // Output each city name: only display 5 cities per line // code goes here // Loop through the parent array to display the parent of each City // code goes here return result; } /** * Breadth first search: * This method follows mostly the same algorithm as in the TestBFS class * The HashMap is used to retrieve the City index from the passed in City name * The WeightedGraph (CityRoadMap) methods cannot retrieve the City vertex * object from the city name. */ public static String bfs (CityRoadMap map, HashMap indexMap, String cityName) throws Exception { String result = ""; // Message to return // Call the bfs method of the AbstractGraph.Tree class // passing in the index of the City in the vertices array // code goes here // Retrieve the City search order into an ArrayList of indexes // code goes here // Output the number of Cities found // code goes here // Loop through the search order ArrayList // Output each city name: only display 5 cities per line // code goes here // Loop through the parent array to display the parent of each City // code goes here return result; } /** * Minimum Spanning Tree: * Minimum distance Road travel path going through all the Cities * This method follows mostly the same algorithm as in the TestMinimumSpanningTree class */ public static String mst (CityRoadMap map) throws Exception { String result = ""; // Message to return // Build Minimum Spanning Tree // code goes here // Output the total weight and the tree // Round weight to 2 places // code goes here return result; } /** * Shortest Path: * This method follows mostly the same algorithm as in the TestShortestPath class * Only code the "AllPaths" piece * The HashMap is used to retrieve the City index from the passed in City name * The WeightedGraph (CityRoadMap) methods cannot retrieve the City vertex * object from the city name. */ public static String shortestPath (CityRoadMap map, HashMap indexMap, String fromCityName) throws Exception { String result = ""; // Message to return // Call the getShortestPath method of the WeightedGraph class // passing in the index of the fromCity in the vertices array // code goes here // Output all the paths from the fromCity // code goes here return result; } /** * Sort the cities by population and display them */ public static String sortCities (List sortCities) { String result = ""; // Message to return // Use the Collections.sort() method to do the sort // code goes here // Loop to output each City object information // code goes here return result; } }