Graphviz - Disegno clique massimo

Question

Voglio usare graphviz per disegnare per un dato grafico tutte le cricche massimali che ha. Quindi vorrei che i nodi nella stessa cricca massimale fossero visivamente incapsulati insieme (nel senso che mi piacerebbe che un grande cerchio li circondasse). So che l'opzione cluster esiste, ma in tutti gli esempi che ho visto fino ad ora - ogni nodo è solo in un cluster. Nella situazione di cricca massimale, un nodo può trovarsi in più clique. Esiste un'opzione per visualizzare questo con graphviz? In caso contrario, ci sono altri strumenti per questa attività (preferibilmente con un python api). Grazie.

Answer 1

Prendere un tè, esso sta andando essere lungo :)

traggo questo con networkx, ma i passi principali possono essere facilmente trasferite in graphviz.

Il piano è il seguente:
a) trovare cricche massime (solo nel caso, cricche massime non sono necessari più grandi cricche);
b) disegnare il grafico e ricordare le coordinate dei vertici utilizzati dal programma di disegno;
c) prendere le coordinate di cricca, calcolare il centro e il raggio dei cerchi che lo circondano;
d) disegnare i cerchi e colorare le vertici delle cricche nello stesso colore (per le vertici nell'intersezione di 2 e più maxcliques non è possibile).

c): ero pigro per capire il cerchio stretto, ma avere un po 'di tempo può essere fatto facilmente. Invece, ho calcolato il "cerchio approssimativo": ho preso come raggio la lunghezza del bordo più lungo nella cricca e moltiplicato per 1,3. In realtà, con questo approccio alcuni nodi potrebbero essere lasciati fuori, poiché solo il quoziente sqrt (3) garantisce che tutti siano presenti. Tuttavia, prendere sqrt (3) renderà il cerchio troppo grande (di nuovo, non è stretto). Come centro ho preso il centro del margine più 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() 

Vediamo cosa otteniamo:

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

Pic:

Un altro esempio con 3 maxcliques:

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

Answer 2

Non penso che tu possa farlo. I cluster sono fatti tramite sottografi, che dovrebbero essere grafici separati, non sovrapposti ad altri sottografi.

Tuttavia, è possibile modificare la visualizzazione; se si immagina che i membri di una clique siano membri di qualche serie S, è possibile semplicemente aggiungere un nodo S e aggiungere bordi diretti o tratteggiati che collegano ciascun membro al nodo S. Se ai nodi S viene assegnata una forma diversa, dovrebbe essere chiaro quali nodi si trovano in quali clique.

Se lo si desidera, è possibile assegnare agli spigoli i membri che si collegano ai relativi pesi del nodo di cricca, che dovrebbero avvicinarli sul grafico.

Si noti che non ci saranno mai spigoli tra i nodi della clique; ciò indicherebbe che due clique sono collegate al massimo, il che implica semplicemente che sono in realtà una grande cricca, non due separate.

Answer 3

Sarebbe un po 'difficile da implementare, ma ecco un esempio di come disegnare insiemi sovrapposti.

• Riche, N.H .; Dwyer, T.;, "Districare i diagrammi di Eulero", Transazioni IEEE su visualizzazione e computer grafica, vol.16, n. 6, pp.1090-1099, nov.-dic. 2010 DOI:10.1109/TVCG.2010.210. PDF