http://upload.wikimedia.org/wikipedia/commons/5/57/6n-graf.png
ese grafo, los nodos con contactos (personas) entonces tengo que
buscar desde un contacto inicial si a traves de los contactos de sus
contactos etc encuentro alguna persona que cumpla las condiciones de
busqueda (ejemplo personas que vienen en españa dentro de mi red de
contactos)
basicamente necesito, recorrer un grafo ( para saber los nodos de ese
grafo lo hago consultando una tabla de la BD ) y sacar todos los
caminos posibles hasta el nodo/nodos que cumplan una cierta
condición..... estuve buscando si había algún algoritmo ya pero
nada....
o un algoritmo para convertir un grafo en un arbol....cada camino del
grafo (no hay nodos repetidos) seria una rama del arbol (nodos
repetidos cuando exista mas de un camino posible)
parto de un nodo...hago una consulta a la BD cuales son los nodos
directamente conectados con el y para cada uno de estos lo mismo, así
hasta una profundidad de 6 arcos, entonces si llego a ese caso y no
encontré un objetivo tengo que volver para atras y seguir por otra
"rama" pero eso es lo que no consigo
yo- contacto directo - contacto a distancia 2 - contacto a distancia 3
- contacto a distancia 4- contacto adistandia 5 -contacto a distancia
7 // 7 nodos y 6 arcos ese es el limite de la búsqueda
lo que hago es que la funcion recursiva le pongo render a false para
que no intente cargar la vista puesto que no tiene....pero no se si
tengo que hacer algo mas
for (para cada uno de los nodos directamente conectados con el actual)
{
if (si el nodo cumple el perfil de busqueda){
tengo que guardar el camino que seguí hasta llegar a el
pero
seguir
buscando, es decir no acabo el algoritmo hasta agotar todas
las posibilidades
}
else{
return llamada recursiva (pararé de hacer llamadas, es decir de
seguir buscando si me paso de 6 arcos, volveré para atras y si al
volver no queda mas grafo que recorrer termino)
}
}
--~--~---------~--~----~------------~-------~--~----~
Has recibido este mensaje porque estás suscrito a Grupo "CakePHP-es" de Grupos
de Google.
Si quieres publicar en este grupo, envía un mensaje de correo
electrónico a [email protected]
Para anular la suscripción a este grupo, envía un mensaje a [EMAIL PROTECTED]
Para obtener más opciones, visita este grupo en
http://groups.google.com/group/CakePHP-es?hl=es.
-~----------~----~----~----~------~----~------~--~---
