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

Question

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

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

Class: Vertice
    - Array arrayOfEdges;
    - String name;

Class: Edge
    - Vertice from;
    - Vertice to;

这使我有可能在以后引入权重,方向等.现在,当我阅读实现图表时,似乎这是一个非常罕见的解决方案.Stack Overflow上的早期问题提出了邻接列表和邻接矩阵,但对图表来说是全新的,我很难理解为什么这比我的方法更好.

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

我选择的语言是Objective-C,但我不相信这应该是有意义的.

Answer 1

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

密集图:

• 邻接矩阵
• 发生率矩阵

稀疏图:

• 邻接清单
• 发病名单

在图形框架(不幸的是,闭源,我写)(> 12k loc图形实现+> 5k loc单元测试并且仍在计数中)我已经能够实现(定向/无向/混合)Hypergraph,(定向) /无向/混合)多图,(有向/无向/混合)有序图,(有向/无向/混合)KPartite图,以及各种树,如通用树,(A,B)-Trees,KAry-树,全KAry树,(树来了:VP树,KD树,BKTrees,B树,R树,八叉树,......).
并且没有单个顶点或边缘类.纯粹的仿制药.几乎没有多余的实现**
哦,好像这还不够,它们都存在于可变,不可变,可观察(NSNotification),线程不安全和线程安全的版本中.
怎么样？通过过度使用装饰器.
基本上所有图形都是可变的,线程不安全且不可观察.所以我使用装饰器为它们添加各种风格(导致不超过35个类,如果没有装饰器,则立即生成500+).

虽然我不能提供任何实际代码,但我的图表基本上是通过使用主要和(以及我的有序树)的发生率列表来实现的.NSMutableDictionariesNSMutableSetsNSMutableArrays

我的Undirected稀疏图只有这些ivars,例如:

NSMutableDictionary *vertices;
NSMutableDictionary *edges;

ivar vertices将顶点映射到顶点的邻接映射到入射边({"vertex": {"vertex": "edge"}})
并且ivar edges将边映射到入射顶点对({"edge": {"vertex", "vertex"}}),其中Pair是保持边的头顶点和尾顶点的对数据对象.

混合稀疏图将具有稍微不同的邻接/发生率列表映射,因此定向稀疏图也会如此,但您应该明白这一点.

这种实现的局限性在于,每个顶点和每个边都需要具有与之关联的对象.为了使事情更有趣(原文如此!),每个顶点对象都需要是唯一的,每个边缘对象也是如此.这是因为词典不允许重复键.此外,对象需要实现NSCopying.NSValueTransformers或者值封装是一种回避这些限制的方法(同样适用于字典密钥复制的内存开销).

虽然实施有其缺点,但有一个很大的好处:广泛的多功能性! 几乎没有任何类型的图表我能想到用我已经拥有的东西来实现它是不可能的.您不必使用自定义构建的零件构建每种类型的图形,而是基本上转到您的乐高积木盒并按照您需要的方式组装图形.

更多见解:

每个主要的图表类型都有自己的协议,这里有几个:

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种图形风格,完全没有黑客攻击.这很值得.

如果您只想绘制一个图形并且能够在屏幕上移动它的节点,那么只需实现一个通用图形类就可以了,如果需要的话可以在以后扩展到特定的直接性.