Разбор входного файла для создания ориентированного графа Переполнение стека
Поэтому я начинаю проект по ориентированным графам и топологической сортировке. Я ищу наиболее эффективный способ разбора входного файла курсов в виде:
COURSE_1 COURSE_2
где COURSE_1 является предпосылкой для COURSE_2
NONE COURSE_3
где COURSE_3 не имеет предпосылок.
Очевидно, что все метки вершин будут строками. Я создал Graph класс с членами данных для хранения вершин, ребер и меток вершин. Позже я буду добавлять методы для топологической сортировки и нахождения кратчайшего пути от одной вершины к другой. Учитывая эти планы на будущее, мои вопросы здесь были бы лучше использовать список смежности? или матрица? Кроме того, что было бы наиболее эффективным способом заполнить график из входных файлов? Моей первоначальной мыслью было использование списка смежности. Так как размер графика не известен во время компиляции, моя идея
std::vector<std::list<std::string>> adjacencyList;
Также я подумал о создании вспомогательной функции для разбора входного файла. Нечто подобное
void populateGraph(std::string filename, Graph* graph)
Я полностью иду в неправильном направлении здесь?
Решение
Вы на правильном пути со многими вещами.
Если вы можете предположить, что все входы, с которыми вы столкнетесь, просто NONE а также COURSE_X и вы можете предположить, что все X образуют непрерывный интервал целых чисел, начиная с 1 (или 0), и охватывают количество вершин, тогда вы можете просто рассматривать вершины как числа внутри. Если это не так, вы можете назначить каждой метке вершины номер (например, используя std :: unordered_map) и в любом случае иметь эту абстрактную структуру.
Теперь, если вы решите придерживаться этой модели, ее удобно использовать, потому что весь ваш график может быть представлен как std::vector<std::list<int>>, Вы могли бы заменить int с некоторым типом структуры, если вы хотите хранить больше информации о ребре, например, метки, веса и т. д. Всякий раз, когда вы хотите получить доступ к списку смежности определенного узла, вы просто получаете доступ к ячейке вектора под идентификатором узла.
Очевидно, что это решение на основе списка смежности. Это хорошо для разреженных графов вообще. Подумайте об этом так: если вы используете матрицу для разреженного графа, очень большая часть этой выделенной памяти не будет использоваться. Использование графа смежности устраняет это, но отнимает постоянное время доступа к любому произвольному ребру. Это означает, что может потребоваться линейное время, чтобы проверить, существует ли данное ребро. При этом я бы не ожидал, что вы будете использовать эту проверку в топологическом порядке. Однако, если вы решили использовать матрицу, вам все равно нужно сопоставить вершины с числами, чтобы эта часть осталась.
И последнее, но не менее важное: вы можете использовать указатели вместо целочисленных идентификаторов. По сути, вы бы не искали вершины в векторе, используя идентификатор, но вы бы напрямую обращались к вершине через сохраненный указатель. Скорее всего, вам все еще нужно иметь отображение строки -> указателя, по крайней мере, для создания графика.
Другие решения
Относительно выбора между списком смежности и матрицей, это зависит от характера вашего графа и того, что вы собираетесь с ним делать.
Видеть это нить например.
Кроме того, вы смотрели на то, что увеличение библиотека предлагает для графиков?
Существует также лимон как альтернатива.
Может быть стоит проверить, существует ли то, что вы собираетесь реализовать.