नेटवर्क नोड्स में अन्य नोड्स/किनारों के साथ न्यूनतम ओवरलैप के साथ लेबल नोड्स

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() 

क्या नेटवर्कक्स में कोई फ़ंक्शन है जो ऐसी स्थिति से निपट सकता है। मैं बिना किसी सफलता के लंबे समय तक googled।

Answer 1

मैंने पहले मुख्य विचार के साथ कुछ किनारों के रास्ते से बाहर निकलने के लिए कुछ ऐसा करने का प्रयास किया है।

यह मानते हुए कि किनारों सीधी रेखाएं हैं, वहाँ इस लक्ष्य को हासिल करने के लिए दो सरल और इसी तरह के तरीके हैं: कोण है कि एक नोड के neighbourhood के किनारों नोड के संबंध में कर रहे हैं के आधार पर

1. अपने आप।

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 जैसे अधिक जटिल एल्गोरिदम जांचना चाहेंगे।

उम्मीद है कि इससे मदद मिलती है।