label nodes outside with minimum overlap with other nodes/edges in networkx

user_1597034 0
Viewed 6456

I am trying to create a graph with node labels printed outside of nodes. I am able to generate 'offset' as shown below that solve the purpose. However, Sometimes the labels overlaps with edges (Which is undesirable as there are lots of empty spaces around nodes where the corresponding labels can be printed). I need to label these nodes in such a way that the labels does not overlap any edge or at least try to minimize overlap as much as possible. 

import networkx as nx
from networkx.utils import is_list_of_ints, flatten
import matplotlib.pyplot as plt

G=nx.Graph()

G = nx.complete_graph(5)
mapping = {0:'aaaaaaa',1:'bbbbbbb',2:'ccccccc', 3:'dddddddd', 4:'eeeeeeeee'}
G = nx.relabel_nodes(G,mapping)

plt.figure(figsize=(10,10), facecolor="w", frameon=False)
pos = nx.graphviz_layout(G, prog="fdp") #calculate position (x,y) coordinates
nx.draw_networkx_nodes(G,pos,node_size=1200,node_shape='o',node_color='0.75')
nx.draw_networkx_edges(G,pos, width=2,edge_color='b')


#for labeling outside the node
offset =10
pos_labels = {}
keys = pos.keys()
for key in keys:
    x, y = pos[key]
    pos_labels[key] = (x, y+offset)
nx.draw_networkx_labels(G,pos=pos_labels,fontsize=2)
plt.show()

Is there any function in networkx that can deal with such situation. I googled for long with no success.

networkx nodes label python
2 Answers

The approaches outlined by @A_A are built on good intuitions and are decent first approximations. However, apart from the problems already mentioned by @A_A, there are some additional issues with both approaches.

  1. Both approaches only reduce label-edge overlaps if all edges in the (Euclidean) vicinity of a node also belong to that node. However, if the graph is large or dense, the majority of the edges in the vicinity of a node can belong to other nodes, which neither approach takes into account.

  2. Even though both approaches typically reduce label-edge overlaps in small and sparse graphs, neither approach addresses label-node and label-label overlaps.

There is a conceptually simple approach that also resolves label-node and label-label overlaps: draw a circle around each node being labelled. On each circle, find the point that is furthest away from everything else (nodes, edges, other labels). This ensures that this position on the circle has the most empty canvas around it, and is thus a good place to put a label.

This can be done in the following way:

  1. Approximate each edge with a series of points densely sampled along the edge. In practice, 10-20 points seem to work well enough, but even 100-1000 points are computationally easily tractable. Make sure to include the start and end points of the edge, i.e. the node positions.

  2. For each label, compute a second set of points sampled along a circle around the corresponding node. Again, 35 points (one point for every 10 degrees) are usually more than enough, but there is no substantial harm in using more points, say 100.

  3. For each circle, find the point on the circle whose nearest Euclidean neighbour is maximally far away (while excluding points on the same circle). Place the label there.

Step 3 can be further refined to use the maximum average distance of the nearest two neighbours. This resolves ties, which can occur when the node is on the periphery of the graph, such that the nearest neighbour for a large section of the circle is the node being labelled.

All of this may sound horrific from a numerical perspective. However, nearest neighbour distances can be computed very efficiently by using KD-trees, as demonstrated below (using 100 points to approximate each edge and circle).

enter image description here

This approach is implemented in netgraph, a python library for visualising networks (I am the author). The library is fully compatible with most common graph data formats, including networkx and igraph Graph objects, so it should be easy and fast to make great looking graphs of graphs. At least that is the idea.

Code to reproduce the animation (mouse movements not included):

#!/usr/bin/env python
import matplotlib.pyplot as plt
import networkx as nx
from netgraph import InteractiveGraph # pip install netgraph

g = InteractiveGraph(nx.complete_graph(10), node_size=2, edge_width=0.5,
                     node_labels=dict(zip(range(10), 'abcdefghij')), node_label_offset=0.05,
                     node_label_fontdict=dict(size=20, fontweight='bold'))
plt.show()
user_29123490
Related