मैं अंत में क्या किया था:
- समस्या 2 नोड्स के बीच लंबाई एन के सभी रास्तों को मिल रहा है। चक्रों को बाहर रखा गया है।
- डेटा को एक edgelist के रूप में पढ़ें, उदा। से-> नोड्स के जोड़े (नोड्स के नाम अद्वितीय होने के लिए माना जाता है)
- नोड नामों के एक हैशटेबल (या बूस्ट और एसटीएल, सी ++ में unordered_map) कुंजी के रूप में और एक हैशटेबल को मान के रूप में बनाएं।
- इस दूसरे हैशटेबल में सभी नोड्स होंगे जिनमें पहला नोड कुंजी के रूप में जाता है।
उदाहरण के लिए
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
आदेश सभी रास्ते निकालने के लिए, कार्य करें::
- सभी पत्र-गांठ को खोजने के प्रत्येक पत्ते नोड से
- शुरू अपनी मूल के माध्यम से पीछे की ओर आगे बढ़ अंत में हम निम्नलिखित पेड़ है रूट नोड और नोड नाम को बचाने के लिए।
उपरोक्त को perl का उपयोग करके कार्यान्वित किया गया था, लेकिन हैशटेबल के लिए boost :: unordered_map का उपयोग करके इसे C++ में भी किया है। मैंने अभी तक सी ++ कोड में एक वृक्ष संरचना नहीं जोड़ा है।
परिणाम: 3281415 किनारों और 18601 अद्वितीय नोड्स के लिए, ए -> '*' -> '*' -> बी खोजने के लिए perl में 3 मिनट लगते हैं। तैयार होने पर मैं सी ++ कोड पर एक अपडेट दूंगा।
यह सब मुझे मिल सकता है: http: //www.vldb.org/conf/1989/P185.PDF – Diego
क्या पथ सरल पथ होने की आवश्यकता है? या क्या उनके चक्र हो सकते हैं? – templatetypedef
चक्र होने से समाधान का एक अनंत सेट इंगित होगा। – Faylixe