Những gì tôi đã làm ở cuối là:
- Vấn đề là để tìm tất cả những con đường có chiều dài N giữa 2 nút. Chu kỳ được loại trừ.
- đọc dữ liệu dưới dạng edgelist, ví dụ: các cặp từ-> đến các nút (tên của các nút được giả định là duy nhất)
- tạo một hashtable (hoặc unordered_map trong boost và stl, C++) của các tên nút làm khóa và một hashtable dưới dạng một giá trị.
- thứ hai có thể bắt đầu này sẽ chứa tất cả các nút mà nút đầu tiên dẫn đến dưới dạng khóa.
Ví dụ
A->B
A->C
B->D
C->E
E->D
cấu trúc dữ liệu kết quả tổ chức các dữ liệu đầu vào trong ký hiệu perl trông như thế này sau khi đọc trong tất cả các dữ liệu như là một 'edgelist':
my %hash = (
'A' => {'B' => 1, 'C' => 1},
'B' => {'D' => 1},
'C' => {'E' => 1},
'E' => {'D' => 1},
);
tìm nếu một cặp nút được kết nối TRỰC TIẾP có thể được thực hiện gần như (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] : []
}
Trong hàm trên có điều khoản trả về tất cả các nút mà nút 'từ' được kết nối, bằng cách đặt $ thành '*'. Sự trở lại là một mảng ref của các nút kết nối trực tiếp với tham số $ from.
Tìm kiếm đường dẫn giữa hai nút yêu cầu sử dụng hàm ở trên một cách đệ quy.
ví dụ:
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;
}
Đó là ok để sử dụng đệ quy nếu độ sâu không phải là quá nhiều (ví dụ: $ nhảy < 6?) Vì stack overflow [sic].
Phần khó khăn nhất là đọc qua các kết quả và trích xuất các nút cho mỗi đường dẫn. Sau nhiều lần cân nhắc, tôi quyết định sử dụng Tree :: Nary (n-ary tree) để lưu trữ kết quả. Cuối cùng chúng ta có cây sau:
|-> B -> D
A -> |-> C -> E -> D
Để trích xuất tất cả các đường dẫn, làm:
- tìm tất cả các nút lá
- bắt đầu từ mỗi nút lá di chuyển ngược qua mẹ vào nút gốc và lưu tên nút.
Ở trên đã được triển khai bằng cách sử dụng perl, nhưng cũng đã thực hiện nó trong C++ bằng cách sử dụng boost :: unordered_map cho hashtable. Tôi chưa thêm một cấu trúc cây vào sau đó mã C++.
Kết quả: cho 3281415 cạnh và 18601 nút duy nhất, perl mất 3 phút để tìm A -> '*' -> '*' -> B. Tôi sẽ cập nhật mã C++ khi sẵn sàng.
Đây là tất cả những gì tôi có thể tìm thấy: http: //www.vldb.org/conf/1989/P185.PDF – Diego
Các đường dẫn có phải là đường dẫn đơn giản không? Hoặc họ có thể có chu kỳ? – templatetypedef
Có chu kỳ sẽ ngụ ý một tập hợp vô hạn của giải pháp. – Faylixe