外部標籤節點與網絡x中其他節點/邊緣的最小重疊

Question

我試圖創建一個節點標籤在節點外部打印的圖。我能夠生成如下所示的'抵消'，以解決目的。但是，有時候標籤會與邊緣重疊（這是不理想的，因爲節點周圍有很多可以打印相應標籤的空白空間）。我需要爲這些節點添加標籤，使標籤不會與任何邊緣重疊，或者儘可能地儘量減少重疊。

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可以對付這種情況的任何功能。我搜索了很長時間沒有成功。

Answer 1

我以前曾嘗試過一些類似的主要想法，主要是避開邊緣的方式。

假設邊緣是直線，有兩種簡單和類似的方式來實現這一點：

1. 在那個節點的neighbourhood的邊緣相對於使該節點的角度的基礎本身。

2. 根據鄰域節點的centroid。

因此，發現從節點出發的邊朝其附近的形式角度，嘗試從多數邊緣的離開位置的標籤;或者估計節點鄰域的質心，並沿相反方向定位標籤。

第一溶液可以是一點點有問題的，這主要是因爲該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」 spring layout輸出。

請注意綠色和黑色標籤上第二個數字接近。本質上，ddddddd的鄰域的質心相對接近節點的實際位置。

對於更復雜的解決方案，您可能需要檢查更復雜的算法，如the one that is used by Wordle，以便在標籤的初始位置與邊相交時調整其初始位置。

希望這會有所幫助。