|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.06.2023, 01:08 | #1 |
Новичок
Джуниор
Регистрация: 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; } //////////////////////////////////////////////////////////////////// Плюс я заметил, что если в этом самом цикле менять местами находящиеся в комментариях выражения, то сам вывод автотестера не обновляется. Буду очень рад любой помощи и любым подсказкам |
28.06.2023, 09:29 | #2 |
Пользователь
Регистрация: 04.07.2012
Сообщений: 32
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Ошибка при чтении из файла | 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 |