Graphviz-绘制最大集团 [英] Graphviz - Drawing maximal cliques

问题描述

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

I want to use graphviz in order to draw for a given graph all the maximal cliques that it has. Therefore I would like that nodes in the same maximal clique will be visually encapsulated together (meaning that I would like that a big circle will surround them). I know that the cluster option exists - but in all the examples that I saw so far - each node is in one cluster only. In the maximal clique situation, a node can be in multiple cliques. Is there an option to visualize this with graphviz? If not, are there any other tools for this task (preferably with a python api). Thank you.

推荐答案

喝茶，时间会很长:)

我使用 networkx 进行绘制，但是主要步骤可以轻松地转移到graphviz中.

I draw this with networkx, but the main steps could be easily transferred into graphviz.

计划如下:
a)查找最大集团(以防万一，最大集团不一定是最大集团)；
b)绘制图形并记住绘图程序使用的顶点坐标；
c)获取集团的坐标，计算围绕它的线圈的中心和半径；
d)绘制圆圈，并用相同的颜色为集团的顶点着色(对于2个或更多maxclique交点处的顶点是不可能的).

The plan is the following:
a) find maximal cliques (just in case, maximal cliques are not necessary the largest cliques);
b) draw the graph and remember the coordinates of vertices that were used by drawing programm;
c) take clique's coordinates, calculate the center and radius of the cirles that surrounds it;
d) draw the circles and color the verteces of the cliques in the same color (for the verteces in the intersection of 2 and more maxcliques it's not possible).

关于 c):我很想弄清楚这个小圆圈，但是花点时间可以很容易地做到. 相反，我计算了近似圆":我将集团中最长边的长度作为半径并将其乘以1.3.实际上，使用这种方法可能会遗漏一些节点，因为只有sqrt(3)商保证每个人都参与其中.但是，使用sqrt(3)会使圆太大(同样，它也不紧).作为中心，我占据了最大边缘的中间.

Concerning c): I was lazy to figure the tight circle, but having some time it can be easily done. Instead, I calculated the "approximating circle": I took as radius the length of the longest edge in the clique and multiplied it by 1.3. Actually, with this approach some nodes might be left out, since only sqrt(3) quotient garantees that everyone is in. However, taking sqrt(3) will make the circle too large (again, it's not tight). As center I took the middle of the largest edge.

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()

让我们看看我们能得到什么:

Let's see what we get:

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

图片:

另一个具有3个maxcliques的示例:

Another example with 3 maxcliques:

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

这篇关于Graphviz-绘制最大集团的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！