Что я сделал в конце было:
- Проблема состоит в том, чтобы найти все пути длины N между двумя узлами. Циклы исключены.
- Считать данные в виде пограничного списка, например, пары узлов from-> to (имена узлов считаются уникальными)
- создать хеш-таблицу (или unordered_map в boost и stl, c ++) имен узлов в качестве ключей и хеш-таблицу в качестве значения.
- эта вторая хеш-таблица будет содержать все узлы, к которым первый узел приводит в качестве ключей.
Например
A->B
A->C
B->D
C->E
E->D
результирующая структура данных, содержащая входные данные в нотации perl, выглядит следующим образом после чтения всех данных в виде '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] : []
}
В вышеприведенной функции предусмотрено возвращение всех узлов, к которым подключен узел «из», путем установки $ to в «*». Возвращаемое значение - это ссылка на массив узлов, напрямую связанных с параметром $ from.
Поиск пути между двумя узлами требует рекурсивного использования вышеуказанной функции.
, например
sub path {
my ($from,$to, $hops, $save_results) = @_;
if( $hops < 0 ){ return 0 }
$results = search($from, '*');
if( "".@$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;
}
Можно использовать рекурсию, если глубина не слишком велика (то есть $ hops <6?) Из-за переполнения стека [sic]. </p>
Самая сложная часть - прочитать результаты и извлечь узлы для каждого пути. После долгих размышлений я решил использовать Tree :: Nary (n-ary tree) для хранения результатов. В конце у нас есть следующее дерево:
|-> B -> D
A -> |-> C -> E -> D
Чтобы извлечь все пути, выполните:
- найти все листовые узлы
- начинать с каждого конечного узла, перемещаясь назад через своего родителя к корневому узлу и сохраняя имя узла.
Выше было реализовано с использованием perl, но мы также сделали это на C ++, используя boost :: unordered_map для хеш-таблицы. Я еще не добавил древовидную структуру в код C ++.
Результаты: для 3281415 ребер и 18601 уникального узла perl требуется 3 минуты, чтобы найти A -> '*' -> '*' -> B. Я дам обновление кода C ++, когда будет готов.