For your first coding step, in your Project05.java file write a static method na

Question

For your first coding step, in your Project05.java file write a static method named readPathsFromFile with the following method signature:

public static Map< String, List<Path> > readPaths(String fname)

This method should take a filename as an argument. It should create a new multimap, and then it should read paths from the file and store them in the multimap to make an adjacency list. Each line of the file will use the following format:

node1,node2,distance

For example, the graph above in the Overview section could be written in the file this way:

Columbus,Chicago,0.5
Columbus,Miami,2.0
Chicago,NewYork,1.5
Chicago,Boston,2.0
Chicago,StLouis,0.5
Chicago,Denver,2.5
Chicago,Seattle,3.0
Boston,NewYork,0.5
StLouis,Atlanta,1
StLouis,Dallas,1.0
Atlanta,Dallas,1.0
Atlanta,Miami,1.0
Dallas,Miami,2.0
Dallas,LosAngeles,2.5
LosAngeles,SanFrancisco,1.0
LosAngeles,LasVegas,0.5
SanFrancisco,LasVegas,1.0
SanFrancisco,Seattle,2.0
SanFrancisco,Denver,2.0
Denver,LasVegas,1.0
Denver,Seattle,2.0

You can read in a line at a time and use the String split method to get out individual values from a line. For example, the following code will break up a comma separated line named input into an array of Strings (you will need to use the Double.parseDouble() method to turn the last element of the array into a Double value yourself):

String[] tokens = input.split(",");

Note that each path between nodes is listed only once, but each path needs to be added twice to the adjacency list. For example, the file lists a path between Columbus and Chicago on the first line. This needs to be added to the adjacency list for Columbus as a path with a destination of Chicago AND it needs to be added to the adjacency list for Chicago with a destination of Columbus (the same adjacency list structure can be used to show one-way paths, but all of the paths for this assignment work in both directions). Your code must be written to add both paths.

Your code should also have a static method named displayPaths that has the following method signature:

public static void displayAdjacencyList(Map< String,List<Path> > map)

This method should display the entire adjacency list stored in the multimap named map that is passed in as a parameter. The output for this method should be similar to how the adjacency list is displayed above. For example, for the file give above, the following would be displayed:

Miami: (Columbus:2.0), (Atlanta:1.0), (Dallas:2.0)
SanFrancisco: (LosAngeles:1.0), (LasVegas:1.0), (Seattle:2.0), (Denver:2.0)
Atlanta: (StLouis:1.0), (Dallas:1.0), (Miami:1.0)
Chicago: (Columbus:0.5), (NewYork:1.5), (Boston:2.0), (StLouis:0.5), (Denver:2.5), (Seattle:3.0)
Boston: (Chicago:2.0), (NewYork:0.5)
StLouis: (Chicago:0.5), (Atlanta:1.0), (Dallas:1.0)
NewYork: (Chicago:1.5), (Boston:0.5)
LasVegas: (LosAngeles:0.5), (SanFrancisco:1.0), (Denver:1.0)
Seattle: (Chicago:3.0), (SanFrancisco:2.0), (Denver:2.0)
Columbus: (Chicago:0.5), (Miami:2.0)
Denver: (Chicago:2.5), (SanFrancisco:2.0), (LasVegas:1.0), (Seattle:2.0)
Dallas: (StLouis:1.0), (Atlanta:1.0), (Miami:2.0), (LosAngeles:2.5)
LosAngeles: (Dallas:2.5), (SanFrancisco:1.0), (LasVegas:0.5)

(Note that the ordering here is different than in the Overview section above. This output uses a HashMap as its underlying map - try calling the method with both a HashMap and a TreeMap to see the difference in output.)

Explanation / Answer

Hello there ,

Please find below Project05.java code and its input Pathfile.txt and o/p using both the map (hashmap and treemap).

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
* This Project05 class is reading path file and dispalying its target with all
* destination with their distance.
*
* @author dipal.prajapati
*
*/
public class Project05 {

   public static void main(String args[]) {
       System.out.println("Testing Project05: ");

       System.out.println(" Using HashMap: ");
       displayAdjacencyList(readPaths("PathFile.txt"));

       System.out.println(" Using TreeMap: ");

       TreeMap<String, List<Path>> treeMap = new TreeMap<String, List<Path>>(
               readPaths("PathFile.txt"));
       displayAdjacencyList(treeMap);
   }

   /**
   * It reads the given file and genrate map of target with its all
   * destination and distance.
   *
   * @param fname
   * @return
   */
   public static Map<String, List<Path>> readPaths(String fname) {
       Map<String, List<Path>> mapOfPath = new HashMap<String, List<Path>>();
       BufferedReader br = null;

       try {

           String sCurrentLine;

           br = new BufferedReader(new FileReader(fname));

           while ((sCurrentLine = br.readLine()) != null) {
               String[] array = sCurrentLine.split(",");
               // Adding first node as a key
               if (mapOfPath.containsKey(array[0])) {
                   List<Path> list = mapOfPath.get(array[0]);
                   list.add(new Path(array[0], array[1], Double
                           .parseDouble(array[2])));
                   mapOfPath.put(array[0], list);
               }
               // Add new entry
               else {
                   List<Path> list = new ArrayList<Path>();
                   list.add(new Path(array[0], array[1], Double
                           .parseDouble(array[2])));
                   mapOfPath.put(array[0], (list));
               }
               // Adding second node as a key
               if (mapOfPath.containsKey(array[1])) {
                   List<Path> list = mapOfPath.get(array[1]);
                   list.add(new Path(array[1], array[0], Double
                           .parseDouble(array[2])));
                   mapOfPath.put(array[1], list);
               }
               // Add new entry
               else {
                   List<Path> list = new ArrayList<Path>();
                   list.add(new Path(array[1], array[0], Double
                           .parseDouble(array[2])));
                   mapOfPath.put(array[1], (list));
               }
           }

       } catch (IOException e) {
           e.printStackTrace();
       } finally {
           try {
               if (br != null)
                   br.close();
           } catch (IOException ex) {
               ex.printStackTrace();
           }
       }

       return mapOfPath;
   }

   /**
   * It display the given multimap in desired way.
   *
   * @param map
   */
   public static void displayAdjacencyList(Map<String, List<Path>> map) {
       for (Map.Entry<String, List<Path>> entry : map.entrySet()) {
           System.out.println(entry.getKey() + ":"
                   + printList(entry.getValue()));
       }
   }

   /**
   * Utility method to display the list for particular target in desired
   * format.
   *
   * @param listOfPath
   * @return
   */
   public static String printList(List<Path> listOfPath) {
       StringBuffer buffer = new StringBuffer();
       for (int index = 0; index < listOfPath.size(); index++) {
           buffer.append("(" + listOfPath.get(index).destination + ":"
                   + listOfPath.get(index).distance + ")");
           if (index != (listOfPath.size() - 1)) {
               buffer.append(",");
           }
       }
       return buffer.toString();
   }

}

/**
* It represents the class containing target,destination and distance between them.
* @author dipal.prajapati
*
*/
class Path {
   String target;
   String destination;
   double distance;

   public Path(String target, String destination, double distance) {
       super();
       this.target = target;
       this.destination = destination;
       this.distance = distance;
   }

}

======I/P======= PathFile.txt

Columbus,Chicago,0.5
Columbus,Miami,2.0
Chicago,NewYork,1.5
Chicago,Boston,2.0
Chicago,StLouis,0.5
Chicago,Denver,2.5
Chicago,Seattle,3.0
Boston,NewYork,0.5
StLouis,Atlanta,1
StLouis,Dallas,1.0
Atlanta,Dallas,1.0
Atlanta,Miami,1.0
Dallas,Miami,2.0
Dallas,LosAngeles,2.5
LosAngeles,SanFrancisco,1.0
LosAngeles,LasVegas,0.5
SanFrancisco,LasVegas,1.0
SanFrancisco,Seattle,2.0
SanFrancisco,Denver,2.0
Denver,LasVegas,1.0
Denver,Seattle,2.0

======O/P=======

Testing Project05:

Using HashMap:

Miami:(Columbus:2.0),(Atlanta:1.0),(Dallas:2.0)
SanFrancisco:(LosAngeles:1.0),(LasVegas:1.0),(Seattle:2.0),(Denver:2.0)
Atlanta:(StLouis:1.0),(Dallas:1.0),(Miami:1.0)
Chicago:(Columbus:0.5),(NewYork:1.5),(Boston:2.0),(StLouis:0.5),(Denver:2.5),(Seattle:3.0)
Boston:(Chicago:2.0),(NewYork:0.5)
StLouis:(Chicago:0.5),(Atlanta:1.0),(Dallas:1.0)
NewYork:(Chicago:1.5),(Boston:0.5)
LasVegas:(LosAngeles:0.5),(SanFrancisco:1.0),(Denver:1.0)
Seattle:(Chicago:3.0),(SanFrancisco:2.0),(Denver:2.0)
Columbus:(Chicago:0.5),(Miami:2.0)
Denver:(Chicago:2.5),(SanFrancisco:2.0),(LasVegas:1.0),(Seattle:2.0)
Dallas:(StLouis:1.0),(Atlanta:1.0),(Miami:2.0),(LosAngeles:2.5)
LosAngeles:(Dallas:2.5),(SanFrancisco:1.0),(LasVegas:0.5)

Using TreeMap:

Atlanta:(StLouis:1.0),(Dallas:1.0),(Miami:1.0)
Boston:(Chicago:2.0),(NewYork:0.5)
Chicago:(Columbus:0.5),(NewYork:1.5),(Boston:2.0),(StLouis:0.5),(Denver:2.5),(Seattle:3.0)
Columbus:(Chicago:0.5),(Miami:2.0)
Dallas:(StLouis:1.0),(Atlanta:1.0),(Miami:2.0),(LosAngeles:2.5)
Denver:(Chicago:2.5),(SanFrancisco:2.0),(LasVegas:1.0),(Seattle:2.0)
LasVegas:(LosAngeles:0.5),(SanFrancisco:1.0),(Denver:1.0)
LosAngeles:(Dallas:2.5),(SanFrancisco:1.0),(LasVegas:0.5)
Miami:(Columbus:2.0),(Atlanta:1.0),(Dallas:2.0)
NewYork:(Chicago:1.5),(Boston:0.5)
SanFrancisco:(LosAngeles:1.0),(LasVegas:1.0),(Seattle:2.0),(Denver:2.0)
Seattle:(Chicago:3.0),(SanFrancisco:2.0),(Denver:2.0)
StLouis:(Chicago:0.5),(Atlanta:1.0),(Dallas:1.0)

Kindly let me know if you have any queries .

Thank you !

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.