प्लानर ग्राफ़ लेआउट

Question

ग्राफ़ डालने पर कुछ किनारे ओवरलैप न्यूनतम तकनीकों क्या हैं? (पसंदीदा रूप से ग्राफवीज़ से संबंधित) क्या कोई मौजूदा सॉफ़्टवेयर भी है जो एक प्लानर फैशन में ग्राफ़ लेआउट कर सकता है?

वर्तमान लेआउट - http://www.evecakes.com/doodles/master.gif

ऊपरी बाएँ हाथ के कोने में गुलाबी अनुभाग ठीक है, जबकि हल्के नीले रंग अनुभाग कुछ परिहार्य बढ़त overlaps है लग रहा है।

Answer 1

सामान्य ग्राफ के लिए, ग्राफ के प्लानर लेआउट को निर्धारित करने की समस्या कम से कम किनारों को पार करने (Crossing Number) एनपी-हार्ड है। तो कुछ ह्युरिस्टिक विधियों का उपयोग किया जाता है (जैसे Force based layout एल्गोरिदम)।

नीचे दिया गया पृष्ठ संक्षेप में ग्राफविज़ एल्गोरिदम का वर्णन करता है और लाभ के लिए उनका उपयोग करने के कुछ तरीकों का सुझाव देता है। यह भी pdfs जो एल्गोरिदम बारे में अधिक जानकारी शामिल करना चाहिए करने के लिए लिंक है:

http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html

आशा है कि मदद करता है।

Answer 2

निम्नलिखित ओपन सोर्स जावा लाइब्रेरी में कुछ एल्गोरिदम हैं जो प्लानर ग्राफ़ डालने में मदद कर सकते हैं। http://open.trickl.com/trickl-graph/index.html

विशेष रूप से, निम्नलिखित वर्गों समस्या के लिए विश्लेषणात्मक समाधान प्रदान करते हैं: (बूस्ट सी के आधार पर ++ हारून विंडसर द्वारा कार्यान्वयन)

ChrobakPayneLayout http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreeLayout (एंकर के आधार पर - सेंसर नेटवर्क में फ्री वितरित स्थानीयकरण * निसानका बी प्रियंथा, हरि बालकृष्णन, एरिक डेमैन और सेठ टेलर)

आप जो करना चाहते हैं वह ऐसा पहला "प्रयास" के रूप में उपयोग करना है जो कोई ओवरलैप सुनिश्चित नहीं करता है, हालांकि यह शानदार नहीं लग सकता है। फिर आप नोड्स को अधिक उचित रूप से स्थानांतरित करने के लिए एक बल-निर्देशित एल्गोरिदम लागू कर सकते हैं।

दुर्भाग्यवश, लाइब्रेरी केवल रिलीज़ हो गई है, इसलिए दस्तावेज़ीकरण पर छोटा है। हालांकि यह सिद्धांत के बजाए कुछ वास्तविक कोड प्रदान करके उपयोगी हो सकता है।