Help with traversing through node/ input file read

Question

So I have this assignment where I read in 1 line at a time separated by comma e.g.

Atlanta, Philadelphia   
New York, Philadelphia   
Philadelphia, Chicago   
Washington, Florida
.....
up to a vast amount.. (I don't know the amount)

Each line represents connectivity between the two locations (e.g. Atlanta connects to Philadelphia) creating connected nodes and nodes which are not connected like Washington and Florida is connected to each other but no one else.

What the program is suppose to do is read the file and given two city arguments its suppose to spit out Yes if its connected/ No if its not.

I finished my program and It works, however its not efficient. I'm stumped as to what I can do. Here is part of the program which makes the code inefficient.

This first input reads the file so I can determine the size of the list of different city, and it also removes any duplicate cities.

private static void createCityList() throws IOException{

        try {
            FileReader a = new FileReader(file);
            BufferedReader br = new BufferedReader(a);
            String line;
            line = br.readLine();

            while(line != null){
                StringTokenizer st = new StringTokenizer(line, ",");
                while(st.hasMoreTokens()){ 
                    String currentToken = st.nextToken();
                    if(!cityList.contains(currentToken.trim())){ 
                        cityList.add(currentToken.trim());
                    }//if
                }//while hasMoreTokens
                line = br.readLine();//read the next line
            }//while line != null
            br.close();
        }//try

        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        length = cityList.size(); // set length to amount of unique cities

    }//createCityList

the 2nd method which does another fileread... allows me to create an adjacency matrix

private static void graph() throws IOException{ 
    cityGraph = new int[cityList.size()][cityList.size()]; 

        try {
            FileReader a = new FileReader(file);
            BufferedReader br = new BufferedReader(a);
            String line;
            line = br.readLine();


            while(line != null){
                StringTokenizer st = new StringTokenizer(line, ",");
                while(st.hasMoreTokens()){ 
                    String firstToken = st.nextToken().trim();
                    String secondToken = st.nextToken().trim();
                    cityGraph[cityList.indexOf(firstToken)][cityList.indexOf(secondToken)] = 1; 
                    cityGraph[cityList.indexOf(secondToken)][cityList.indexOf(firstToken)] = 1; 
                }//while hasMoreTokens

                line = br.readLine();//read the next line

            }//while line != null

            br.close();

        }//try

        catch (FileNotFoundException e) {
            e.printStackTrace();
        }//catch
    }//graph

And my final method runs a DFS on the 2 cities to determine if its connected

private static void isConnected(String s1, String s2){

        city1 = cityList.indexOf(s1); //set city to the index of s1 or s2 in the cityList LinkedList.
        city2 = cityList.indexOf(s2); 


        int startNode = city1;
        q.add(startNode); // start node

        while(!q.isEmpty()){
        //visit vertex
            for(int i = 0; i < length; i++){
                if(cityGraph[startNode][i] == 1){
                    if( i == city2 ){ 
                        System.out.println("yes");
                        return;
                    }//if city2 found
                    q.add(i);
                    cityGraph[startNode][i] = 0; //Set to visited
                }//if vertex exist
            }//for
            q.remove();//remove the top element and start with new node
            if(!q.isEmpty()){
                startNode = (Integer) q.element();
            }//if

        }//while q is not empty     
        System.out.println("no");
    }//isConnected

I'm trying to only have one file read, but I'm having issues making a matrix from an unknown size its only after the file read that I find out the size. Any help or suggestion would be greatly appreciated!

Answer 1

I have a few comments on the code:

1) Take those lines in the first code snippet:

while(st.hasMoreTokens()){ 
    String currentToken = st.nextToken();
    if(!cityList.contains(currentToken.trim())){ 
        cityList.add(currentToken.trim());
    }//if
}//while hasMoreTokens

The cityList.contains() method consumes linear time on the number of cities, and the while(st.hasMoreTokens()) might run O(V^2) times where V is the number of vertices, since you can have a dense graph. So, just in this one loop, you are consuming O(V^3) time, which is already worst than a DFS (O(V + E) which is O(V^2) in a dense graph). You can't speed up the O(V^2) loop because you have to read all the edges, but you can use a more efficient data structure to hold that city list, namely a hash (O(1) lookup, O(1) insertion).

2) On the second code snippet:

while(st.hasMoreTokens()){ 
    String firstToken = st.nextToken().trim();
    String secondToken = st.nextToken().trim();
    cityGraph[cityList.indexOf(firstToken)][cityList.indexOf(secondToken)] = 1; 
    cityGraph[cityList.indexOf(secondToken)][cityList.indexOf(firstToken)] = 1; 
}//while hasMoreTokens

Exactly the same thing. Use a hash instead of a list.

3) Inner loop of your DFS

if(cityGraph[startNode][i] == 1){
    if( i == city2 ){ 
        System.out.println("yes");
        return;
    }//if city2 found
    q.add(i);
    cityGraph[startNode][i] = 0; //Set to visited
}//if vertex exist

There are two problems. One is that you are overwriting your graph representation every time you run a DFS. By setting cityGraph[startNode][i] = 0; you are actually deleting an edge of your graph. If you are reconstructing the graph for every DFS, that is a huge problem.

Second problem is that it seems to me you are marking visited nodes in the wrong way. You are just marking visited EDGES, not nodes. If you have the path 1 -> 2 and the path 1 -> 4 -> 2, you are going to visit (and add to queue) node 2 two times.

To solve both problems, use a boolean visited[#cities] array. Everytime you start the DFS, you set all nodes to not visited. Everytime you check an edge, you check if you have already visited that node. If not, add it to the queue.

On a final note,

q.remove();//remove the top element and start with new node
if(!q.isEmpty()){
    startNode = (Integer) q.element();
}//if

This is ugly since you are already checking if the queue is empty on the while loop. Instead, you can just move this code to the beggining of the while loop, removing the if condition (because you know the queue is not empty):

while(!q.isEmpty()){
    startNode = (Integer) q.element();
    q.remove();

Hope that helps....

Answer 2

Is this a bidirectional or unidirectional graph?

Either way, you might do well to use a Map to represent edges from one city to another. Given that, you can write a method

Set getReachableNodes(String startingNode, Map reachability);

and see whether the desired target is in the resulting set.

Answer 3

I think the key to good software is choosing the optimal data structure. I think that is more important than the procedures (though those are important, of course). I don't believe 2-dimensional array for a huge graph and lists for a huge number of cities are the optimal data structures; for both types of data structure you're forced to do linear search. Meaning that the speed will get worse as those data structures grow in size.

So I propose a re-design where you rely on HashMap<String> and HashSet<String>. The main value of a HashMap is the constant look-up time, meaning the performance will not get worse (read more on Wikipedia if you're interested in how it works).

So, as some answers above suggested, the outline in pseudocode would be:

HashMap<String, HashSet<String>> m = new ...
For each pair c1 c2 {
     if c1 is not a key in m {
          HashSet<String> set = new HashSet<String>
          set.add(c2)
          m.put(c1, set);

     }
     else //c is a key
          m.get(c1).add(c2)
 }

Now for looking up if c1 and c2 are connected:

boolean isDirectlyConnected(c1, c2) { 
  return m.get(c1).contains(c2) || m.get(c2).contains(c1) 
}         

boolean isConnected (c1, c2) {    //checking the transitive closure of directly connected
   HashSet<String> citiesAlreadyChecked = new ...   //cities whose edges have already been checked
   Queue<String>  citiesToCheck = new ...
   citiesToCheck.push(c1)
   while (citiesToCheck is not empty) {
         String cityBeingCurrentlyChecked = citiesToCheck.pull
         if (isDirectlyConnected(cityBeingCurrentlyChecked,c2)) {
               return true;
         } 
         else {
               citiesAlreadyChecked.add(cityBeingCurrentlyChecked)
               for (String adjacentCity: m.get(cityBeingCurrentlyChecked)) {
                    if (adjacentCity is not in citiesAlreadyChecked) {
                           citiesToCheck.push(adjacentCity)
                    }
               }
          }
    }
    return false  
   //transitive colsure of cities connected to c1 have been checked, and c2 was not found there.

} 

One could also make the graph doubly linked, and thus get rid of the || in isDirectlyConnected. Making doubly linked is done while constructing by calling

m.put(c1, set with c2 added) AND m.put(c2, set with c1 added)