python - Graphviz - 绘制最大派系

Question

我想使用 graphviz 来绘制给定图形的所有最大派系。因此，我希望同一个最大集团中的节点在视觉上被封装在一起(这意味着我希望一个大圆圈将它们包围)。我知道集群选项存在——但在我目前看到的所有示例中——每个节点仅在一个集群中。在最大团的情况下，一个节点可以在多个团中。是否可以选择使用 graphviz 将其可视化？如果没有，是否有任何其他工具可以完成此任务(最好使用 python api)。谢谢。

Answer 1

喝杯茶，它会很长:)

我用 networkx 画了这个, 但主要步骤可以很容易地转移到 graphviz 中。

计划如下:
a)找到最大派系(以防万一，最大派系不一定是最大派系)；
b)绘制图形并记住绘图程序使用的顶点坐标；
c)取clique的坐标，计算其周围circles的圆心和半径；
d) 绘制圆圈并用相同颜色为派系的顶点着色(对于 2 个和更多 maxcliques 的交集处的顶点，这是不可能的)。

关于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 个 maxcliques 的例子:

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