Comments 10
Советую посмотреть https://github.com/yourbasic/graph, там есть интересные идеи.
Да, делить, конечно, так можно. Но без потери общности можно предположить, что существуют только направленные взвешенные графы. Остальные категории — их частные случаи.
Что касается списков смежности, то для взвешенных графов это не самая оптимальная структура. Матрица смежности — более универсальна и удобна. Хотя в случае разреженных графов (а так же в некоторых задачах на плотных графах) значительно проигрывает спискам как по памяти, так и по быстродействию.
Т.е., IMHO, в случае невзвешенных разреженных графов оптимальной структурой хранения будут списки смежности. Во всех остальных (почти всегда) — матрицы смежности.
Честно говоря, так и не понял что такое "Имя вершины" и зачем его с чем-то сравнивать.
Также в репозитории рекомендую пример использования перенести из исполняемого пакета в `README.md`.
Это полезное дело, но я бы добавил как минимум реализации базовых алгоритмов поиска кратчайших путей (дейкстру, А* и более сложные) и максимальных потоков, если библиотека претендует на универсальную полезность.
Ну и код, на мой взгляд, следует делать более "общим". В частности, функции поиска должны принимать не конкретные значения для сравнения, а другие функции, которые внутри себя сами способны определить искомые вершины. Ну и сами вершины тоже можно сделать более универсальными, храня внутри них только указатели на любые структуры данных. Также более универсальными можно сделать связи. Дело в том, что связи могут хранить и другие атрибуты, кроме "веса".
Кроме того, я вижу, что вы используете флаги посещенности для вершин. Такой подход не масштабируется на более чем 1 поток. Существует альтернативный вариант - при обходах создавать в каждом потоке по независимому стеку посещенных вершин. У вашего способа тоже есть свои плюсы, поэтому идеальная библиотека, по-моему, должна отдавать выбор пользователю. При инициализации графа он должен иметь возможность выбрать то, как будет храниться информация о посещенных вершинах.
И последнее, я рекомендую уделить больше внимания тестам вашего кода.
Это полезное дело, но я бы добавил как минимум реализации базовых алгоритмов поиска кратчайших путей (дейкстру, А* и более сложные) и максимальных потоков, если библиотека претендует на универсальную полезность.
Это первая статья цикла, библиотека еще дополняется и будет дополняться различными алгоритмами, они будут рассмотрены в следующих частях. Что касается кода - я согласен, что пока что не учли многих аспектов и возможный путей применения и использования, будем думать, спасибо за фидбэк!
Увидел несколько комментариев с ссылками на графовые библиотеки, исправил в статье соответствующее предложение, видимо, недостаточно хорошо провёл ресерч.
Библиотека алгоритмов на графах на языке Go. Часть 1