zenphp :: blog

Cómo ..¿grafos multietapa?…¿eso qué es y para qué sirve?
pues resulta que en un grafo multietapa sólo se puede llegar a un punto “etapa” desde una etapa anterior, y sólo se puede ir a una etapa posterior…hasta ahí bien…pero en la fase final convergen varias líneas!
Repasemos ésta cosa de los estados de una aplicación multiusuario y echemos mano de la memoria…a ver a qué me suena?,ah si!…el carro de la compra!…bueno…y transacciones, reservas de vuelo, etc. etc.

Al final resulta ser un problema de minimización…en principio, pero claro, quién nos iba a decir que un problema de Programación Dinámica es rentable en una aplicación de servidor,…que necesita, precisamente , descargar la CPU a toda costa…entonces, ésto requiere una reflexión más profunda, dado que no podemos sobrecargar un servidor con cálculos debe existir una solución intermedia para realizar las conexiones entre ,pongamos un ejemplo: unidades y productos…una conexión es una asignación con máximo beneficio…¿y qué es el beneficio en una aplicación tipo web?, ésta elección amigos, puede ser la solución al problema…ya que la matriz que vamos a construir puede llegar a ser muy grande, lo más probable es que desechemos el problema una vez que concluimos la solución…pero, ¿por qué no es factible? pensándolo bien, realmente no necesitamos llegar a analizar el problema completo…es decir, podemos cortar el proceso en un punto de la resolución si el tiempo que está llevando a cabo es demasiado y aplicar otro algoritmo con peor solución pero mejor tiempo medio…o…podemos calcular las mejores soluciones de los subproblemas y utilizarlas para procesar las peticiones del cliente al servidor…es decir, realizar las mejores asignaciones por lotes.
Casos de uso: procesamiento de aplicaciones que necesiten comprobar el estado de semáforo
Veamos una implementación

<?php

class Grafo {
  //Representación del grafo en forma de matriz

  /**
  * @var array
  */
  var $adjuntos = array();
  /**
  * @var array
  */
  var $grafo1 = array(
      array(' ', 'S', 'A', 'B', 'C', 'D', 'E', 'F'),
      array('S', -1, 3, 5, 7, -1, -1, -1),
      array('A', 3, -1, -1, -1, 5, 6, -1),
      array('B', 5, -1, -1, -1, 4, 8, -1),
      array('C', 7, -1, -1, -1, 3, 6, -1),
      array('D', -1, 5, 4, 3, -1, -1, 1),
      array('E', -1, 6, 8, 6, -1, -1, 2),
      array('F', -1, -1, -1, -1, 1, 2, -1)
  );

  //Matriz que cada fila contiene los nodos de una misma etapa
  var $etapas = array(
        array('S') //Etapa 0
      , array('A', 'B', 'C') //Etapa 1
      , array('D', 'E') //Etapa 2
      , array('F') //Etapa 3
  );

  /**
   * Constructor de la clase
   */
  function Grafo() {
    $this->adjuntos = $this->grafo1;
  }

  /**
   * Método que dada la ETAPA de un nodo devuelve un array con
   * TODOS los nodos
   * que pertenecen a la siguiente etapa.
   *
   * @param etapa int Número de la etapa a al que pertenece el
   * nodo del cual queremos
   * saber qué nodos existen en la etapa siguiente
   * @access public
   * @param int $etapa
   * @return char[] Array con el nombre de los nodos de la etapa posterior
   */
  // public //SINTAXIS PARA PHP5
   function getNodosSiguentes($etapa) {
    $index = 0;
    $k = $etapa + 1;
    //Etapa siguiente, es de la que quiero la lista de nodos
    $nodos = array();

    //try { //Para PHP 5
      //Recorro la matriz de etapas en busca del nodo
      for ($i = 0; $i < count($etapas); $i++) {
        for ($j = 0; $j < count($etapas[$k]); $j++) {
          $nodos[$index] = $etapas[$k][$j];
          $index++;
        }
        return $nodos;
      }

      //Si algo rompe lo cazo aqui
  //  } //Para PHP 5    catch (Exception $e) {
       //Para PHP 5     return $e->getMessage();
   //Para PHP 5  }

    return null;
  }

  /**
   * Método que dada la ETAPA de un nodo devuelve un array con
   * TODOS los nodos que pertenecen a la anterior etapa.
   *
   * @param etapa int Número de la etapa a al que pertenece el
   * nodo del cual queremos saber qué nodos existen
   * en la etapa anterior
   * @param int $etapa
   * @return Array con el nombre de los nodos de la etapa anterior
   */
  //public //Para PHP5
    function getNodosAnteriores($etapa) {
    $index = 0;
    //Etapa anterior, es de la que quiero la lista de nodos
    $k = $etapa - 1; 

    $nodos = array();

    //try { //Para PHP5 quitar comentario al inicio
      //Recorro la matriz de etapas en busca del nodo
      for ($i = 0; $i < count($etapas); $i++) {
        for ($j = 0; $j < count($etapas[$k]); $j++) {
          $nodos[$index] = $etapas[$k][$j];
          $index++;
        }
        return $nodos;
      }

      //Si algo rompe lo cazo aqui
    //}  catch (Exception $e) { //PARA PHP5  return $e->getMessage(); }

    return null;
  }

  /**
  * @param str $origen
  * @param str $destino
  * @return int
  */
  function getPeso($origen, $destino) {
    $columna = -1;
    $fila = -1;
    //busco el oriegen en la matriz columna 0 y el destino en la fila 0

    //Busco la columna del origen:
    for ($i = 0; $i < count($this->adjuntos); $i++) {

      //Si encuentro el origen en la column, busco el destino
      if ($this->adjuntos[$i][0] == $origen) {
        $columna = $i;
        break;
      }
    }

    //Busco la fila del destino:
    for ($j = 0; $j < count($this->adjuntos); $j++) {

      //Si encuentro el origen en la column, busco el destino
      if ($this->adjuntos[0][$j] == $destino) {
        $fila = $j;
        break;
      }
    }

    // try { //Bloque try solo para PHP5 ( se puede intentar
    // con version_compare(phpversion(),'5','<') )
    // devuelvo el peso; si esa posicion no existe, retorno -1;
    // try puede cambiarse por if (isset($adjuntos[$fila][$columna])
      return $this->adjuntos[$fila][$columna];
    //}//Fin bloque try:    catch (Exception $e) {
      return -1;
   // }
  }

  /**
   * @param nodo str
   * @return int etapa del nodo recibido como parametro.
   */
  //public //Para PHP5
   function getEtapa($nodo) {
    for ($i = 0; $i < count($this->etapas); $i++) {
      for ($j = 0; $j <count($this->etapas[$i]); $j++) {
        if ($this->etapas[$i][$j] == $nodo) {
          return $i;
        }
      }
    }
    return -1;
  }

  /**
   * @return int Numero de nodos del grafo.
   */
 // public
 function getNumNodos() {
    return count($this->adjuntos[0]) - 1;
  }

  /**
   * @return int numero de etapas del grafo
   */
 // public
 function getNumEtapas() {
    return count($this->etapas);
  }

  /**
   * @return char[] Array de nombres (caracter) de los nodos
   */
  // public
 function getNodos() {
    $nodos = array();
    for ($i = 1; $i < count($this->adjuntos[0]); $i++) {
      $nodos[$i - 1] = $this->adjuntos[0][$i];
    }
    return $nodos;
  }

}

?>

Ahora, ¿cómo podemos insertar la clase en zenphp?

1. Guarda el fichero como web/aplicaciones/ayudantes/clase_grafo.php
2. Crea web/index.php e instancia la clase