图数据结构的面向对象实现
最近我读了很多图数据结构，因为我打算编写自己的 UML 工具。据我所知，我想要的可以建模为由顶点和边组成的简单图。顶点将具有一些值，因此最好将其表示为对象。据我所知，边缘不需要定向或加权，但我不想选择一种以后无法包含此类属性的实现。
在接受过纯面向对象编程的教育后，我首先想到的是用类来表示顶点和边，例如：
Class: Vertice
- Array arrayOfEdges;
- String name;
Class: Edge
- Vertice from;
- Vertice to;
这使我有可能稍后引入权重、方向等。现在，当我阅读有关实现图的内容时，这似乎是一个非常不常见的解决方案。 Stack Overflow 上的早期问题建议使用邻接列表和邻接矩阵，但由于对图完全陌生，我很难理解为什么这比我的方法更好。
我的应用程序最重要的方面是能够轻松计算单击和移动的顶点，以及添加和删除顶点以及顶点之间的边的能力。在一种实现中比在另一种实现中更容易实现这一点吗？
我选择的语言是 Objective-C，但我认为这没有任何意义。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
以下是两种基本图形类型及其典型实现：
密集图：< /strong>
稀疏图：
在我一直在编写的图形框架（不幸的是，封闭源代码）（> 12k loc 图形实现 + > 5k loc 单元测试并且仍在计数）我已经能够实现（有向/无向/混合）超图，（有向/无向/混合）多重图，（有向/无向/混合）有序图，（有向/无向/混合）KPartite图，以及所有各种树，例如通用树、(A,B)-树、KAry-树、 Full-KAry-Trees，（即将推出的树：VP-Trees、KD-Trees、BKTrees、B-Trees、R-Trees、八叉树，...）。
并且所有这些都没有单个顶点或边类。纯粹是泛型。并且几乎没有冗余实现**
哦，好像这还不够，它们都以可变、不可变、可观察 (
NSNotification)、线程不安全和线程安全版本的形式存在。如何？通过过度使用装饰器。
基本上所有的图都是可变的、线程不安全的并且不可观察的。因此，我使用装饰器向它们添加各种风格（导致不超过 35 个类，而如果现在不使用装饰器实现，则需要 500 多个类）。
虽然我无法给出任何实际代码，但我的图表基本上是通过 发生率列表 实现的，主要使用
NSMutableDictionaries和NSMutableSets（以及用于我的有序树的NSMutableArrays）。我的无向稀疏图只有这些ivars，例如：
ivar
vertices将顶点映射到顶点到关联边的邻接图 ({"vertex": {"顶点": "边"}})ivar
edges将边映射到事件顶点对 ({"edge": {"vertex", "vertex"}})，其中 Pair 是一个包含数据对的对象边的头顶点和尾顶点。混合稀疏图的邻接/关联列表映射略有不同，有向稀疏图也是如此，但您应该明白这个想法。
此实现的限制是，每个顶点和每条边都需要有一个与其关联的对象。为了让事情变得更有趣（原文如此！），每个顶点对象都需要是唯一的，每个边对象也是如此。这是因为字典不允许重复的键。此外，对象需要实现
NSCopying。 NSValueTransformers 或值封装是规避这些限制的一种方法（字典键复制的内存开销也是如此）。虽然该实现有其缺点，但有一个很大的好处：巨大的多功能性！
我能想到的几乎没有任何类型图是不可能用我已经拥有的来实现的。您无需使用定制部件构建每种类型的图表，而是直接打开乐高积木盒，按照您需要的方式组装图表。
更多见解：
每种主要图形类型都有自己的协议，以下是一些协议：
协议嵌套意味着（两种协议以及实现的）继承性。
如果您还有什么想了解更多见解，请随时发表评论。
Ps：在应得的地方给予赞扬：建筑深受
的影响
JUNG Java 图形框架（55k+ loc）。
Pps：在选择这种类型的实现之前，我已经用无向图编写了它的一个小兄弟，我想扩展它以支持有向图。我的实现与您在问题中提供的实现非常相似。这就是我的第一个（相当幼稚）项目突然结束的原因：在 Objective-C 中对一组相互依赖的类进行子类化并确保类型安全 在我的图中添加一个简单的有向性会导致我的整个代码崩溃。 （我什至没有使用当时发布的解决方案，因为它只会推迟痛苦）现在，通过通用实现，我实现了 20 多种图形风格，根本没有任何黑客攻击。这是值得的。
不过，如果您想要的只是绘制一个图形并能够在屏幕上移动其节点，那么您只需实现一个通用图形类就可以了，如果需要的话，稍后可以将其扩展到特定的有向性。
Here are the two basic graph types along with their typical implementations:
Dense Graphs:
Sparse Graphs:
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
NSMutableDictionariesandNSMutableSets(andNSMutableArraysfor my ordered Trees).My Undirected Sparse Graph has nothing but these ivars, e.g.:
The ivar
verticesmaps vertices to adjacency maps of vertices to incident edges ({"vertex": {"vertex": "edge"}})And the ivar
edgesmaps 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.NSValueTransformersor 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:
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.
邻接矩阵在添加和删除顶点（但不是边）方面比对象模型更困难，因为这涉及在矩阵中添加和删除行和列。您可以使用一些技巧来做到这一点，例如保留空行和空列，但它仍然会有点复杂。
当在屏幕上移动顶点时，边缘也会移动。这也为您的对象模型带来了一些优势，因为它将具有连接边的列表，并且不必搜索矩阵。
两种模型都对边缘具有固有的定向性，因此如果您想要拥有无向边缘，那么无论哪种方式您都必须做额外的工作。
我想说，总体而言，没有太大差异。如果我要实现这个，我可能会做类似于你正在做的事情。
An adjacency matrix will have a bit more difficulty than your object model in adding and removing vertices (but not edges), since this involves adding and removing rows and columns from a matrix. There are tricks you could use to do this, like keeping empty rows and columns, but it will still be a bit complicated.
When moving a vertex around the screen, the edges will also be moved. This also gives your object model a slight advantage, since it will have a list of connected edges and will not have to search through the matrix.
Both models have an inherent directedness to the edges, so if you want to have undirected edges, then you will have to do additional work either way.
I would say that overall there is not a whole lot of difference. If I were implementing this, I would probably do something similar to what you are doing.
如果您使用的是 Objective-C，我假设您可以访问核心数据，这可能是一个很好的起点 - 我知道您正在创建自己的图表，核心数据的优势在于如果你正确设置你的模式，它可以免费完成你所说的很多检查
If you're using Objective-C I assume you have access to Core Data which would be probably be a great place to start - I understand you're creating your own graph, the strength of Core Data being that it can do a lot of the checking you're talking about for free if you set up your schema properly