Graphviz - 绘制极大团

Question

我想用graphviz来绘制一个图的所有最大团。最大团就是图中节点之间的连接关系，节点之间的连接非常紧密。我的想法是，把同一个最大团里的节点用一个大圈圈起来，这样看起来更清晰。我知道有一个“cluster”选项可以用来分组，但我看到的例子里，每个节点只能属于一个组。而在最大团的情况下，一个节点可以同时属于多个团。请问有没有办法用graphviz来实现这个效果？如果没有，还有没有其他工具可以做到这个（最好是有Python接口的）？谢谢。

Answer 1

我觉得这个是做不到的。聚类是通过子图来完成的，这些子图应该是独立的，不应该和其他子图重叠。

不过你可以改变一下可视化的方式；如果你想象一下，一个团体的成员是某个集合 S 的成员，那么你可以简单地添加一个节点 S，并用有向边或者虚线把每个成员连接到 S 节点。如果把 S 节点做成不同的形状，那么就能清楚地看出哪些节点属于哪个团体。

如果你真的想这样做，可以给连接成员和他们团体节点的边设置较大的权重，这样它们在图上就会靠得更近。

需要注意的是，团体节点之间是不会有边的；如果有边的话，就说明这两个团体是完全连接的，这实际上意味着它们是一个大的团体，而不是两个独立的团体。

Answer 2

实现这个功能可能有点挑战性，但这里有一个关于如何绘制重叠集合的例子。

• Riche, N.H.; Dwyer, T.; "解开欧拉图的复杂性," IEEE可视化与计算机图形学杂志, 第16卷，第6期, 第1090-1099页, 2010年11-12月 DOI:10.1109/TVCG.2010.210. PDF

Answer 3

喝杯茶吧，这会花点时间 :)

我用 networkx 画了这个图，但主要步骤也可以很容易地用 graphviz 来实现。

计划如下：
a) 找到最大的团（顺便说一下，最大的团不一定是最大的那个）；
b) 画出图形，并记下绘图程序使用的顶点坐标；
c) 获取团的坐标，计算包围它的圆的中心和半径；
d) 画出这些圆，并把团的顶点涂成相同的颜色（对于两个或更多最大团交叉的顶点，这个就不行了）。

关于c)：我懒得去算最紧的圆，但如果有时间其实可以很容易做到。相反，我计算了一个“近似圆”：我把团中最长边的长度作为半径，然后乘以 1.3。实际上，使用这种方法可能会漏掉一些节点，因为只有用 sqrt(3) 的比例才能保证每个节点都在里面。不过，使用 sqrt(3) 会让圆太大（再次强调，这不是最紧的）。我把最大的边的中点作为圆心。

import networkx as nx
from math import *
import matplotlib.pylab as plt
import itertools as it

def draw_circle_around_clique(clique,coords):
    dist=0
    temp_dist=0
    center=[0 for i in range(2)]
    color=colors.next()
    for a in clique:
        for b in clique:
            temp_dist=(coords[a][0]-coords[b][0])**2+(coords[a][1]-coords[b][2])**2
            if temp_dist>dist:
                dist=temp_dist
                for i in range(2):
                    center[i]=(coords[a][i]+coords[b][i])/2
    rad=dist**0.5/2
    cir = plt.Circle((center[0],center[1]),   radius=rad*1.3,fill=False,color=color,hatch=hatches.next())
    plt.gca().add_patch(cir)
    plt.axis('scaled')
    # return color of the circle, to use it as the color for vertices of the cliques
    return color

global colors, hatches
colors=it.cycle('bgrcmyk')# blue, green, red, ...
hatches=it.cycle('/\|-+*')

# create a random graph
G=nx.gnp_random_graph(n=7,p=0.6)
# remember the coordinates of the vertices
coords=nx.spring_layout(G)

# remove "len(clique)>2" if you're interested in maxcliques with 2 edges
cliques=[clique for clique in nx.find_cliques(G) if len(clique)>2]

#draw the graph
nx.draw(G,pos=coords)
for clique in cliques:
    print "Clique to appear: ",clique
nx.draw_networkx_nodes(G,pos=coords,nodelist=clique,node_color=draw_circle_around_clique(clique,coords))

plt.show()

让我们看看结果：

>> Clique to appear:  [0, 5, 1, 2, 3, 6]
>> Clique to appear:  [0, 5, 4]

图片：

另一个有 3 个最大团的例子：

>> Clique to appear:  [1, 4, 5]
>> Clique to appear:  [2, 5, 4]
>> Clique to appear:  [2, 5, 6]