维恩图绘制算法

Question

有人问起在GraphViz中如何处理重叠的子群集(subclusters)，并得到了以下回复：

抱歉，不行。一般的子图可以共享节点而不暗示子集包含关系，但簇则不行。问题在于绘图。 如果群集可以任意重叠，那么绘制它们就成为了绘制Venn图的问题，而这方面并没有好的算法。

"绘制Venn图的问题"的正式定义或示例是什么？为什么它很难（我假设是NP完全/难）？（额外加分：说明一个到一个众所周知的NP完全问题的约化(reduction)）

- Andrew Tomazos

---

这似乎更适合在 数学 上讨论。 - Kevin Reid

这句话的意思是：引用可在此处找到：Gansner, Emden R. (2006-03-30). "overlapping subgraphs" graphviz-interest邮件列表. [e-mail]。 - minopret

我发现我使用GraphViz绘图的计划与gauden在NetworkX和matplotlib中绘制图表的计划相似。 - minopret

Answer 1

您有N个点和一个二元关系R，需要用图形方式表示该关系，使得每个节点都在欧几里得平面上以圆的形式表示，当且仅当对于相应的节点n和n'，它们满足n R n'时，两个圆重叠。

- Antti Huima

---

假设N = 100，并且对于所有的i和j，i R j都是成立的，那么这个图表会是什么样子？ - Andrew Tomazos

你有100个圆，它们都重叠在一起。 - Antti Huima

然而，正如您可以在维基百科“Venn diagram”中看到的那样，实际上有算法（由Venn和其他人）可以在平面上绘制任意数量N个区域（不全是圆），以显示所有2^N-1个交集区域（加上一个外部区域）。这些构造的问题是显而易见的：更多或更少的审美判断、大量的2^N个交集区域以及为使它们足够大而必要的空间。 - minopret

Answer 2

除了使用Venn图之外，我们在许多情况下可以使用GraphViz来实现相同的目的，使用双重图，即集合交点的布尔格。每个节点表示要包括和排除的唯一集合选择。仅由单个集合的包含/排除区别的节点是连接的。

对于越来越多的集合，通常会有许多节点和边缘。但在许多实际设置中，将存在许多不相交的集合，因此这些交点节点及其与其他节点的任何边缘都可以省略。通过这种方法，节点和边的数量可以减少到实用的数量。

在布局结果图时，最好选择GraphViz算法“neato”，并要求避免重叠节点。设置这些设置的一种方法是在图形的开放花括号内写入layout=neato,overlap=prism; 。

- minopret