Объектно-ориентированная реализация структур данных графа

Question

В последнее время я читал довольно много структур данных графа, так как у меня есть намерение написать свой собственный инструмент UML. Насколько я вижу, то, что я хочу, можно смоделировать как простой граф, состоящий из вершин и ребер. Вершины будут иметь несколько значений и поэтому будут лучше всего представлены в виде объектов. Насколько мне известно, Edges не должен быть ни направленным, ни взвешенным, но я не хочу выбирать реализацию, которая делает невозможным включение таких свойств в дальнейшем.

Получив образование в чисто объектно-ориентированном программировании, первое, что приходит мне в голову, это представление вершин и ребер классами, например:

Class: Vertice
    - Array arrayOfEdges;
    - String name;

Class: Edge
    - Vertice from;
    - Vertice to;

Это дает мне возможность позже ввести веса, направление и так далее. Теперь, когда я читаю о реализации графиков, кажется, что это очень необычное решение. Более ранние вопросы здесь о переполнении стека предлагают списки смежности и матрицы смежности, но, будучи совершенно новым для графов, мне трудно понять, почему это лучше, чем мой подход.

Самым важным аспектом моего приложения является возможность легко вычислить, какая вершина нажата и перемещена, а также возможность добавлять и удалять вершины и ребра между вершинами. Будет ли это легче осуществить в одной реализации над другой?

Мой язык выбора - Objective-C, но я не верю, что это должно иметь какое-либо значение.

Answer 1

Вот два основных типа графов вместе с их типичными реализациями:

Плотные графы :

• СмежностьМатрица
• Матрица заболеваемости

Разреженные графики :

• Список смежности
• Список инцидентов

В рамках графа (к сожалению, с закрытым исходным кодом), который яПишу (> 12k локальных графовых реализаций +> 5k локальных модульных тестов и продолжаю считать) Мне удалось реализовать (направленный / ненаправленный / смешанный) гиперграфы, (направленный / ненаправленный / смешанный) мультиграфы, (направленный/ Ненаправленные / Смешанные) Упорядоченные графы, (Направленные / Ненаправленные / Смешанные) Графы KPartite , а также все виды деревьев, такие как Общие деревья, (A, B) -деревья, KAry-Trees, Full-Kry-Trees , (Будущие деревья: VP-Trees, KD-Trees, BKTrees, B-Trees, R-Trees, Octrees ,…).
И все без единоговершина или реброучебный класс.Чисто дженерики.И практически без избыточных реализаций **
О, и как будто этого недостаточно, все они существуют как изменяемые, неизменяемые, наблюдаемые (NSNotification), поточно-небезопасные и поточно-безопасные версии.
Как?Из-за чрезмерного использования Декораторов .
В основном все графики являются изменяемыми, поточно-небезопасными и не наблюдаемыми.Поэтому я использую декораторы, чтобы добавить к ним всевозможные ароматы (в результате получается не более 35 классов против 500+, если они реализованы без декораторов, прямо сейчас).

Хотя я не могу дать никакого реального кода, мои графикив основном реализованы с помощью списков инцидентов с использованием в основном NSMutableDictionaries и NSMutableSets (и NSMutableArrays для моих заказанных деревьев).

My Undirected Sparse Graph не имеет ничего, кроме этих иваров, например:

NSMutableDictionary *vertices;
NSMutableDictionary *edges;

ивар vertices отображает вершины на карты смежности вершин с падающими ребрами ({"vertex": {"vertex": "edge"}})
И ивар edges отображает ребра в инцидентыпары вершин ({"edge": {"vertex", "vertex"}}), причем Pair является парным объектом данных, содержащим вершину ребра и хвостовую вершину.

Смешанные разреженные графы будет иметь немного другое отображение списков смежности / инцидентностии Направленные разреженные графы , но вы должны понять.

Ограничением этой реализации является то, что каждая вершина и каждое ребро должны иметь связанный объектс этим.И чтобы сделать вещи немного более интересными ( sic! ), каждый объект вершины должен быть уникальным, как и каждый объект ребра.Это как словари не позволяют дублировать ключи.Также объекты необходимо реализовать NSCopying.NSValueTransformers или инкапсуляция значений - это способ обойти это ограничение (то же самое относится и к накладным расходам памяти при копировании ключа словаря).

Хотя реализация имеет свои недостатки, есть большое преимущество: огромныйуниверсальность! Едва ли я мог бы придумать график типов, который невозможно отархивировать с тем, что у меня уже есть.Вместо того, чтобы строить каждый тип графиков из пользовательских частей, вы в основном идете к своей коробке с кирпичами Lego и собираете графики именно так, как вам нужно.

Еще несколько идей:

Каждый основной графТип имеет свой собственный протокол, вот некоторые из них:

HypergraphProtocol
    MultigraphProtocol [tagging protocol] (allows parallel edges)
    GraphProtocol (allows directed & undirected edges)
        UndirectedGraphProtocol [tagging protocol] (allows only undirected edges)
        DirectedGraphProtocol [tagging protocol] (allows only directed edges)
            ForestProtocol (allows sets of disjunct trees)
                TreeProtocol (allows trees)
                    ABTreeProtocol (allows trees of a-b children per vertex)
                        FullKAryTreeProtocol [tagging protocol] (allows trees of either 0 or k children per vertex)

Вложенность протокола подразумевает наследование (как протоколов, так и реализаций).

Если есть что-то еще, что вы хотели быЧтобы получить более глубокое понимание, не стесняйтесь оставлять комментарии.

Ps : Чтобы отдать должное, когда кредит заслуживает: Архитектура находилась под сильным влиянием
JUNG Фреймворк Java-графов (55k + loc).

Pps : Перед тем, как выбрать этот тип реализации, я написал его маленького брата с просто неориентированными графами, который я хотел расширить, чтобы также поддерживать ориентированные графы. Моя реализация была очень похожа на ту, что вы указали в своем вопросе. Это то, что дало моему первому (довольно наивному) проекту неожиданный конец, тогда: Создание подкласса класса взаимозависимых классов в Objective-C и обеспечение безопасности типов Добавление простой направленности к моему графу вызывает мое весь код разбить на части. (Я даже не использовал решение, которое я опубликовал в то время, потому что это просто отложило бы боль). Теперь с общей реализацией у меня реализовано более 20 вариантов графического интерфейса без каких-либо хаков. Оно того стоит.

Если все, что вам нужно, - это нарисовать график и иметь возможность перемещать его узлы на экране, вам будет достаточно просто реализовать универсальный класс графиков, который впоследствии можно будет при необходимости расширить до определенной направленности.

Answer 2

Проверьте эту презентацию PowerPoint, особенно последний слайд: http://digital.cs.usu.edu/~cyan/CS5050/Graph.ppt

Answer 3

Матрица смежности будет немного сложнее, чем ваша объектная модель, при добавлении и удалении вершин (но не ребер), поскольку это включает добавление и удаление строк и столбцов из матрицы. Есть приемы, которые вы можете использовать для этого, например, сохранение пустых строк и столбцов, но все равно это будет немного сложнее.

При перемещении вершины по экрану края также будут перемещаться. Это также дает вашей объектной модели небольшое преимущество, так как она будет иметь список соединенных ребер и не будет искать в матрице.

Обе модели имеют внутреннюю направленность на ребра, поэтому, если вы хотите иметь неориентированные ребра, вам придется выполнять дополнительную работу в любом случае.

Я бы сказал, что в целом нет большой разницы. Если бы я реализовывал это, я бы сделал что-то похожее на то, что вы делаете.

Answer 4

Если вы используете Objective-C, я предполагаю, что у вас есть доступ к Базовым данным , что, вероятно, было бы отличным местом для начала - я понимаю, что вы создаете свой собственный график, силу Core Данные о том, что он может выполнять большую часть проверок, о которых вы говорите, бесплатно, если вы правильно настроили свою схему