Graphviz - drawing maximum clicks

Question

I want to use graphviz to draw for this graph all the maximum clicks it has. Therefore, I would like the nodes in the same maximum click to be visually encapsulated together (this means that I would like a large circle to surround them). I know that the cluster parameter exists, but in all the examples that I have seen so far, each node is in only one cluster. In the maximum click situation, a node can be in a few clicks. Is it possible to visualize this with Graphviz? If not, are there any other tools for this task (preferably with python api). Thanks.

Answer 1

Take tea, it will be long :)

I draw this with networkx , but the basic steps can be easily ported to graphviz.

The plan is as follows:
a) find the maximum clicks (just in case, the maximum clicks are not needed by the largest clicks),
b) draw a graph and remember the coordinates of the vertices that were used by the drawing program;
c) take the coordinates of the clique, calculate the center and radius of the circles surrounding it,
d) draw circles and color the vertices of the clicks of the same color (for vertices at the intersection of 2 or more maxcliques this is not possible).

Regarding c) : I was lazy to draw a narrow circle, but with some time it can be easily done. Instead, I calculated the “approaching circle”: I took the radius of the length of the longest edge of the clique and multiplied it by 1.3. In fact, with this approach, some nodes can be omitted, since only the sqrt (3) factor ensures that everyone is inside. However, taking sqrt (3) will make the circle too large (again, it is not hard). As a 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] 

Pic:

Another example with 3 maxcliques:

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

Answer 2

I do not think you can do this. Clusters run through subgraphs, which are expected to be separate graphs, rather than overlapping with other subgraphs.

However, you could change the visualization; if you imagine that clique members are members of some set S , then you can simply add node S and add directional or dotted edges that connect each member to S node. If the nodes S given a different form, then it should be clear which nodes are in clicks.

If you really want this, you can give the edges connecting the members, with their maximum clika node weights, which should bring them closer together on the graph.

Note that there will never be borders between click nodes; this indicates that the two clicks are maximally connected, which implies that they are in fact one big click and not two separate.

Answer 3

It would be difficult to implement, but here is an example of how to draw overlapping sets.

• Riche, NH; Dwyer, T., "Untangles Euler Diagrams", "IEEE Transactions on Visualization and Computer Graphics", vol.16, no.6, pp.1090-1099, November-December. 2010 DOI: 10.1109 / TVCG.2010.210 . Pdf