2012-02-17 20 views
5

सहित नोड्स की सूची का उपयोग कर सबग्राफ ढूंढें क्या निम्नलिखित समस्या का नाम है और क्या इसे हल करने के लिए कोई एल्गोरिदम है? : एक ग्राफ को देखते हुए, या तो निर्देशित है या नहीं, सभी रास्ते जो विनिर्देश सटीक नोड्स की एक सूची सेग्राफ: वाइल्डकार्ड

  1. दिया संतुष्ट, या
  2. लगता है '*?' जो सिर्फ 'किसी भी नोड या फिर कोई नोड', या
  3. '* {n}' जो निरूपित 'किसी भी n लगातार जुड़े हुए नोड'

जैसे अर्थ है

A -> B -> *? -> D which results in ABXD and ABYD and ABD etc. 

या

A -> *{1} -> D -> *? -> E which results in ABXDZE and ABYDZE and ABDZE etc. etc. 

धन्यवाद

पी.एस. क्या कोई भी आर या पर्ल या सी में ऐसा करने वाली ग्राफ लाइब्रेरी को जानता है?

+0

यह सब मुझे मिल सकता है: http: //www.vldb.org/conf/1989/P185.PDF – Diego

+0

क्या पथ सरल पथ होने की आवश्यकता है? या क्या उनके चक्र हो सकते हैं? – templatetypedef

+0

चक्र होने से समाधान का एक अनंत सेट इंगित होगा। – Faylixe

उत्तर

1

मैं अंत में क्या किया था:

  1. समस्या 2 नोड्स के बीच लंबाई एन के सभी रास्तों को मिल रहा है। चक्रों को बाहर रखा गया है।
  2. डेटा को एक edgelist के रूप में पढ़ें, उदा। से-> नोड्स के जोड़े (नोड्स के नाम अद्वितीय होने के लिए माना जाता है)
  3. नोड नामों के एक हैशटेबल (या बूस्ट और एसटीएल, सी ++ में unordered_map) कुंजी के रूप में और एक हैशटेबल को मान के रूप में बनाएं।
  4. इस दूसरे हैशटेबल में सभी नोड्स होंगे जिनमें पहला नोड कुंजी के रूप में जाता है।

उदाहरण के लिए

A->B 
A->C 
B->D 
C->E 
E->D 

परिणामी डेटा संरचना पर्ल अंकन में इनपुट डेटा धारण करने वाले 'edgelist' के रूप में सभी डेटा में पढ़ने के बाद इस तरह दिखता है:

my %hash = (
'A' => {'B' => 1, 'C' => 1}, 
'B' => {'D' => 1}, 
'C' => {'E' => 1}, 
'E' => {'D' => 1}, 
); 

अगर खोजने नोड्स की एक जोड़ी प्रत्यक्ष रूप से कनेक्ट की जा सकती है (perl):

sub search { 
    my ($from,$to) = @_; 
    if($to eq '*'){ return defined($x=$hash{$from}) ? [keys $hash{$from}] : [] } 
    return defined($x=$hash{$from}) && defined($x{$to}) ? [$to] : [] 
} 

उपरोक्त फ़ंक्शन में $ 'से' को सेट करके, 'से' नोड से जुड़े सभी नोड्स को वापस करने का प्रावधान है। रिटर्न पैरामीटर से सीधे $ से जुड़े नोड्स का एक सरणी रेफरी है।

दो नोड्स के बीच पथ की खोज करने के लिए उपर्युक्त फ़ंक्शन का पुनरावृत्ति उपयोग करना आवश्यक है।

उदा।

sub path { 
    my ($from,$to, $hops, $save_results) = @_; 
    if($hops < 0){ return 0 } 
    $results = search($from, '*'); 
    if(""[email protected]$results == 0){ return 0 } 
    $found = 0; 
    foreach $result (@$results){ 
     $a_node = new Tree::Nary($result); 
     if(path($result, $to, $hops-1, $a_node) == 1){ 
      $save_results->insert($save_results, -1, $a_node); 
      $found = 1; 
     } 
    } 
    return $found; 

}

यह प्रत्यावर्तन उपयोग करने के लिए ठीक है अगर गहराई बहुत ज्यादा नहीं है [वैसा] ढेर अतिप्रवाह की वजह से (अर्थात $ < 6 होप्स?)।

सबसे कठिन हिस्सा परिणामों के माध्यम से पढ़ने और प्रत्येक पथ के लिए नोड निकालने के लिए है। कई विचार-विमर्श के बाद मैंने परिणामों को संग्रहीत करने के लिए वृक्ष :: नारी (एन-आरी पेड़) का उपयोग करने का निर्णय लिया।

 |-> B -> D 
A -> |-> C -> E -> D 

आदेश सभी रास्ते निकालने के लिए, कार्य करें::

  1. सभी पत्र-गांठ को खोजने के प्रत्येक पत्ते नोड से
  2. शुरू अपनी मूल के माध्यम से पीछे की ओर आगे बढ़ अंत में हम निम्नलिखित पेड़ है रूट नोड और नोड नाम को बचाने के लिए।

उपरोक्त को perl का उपयोग करके कार्यान्वित किया गया था, लेकिन हैशटेबल के लिए boost :: unordered_map का उपयोग करके इसे C++ में भी किया है। मैंने अभी तक सी ++ कोड में एक वृक्ष संरचना नहीं जोड़ा है।

परिणाम: 3281415 किनारों और 18601 अद्वितीय नोड्स के लिए, ए -> '*' -> '*' -> बी खोजने के लिए perl में 3 मिनट लगते हैं। तैयार होने पर मैं सी ++ कोड पर एक अपडेट दूंगा।

+0

ओह, बीटीडब्ल्यू एक बड़ी फाइल पढ़ने में भी एक विषय है। फ़ाइलफॉर्मेट नोड नामों के जोड़े हैं जो स्वयं की रेखा पर सफेद जगह से अलग होते हैं। पर्ल में, रेखा से रेखा को पढ़ना ठीक है और फिर प्रत्येक पंक्ति को पढ़ने के बाद विभाजित करना ठीक है। फ़ाइल को पहले मेमोरी में पढ़ना और फिर रेगेक्स के माध्यम से लूपिंग लगभग एक ही समय लेता है। सी ++ में, मैंने एक पंक्ति को नोड नामों में विभाजित करने के लिए boost :: split का उपयोग किया।रेखा से एक फ़ाइल लाइन पढ़ना (सी के फॉपेन और फाग्स का उपयोग करना) इसे स्मृति में पढ़ने से थोड़ा धीमा है (सी के पढ़ने() का उपयोग करके) और फिर बूस्ट :: स्प्लिट का उपयोग करके इसे स्मृति में विभाजित करना, लगभग 10% धीमा। – bliako

1

मुझे लगता है कि किसी भी पुस्तकालय पता नहीं, लेकिन आप दो भाग में इस अलग करने के लिए है:

  • उपयोगकर्ता क्वेरी को पार्स
  • एल्गोरिथ्म आप के लिए

के लिए क्या देख रहे लगाने के लिए पार्सिंग, मैं आपको यह जानने देता हूं कि आपको क्या करना है (पार्सिंग लाइब्रेरी या अपने आप से)

एल्गोरिदम भाग के बारे में मैं आपको एक विशेष संरचना को परिभाषित करने का सुझाव देता हूं (एक लिंक्ड सूची की तरह) आपको क्वेरी का प्रतिनिधित्व करने के लिए, जिसमें प्रत्येक तत्व या तो वास्तविक नोड, नोड की एक्स संख्या, या नोड्स की असीमित संख्या को दर्शा सकता है।

आपके एल्गोरिदम पर एकमात्र समस्या एक असीमित संख्या या इंटरमीडिएट नोड्स की सीमित संख्या का उपयोग करके नोड ए से नोड बी तक सभी पथ ढूंढना है। आप गतिशील प्रोग्रामिंग, या एक खोज एल्गोरिदम जैसे डीएफएस या बीएफएस का उपयोग करके ऐसा कर सकते हैं।