न्यूनतम छेड़छाड़ लेआउट एल्गोरिदम

Question

मैं जानना चाहता हूं कि ग्राफ़ के लिए न्यूनतम अंतरंग लेआउट एल्गोरिदम (बल-आधारित नहीं) का कोई उदाहरण है, इसलिए मैं इसे d3.js. पर अनुकूलित कर सकता हूं।

Answer 1

किनारे क्रॉसिंग को कम करने वाले ग्राफ के लेआउट की गणना करना एनपी-हार्ड है, इसलिए कोई एकल एल्गोरिदम नहीं है; अलग-अलग व्यापार-बंद के साथ अलग-अलग एल्गोरिदम हैं। बल-आधारित लेआउट (Fruchterman–Reingold) एक दृष्टिकोण है, स्तरित (Sugiyama) दूसरा है। विशिष्ट प्रकार के ग्राफ, जैसे पेड़ (Reingold–Tilford) और छोटी दुनिया (van Ham–van Wijk) के लिए लेआउट भी हैं। डिग-कोला (Dwyer–Koren) जैसे सीमित लेआउट एल्गोरिदम का एक और वर्ग है।

यदि आप एक एल्गोरिदम चाहते हैं जो विशेष रूप से एज क्रॉसिंग की संख्या को कम करने की कोशिश करता है, तो आप simulated annealing का उपयोग कर सकते हैं। हालांकि अंत में यह सही जवाब मिलेगा, यह काफी धीमा हो सकता है।