Графвиз - Рисование максимальных кликов

Question

Я хочу использовать graphviz, чтобы нарисовать для данного графа все максимальные клики, которые у него есть. Поэтому я хотел бы, чтобы узлы в одной и той же максимальной клике были визуально инкапсулированы вместе (это означает, что я хотел бы, чтобы их окружал большой круг). Я знаю, что опция кластера существует, но во всех примерах, которые я видел до сих пор, каждый узел находится только в одном кластере. В ситуации максимальной клики узел может быть в нескольких кликах. Есть ли возможность визуализировать это с graphviz? Если нет, есть ли другие инструменты для этой задачи (желательно с Python API). Спасибо.

Answer 1

Пей чай, это будет долго :) 1001 *

Я рисую это с помощью networkx , но основные шаги можно легко перенести в graphviz.

План следующий:
a) найти максимальные клики (на всякий случай, максимальные клики необязательны, самые большие клики);
b) нарисуйте график и запомните координаты вершин, которые использовались программой рисования;
в) взять координаты клики, вычислить центр и радиус окружностей, окружающих ее;
d) нарисуйте круги и раскрасьте вершины клик в один цвет (для вершин в пересечении 2 и более макскликов это невозможно).

Относительно в) : Мне было лень вычислять крутой круг, но, имея некоторое время, это легко сделать. Вместо этого я вычислил «аппроксимирующий круг»: в качестве радиуса я взял длину самого длинного края клики и умножил ее на 1,3. На самом деле, при таком подходе некоторые узлы могут быть пропущены, поскольку только квантовая (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]

Pic:

Другой пример с 3 максимальными кликами:

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

Answer 2

Это было бы немного сложно реализовать, но вот пример того, как рисовать перекрывающиеся множества.

• Riche, NH;Дуайер Т., «Распутывающие диаграммы Эйлера», «IEEE транзакции по визуализации и компьютерной графике», том 16, № 6, с. 1090-1099, ноябрь-декабрь.2010 DOI: 10.1109 / TVCG.2010.210 . PDF

Answer 3

Я не думаю, что вы можете сделать это. Кластеры создаются через подграфы, которые, как ожидается, будут отдельными графами, не пересекающимися с другими подграфами.

Вы можете изменить визуализацию, хотя; если вы представляете, что члены клики являются членами некоторого набора S, то вы можете просто добавить узел S и добавить направленные или пунктирные ребра, связывающие каждый член с узлом S. Если узлам S придана другая форма, тогда должно быть ясно, какие узлы в каких кликах.

Если вы действительно хотите, вы можете дать ребрам, соединяющим элементы с их узлами клики, большие веса, которые должны сблизить их на графике.

Обратите внимание, что между узлами клика никогда не будет ребер; это указывало бы на то, что две клики максимально связаны, что просто означает, что они на самом деле являются одной большой кликой, а не двумя отдельными.