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

Question

Так что у меня есть это задание, где я читаю в 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-й метод, который делает другой fileread... позволяет мне создать матрицу смежности

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 на 2 города, чтобы определить, подключен ли он

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

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

Answer 1

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

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) уважать, 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();

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

Answer 2

Это двунаправленный или однонаправленный граф?

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

Установите getReachableNodes(String startNode, Карта достижимости);

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

Answer 3

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

Поэтому я предлагаю изменить дизайн, где вы полагаетесь на 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)