Метод не работает для большого набора данных
Я пытаюсь найти самый центральный символ в наборе данных, который содержит каждый символ Marvel и каждую книгу, в которой он находился. Код, который я написал ниже, работает для небольшого тестового файла, который мы создали сами, чтобы быстрее протестировать метод, но когда я запускаю код в файле Marvel, код разрывается с самого начала. Я поместил операторы печати во весь код, чтобы найти, где он перестал работать, и я подумал, что это будет чем-то, что связано с итерацией стольких символов, но с самого начала это не работает. В самом первом цикле while() я добавляю startVertex в группу и пишу оператор System.out.println(group) сразу после добавления startVertex, а когда я запускаю тест, оператор print выдает "[]" (который я Я уверен, что это означает, что группа ничего не получает от startVertex), а затем застревает в бесконечном цикле (но для небольшого списка символов / книг код работает отлично)... Любые предложения о том, как получить это работать для большего файла?
РЕДАКТИРОВАТЬ: Вот ссылки на файлы. Большой файл должен быть в необработанном виде, потому что github не может его открыть. Они оба отформатированы одинаково, и оба файла правильно анализируются из файла TSV в мультиграф.
Небольшой файл: https://github.com/EECE-210/2013-L1A1/blob/master/mp5/testTSVfile.tsv
/**
* First find the largest connected set of characters and then
* find the most central character of all characters in this set.
*
* @param none
* @return the name of the character most central to the graph
*/
public String findMostCentral() {
Set<String> vertexSet = new LinkedHashSet<String>();
vertexSet = vertexMap.keySet();
Iterator<String> iterator = vertexSet.iterator();
List<String> group = new ArrayList<String>();
List<String> largestGroup = new ArrayList<String>();
List<String> Path = new ArrayList<String>();
Map<String, Integer> longestPathMap = new HashMap<String, Integer>();
/*
* This first while loop sets the starting vertex (ie the character that will be checked
* with every other character to identify if there is/isn't a path between them.
* We add the character to a group list to later identify the largest group of
* connected characters.
*/
while(iterator.hasNext()){
String startVertex = iterator.next();
group.add(startVertex);
/*
* This second while loop sets the destination/end vertex (ie the character that is the
* destination when compared to the starting character) to see if there is a path between
* the two characters. If there is, we add the end vertex to the group with the starting
* vertex.
*/
for(String key : vertexSet){
String endVertex = key;
if( findShortestPath(startVertex, endVertex) != null )
group.add(endVertex);
}
/*
* If the group of connected characters is larger than the largest group, the largest
* group is cleared and replaced with the new largest group.
* After the group is copied to largest group, clear group.
*/
if(group.size() > largestGroup.size()){
largestGroup.clear();
for(int i = 0; i < group.size(); i++){
largestGroup.add(group.get(i));
}
}
group.clear();
}
/*
* Iterate through the largest group to find the longest path each character has
* to any other character.
*/
for(String LG : largestGroup){
String startingVertex = LG;
int longestPath = 0;
for(String LG2 : largestGroup){
String endingVertex = LG2;
Path = findShortestPath(startingVertex, endingVertex);
/*
* If the path size from startingVertex to endingVertex is longer than any other
* path that startingVertex is connected to, set it as the longest path for that
* startingVertex.
*/
if(Path.size() > longestPath){
longestPath = Path.size();
}
}
//save the starting vertex and it's longest path to a map
longestPathMap.put(startingVertex, longestPath);
}
/*
* Iterates through the longestPathMap and finds the shortest longest path and assigns
* the character with the shortest longest path to mostCentralCharacter.
*/
int shortestLongestPath = Integer.MAX_VALUE;
String mostCentralCharacter = new String();
for(Map.Entry<String, Integer> entry : longestPathMap.entrySet()){
if((Integer) entry.getValue() < shortestLongestPath){
shortestLongestPath = (Integer) entry.getValue();
mostCentralCharacter = (String) entry.getKey();
}
}
return mostCentralCharacter;
}
1 ответ
Спасибо за быстрые ответы! Я обнаружил проблему при печати vertexSet перед началом любых циклов for-in. Первая строка vertexSet была "" (то есть ничего), поэтому она будет хранить первую строку "" в startVertex, затем получит endVertex и затем застрянет в бесконечном цикле, пытаясь найти ShortestPath между ничем и символом.... Спасибо за твоя помощь!