Vuelvo de nuevo a traer otro code-kata. Esta vez estoy tratando de sacar en claro cómo generar matrices de adyacencia para trabajar con los grafos asociados a mapas. En este escenario tenemos un mapa, que se genera aleatoriamente. En cada casilla tenemos un coste de movernos a dicha casilla. Sólo podemos movernos a la casilla adyacente, como si se tratara del movimiento de un peón de ajedrez.
Así pues, si estamos en la casilla (0,0) sólo podremos movernos a la (0,1), (1,1) y la de abajo, la (1,0). Así que ese coste de ese movimiento se representa por el valor del mapa generado. Y ese coste se guarda en la matriz de adyacencia como valor de la arista.
Un mapa aleatorio
Este es un mapa generado con costes de movernos en cada casilla:
| 0 1 2 3 4 5 ------------------------ 0 | 3->8 2 1 1 1 1 | 0 2 3 4 8 3 2 | 2 9 4 7 1 7 3 | 2 4 6 6 2 8 4 | 1 5 3 9 7 8 5 | 0 5 0 3 8 7
Si por ejemplo estamos en la casilla (0,0) y nos queremos mover a la (0,1), tendríamos un coste del movimiento de 8 unidades.
Numerando las casillas, los nodos del grafo
Con la especificación anterior tenemos que: el coste de movernos a otra casilla adyacente es el coste que pone en la casilla de destino.
Para construir el grafo se han numerado las casilla del mapa del 0 en adelante, así queda el mapa numerado:
| 0 1 2 3 4 5 ------------------------ 0 | 0 1 2 3 4 5 1 | 6 7 8 9 10 11 2 | 12 13 14 15 16 17 3 | 18 19 20 21 22 23 4 | 24 25 26 27 28 29 5 | 30 31 32 33 34 35
La matriz de adyacencia correspondiente
Para el mapa este, tenemos que el movimiento que queremos hacer es de la casilla número 0 a la 1. Tenemos 36 casillas, es decir, 36 nodos del grafo la matriz de adyacencia para el grafo correspondiente queda así:
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ------------------------------------------------------------------------------------------------------------------ 0 | 0 8 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 3 0 2 0 0 0 0 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 | 0 8 0 1 0 0 0 2 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 | 0 0 2 0 1 0 0 0 3 4 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 | 0 0 0 1 0 1 0 0 0 4 8 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 | 0 0 0 0 1 0 0 0 0 0 8 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 | 3 8 0 0 0 0 0 2 0 0 0 0 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 | 3 8 2 0 0 0 0 0 3 0 0 0 2 9 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 | 0 8 2 1 0 0 0 2 0 4 0 0 0 9 4 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 | 0 0 2 1 1 0 0 0 3 0 8 0 0 0 4 7 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 | 0 0 0 1 1 1 0 0 0 4 0 3 0 0 0 7 1 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 | 0 0 0 0 1 1 0 0 0 0 8 0 0 0 0 0 1 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 | 0 0 0 0 0 0 0 2 0 0 0 0 0 9 0 0 0 0 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 | 0 0 0 0 0 0 0 2 3 0 0 0 2 0 4 0 0 0 2 4 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 | 0 0 0 0 0 0 0 2 3 4 0 0 0 9 0 7 0 0 0 4 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 | 0 0 0 0 0 0 0 0 3 4 8 0 0 0 4 0 1 0 0 0 6 6 2 0 0 0 0 0 0 0 0 0 0 0 0 0 16 | 0 0 0 0 0 0 0 0 0 4 8 3 0 0 0 7 0 7 0 0 0 6 2 8 0 0 0 0 0 0 0 0 0 0 0 0 17 | 0 0 0 0 0 0 0 0 0 0 8 3 0 0 0 0 1 0 0 0 0 0 2 8 0 0 0 0 0 0 0 0 0 0 0 0 18 | 0 0 0 0 0 0 0 0 0 0 0 0 2 9 0 0 0 0 0 4 0 0 0 0 1 5 0 0 0 0 0 0 0 0 0 0 19 | 0 0 0 0 0 0 0 0 0 0 0 0 2 9 4 0 0 0 2 0 6 0 0 0 1 5 3 0 0 0 0 0 0 0 0 0 20 | 0 0 0 0 0 0 0 0 0 0 0 0 0 9 4 7 0 0 0 4 0 6 0 0 0 5 3 9 0 0 0 0 0 0 0 0 21 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 7 1 0 0 0 6 0 2 0 0 0 3 9 7 0 0 0 0 0 0 0 22 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 1 7 0 0 0 6 0 8 0 0 0 9 7 8 0 0 0 0 0 0 23 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 7 0 0 0 0 2 0 0 0 0 0 7 8 0 0 0 0 0 0 24 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 0 0 0 0 0 5 0 0 0 0 0 5 0 0 0 0 25 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 6 0 0 0 1 0 3 0 0 0 0 5 0 0 0 0 26 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 6 6 0 0 0 5 0 9 0 0 0 5 0 3 0 0 27 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 2 0 0 0 3 0 7 0 0 0 0 3 8 0 28 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 2 8 0 0 0 9 0 8 0 0 0 3 8 7 29 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 8 0 0 0 0 7 0 0 0 0 0 8 7 30 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 5 0 0 0 0 0 5 0 0 0 0 31 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 5 3 0 0 0 0 0 0 0 0 0 32 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 3 9 0 0 0 5 0 3 0 0 33 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 9 7 0 0 0 0 0 8 0 34 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 7 8 0 0 0 3 0 7 35 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 8 0 0 0 0 8 0
Fíjate que no es lo mismo movernos de la casilla 0 a la 1, de coste 8, que de la 1 a la 0, de coste 3. Tienen costes distintos y esto queda reflejado en la matriz de adyacencia.
El código fuente
Sólo me queda dejar el código fuente por si a alguien le sirve:
<?php
/**
* This script makes a random map filled with costs of walking throw each box. Moving from
* a position to an adjacent is are the posible movements. Then, is calculated an adjacent matrix
* to represent the graph of possible movements from each box.
*/
define('NUMBER_OF_ROWS', 6);
define('NUMBER_OF_COLS', 6);
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 matrix.
$adjacentMatrix = array();
for ($from = 0; $from < NUMBER_OF_NODES; ++$from) {
for ($to = 0; $to < NUMBER_OF_NODES; ++$to) {
if ($from == $to) {
$adjacentMatrix[$from][$to] = 0;
} else {
// Get row and col from current number of node..
$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 possible movement..
if (abs($fromCol - $toCol) <= 1
and abs($fromRow - $toRow) <= 1) {
$adjacentMatrix[$from][$to] = $randomMap[$toRow][$toCol];
} else {
$adjacentMatrix[$from][$to] = 0;
}
}
}
}
// Print map.
echo PHP_EOL;
echo ' | ';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
echo str_pad($col, 3, ' ');
}
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], 3, ' ');
}
echo PHP_EOL;
}
// Print map positions.
$currentPosition = 0;
echo PHP_EOL;
echo ' | ';
for ($col = 0; $col < NUMBER_OF_COLS; ++$col) {
echo str_pad($col, 3, ' ');
}
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, 3, ' ');
++$currentPosition;
}
echo PHP_EOL;
}
// Print adjacent matrix.
echo PHP_EOL;
echo ' | ';
for ($col = 0; $col < NUMBER_OF_NODES; ++$col) {
echo str_pad($col, 3, ' ');
}
echo PHP_EOL;
echo '------';
for ($col = 0; $col < NUMBER_OF_NODES; ++$col) {
echo '---';
}
echo PHP_EOL;
for ($from = 0; $from < NUMBER_OF_NODES; ++$from) {
echo str_pad($from, 3, ' ').'| ';
for ($to = 0; $to < NUMBER_OF_NODES; ++$to) {
echo str_pad($adjacentMatrix[$from][$to], 3, ' ');
}
echo PHP_EOL;
}
He marcado en negrita lo principal del llenado de la matriz. Simplemente se recorren las casillas del mapa siguiendo la numeración de cada casilla, es decir, siguiendo la numeración de cada nodo del grafo correspondiente.
