PrEDA: grafos y mapas, ahora guardando en una lista de adyacencia..

Continuando con el post de ayer sobre cómo crear una matriz de adyacencia a partir de un mapa aleatorio, traigo otro code-kata. Es el mismo ejercicio de ayer, pero hoy para sacar en claro cómo almacenar un grafo en una lista de adyacencia.

¿Porqué una lista o matriz de adyacencia va a ser mejor o peor? Dependerá de cada grafo. Si el grafo es muy denso, porque tiene muchas aristas entre nodo y nodo, está demostrado que es mejor usar una matriz. Pero si el grafo es poco denso es mejor usar una lista de adyacencia.

Igual que en el post de ayer, el escenario consiste en un mapa aleatorio, y nos podemos mover de casilla en casilla haciendo movimientos de peón de ajedrez. El coste de hacer cada movimiento, es el número que ponga en la casilla de destino. La interpretación de estos datos del mapa puede variar según lo que necesites.

Al grano

Un mapa generado aleatoriamente:

   |  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
----------------------------------------------------------------------
0  |  9   3   0   8   1   6   0   7   5   6   9   7   5   9   9   7   
1  |  4   5   2   7   9   5   9   3   0   6   0   6   8   3   7   6   
2  |  9   4   3   7   5   8   2   6   1   0   7   5   5   6   9   4   
3  |  7   3   9   4   5   2   9   9   1   1   8   5   0   6   9   0   
4  |  5   8   7   2   1   2   5   1   7   8   7   1   4   4   8   0   
5  |  0   6   7   6   4   2   6   0   3   6   6   2   4   9   8   6

Igual que en post de ayer, tenemos que numerar cada casilla para orientarnos. Como tenemos 6 filas con 16 columnas nos salen 96 nodos en este grafo:

   |  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
----------------------------------------------------------------------
0  |  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
1  |  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  
2  |  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  
3  |  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  
4  |  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  
5  |  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95

Qué es una lista de adyacencia

Es un array/vector/lista en la que cada elemento es a su vez otra lista/vector/array con los elementos adyacentes a dicho nodo. Para este ejemplo, su lista de adyacencia queda así:

0   --> 1(3) --> 16(4) --> 17(5)
1   --> 0(9) --> 2(0) --> 16(4) --> 17(5) --> 18(2)
2   --> 1(3) --> 3(8) --> 17(5) --> 18(2) --> 19(7)
3   --> 2(0) --> 4(1) --> 18(2) --> 19(7) --> 20(9)
4   --> 3(8) --> 5(6) --> 19(7) --> 20(9) --> 21(5)
5   --> 4(1) --> 6(0) --> 20(9) --> 21(5) --> 22(9)
6   --> 5(6) --> 7(7) --> 21(5) --> 22(9) --> 23(3)
7   --> 6(0) --> 8(5) --> 22(9) --> 23(3) --> 24(0)
8   --> 7(7) --> 9(6) --> 23(3) --> 24(0) --> 25(6)
9   --> 8(5) --> 10(9) --> 24(0) --> 25(6) --> 26(0)
10  --> 9(6) --> 11(7) --> 25(6) --> 26(0) --> 27(6)
11  --> 10(9) --> 12(5) --> 26(0) --> 27(6) --> 28(8)
12  --> 11(7) --> 13(9) --> 27(6) --> 28(8) --> 29(3)
13  --> 12(5) --> 14(9) --> 28(8) --> 29(3) --> 30(7)
14  --> 13(9) --> 15(7) --> 29(3) --> 30(7) --> 31(6)
15  --> 14(9) --> 30(7) --> 31(6)
16  --> 0(9) --> 1(3) --> 17(5) --> 32(9) --> 33(4)
17  --> 0(9) --> 1(3) --> 2(0) --> 16(4) --> 18(2) --> 32(9) --> 33(4) --> 34(3)
18  --> 1(3) --> 2(0) --> 3(8) --> 17(5) --> 19(7) --> 33(4) --> 34(3) --> 35(7)
19  --> 2(0) --> 3(8) --> 4(1) --> 18(2) --> 20(9) --> 34(3) --> 35(7) --> 36(5)
20  --> 3(8) --> 4(1) --> 5(6) --> 19(7) --> 21(5) --> 35(7) --> 36(5) --> 37(8)
..
etcétera

Si nos fijamos en la primera línea, tenemos que a partir del nodo que es el 0 podemos ir al 1, 16 y 17. Con sus costes entre paréntesis. Igualmente para el resto de los nodos.

El código

A partir del otro post, el código es bien sencillo con una pequeña modificación:

<?php
/**
 * This script makes a random map filled with costs of walking throw each box. Moving from
 * a position to an adjacent are the only possible movements. Then, is calculated an adjacent list
 * to represent the graph.
 */
define('NUMBER_OF_ROWS', 6);
define('NUMBER_OF_COLS', 16);
define('NUMBER_OF_NODES', NUMBER_OF_ROWS * NUMBER_OF_COLS);

// Fill random map.
$randomMap = array();
for ($row = 0; $row < NUMBER_OF_ROWS; ++$row) {
    for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
        $randomMap[$row][$col] = rand(0, 9);
    }
}

// Fill adjacent list.
$adjacentList = array();
for ($from = 0; $from < NUMBER_OF_NODES; ++$from) {
    for ($to = 0; $to < NUMBER_OF_NODES; ++$to) {
        if ($from == $to) {
            //$adjacentList[$from][$to] = 0;
        } else {
            $fromRow = floor($from / NUMBER_OF_COLS);
            $fromCol = $from % NUMBER_OF_COLS;
            $toRow = floor($to / NUMBER_OF_COLS);
            $toCol = $to % NUMBER_OF_COLS;

            //echo 'from '.$from.' to '.$to
            //.': fromRow '.$fromRow.' fromCol '.$fromCol
            //.', toRow '.$toRow.' toCol '.$toCol.PHP_EOL;

            // If is adjacent box, save node to list..
            if (abs($fromCol - $toCol) <= 1
            and abs($fromRow - $toRow) <= 1) {
                $adjacentList[$from][$to] = $randomMap[$toRow][$toCol];
            } else {
                //$adjacentList[$from][$to] = 0;
            }
        }
    }
}

// Print map.
echo PHP_EOL;
echo '   |  ';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo str_pad($col, 4, ' ');
}
echo PHP_EOL;
echo '------';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo '----';
}
echo PHP_EOL;
for ($row = 0; $row < NUMBER_OF_ROWS; ++$row) {
    echo str_pad($row, 3, ' ').'|  ';
    for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
        echo str_pad($randomMap[$row][$col], 4, ' ');
    }
    echo PHP_EOL;
}

// Print map positions.
$currentPosition = 0;
echo PHP_EOL;
echo '   |  ';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo str_pad($col, 4, ' ');
}
echo PHP_EOL;
echo '------';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
    echo '----';
}
echo PHP_EOL;
for ($row = 0; $row < NUMBER_OF_ROWS; ++$row) {
    echo str_pad($row, 3, ' ').'|  ';
    for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
        echo str_pad($currentPosition, 4, ' ');
        ++$currentPosition;
    }
    echo PHP_EOL;
}

// Print adjacent list.
echo PHP_EOL;
for ($from = 0; $from < NUMBER_OF_NODES; ++$from) { echo str_pad($from, 3, ' '); 
    foreach ($adjacentList[$from] as $node => $cost) {
        echo ' --> '.$node.'('.$cost.')';
    }
    echo PHP_EOL;
}

He marcado en negrita lo principal del algoritmo de llenado de la lista de adyacencia. No necesitamos tener un mapa de nodos numerados, pero sí que necesitamos tener en mente que existe la numeración que comento antes. Así de esta forma, para averiguar si dos nodos son adyacentes, y es posible así moverse de uno a otro, se usa esta numeración.

Es curioso ver que en PHP se trabaja igual una matriz que una lista dinámica. Así sólo con guardar los destinos accesibles nos basta, he dejado comentado el código que ponía a 0 los destinos innaccesibles de la matriz anterior.