Lo que hice al final fue:
- El problema es encontrar todos los caminos de longitud N entre 2 nodos. Los ciclos están excluidos.
- lee los datos como edgelist, p. pares de from-> a nodos (se supone que los nombres de los nodos son únicos)
- crean una tabla hash (o unordered_map en boost y stl, C++) de nombres de nodo como claves y una tabla hash como un valor.
- esta segunda tabla hash contendrá todos los nodos que el primer nodo lleva como claves.
Por ejemplo
A->B
A->C
B->D
C->E
E->D
la estructura de datos resultante que contiene los datos de entrada en notación Perl se parece a esto después de leer todos los datos como un 'edgelist':
my %hash = (
'A' => {'B' => 1, 'C' => 1},
'B' => {'D' => 1},
'C' => {'E' => 1},
'E' => {'D' => 1},
);
encontrar si un par de nodos está DIRECTAMENTE conectado se puede hacer más o menos como (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] : []
}
En la función anterior hay una provisión para devolver todos los nodos a los que está conectado un nodo 'from', configurando $ to a '*'. El retorno es una referencia de matriz de nodos conectados directamente al parámetro $ from.
La búsqueda de la ruta entre dos nodos requiere el uso recursivo de la función anterior.
p. Ej.
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;
}
Es aceptable utilizar la recursividad si la profundidad no es demasiado (es decir, $ lúpulo < 6?), Debido a desbordamiento de pila [sic].
La parte más complicada es leer los resultados y extraer los nodos para cada ruta. Después de mucha deliberación, decidí usar Tree :: Nary (árbol n-ary) para almacenar los resultados. Al final tenemos el siguiente árbol:
|-> B -> D
A -> |-> C -> E -> D
Con el fin de extraer todos los caminos, hacer:
- encontrar todos los nodos hoja
- inicio de cada nodo hoja se mueve hacia atrás a través de su matriz al nodo raíz y guardando el nombre del nodo.
Lo anterior se implementó utilizando perl, pero también lo hemos hecho en C++ utilizando boost :: unordered_map for hashtable. Todavía no he agregado una estructura de árbol en el código C++.
Resultados: para 3281415 bordes y 18601 nodos únicos, perl toma 3 minutos para encontrar A -> '*' -> '*' -> B. Daré una actualización sobre el código de C++ cuando esté listo.
Esto es todo lo que pude encontrar: http: //www.vldb.org/conf/1989/P185.PDF – Diego
¿Las rutas requeridas son simples? ¿O pueden tener ciclos? – templatetypedef
Tener ciclo implicaría un conjunto infinito de soluciones. – Faylixe