एक बड़े (~ 300k शिखर) यादृच्छिक प्लानर ग्राफ ("यादृच्छिक" यहां समान रूप से वितरित करने का अर्थ है) उत्पन्न करने का सबसे प्रभावी तरीका क्या है? और देखें कि क्या इसे प्रयोग हे (एन) समय में समतल है -एक बड़ा यादृच्छिक प्लानर ग्राफ़ उत्पन्न करें
खैर एक विधि कोशिश करते हैं और एक यादृच्छिक ग्राफ जो एक समतल ग्राफ के रूप में इसी तरह की बाधाओं को संतुष्ट करता है उत्पन्न करने के लिए (6 उदाहरण के लिए, किनारों < = 3 * कोने) होगा तारजन की प्लानरिटी परीक्षण एल्गोरिदम। यदि यह प्लानर नहीं है, तो फिर से उत्पन्न करें। यह सुनिश्चित नहीं है कि 300K शिखर के लिए यह कितना कुशल होगा !, हालांकि (या यदि यह आपको समान संभावना के साथ ग्राफ भी देगा)।
प्लानर ग्राफ बनाने पर कुछ साहित्य हैं, मुझे यहां एक पेपर मिल सकता है: Generating Labeled Planar Graphs जो स्पष्ट रूप से ओ (एन^4) चलने का समय अपेक्षित है, और शायद इसके लायक नहीं हो सकता है। शायद वहां के संदर्भ आपको उस चीज़ को ट्रैक करने में मदद करेंगे जो मदद कर सकता है।
शुभकामनाएं!
किसी अन्य आवश्यकता के बिना, मैं कहूंगा कि यादृच्छिक भूलभुलैया पीढ़ी देखें। यदि आप ग्राफ में चक्र चाहते हैं, तो कुछ दीवारों को यादृच्छिक रूप से एक साधारण भूलभुलैया से हटा दें। भूलभुलैया में चौराहे आपके ग्राफ में नोड्स बन जाते हैं और हटाए गए दीवार किनारों पर होते हैं। इसका मतलब है कि आप भूलभुलैया का आकार चुनकर नोड्स की संख्या का चयन कर सकते हैं।
माज़ आमतौर पर 2 डी ग्रिड पर एक बिंदु से दूसरे में 4 कनेक्शन के साथ किया जाता है, लेकिन हेक्स टाइल्स या किसी और चीज़ पर भूलभुलैया करने से आपको कुछ भी नहीं रोकता है।
यदि वर्दी से आप अंतरिक्ष में समान रूप से वितरित होते हैं, तो यह एक बहुत तेज़ एल्गोरिदम है जिसे मैंने एक स्थानिक पारिस्थितिक/विकासवादी सिम्युलेटर के लिए प्लानर ग्राफ बनाने के लिए विकसित किया है। यह आपके द्वारा निर्दिष्ट अपेक्षित डिग्री के साथ यादृच्छिक प्लानर ग्राफ उत्पन्न करेगा, निश्चित रूप से इसके आसपास कुछ भिन्नता के साथ। यदि आप अपने प्लानर ग्राफ में वर्दी यादृच्छिक डिग्री चाहते हैं तो आप एक समान यादृच्छिक संख्या के आधार पर अपेक्षित डिग्री चुनने के लिए इसे बढ़ा सकते हैं।
https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py
ऐसा लगता है कि यह एल्गोरिदम ग्राफ उत्पन्न कर सकता है जिसका किनारों पार हो जाते हैं? यह एक प्लानर ग्राफ नहीं है। उदाहरण के लिए, यदि दिए गए त्रिज्या के एक सर्कल में 4 अंक हैं, तो वे सभी एक-दूसरे से जुड़ जाएंगे और ग्राफ गैर-प्लानर बनाने के लिए विकर्ण पार हो जाएंगे। –
एक और संभावना में होते हैं (और अच्छे रूप में अच्छी तरह दिखता है) बेतरतीब ढंग से निर्देशांक चुनने और उसके बाद की गणना एक डेलॉनाय त्रिकोणीयकरण है, जो एक समतल ग्राफ है। http://en.wikipedia.org/wiki/Delaunay_triangulation देखें इस तरह के त्रिभुज की गणना करने के लिए ओ (एन लॉग (एन)) एल्गोरिदम हैं।
लेकिन यह डिग्री 3 तय कर देगा? –
इसमें निश्चित डिग्री 3 नहीं होगी, लेकिन यह प्लानर होगा। –
ओह, क्षमा करें, आप सही हैं - मैं दोहरी सोच रहा हूं। –
क्या आपने बोल्टज़मान नमूना देखा है? एरिक फूसी द्वारा पेपर देखें "रैखिक समय में प्लानर ग्राफ के समान यादृच्छिक नमूनाकरण"। कागज और कार्यान्वयन उनके homepage में उपलब्ध है जो पेपर कहता है कि कुछ सेकंड में आकार 100K के उदाहरण उत्पन्न कर सकते हैं।
निश्चित रूप से लगभग सभी यादृच्छिक ग्राफ प्लानर नहीं हैं? –