Graphviz – Dibujando camarillas máximas

Quiero usar graphviz para dibujar para un gráfico dado todas las camarillas máximas que tiene. Por lo tanto, me gustaría que los nodos en la misma camarilla máxima se encapsulen visualmente juntos (lo que significa que me gustaría que un círculo grande los rodea). Sé que la opción de clúster existe, pero en todos los ejemplos que he visto hasta ahora, cada nodo está solo en un clúster. En la situación de camarilla máxima, un nodo puede estar en múltiples camarillas. ¿Hay alguna opción para visualizar esto con graphviz? Si no es así, ¿existen otras herramientas para esta tarea (preferiblemente con una api de python)? Gracias.

Toma un té, va a ser largo 🙂

Dibujé esto con networkx , pero los pasos principales podrían transferirse fácilmente a graphviz.

El plan es el siguiente:
a) encontrar camarillas máximas (por si acaso, las camarillas máximas no son necesarias las camarillas más grandes);
b) dibuje la gráfica y recuerde las coordenadas de los vértices que se usaron para dibujar programm;
c) tomar las coordenadas de la camarilla, calcular el centro y el radio de los círculos que lo rodean;
d) dibuje los círculos y coloree las vértices de las camarillas en el mismo color (para las vértices en la intersección de 2 y más maxcliques no es posible).

Con respecto a c) : era perezoso para calcular el círculo cerrado, pero al tener un tiempo se puede hacer fácilmente. En cambio, calculé el “círculo aproximado”: tomé como radio la longitud del borde más largo de la pandilla y lo multipliqué por 1.3. En realidad, con este enfoque algunos nodos pueden quedar fuera, ya que solo el cociente sqrt (3) garantiza que todos están dentro. Sin embargo, tomar sqrt (3) hará que el círculo sea demasiado grande (de nuevo, no es estrecho). Como centro tomé el centro del borde más grande.

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

Veamos lo que obtenemos:

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

Foto: Círculos máximos en círculo

Otro ejemplo con 3 maxcliques:

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

Círculos máximos en círculo

No creo que puedas hacer esto. Los agrupamientos se realizan a través de subgrafos, que se espera que sean grafos separados, no superpuestos con otros subgrafos.

Sin embargo, podrías cambiar la visualización; Si imagina que los miembros de una camarilla son miembros de algún conjunto S , entonces simplemente podría agregar un nodo S y agregar bordes dirigidos o discontinuos que unen cada miembro al nodo S Si a los nodos S les da una forma diferente, entonces debería quedar claro qué nodos están en qué camarillas.

Si realmente lo desea, puede asignar a los bordes que conectan a los miembros los pesos altos de su clique, lo que debería reunirlos en el gráfico.

Tenga en cuenta que nunca habría bordes entre los nodos clique; eso indicaría que dos camarillas están conectadas al máximo, lo que simplemente implica que en realidad son una camarilla grande, no dos separadas.

Sería un poco difícil de implementar, pero aquí hay un ejemplo de cómo dibujar conjuntos superpuestos.

  • Riche, NH; Dwyer, T.,, “Untangling Euler Diagrams,” IEEE Transactions on Visualization and Computer Graphics, vol.16, no.6, pp.1090-1099, noviembre-diciembre. DOI 2010 : 10.1109 / TVCG.2010.210 . PDF

introduzca la descripción de la imagen aquí