objective-c - 图数据结构的面向对象实现

Question

我最近一直在阅读相当多的图形数据结构，因为我打算编写自己的 UML 工具。据我所知，我想要的可以建模为一个由顶点和边组成的简单图形。顶点将具有一些值，因此最好将其表示为对象。据我所知，Edges 既不需要定向也不需要加权，但我不想选择一个实现，使得以后不可能包含这些属性。

受过纯面向对象编程的教育，我想到的第一件事是通过类表示顶点和边，例如:

Class: Vertice
    - Array arrayOfEdges;
    - String name;

Class: Edge
    - Vertice from;
    - Vertice to;

这使我有可能在以后引入权重、方向等。现在，当我阅读实现图时，这似乎是一个非常不常见的解决方案。 Stack Overflow 上的早期问题建议使用邻接表和邻接矩阵，但我对图形完全陌生，我很难理解为什么这比我的方法更好。

我的应用程序最重要的方面是能够轻松计算单击和移动哪个顶点，以及添加和删除顶点和顶点之间的边的能力。这在一种实现中比另一种更容易实现吗？

我选择的语言是 Objective-C，但我认为这没有任何意义。

Answer 1

以下是两种基本图形类型及其典型实现:

Dense Graphs :

Adjacency Matrix

Incidence Matrix

Sparse Graphs :

Adjacency List

Incidence List

图框架中 (不幸的是，封闭源代码)我一直在写(> 12k loc 图实现 + > 5k loc 单元测试并且仍在计数) 我已经能够实现(有向/无向/混合)超图、(有向/无向/混合)多重图、(有向/无向/混合)有序图、(有向/无向/混合)KPartite 图 ，以及各种树，如 泛型树、(A,B)-树、Kary 树、全 Kary 树 ，(即将出现的树: VP-Trees、KD-Trees、BKTrees、B-Trees、R-Trees、八叉树 ，...)。
而且都没有单个顶点或边类。纯泛型。并且几乎没有冗余实现**
哦，好像这还不够，它们都以可变、不可变、可观察 ( NSNotification )、线程不安全和线程安全版本的形式存在。
如何？通过过度使用 Decorators .
基本上所有的图都是可变的、线程不安全的并且不可观察。所以我使用装饰器为它们添加各种风格(导致不超过 35 个类，而如果现在没有装饰器实现则为 500+)。

虽然我无法给出任何实际代码，但我的图表基本上是通过 Incidence Lists 实现的。主要使用 NSMutableDictionaries和 NSMutableSets (和 NSMutableArrays 用于我订购的树)。

我的 无向稀疏图 除了这些 ivars 什么都没有，例如:

NSMutableDictionary *vertices;
NSMutableDictionary *edges;

ivar vertices将顶点映射到顶点到事件边的邻接图 ( {"vertex": {"vertex": "edge"}})
和 ivar edges将边映射到事件顶点对 ( {"edge": {"vertex", "vertex"}} )，其中 Pair 是一对数据对象，包含边的头顶点和尾顶点。

混合稀疏图 邻接/发生率列表的映射略有不同， 也是如此。有向稀疏图 ，但你应该明白。

这种实现的一个限制是，每个顶点和每个边都需要有一个与之关联的对象。为了让事情变得更有趣(原文如此!)每个顶点对象都需要是唯一的，每个边对象也是如此。这是因为字典不允许重复键。此外，对象需要实现 NSCopying . NSValueTransformers或值封装是一种规避这些限制的方法(同样适用于字典键复制的内存开销)。

虽然实现有其缺点，但有一个很大的好处: 巨大的多功能性!
几乎没有任何我能想到的类型图是不可能用我已经拥有的东西来归档的。无需使用自定义构建的部件构建每种类型的图形，您基本上可以使用乐高积木盒并按照您需要的方式组装图形。

更多的见解:

每个主要的图形类型都有自己的协议(protocol)，这里有一些:

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)

协议(protocol)嵌套意味着 inharitance(两个协议(protocol)，以及实现)。

如果您还有什么想了解的更多信息，请随时发表评论。

ps : 在信用到期时给予信用:建筑受到了高度的影响
JUNG Java图框架 (55k+ 定位)。

pps :在选择这种类型的实现之前，我写了一个只有无向图的小兄弟，我想扩展它以支持有向图。我的实现与您在问题中提供的实现非常相似。这就是我的第一个(相当幼稚的)项目突然结束的原因，当时: Subclassing a set of inter-dependent classes in Objective-C and ensuring type-safety向我的图中添加一个简单的方向性会导致我的整个代码分崩离析。 (我什至没有使用我当时发布的解决方案，因为它只会推迟痛苦)现在通过通用实现，我实现了 20 多种图形风格，根本没有任何黑客攻击。这很值得。

但是，如果您想要的只是绘制图形并能够在屏幕上移动其节点，那么您只需实现一个通用图形类就可以了，如果需要，该类稍后可以扩展到特定的方向。