Почему структуры данных C ++ для графов скрывают смежные целочисленные индексы?
Структуры данных для ориентированных и неориентированных графов имеют фундаментальное значение. Хорошо известные и широко используемые реализации, такие как Boost Graph Library а также Лимон разработаны так, что смежные целочисленные индексы узлов и ребер не предоставляются пользователю через интерфейс.
Вместо этого пользователь идентифицирует узлы и ребра по (маленьким) представительным объектам. Одним из преимуществ является то, что эти объекты обновляются автоматически, когда индексы узлов и ребер изменяются из-за удаления ребер или узлов из графика.
На мой взгляд (!) Это преимущество переоценено. Пользователи обычно сохраняют репрезентативные объекты узлов и / или ребер в контейнере, например std::vector, Теперь, если узлы или ребра удалены из графа и их репрезентативные объекты становятся недействительными, пользователь должен либо проигнорировать это, либо переставить вектор так, чтобы действительные целочисленные индексы оставались смежными, т. Е. Вести именно ту бухгалтерию, которую должен был выполнить проект сделать ненужным.
Следовательно, мой вопрос: Есть ли у выбора дизайна (скрытия смежных целочисленных индексов узлов и ребер от пользователя) другие преимущества?
Решение
(Я нахожусь дома в мире Java, но надеюсь, что это нормально, чтобы дать ответ, который не сфокусирован на конкретных библиотеках, о которых идет речь)
Есть несколько возможных преимуществ такой абстракции. Один из самых важных уже упоминался в вопросе: консистенция при выполнении изменений в графике гораздо сложнее выполнить, когда индексы должны поддерживаться.
Причина Зачем это может быть трудно из-за различных возможных представлений графа: может быть легко поддерживать согласованные индексы, если только внутреннее представление (и всегда) состоит из списков произвольного доступа Vertex а также Edge объекты. Но для других представлений определение индекса может быть затруднено.
Это напрямую связано со вторым главным преимуществом: каждый может использовать разные реализации графического интерфейса. Раздел «Структуры графических данных» в Обзор теории элементарных графов из документации наддува перечислены несколько структур данных, которые уже предлагаются BGL (и каждый может добавить свою собственную реализацию). Время выполнения для определенных операций указано в нотации Big-O, и однажды видно, что они сильно различаются в разных структурах данных.
Таким образом, можно легко представить, что различные реализации лучше подходят для определенных задач. Например, рассмотрим алгоритм часто должен проверить, содержится ли конкретная вершина в графе. Для индексированных (то есть listна основе) хранения вершин, это потребует На) за каждый тест. С setна основе хранения вершин, это может быть сделано в O (1) — но в этом случае просто нет разумных «показателей».
Кроме того, как указано в Концепции Графа Обзор:
Фактически, интерфейс BGL даже не нужно реализовывать с использованием структуры данных, поскольку для некоторых задач проще или эффективнее определить граф, неявно основанный на некоторых функциях.
Так предлагая то, что существует «индексированный доступ», даже если граф даже не существует в памяти, может препятствовать такой чисто функциональной реализации.
Другие решения
Я не могу говорить о Лимонном графике, но о повышающем графике я думаю, что главная цель — быть универсальным. Таким образом, абстрагирование доступа к вершине (ребру) помогает достичь этой цели.
В документации указано, что буст-граф основан на магистерской диссертации Дитмара Кюля об общих графовых алгоритмах. (См. Мой ответ на Карты недвижимости остаются необходимыми для BGL?). Таким образом, главная цель библиотеки — быть универсальной и расширяемой. Выбор инкапсулирующего доступа является частью абстрагирования алгоритмов от представления графа. Для меня непрерывные целочисленные индексы — это деталь реализации.
Boost не делает никаких предположений о том, как вы будете использовать график или какие компромиссы производительности важны для вас. Это позволяет вам выбрать (или внедрить) контейнер, который будет наилучшим образом соответствовать вашим потребностям.
Если вы хотите нарушить эту инкапсуляцию, вы можете это сделать. На самом деле, мое самое распространенное использование графика повышения включает в себя vecS контейнеры и vector из structs. Я обычно работаю с графиками, где размер фиксирован. Я мог бы так же легко использовать map из vertex_descriptorс (или edge_descriptors) к объектам для достижения той же цели.
Итак, в заключение, я бы сказал, что это не столько выбор дизайна, сколько следствие достижения более широкой цели — быть универсальным. Таким образом, скрытие доступа имеет то преимущество, что оно более общее.