Модель данных, библиотека графов, C ++

Question

Я создаю библиотеку C ++ для реализации алгоритмов графов. Я думаю о соответствующем представлении класса «График».

Два основных типа графиков (ориентированных / не ориентированных) и представлений (список / матрица).

У меня нет проблем с алгоритмами ... Но я хотел бы предложить подходящую и надежную структуру данных (включая последовательность наследования классов при необходимости).

В настоящее время я не использую никакую специальную структуру данных, представляющую граф, статические методы имеют в качестве входных параметров встречаемость, смежность ... матрицы.

Должен ли такой класс хранить оба представления графа или только одно представление с функцией преобразования между обоими представлениями? Что может быть предпочтительнее?

Эта проблема была решена многими людьми, использующими разные подходы.

Answer 1

Прежде чем изобретать велосипед, вы можете взглянуть на boost :: graph .Не забудьте в комплекте свойства .

Answer 2

Вы делаете это для класса или в качестве учебного упражнения?Потому что, если нет, как вы указали, эта проблема решалась много раз.И когда вы просматриваете различные решения, вы понимаете, что есть проблемы, которых у вас даже нет, такие как:

• ориентированные / ненаправленные графы
• связывание пользовательских данных с узлами и ребрами
• разреженные и плотные графы
• большие и маленькие графы
• шаблон против не-шаблонной
• зависимость от других пакетов

и так далее ...

Попробуйте взглянуть на некоторые из самых популярных реализаций:

https://stackoverflow.com/questions/2751826/which-c-graph-library-should-i-use