2011-08-25 18 views
6

में द्वीप खोजें I गरीब निर्भरता प्रबंधन के साथ एक अस्पष्ट भाषा में काम कर रहा हूं। 14000 फ़ाइल कोडबेस की सहायता के लिए, मैंने कुछ पार्सिंग टूल (जावा में) लिखा है और एक निर्भरता ग्राफ उत्पन्न किया है।निर्देशित ग्राफ

मैंने अपना खुद का ग्राफ और बीएफएस कक्षाएं लिखीं, और वे ठीक काम करते हैं। उनके साथ, मेरे पास getParents() और getChildren() जैसी विधियां हैं।

अब मैं इस ग्राफ में 'द्वीप' ढूंढने की कोशिश कर रहा हूं; यह कहना है, मैं यह जानने की कोशिश कर रहा हूं कि हमारे कोडबेस के कौन से वर्ग एक दूसरे पर निर्भर नहीं हैं, उन्हें अलग मॉड्यूल में इकट्ठा करने की उम्मीद में।

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

अभी, मैं ऐसा करने का सोच रहा हूँ:

Map<DependencyEntry, Set<DependencyEntry>> allChildren = new ...; 
for(DependencyEntry entry : allFiles) allChildren.put(entry,getAllChildren(entry)); 
Set<DependencyEntry> visited = new ...; 
Set<DependencyEntry> largest = new HashSet<DependencyEntry>(); // size 0 
// slightly more expensive but more readable 
for(DependencyEntry entry : allChildren.keySet()) { 
    Set<DependencyEntry> set = allChildren.get(key); 
    if(set.size() > largest.size()) largest = set; 
} 
visited.addAll(largest); 

यह मैं सबसे बड़ा द्वीप देना चाहिए। वहां से, मैं किसी भी सेट को छोड़कर बाहर कर सकता हूं जिसमें किसी भी नजदीक नोड्स शामिल हैं, और फिर इसे अगले सबसे बड़े द्वीप, और आगे के लिए फिर से चलाएं।

क्या यह एक सटीक एल्गोरिदम है? क्या इस समस्या को हल करने का कोई बेहतर तरीका है जिसे मैं नहीं देख रहा हूं?

+0

दिलचस्प सवाल देखते हैं, कैसे मैं YY भाषा में XX करते हैं या त्रुटि कोड के साथ 0x34 सवालों में मदद करते हैं! – GBa

उत्तर

2

लगता है जैसे आप निर्भरता ग्राफ में connected components का संग्रह बनाना चाहते हैं। वहां से आप संग्रह को फिर से शुरू कर सकते हैं और सबसे बड़े घटक (या किसी अन्य दिलचस्प मीट्रिक) की पहचान कर सकते हैं।

1

ग्राफ लाइब्रेरी का उपयोग करना आसान होता, क्योंकि इस तरह की चीजें अंतर्निहित हैं। आम तौर पर वे आपको नोड्स, किनारों में मनमाने ढंग से जानकारी स्टोर करने देते हैं, ताकि आप डेटा के लिए अपने स्वयं के वर्गों का उपयोग कर सकें, लेकिन लाइब्रेरी समर्थन और मानक एल्गोरिदम प्रदान करती है।

एल्गोरिदम जैसा कि आप वर्णन करते हैं, यह रूट नोड्स पर थोड़ा अस्पष्ट लगता है। यदि आप रूट पर शुरू नहीं करते हैं तो आपको "पूरा द्वीप" नहीं मिलेगा - बस नीचे दिए गए हिस्सों (बच्चों) जहां आपने शुरू किया था। आप माता-पिता और बच्चों का पालन करके इसे ठीक कर सकते हैं। इसके अलावा, यह ठीक लगता है - यह पॉलफ के जवाब के रूप में कर रहा है, जहां तक ​​मैं कह सकता हूं, और जुड़े घटकों को ढूंढ रहा हूं।

से परिवर्तन ताज़ा भी Good Java graph algorithm library?

संबंधित मुद्दे