Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.06.2023, 01:08   #1
vertusama
Новичок
Джуниор
 
Регистрация: 28.06.2023
Сообщений: 1
По умолчанию Класс AdjacentArrayGraph, баг в чтении данных с файла

Здравствуйте
Повилась следующая проблема, есть задание:

Реализуйте Java-Class AdjacencyArrayGraph, который представлял бы ориентированный граф без весов G = (V, E) с узлами V = {0,..., n - 1}.
Этот график имеет два атрибута:
1. int[] numSmallerOrigins — это массив с n + 1 элементами, в котором для каждого узла хранится количество ребер, имеющих исходную точку с меньшим индексом:
numSmallerOrigins[i] = | { (j, k) | (j, k) \ in E \ клин j < i } |
В частности: numSmallerOrigins[0] = 0 и numSmallerOrigins[n] = |E|
2. int[] destinations — это массив с с |E| элементами, где интервал destination[numSmallerOrigins[i], ..., numSmallerOrigins[i+1] - 1] содержит узлы, следующие за i, т. е. {j | (i, j) ∈ E}. Они могут появляться в любом порядке.

Класс должен предоставлять следующие общедоступные методы, для которых вы можете использовать обычные библиотеки Java для чтения файлов и построения строк:

1. статический AdjacencyArrayGraph readFile(String file) должен читать файл по указанному пути. В каждой строке сначала находится управляющий символ, указывающий, что представляют данные за ним, за которым следует одно или несколько значений. Если строка начинается с "#" или пуста, это означает, что эту строку можно игнорировать, поскольку она является комментарием. Если строка начинается с «d», необходимо построить ориентированный граф. Последующее значение указывает количество узлов в графе. Если строка начинается с «e», за ней следуют два целых числа, которые определяют (начиная с 0) начальный и конечный узлы. Вы можете предположить, что есть только одна строка, начинающаяся с d, и что она идет перед информацией о ребре. Если ваш код обнаруживает ошибку при чтении файла, он должен возвращать значение null. Соответствующий файл со связанным графом может выглядеть, например, так:
# Это определяет граф с 3 узлами.
д 3
# Это определяет ребра между графами.
е 0 1
е 0 2
# Допускаются пустые строки и
# следует пропустить.
е 1 2
е 2 1

2. Строковый вывод toString() представляет собой массив смежности графа, представленный в виде строки.

3. Результатом int numberOfNodes() являются узлы |V|.

4. Результатом int numberOfEdges() являются узлы |E|.

5. int numberOfSuccessors(int node) вывод - количество преемников, которые есть у этого узла.

6. int getSuccessor(int node, int k) вывод является k-te преемником узла, который рассчитывается следующим образом: destinations[numSmallerOrigins[node] + k]

7. вывод public boolean hasHamiltonCycle() истинен тогда и только тогда, когда данный граф содержит цикл Гамильтона. Поиск гамильтоновой цепи — одна из классических NP-полных задач Карпа. Так что вам, вероятно, не удастся реализовать какую-либо реализацию за полиномиальное время. Поэтому для полной оценки достаточно, если ваш алгоритм вычисляет результат для графа с 10 узлами за несколько секунд.

Для выполнения этого задания я написал код из прикреплённого файла.

И вот когда я запускаю автотестер, я получаю следующий отчёт:
Overall result............................. ..............................ERR
└─AdjacencyArrayGraphTest.......... ................................... ...ERR
├─core_getSuccessor................ ................................... .ERR
│ The number of successors does not match the the read file. ==> expected:<0> but was: <6>
├─core_hasHamiltonCycle............ ................................... ..OK
├─core_numberOfEdges............... ................................... ..OK
├─core_numberOfNodes............... ................................... ..OK
├─core_numberOfSuccessors.......... ................................... ..OK
├─core_readFile_constructs_graph_co rrectly............................ .ERR
│ The graph is missing an edge from the input ==> expected: <true> but was: <false>
├─core_toString.................... ................................... ..OK
├─edge_hasHamiltonCycle............ ................................... ..OK
├─edge_numberOfEdges............... ................................... ..OK
├─edge_numberOfNodes............... ................................... ..OK
├─edge_numberOfSuccessors.......... ................................... ..OK
└─edge_readFile_returns_null_for_fa ulty_files......................... ..OK

И что касается обоих ошибок:
Обе ошибки постоянно меняются - в первой ошибке меняются ожидаемые узлы и соответственно узлы которые выдаёт программа однако порой выводится
Missing successor in provided successors via getSuccessor
а во второй ошибке
The graph is missing an edge from the input ==> expected: <true> but was: <false>
меняется на
The graph contains an edge not in the input ==> expected: <false> but was: <true>

Я не могу понять, в чём именно заключается баг, из-за которого эти ошибки появляются.
Хотел бы попросить помощи - может кто-нибудь может подсказать, где стоит начать искать баги и где баг может лежать в принципе.
Я подозреваю, что он лежит в цикле в конце readFile:
////////////////////////////////////////////////////////////////////
//int edgeIndex = 0;
for (int[] edges : edgeList) {
int node1 = edges[0];
int node2 = edges[1];

//if(node1 <= node2){
graph.numSmallerOrigins[node2 + 1]++;
//graph.destinations[graph.numSmallerOrigins[node1]] = node2;}
graph.destinations[graph.numSmallerOrigins[node2]] = node1;
}
////////////////////////////////////////////////////////////////////
Плюс я заметил, что если в этом самом цикле менять местами находящиеся в комментариях выражения, то сам вывод автотестера не обновляется.
Буду очень рад любой помощи и любым подсказкам
Вложения
Тип файла: txt AdjacencyArrayGraph.txt (5.1 Кб, 3 просмотров)
vertusama вне форума Ответить с цитированием
Старый 28.06.2023, 09:29   #2
MansMI
Пользователь
 
Регистрация: 04.07.2012
Сообщений: 32
По умолчанию

Цитата:
Сообщение от vertusama Посмотреть сообщение
должен читать файл по указанному пути
файл то где?
MansMI вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Ошибка при чтении из файла Uefa Помощь студентам 7 09.01.2016 13:10
проблема при чтении данных из файла Eshansky Visual C++ 1 07.07.2013 21:08
Ошибка при чтении файла Стремящийся Общие вопросы по Java, Java SE, Kotlin 4 03.07.2012 16:50
Кодировка при чтении из файла _-Re@l-_ Общие вопросы .NET 2 21.11.2010 20:12
ошибка при чтении файла ongleb Общие вопросы C/C++ 17 30.07.2009 13:48