मेरे पास पुस्तकालय jgrapht के साथ प्रतिनिधित्व किया गया एक पेड़ है, विभिन्न प्रकार के नोड्स हैं जिन्हें मुझे किसी विशेष नोड प्रकार से शुरू होने वाले किसी भी उपट्री को काटने की आवश्यकता है।

graph example

जैसा कि आप इस उदाहरण में देख सकते हैं, यह पेड़ जावा वर्ग के स्रोत कोड का प्रतिनिधित्व करता है। मुझे प्रत्येक "एंट्री" नोड प्रकार के लिए शुरू होने वाले मुख्य पेड़ को विभाजित करके एकाधिक jgrapht ऑब्जेक्ट्स बनाने की आवश्यकता है। कुल मिलाकर मुझे इस बड़े वाले से ७ पेड़ मिलने चाहिए। मैं जिस संरचना का उपयोग करता हूं वह एक DirectedPseudograph है।

0
Philip 10 सितंबर 2019, 14:57

1 उत्तर

सबसे बढ़िया उत्तर

यद्यपि आप जो चाहते हैं उसके बारे में मैं 100% स्पष्ट नहीं हूं, ऐसा लगता है कि विभिन्न समाधान दृष्टिकोण हैं।

  1. रूट नोड के प्रत्येक आउटगोइंग पड़ोसी से शुरू करके, आप पहले गहराई से खोज कर सकते हैं और नोड्स को वापस रिकॉर्ड कर सकते हैं। डीएफएस एल्गोरिथम द्वारा पहुंच योग्य नोड्स एक ही सबट्री से संबंधित हैं। इसके लिए आप DepthFirstIterator
  2. आप रूट नोड के बिना एक सबग्राफ बना सकते हैं, उदाहरण के लिए AsSubgraph क्लास। इसके बाद आप ConnectivityInspector। चूंकि प्रत्येक सबट्री एक डिस्कनेक्टेड ग्राफ़ घटक है, इसलिए कनेक्टिविटी इंस्पेक्टर इनमें से प्रत्येक घटक को खोजने में सक्षम होगा।

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

1
Joris Kinable 11 सितंबर 2019, 18:40