标记外部的节点，使其与networkx中的其他节点/边缘最小重叠 [英] label nodes outside with minimum overlap with other nodes/edges in networkx
问题描述
我正在尝试创建一个带有在节点外部打印的节点标签的图形.我能够生成如下所示的偏移"来解决此目的.但是，有时标签与边缘重叠(这是不希望有的，因为节点周围有很多空白空间，可以打印相应的标签).我需要以以下方式标记这些节点:标记不重叠任何边缘，或者至少尝试尽可能减少重叠.
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()
networkx中是否有任何功能可以应对这种情况.我用谷歌搜索了很长时间，没有成功.
我以前曾尝试过类似的方法，其主要思想是尽可能避开边缘.
假设边缘是直线，可以通过两种简单且相似的方法来实现:
因此，找到边缘从节点朝向其邻域形式的角度，并尝试将标签远离大多数边缘放置；或估计节点邻域的质心，然后沿相反方向放置标签.
第一个解决方案可能会有些问题，主要是因为 atan2 函数可以运行(这基本上确定了边缘角度)，但确实在标签定位方面提供了一定的灵活性.
第二种解决方案最简单，其工作方式如下:
import networkx as nx
import matplotlib.pyplot as plt
#Build the graph
#Please note, the code here is as per the original post
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)
#Get a graph layout
pos = nx.graphviz_layout(G, prog="fdp") #calculate position (x,y) coordinates
#Here is an alternative layout, please see below.
#pos = nx.layout.spring_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=1200,node_shape='^',node_color='0.75')
nx.draw_networkx_edges(G,pos, width=2,edge_color='r')
#Show the original position of the labels using a Green colour.
nx.draw_networkx_labels(G,pos,font_color='g')
#Please note, the code below uses the original idea of re-calculating a dictionary of adjusted label positions per node.
label_ratio = 1.0/8.0
pos_labels = {}
#For each node in the Graph
for aNode in G.nodes():
#Get the node's position from the layout
x,y = pos[aNode]
#Get the node's neighbourhood
N = G[aNode]
#Find the centroid of the neighbourhood. The centroid is the average of the Neighbourhood's node's x and y coordinates respectively.
#Please note: This could be optimised further
cx = sum(map(lambda x:pos[x][0], N)) / len(pos)
cy = sum(map(lambda x:pos[x][1], N)) / len(pos)
#Get the centroid's 'direction' or 'slope'. That is, the direction TOWARDS the centroid FROM aNode.
slopeY = (y-cy)
slopeX = (x-cx)
#Position the label at some distance along this line. Here, the label is positioned at about 1/8th of the distance.
pos_labels[aNode] = (x+slopeX*label_ratio, y+slopeY*label_ratio)
#Finally, redraw the labels at their new position.
nx.draw_networkx_labels(G,pos=pos_labels,fontsize=2)
#Show the figure
plt.show()
大多数情况下，此方法适用于大部分位于图外围的节点，但对于朝向图中心定位的节点则具有挑战性，因为质心无法提供可避免大部分边缘的可靠方向.
以下是graphviz的 fdp 布局的输出...
...这是networkx的输出 Wordle所使用的一种语言，用于在标签与边缘相交时适应标签的初始位置.
希望这会有所帮助.
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.
I have previously attempted something similar with the main idea being to keep out of the way of the edges mostly.
Assuming that the edges are straight lines, there are two simple and similar ways to achieve this:
On the basis of the angles that the edges of a node's neighbourhood are making with respect to the node itself.
On the basis of the centroid of the neighbourhood's nodes.
So, find the angles that the edges departing from a node towards its neighbourhood form and try to position the label AWAY from the majority of the edges; OR estimate the centroid of a node's neighbourhood and position the label along the opposite direction.
The first solution can be a little bit problematic, primarily because of the way that the atan2 function operates (which essentially determines the edge angles) but it does provide some flexibility in terms of positioning the label.
The second solution is the simplest and works as follows:
import networkx as nx
import matplotlib.pyplot as plt
#Build the graph
#Please note, the code here is as per the original post
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)
#Get a graph layout
pos = nx.graphviz_layout(G, prog="fdp") #calculate position (x,y) coordinates
#Here is an alternative layout, please see below.
#pos = nx.layout.spring_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=1200,node_shape='^',node_color='0.75')
nx.draw_networkx_edges(G,pos, width=2,edge_color='r')
#Show the original position of the labels using a Green colour.
nx.draw_networkx_labels(G,pos,font_color='g')
#Please note, the code below uses the original idea of re-calculating a dictionary of adjusted label positions per node.
label_ratio = 1.0/8.0
pos_labels = {}
#For each node in the Graph
for aNode in G.nodes():
#Get the node's position from the layout
x,y = pos[aNode]
#Get the node's neighbourhood
N = G[aNode]
#Find the centroid of the neighbourhood. The centroid is the average of the Neighbourhood's node's x and y coordinates respectively.
#Please note: This could be optimised further
cx = sum(map(lambda x:pos[x][0], N)) / len(pos)
cy = sum(map(lambda x:pos[x][1], N)) / len(pos)
#Get the centroid's 'direction' or 'slope'. That is, the direction TOWARDS the centroid FROM aNode.
slopeY = (y-cy)
slopeX = (x-cx)
#Position the label at some distance along this line. Here, the label is positioned at about 1/8th of the distance.
pos_labels[aNode] = (x+slopeX*label_ratio, y+slopeY*label_ratio)
#Finally, redraw the labels at their new position.
nx.draw_networkx_labels(G,pos=pos_labels,fontsize=2)
#Show the figure
plt.show()
This works, mostly, for nodes that are largely in the periphery of the Graph but is challenging for nodes that are positioned towards the centre of the graph because the centroid will not provide a reliable direction that avoids the majority of the edges.
Here is the output for graphviz's fdp layout...
...and here is the output for networkx' spring layout.
Please note the proximity of the green and black coloured labels on the second figure. Essentially, the centroid of ddddddd's neighbourhood is relatively close to the node's actual position.
For a more complex solution, you might want to check more complex algorithms such as the one that is used by Wordle in order to adapt the initial position of the label if it intersects an edge.
Hope this helps.
这篇关于标记外部的节点，使其与networkx中的其他节点/边缘最小重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
