ग्राफ में क्रॉस एज को कम करें

Question

मैं अपने प्रोजेक्ट में से किसी एक के लिए नेटवर्कक्स (एक पायथन ग्राफ-ड्राइंग पैकेज) http://networkx.lanl.gov/index.html का उपयोग कर रहा हूं। हालांकि नेटवर्कक्स बहुत अच्छा है, डिस्प्ले फ़ंक्शन क्रॉस किनारों की संख्या के कारण बेकार है। क्या ग्राफ में क्रॉस एज को कम करने का कोई तरीका है? मेरा मतलब है कि एक एल्गोरिदम जो नोड्स को इस तरह से सॉर्ट कर सकता है जैसे क्रॉस किनारों को कम किया जाता है?

Answer 1

एक प्लानर ग्राफ लेआउट निर्धारित करना जो क्रॉसिंग की संख्या को कम करता है एनपी-हार्ड है। Crossing Number पर विकी पेज देखें।

आप कुछ ह्युरिस्टिक्स आज़मा सकते हैं, बल आधारित लेआउट काफी लोकप्रिय हैं मेरा मानना ​​है (ग्राफ़विज़ उनका उपयोग करता है, अगर मैं सही ढंग से याद करता हूं)।

आप कुछ अनुमानित एल्गोरिदम भी आज़मा सकते हैं, आपको लिंक किए गए विकी पेज पर संदर्भ मिलना चाहिए।

उम्मीद है कि मदद करता है।