Помогите с обходом чтения узла / входного файла - PullRequest
Новая
       16

Помогите с обходом чтения узла / входного файла

2 голосов
/ 17 февраля 2011

Итак, у меня есть это назначение, где я читаю по 1 строке за раз, разделенные запятой, например: 

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

Каждая строка представляет связь между двумя точками (например, Атланта соединяется с Филадельфией), создавая соединенные узлы и узлыкоторые не связаны, как Вашингтон, и Флорида связана друг с другом, но больше ни с кем.

Что программа должна сделать, это прочитать файл и получить два городских аргумента, которые она должна выплюнуть Да, если она подключена /Нет, если это не так.

Я закончил свою программу, и она работает, однако она неэффективна.Я озадачен тем, что я могу сделать.Вот часть программы, которая делает код неэффективным.

Этот первый ввод считывает файл, чтобы я мог определить размер списка разных городов, а также удаляет все дубликаты городов. 

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

2-й метод, который выполняет еще одно чтение файла ... позволяет мне создать матрицу смежности 

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

И мой последний метод запускает DFS в двух городах, чтобы определить, подключен ли он 

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

Я пытаюсь прочитать только один файл, но у меня возникают проблемы с созданием матрицы с неизвестным размером только после чтения файла, когда я узнаю размер.Любая помощь или предложение будет принята с благодарностью!

Ответы [ 3 ]

2 голосов
/ 17 февраля 2011

У меня есть несколько комментариев к коду:

1) Взять те строки в первом фрагменте кода: 

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

Метод cityList.contains() использует линейное время для числа городов, и while(st.hasMoreTokens()) может выполняться O(V^2) раз, где V - число вершин, поскольку вы можете иметь плотный граф. Итак, только в этом одном цикле вы потребляете O (V ^ 3) времени, которое уже хуже, чем DFS (O(V + E), что составляет O(V^2) в плотном графе). Вы не можете ускорить цикл O (V ^ 2), потому что вам нужно прочитать все границы, но вы можете использовать более эффективную структуру данных для хранения этого списка городов, а именно хеш (O(1) lookup, O(1) вставки).

2) Во втором фрагменте кода: 

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

Точно так же. Используйте хеш вместо списка.

3) Внутренняя петля вашего 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

Есть две проблемы. Во-первых, вы перезаписываете представление графа каждый раз, когда запускаете DFS. Установив cityGraph[startNode][i] = 0;, вы фактически удаляете край вашего графика. Если вы восстанавливаете график для каждой DFS, это огромная проблема.

Вторая проблема заключается в том, что мне кажется, что вы отмечаете посещенные узлы неправильно. Вы просто отмечаете посещенные EDGES, а не узлы. Если у вас есть путь 1 -> 2 и путь 1 -> 4 -> 2, вы собираетесь посетить (и добавить в очередь) узел 2 два раза.

Чтобы решить обе проблемы, используйте массив boolean visited[#cities]. Каждый раз, когда вы запускаете DFS, вы устанавливаете все узлы как не посещенные. Каждый раз, когда вы проверяете ребро, вы проверяете, уже посещали ли вы этот узел. Если нет, добавьте его в очередь.

На последней ноте 

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

Это ужасно, так как вы уже проверяете, пуста ли очередь в цикле while. Вместо этого вы можете просто переместить этот код в начало цикла while, удалив условие if (поскольку вы знаете, что очередь не пуста): 

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

Надеюсь, это поможет ....

1 голос
/ 17 февраля 2011

Я думаю, что ключом к хорошему программному обеспечению является выбор оптимальной структуры данных. Я думаю, что это важнее, чем процедуры (хотя они, конечно, важны). Я не верю, что двумерный массив для огромного графа и списки для огромного числа городов являются оптимальными структурами данных; для обоих типов структуры данных вы вынуждены выполнять линейный поиск. Это означает, что скорость будет ухудшаться по мере увеличения размера этих структур данных.

Поэтому я предлагаю изменить дизайн, в котором вы полагаетесь на HashMap<String> и HashSet<String>. Основным значением HashMap является постоянное время поиска, то есть производительность не ухудшится (читайте больше в Википедии, если вам интересно, как она работает).

Итак, как предложили некоторые ответы выше, набросок в псевдокоде будет выглядеть так: 

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)
 }

Теперь для поиска, если c1 и c2 связаны: 

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.

}

Можно также сделать график двусвязным и, таким образом, избавиться от || в isDirectlyConnected. Создание двусвязного выполняется при построении вызова

m.put (c1, установлен с добавленным c2) И m.put (c2, устанавливается с добавленным c1)

1 голос
/ 17 февраля 2011

Является ли это двунаправленным или однонаправленным графом?

В любом случае, вам может быть полезно использовать карту для представления краев от одного города к другому.Учитывая это, вы можете написать метод

Set getReachableNodes (String startNode, Map достижимость);

и посмотреть, есть ли нужная цель в результирующем наборе.

...