Obtener todas las rutas posibles de un mapa de grafos

[zeuslife]

Buenas a todos!!

Estoy intentando obtener, desde un array de arrays de estados (ahora pondré un ejemplo), todos los caminos posibles para llegar de un nodo a otro. Por ejemplo, yo tengo los siguientes estados (su array interior indica a que otros estados puede conectarse):

Código PHP:

  'states' => array(
        '0' => array( 'to' => array( 1, 10, 5, 12) ),
    '1' => array( 'to' => array( 2, 5, 10, 11) ),
    '2' => array( 'to' => null),
    '3' => array( 'to' => null),
    '4' => array( 'to' => array( 5, 6, ) ),
    '5' => array( 'to' => array( 2, 8, 6, 12) ),
    '6' => array( 'to' => array( 8, 1, 3, 7) ),
    '7' => array( 'to' => null),
    '8' => array( 'to' => array( 2, 1, 3, 4 ),
    '9' => array( 'to' => array( 1, 5, 6, 4) ),
    '10' => array( 'to' => null),
    '11' => array( 'to' => array( 4) ),
    '12' => array( 'to' => array( 1, 5, 8, 3) ),
), 
   

Pues bien, tengo que sacar todos los caminos posibles hacía el 1, desde, por ejemplo, el 0, teniendo en cuenta que no puedo repetir caminos y que puede haber recursión.

Me gustaría hacerlo con una función por el cual me diese un array con todas las rutas posibles (osea, un array con subarray en cada posición indicando los diferentes nodos por los que pasa).

¿Se os ocurre cómo hacer esto?


¡¡Gracias!!

[dashtrash]

Asi, en principio, la funcion recursiva tendría una signature del tipo

function getPath($startNode, $endNode, $availableNodes, $connections, $currentPath, & $solutions)

La llamada inicial tiene
$startNode=<nodo inicial>,
$endNode=<nodo final>,
$availableNodes=<todos>,
$connections=<array de conexiones entre nodos>,
$currentPath=array(),
$solutions=array()

Las llamadas recursivas se realizan con:
$startNode=<nodo iactual>,
$endNode=<nodo final>, <-- fijo
$availableNodes=<aquellos no usados>,
$connections=<array de conexiones entre nodos>, <--- fijo
$currentPath=array(<nodos ya usados>)
$solutions=array(<arrays de soluciones>)

Si una llamada recursiva llega al nodo final, mete el valor de $currentPath dentro de $solutions.

Otra posibilidad es no pasar el array $solutions, y devolverlo como valor de retorno de la funcion, o null si no hay caminos entre $start y $end

[zeuslife]

Hola @dashtrash, gracias por tu rápida respuesta.

Me gusta mucho como punto de partida, y ya había conseguido "algo" similar, la cuestión es que no termino de entender del todo tu pseudo código.

¿Para qué uso realmente availableNodes, si al final puede que tenga que pasar por el mismo para ir a otro punto? ¿Cómo vuelvo a un nodo padre cuando he agotado uno o varios de sus hijos?

A lo mejor es mucho pedir, pero un pequeño ejemplo "funcional" vendría de perlas :)


¡Muchas gracias de nuevo!!

[zeuslife]

Creo que ya lo he entendido... Voy a terminar mi ejemplo a ver que sale y si lo consigo lo publico.


¡¡Gracias!!

[zeuslife]

Iniciado por zeuslife

Creo que ya lo he entendido... Voy a terminar mi ejemplo a ver que sale y si lo consigo lo publico.


¡¡Gracias!!

Pues no... :(

[dashtrash]

Iniciado por zeuslife

Hola @dashtrash, gracias por tu rápida respuesta.
¿Para qué uso realmente availableNodes, si al final puede que tenga que pasar por el mismo para ir a otro punto? ¿Cómo vuelvo a un nodo padre cuando he agotado uno o varios de sus hijos?

Am, lo que no quieres es repetir caminos.Lo mismo da.Available <lo que sea> es la lista de nodos, caminos, o lo que sea que aun quedan disponibles.

Iniciado por zeuslife

A lo mejor es mucho pedir, pero un pequeño ejemplo "funcional" vendría de perlas :)

Not going to happen.Pero es muy sencillo:

- start == end ? SI->Devolver el path actual, con end como ultimo elemento.
- No?
Crear un array de soluciones vacio.
Por cada uno de los caminos que existen en availableNodes (aunque ya no son nodos, sino caminos), que comienzan (o terminan) en $start:
-crear un array availableNodes nuevo , donde no existe el camino actual.
-crear un array con currentPath + $start
-llamar recursivamente, con start==nodo opuesto del camino, y currentPath, el array anterior.
- Si la llamada devolvio un array, añadirlo al array de soluciones.

- Devolver el array de soluciones.