Graphviz - 绘制最大派系

Question

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

Answer 1

喝茶,它会很长:)

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

计划如下:
a)找到最大派系(以防万一,最大派系不是最大派系);
b)绘制图形并记住绘图程序使用的顶点坐标;
c)取clique的坐标,计算围绕它的圆周的中心和半径;
d)绘制圆圈并以相同的颜色为团体的椎体着色(对于2个或更多个最大轮廓的交叉处的椎骨,这是不可能的).

关于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]