ShouldBeAble ShouldBeAble - 29 days ago 8
Java Question

Reading an adjacency list from a file into a multimap

So I have this adjacency list: Columbus node to Chicago node is .5 distance etc.

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


And I have the below method that reads in the above list from a txt file. This adds the list into a multi map adj_list but it is missing this part:

"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"

public static Map<String, List<Path>> readPathsFromFile(Scanner inFile) {
Map<String, List<Path>> adj_list = new TreeMap<String, List<Path>>();
ArrayList<Path> list1 = new ArrayList<Path>();

while (inFile.hasNext()){ // TO- DO add parts for both ways.
String input = inFile.nextLine();
String[] token = input.split(",");

if(!adj_list.containsKey(token[0])){
list1 = new ArrayList<Path>();
Path path2 = new Path(token[1],Double.parseDouble(token[2]));
list1.add(path2);
adj_list.put(token[0], list1);

}else{
Path path = new Path(token[1],Double.parseDouble(token[2]));
list1.add(path);
}

}

return adj_list;
}


So, my question is first is the above method a good way to go about it to start with and if it is how can I modify this method to make it add nodes to my list in both directions instead of just the order of the list?

Edit: To be clearer on what I want.

For example eventually I would have:
SanFrancisco: (LasVegas:1.0), (Seattle:2.0), (Denver:2.0)

I have that part but what it needs to be is:

SanFrancisco: (LosAngeles:1.0), (LasVegas:1.0), (Seattle:2.0), (Denver:2.0)

i.e. LosAngeles has a connecting node to San Francisco but it is not explicitly listed for San Francisco in the adj list.
Thank you!

Answer

You need to be careful with your ArrayList<Path> list1. If you input

Columbus,Chicago,0.5
Chicago,NewYork,1.5
Columbus,Miami,2.0

you would get a map of

Columbus (Chicago,0.5)
Chicago (NewYork,1.5),(Miami,2.0)

because when reading the 3rd line, the list1 array is the Chicago array (as created during the 2nd line). Your token[0] is known (yes, there is already a Columbus entry in the map because of line 1), so you jump straight to adding the (Miame,2.0) distance to the list1 -- the Chicago list.

The following code solves both the above problem and the problem you stated by getting rid of the list outside the while loop and instead fetching the correct list from the map every single time.

public static Map<String, List<Path>> readPathsFromFile(Scanner inFile) {
  Map<String, List<Path>> adj_list =  new TreeMap<String, List<Path>>();

  // You do not need a list here
  // ArrayList<Path> list1 = new ArrayList<Path>();

  while (inFile.hasNext()){ // TO- DO add parts for both ways.
    String input = inFile.nextLine();
    String[] token = input.split(",");

    // 1.) Take care of 0 -> 1
    // Try and fetch the list from your treemap saved under 0
    List<Path> token0List = adj_list.get(token[0]);

    // If there was no list previously saved, you have a null value now
    if(token0List == null){

        // since there was no list previously saved,
        // create a new (empty) one and save it in the tree
        token0List = new ArrayList<Path>();
        adj_list.put(token[0], token0List );

    }

    // At this point of time, you can be sure that the token0List
    // exists and is saved correctly in the tree.

    // now you only need to add the 0 -> 1 path to the list
    // and you are done with this part of the saving.
     Path path = new Path(token[1],Double.parseDouble(token[2]));    
    token0List .add(path); // finish 0 -> 1


    // 2.) Take care of 1 -> 0
    // same procedure as 0 -> 1, only that you are swapping 
    // token[0] and token[1]
    List<Path> token1List = adj_list.get(token[1]);
    if(token1List == null){
        token1List = new ArrayList<Path>();
        adj_list.put(token[1], token1List );

    }
     Path path2 = new Path(token[0],Double.parseDouble(token[2]));    
    token1List .add(path2); // finish 1 -> 0



  }

  return adj_list;
}