面向对象的图形数据结构的实现 [英] Object Oriented implementation of graph data structures
问题描述
最近我一直在读数据结构，因为我有意写自己的UML工具。据我所见，我想要的可以被建模为由顶点和边缘组成的简单图形。顶点将具有几个值，最好被表示为对象。根据我所看到的，边缘不需要既不是直接的也不是加权的，但是我不想选择一个实现，以后不可能包含这些属性。
在纯面向对象编程中受过教育，我想到的第一件事是按类代表顶点和边，例如：
类：Vertice
- 数组arrayOfEdges;
- 字符串名称;
类：Edge
- Vertice from;
- Vertice to;
这给了我以后介绍权重，方向等的可能性。现在，当我阅读实现图形时，似乎这是一个非常不寻常的解决方案。在Stack Overflow上的一些早期问题表明了邻接列表和邻接矩阵，但是对于图形来说完全是新的，我很难理解为什么比我的方法更好。
我的应用程序的最重要的方面是能够轻松计算哪个顶点被点击和移动，以及添加和删除顶点之间的顶点和边缘的能力。这样做在一个实现中比另一个更容易实现吗？
我的选择语言是Objective-C，但我不认为这应该没有任何意义。 / p>
以下是两种基本图形类型及其典型实现：
密集图：
稀疏图：
在图形框架（不幸的是，封闭的源代码）我已经写了（> 12k的位图实现+> 5k的位置单元测试，还在计数）我已经能够实现（定向/非定向/混合）超图，（定向/非定向/混合）多图，（定向/非定向/混合）有序图，（定向/非定向/混合）KPartite图，以及各种树，例如通用树，（A，B）-Trees，KAry-Trees ，全KAry-Trees ，（要来的树： VP树，KD树，BKTrees，B树，R树，Octrees ，...）。
所有没有单个顶点或边缘类。纯粹的泛型而且几乎没有多余的实现**
哦，如果这还不够，它们都以mutable，immutable，observable（ NSNotification ），线程不安全和线程安全的版本。
如何？通过过度使用 装饰 。
基本上所有图形都是可变的，线程不安全的，不可观察的。所以我使用Decorators来添加各种各样的口味（如果实现没有装饰器，则不会超过35个类，而如果没有装饰器，则为500）。
我不能给出任何实际代码，我的图表基本上通过发现列表实现，主要使用<$对于我订购的树，c $ c> NSMutableDictionaries 和 NSMutableSets （和 NSMutableArrays ）
我的无向稀疏图只有这些ivars，例如：
NSMutableDictionary * vertices;
NSMutableDictionary * edges;
ivar 顶点将顶点映射到邻接图顶点到事件边缘（ {vertex：{vertex：edge}} ）
和ivar {edge：{vertex，vertex}} ），Pair为对数据对象持有边缘的头顶点和尾部顶点。
混合稀疏图将具有略有不同的附件/入口列表映射等定向稀疏图，但您应该了解这个想法。
此实现的一个限制是，每个顶点和每个边缘都需要具有与之相关联的对象。并且要使事情更有趣（ sic！）每个顶点对象需要是唯一的，每个边缘对象也是如此。这是因为字典不允许重复键。此外，对象需要实现 NSCopying 。 NSValueTransformers 或值封装是一种避开这些限制的方法（相同于从字典密钥复制的内存开销）。
虽然实现有其缺点，但是有一个很大的好处：多功能性
几乎没有任何类型的图形，我可以想到这是不可能与我已经拥有的。而不是使用自定义构建的零件构建每种类型的图形，您基本上可以通过您的方块砖，并按照需要的方式组合图形。
更多的洞察力：
每个主要图形类型都有自己的协议，这里有几个：
HypergraphProtocol
MultigraphProtocol [标记协议]（允许并行边）
GraphProtocol（允许有向和无向边）
UndirectedGraphProtocol [标记协议]（仅允许无向边）
DirectedGraphProtocol [标记协议]（仅允许有向边）
ForestProtocol（允许一组分离树）
TreeProtocol（允许树）
ABTreeProtocol（允许每个顶点的ab子树）
FullKAryTreeProtocol [标记协议]（允许每个顶点的0或k个孩子的树）
协议嵌套imp谎言（两个协议，以及实现）。
如果还有其他任何你想获得某种意见的话，可以随意发表评论。 / p>
Ps ：在信用到期时给予信用：建筑受到
JUNG Java graph framework （55k + loc）。
Pps ：在选择这种类型的实现之前，我已经用无向图形写了一个小弟弟，我想扩展也支持定向图。我的实现与您在问题中提供的实现非常相似。这是什么让我的第一个（相当天真的）项目突然结束，然后：在Objective-C中对一组相互依赖的类进行子类化，并确保类型安全性向我的图表添加简单的指导性使我的整个代码分开。 （我甚至没有使用我当时发布的解决方案，因为它只会推迟痛苦）现在，通用实现我实现了20多种图形风格，没有任何黑客。这是值得的。
如果你想要的是绘制一个图形，并且能够在屏幕上移动它的节点，但是，只要实现一个泛型图表类，如果需要，可以稍后将其扩展到特定的指导性。
I have been reading quite a bit graph data structures lately, as I have intentions of writing my own UML tool. As far as I can see, what I want can be modeled as a simple graph consisting of vertices and edges. Vertices will have a few values, and will so best be represented as objects. Edges does not, as far as I can see, need to be neither directed or weighted, but I do not want to choose an implementation that makes it impossible to include such properties later on.
Being educated in pure object oriented programming, the first things that comes to my mind is representing vertices and edges by classes, like for example:
Class: Vertice
- Array arrayOfEdges;
- String name;
Class: Edge
- Vertice from;
- Vertice to;
This gives me the possibility to later introduce weights, direction, and so on. Now, when I read up on implementing graphs, it seems that this is a very uncommon solution. Earlier questions here on Stack Overflow suggests adjacency lists and adjacency matrices, but being completely new to graphs, I have a hard time understanding why that is better than my approach.
The most important aspects of my application is having the ability to easily calculate which vertice is clicked and moved, and the ability to add and remove vertices and edges between the vertices. Will this be easier to accomplish in one implementation over another?
My language of choice is Objective-C, but I do not believe that this should be of any significance.
Here are the two basic graph types along with their typical implementations:
In the graph framework (closed source, unfortunately) that I've ben writing (>12k loc graph implementations + >5k loc unit tests and still counting) I've been able to implement (Directed/Undirected/Mixed) Hypergraphs, (Directed/Undirected/Mixed) Multigraphs, (Directed/Undirected/Mixed) Ordered Graphs, (Directed/Undirected/Mixed) KPartite Graphs, as well as all kinds of Trees, such as Generic Trees, (A,B)-Trees, KAry-Trees, Full-KAry-Trees, (Trees to come: VP-Trees, KD-Trees, BKTrees, B-Trees, R-Trees, Octrees, …).
And all without a single vertex or edge class. Purely generics. And with little to no redundant implementations**
Oh, and as if this wasn't enough they all exist as mutable, immutable, observable (NSNotification), thread-unsafe and thread-safe versions.
How? Through excessive use of Decorators.
Basically all graphs are mutable, thread-unsafe and not observable. So I use Decorators to add all kinds of flavors to them (resulting in no more than 35 classes, vs. 500+ if implemented without decorators, right now).
While I cannot give any actual code, my graphs are basically implemented via Incidence Lists by use of mainly NSMutableDictionaries and NSMutableSets (and NSMutableArrays for my ordered Trees).
My Undirected Sparse Graph has nothing but these ivars, e.g.:
NSMutableDictionary *vertices;
NSMutableDictionary *edges;
The ivar vertices maps vertices to adjacency maps of vertices to incident edges ({"vertex": {"vertex": "edge"}})
And the ivar edges maps edges to incident vertex pairs ({"edge": {"vertex", "vertex"}}), with Pair being a pair data object holding an edge's head vertex and tail vertex.
Mixed Sparse Graphs would have a slightly different mapping of adjascency/incidence lists and so would Directed Sparse Graphs, but you should get the idea.
A limitation of this implementation is, that both, every vertex and every edge needs to have an object associated with it. And to make things a bit more interesting(sic!) each vertex object needs to be unique, and so does each edge object. This is as dictionaries don't allow duplicate keys. Also, objects need to implement NSCopying. NSValueTransformers or value-encapsulation are a way to sidestep these limitation though (same goes for the memory overhead from dictionary key copying).
While the implementation has its downsides, there's a big benefit: immensive versatility! There's hardly any type graph that I could think of that's impossible to archieve with what I already have. Instead of building each type of graph with custom built parts you basically go to your box of lego bricks and assemble the graphs just the way you need them.
Some more insight:
Every major graph type has its own Protocol, here are a few:
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)
The protocol nesting implies inharitance (of both protocols, as well as implementations).
If there's anything else you'd like to get some mor insight, feel free to leave a comment.
Ps: To give credit where credit is due: Architecture was highly influenced by the
JUNG Java graph framework (55k+ loc).
Pps: Before choosing this type of implementation I had written a small brother of it with just undirected graphs, that I wanted to expand to also support directed graphs. My implementation was pretty similar to the one you are providing in your question. This is what gave my first (rather naïve) project an abrupt end, back then: Subclassing a set of inter-dependent classes in Objective-C and ensuring type-safety Adding a simple directedness to my graph cause my entire code to break apart. (I didn't even use the solution that I posted back then, as it would have just postponed the pain) Now with the generic implementation I have more than 20 graph flavors implemented, with no hacks at all. It's worth it.
If all you want is drawing a graph and being able to move its nodes on the screen, though, you'd be fine with just implementing a generic graph class that can then later on be extended to specific directedness, if needed.
这篇关于面向对象的图形数据结构的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
