Open Source


PrEDA: grafos, el algoritmo de Dijkstra

2017-10-29 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Después de haber repasado los fundamentos de los grafos: cómo se almacenan mediante matrices o listas de adyacencia, cómo se mantienen conectados mediante el algoritmo de Prim o Kruskal.. llegamos al algoritmo de Dijkstra.

Con este algoritmo, que nos sirve tanto para grafos dirigidos como no dirigidos, podemos saber cuál es el camino de menor coste desde un nodo origen a todos los demás. Usa la estrategia de programación voraz, mediante la cual, vamos construyendo la solución sin tener que volver atrás en cada decisión que vamos tomando.

Las aplicaciones de este algorimo son muchas más que los algoritmos predecesores. Por ejemplo, para calcular rutas en un mapa de carreteras, para conectar llamadas telefónicas mediante circuitos virtuales, enrutamiento de paquetes de red, coger varios autobuses/trenes/aviones minimizando coste o tiempo, buscar el mejor camino hasta el punto de recarga de un robot aspiradora, y un largo etcétera..

Estructura del algoritmo

Se basa en la selección arbitraria de un nodo origen, en el uso de un conjunto de nodos pendientes de estudiar, un vector especial que almacena el coste de llegar a cada nodo, y un vector de predecesores que guarda el nodo anterior para llegar a cada posición.

Mediante estas estructuras de datos, vamos estudiando las aristas entre nodo y nodo. Así de esta manera, se van recalculando el vector de los costes y el de los predecesores. En este ejemplo se parte del nodo inicial 0. Y se van estudiando nodo a nodo, los caminos posibles hasta el siguiente nodo en estudio. Cuando ya hemos estudiado todos los nodos, tendremos el camino de menor coste a cualquier nodo desde el nodo origen.

Por ejemplo

En este caso está configurado el script para generar grafos dirigidos:

0 --> 1(3)
1 --> 3(4) --> 2(1)
2 --> 5(2) --> 3(1)
3 --> 1(1) --> 4(4)
4 --> 6(1)
5 --> 3(5)
6 --> 4(1)
INITIAL> Not used nodes: 1-2-3-4-5-6
INITIAL> Special: 3-INF-INF-INF-INF-INF
INITIAL> Predecessor: 0-#-#-#-#-#
>>>> Found min edge! $adjacentList[0][1]=3
>>>> Next min node to use is 1
Not used nodes: 2-3-4-5-6
Special: 3-4-7-INF-INF-INF
Predecessor: 0-1-1-#-#-#
>>>> Found min edge! $adjacentList[1][2]=1
>>>> Next min node to use is 2
Not used nodes: 3-4-5-6
Special: 3-4-5-INF-6-INF
Predecessor: 0-1-2-#-2-#
>>>> Found min edge! $adjacentList[1][3]=4
>>>> Found min edge! $adjacentList[2][3]=1
>>>> Next min node to use is 3
Not used nodes: 4-5-6
Special: 3-4-5-9-6-INF
Predecessor: 0-1-2-3-2-#
>>>> Found min edge! $adjacentList[2][5]=2
>>>> Next min node to use is 5
Not used nodes: 4-6
Special: 3-4-5-9-6-INF
Predecessor: 0-1-2-3-2-#
>>>> Found min edge! $adjacentList[3][4]=4
>>>> Next min node to use is 4
Not used nodes: 6
Special: 3-4-5-9-6-10
Predecessor: 0-1-2-3-2-4
FINAL> Special: 3-4-5-9-6-10
FINAL> Predecessor: 0-1-2-3-2-4

El resultado final son los dos vectores de las dos últimas líneas. El vector especial, nos indica el coste hasta el nodo i. Por ejemplo, veamos el camino desde el nodo 0 al 4. Tiene un coste de 9 unidades y su camino se construye de atrás a adelante 4-3-2-1-0, mediante el vector predecesor. Es decir, el camino de mínimo coste posible es el 0-1-2-3-4. Si estudiamos las opciones podemos ver que así es.

El código

<?php define('NUMBER_OF_NODES', 7);
define('NUMBER_OF_EDGES_PER_NODE', 2); 
define('IS_DIRECTED_GRAPH', true); 

$adjacentList = array(); 
fillRandomCosts($adjacentList); 
printToScreen($adjacentList); 

$special = $predecessor = array(); 
dijkstra($adjacentList, $special, $predecessor); 

echo 'FINAL> Special: '.implode('-', $special).PHP_EOL
    .'FINAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;

function dijkstra($adjacentList, &$special, &$predecessor)
{
    // Fill C with not used nodes.
    $C = array();
    for ($i = 1; $i < NUMBER_OF_NODES; ++$i) {
        $C[] = $i;
    }

    // Fill special distances.
    for ($i = 1; $i < NUMBER_OF_NODES; ++$i) {
        $special[$i] = distanceFromTo($adjacentList, 0, $i);
        if ($special[$i] < INF) { 
            $predecessor[$i] = 0; 
        } else { 
            $predecessor[$i] = '#'; 
        } 
    } 
    
    echo 'INITIAL> Not used nodes: '.implode('-', $C).PHP_EOL
        .'INITIAL> Special: '.implode('-', $special).PHP_EOL
        .'INITIAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;

    // Study nodes in C to update $special and predecessor vectors.
    while (count($C) > 1) {
        $v = selectNextNodeThatMinimizesSpecial($adjacentList, $C, $special);
        $C = array_diff($C, array($v));

        if ($v == -1) {
            echo 'IMPOSSIBLE TO FIND DIJKSTRA WITH ALL NODES! Cannot achieve all nodes!'.PHP_EOL;
            exit;
        }

        foreach ($C as $w) {
            if ($special[$w] > $special[$v] + distanceFromTo($adjacentList, $v, $w)) {
                $special[$w] = $special[$v] + distanceFromTo($adjacentList, $v, $w);
                $predecessor[$w] = $v;
            }
        }

        echo 'Not used nodes: '.implode('-', $C).PHP_EOL
            .'Special: '.implode('-', $special).PHP_EOL
            .'Predecessor: '.implode('-', $predecessor).PHP_EOL;
    }
}

function selectNextNodeThatMinimizesSpecial($adjacentList, &$C, &$special)
{
    $minCost = INF;
    $minNode = -1;

    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        foreach ($C as $node) {
            if (!in_array($i, $C)
            and isset($adjacentList[$i][$node])
            and $adjacentList[$i][$node] < $minCost) { 
                echo '>>>> Found min edge! $adjacentList['.$i.']['.$node.']='.$adjacentList[$i][$node].PHP_EOL;
                $minCost = $adjacentList[$i][$node];
                $minNode = $node;
            }
        }
    }

    echo '>>>> Next min node to use is '.$minNode.PHP_EOL;

    return $minNode;
}

function distanceFromTo($adjacentList, $from, $to)
{
    if (isset($adjacentList[$from][$to])) {
        return $adjacentList[$from][$to];
    } else {
        return INF;
    }
}

function fillRandomCosts(&$adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        $added = false;
        while (!$added) {
            for ($j = 0; $j < NUMBER_OF_EDGES_PER_NODE; ++$j) {
                $adjacentNode = rand(0, NUMBER_OF_NODES - 1);
                if ($adjacentNode != $i and $adjacentNode != $j) {
                    $adjacentNodeCost = rand(1, 5);
                    $adjacentList[$i][$adjacentNode] = $adjacentNodeCost;
                    if (!IS_DIRECTED_GRAPH) {
                        $adjacentList[$adjacentNode][$i] = $adjacentNodeCost;
                    }
                    $added = true;
                }
            }
        }
    }
}
function printToScreen($adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { echo $i; foreach ($adjacentList[$i] as $key => $value) {
            echo ' --> '.$key.'('.$value.')';
        }
        echo PHP_EOL;
    }
}


PrEDA: grafos, el algoritmo de Prim

2017-10-26 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

Hoy vuelvo a traer otro code-kata, siguiendo con la serie de algoritmos de programación relacionados con los grafos. Esta vez se trata del algoritmo de Prim, que sirve para calcular el árbol de recubrimiento de mínimo coste de un grafo.

Es decir, tenemos un grafo que se compone de nodos, que se interconectan mediante aristas. Dichas conexiones entre nodo y nodo, tienen un coste. Entonces queremos hallar la forma de interconectar todo con el mínimo coste. Una aplicación directa de esto puede ser para una red de ordenadores, eléctrica, tuberías, carreteras, etcétera.. mediante este algoritmo puedes obtener la forma de mantener conectados todos los nodos del grafo con el mínimo coste.

Continuar leyendo..

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

2017-10-23 - Categorías: PHP / PrEDA
Grafos, mapas y matrices 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.

Continuar leyendo..

PrEDA: grafos, generando mapas aleatorios y su matriz de adyacencia..

2017-10-22 - Categorías: PHP / PrEDA
Grafos, mapas y matrices de adyacencia

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.

Continuar leyendo..

Estudiando logs de CloudFront con GoAccess

2017-10-13 - Categorías: Amazon Web Services / General / GNU/Linux
Vista de GoAccess

Quizá tienes que estudiar los registros de visitas de un proyecto que está en una nube, detrás de un CloudFront de Amazon Web Services. En este proyecto tenemos guardados los registros de las peticiones web que tenemos a los servidores. A veces es interesante revisarlos a este nivel.

Es decir, que tenemos registros de las visitas, anonimizados, por ejemplo con Google Analytics. Pero pasan muchas más cosas por debajo de Google Analytics que sólo quedan reflejados en los registros de los servidores. Así que resulta que queremos saber absolutamente cuáles han sido todos los registros. Queremos saber qué IPs son las que más nos visitan. Qué consultas al servidor son las que están provocando errores de servidor, los 500, incluso antes de que lleguen los robots que nos indexan. Qué IPs son de robots que nos están crawleando, o indexando, y un largo etcétera. Probablemente aquí veamos las IPs de los robots de Google, Bing, Yahoo que nos visitan en busca de información de la web..

Continuar leyendo..

Servidor GNU/Linux bloqueado, no responde, no actualiza, no da servicio

2017-10-05 - Categorías: Amazon Web Services / General / GNU/Linux
GNULinux

Si has puesto un servidor Ubuntu/Linux lanzándole actualizaciones automáticas puede que hayas llegado a encontrarlo bloqueado. El servidor ha dejado de actualizarse y no hay manera de encontrar el problema. Cuesta mucho entrar al servidor. Un reinicio, paramos servicios, podemos hacer un par de cosas recién conectados, pero vuelve a bloquearse.. Volvemos a reiniciar para volver a entrar corriendo a ver qué pasa.. la gente corre.. ¡las mujeres y los niños primero! 😀

Esto pueden ser los síntomas de un servidor lleno. Lleno el disco duro, la memoria RAM, los i-nodos.. ha empezado a reventar por todos lados y necesitamos volverlo a la normalidad. Toca pues hacer un par de cosas..

Continuar leyendo..

Yo, robot IV – White/Gray/Black Hat SEO – El Text to HTML ratio

2017-08-26 - Categorías: PHP / SEO
YoRobot4 - Text to HTML ratio

El contenido es el rey para el posicionamiento, rezan muchos SEOs y muchas herramientas para SEOs. He leído por Internet que muchos hablan de que lo más importante para posicionar las páginas web es que el contenido sea bueno, que sea geniuno, interesante para el usuario.

Desde nuestro punto de vista, tenemos varios enfoques para hacernos una idea de si el contenido de una web es bueno. El más sencillo es la tasa que hay entre el texto y el código HTML, CSS y Javascript de nuestra web. Realmente, es la tasa entre el texto y el HTML, CSS y Javascript, aunque muchos se olvidan de que no sólo hay HTML.. Y muchas veces este CSS y Javascript puede ser tanto que la tasa de texto resultante baje demasiado. Todo esto se reduce en la tasa llamada Text to HTML ratio.

Continuar leyendo..

Yo, robot III – White/Gray/Black Hat SEO – El Time To First Byte

2017-08-15 - Categorías: General / PHP / SEO
YoRobot3 - El Time To First Byte

Hoy vengo a compartir otro pequeño script para testear el tiempo de respuesta de un servidor. Este es el llamado TTFB, Time To First Byte en inglés. Simplemente es el tiempo que pasa entre que tu navegador pide una web hasta que empieza el servidor a enviar los bytes de respuesta. Esta prueba nos da una buena visión de si el servidor y la web se pueden optimizar. Un TTFB bajo es buena señal, indica que tanto el servidor (a nivel hardware y software) como la aplicación web esta todo bien optimizado. Sino, ya tenemos algo en lo que enfocarnos.

Continuar leyendo..

Qué es realmente la Accesibilidad Web, el responsive design, el mobile-first.. una puesta al día con Bootstrap

2017-07-20 - Categorías: General
Usuarios por dispositivo mes a mes año pasado

Este post es una puesta al día sobre herramientas de desarrollo, el mobile-first, el responsive, y la accesibilidad en la web. Es una puesta al día con esta herramienta de desarrollo web para proyectos mobile-first. Hablo de Bootstrap, que como reza en su web, es muy popular desde hace años:

Bootstrap is the most popular HTML, CSS, and JS framework for developing responsive, mobile first projects on the web.

Si tienes una plantilla contruída sobre Bootstrap, ya tienes una página preparada para todo tipo de dispositivos. Esta herramienta creada por Twitter es todo un referente desde hace años. Puede que tu web esté mejor o peor hecha, pero si tienes Bootstrap, ya tienes un buen punto de partida. Y una de las herramientas de mayor renombre. Así que si no lo has tenido en cuenta, ya es hora de cambiar el chip, y empezar a pensar de otra forma.

¿Qué es la Accesibilidad Web?

Si vamos al origen de la creación de la Web. No hablo de la creación de Internet, sino de la creación de la web. La web se creó en su origen para dar un acceso universal a la información. Normalmente se asocia la accesibilidad exclusivamente a las personas con alguna discapacidad, pero en la web, esto cobra un sentido más amplio. Aquí se añaden más variables, como pueden ser la resolución de pantalla, la capacidad de procesamiento, el software del navegador, el lenguaje del usuario, la velocidad de conexión, su ubicación geográfica, etc..

Es decir, que la Accesibilidad toma un concepto más amplio en la Web, que el que normalmente puede tomar fuera de Internet. Aquí entra en gran medida conceptos que repercuten directamente en el posicionamiento de la web, en la usabilidad. Entran conceptos que van a repercutir directamente en el éxito o fracaso, en mayor o menor medida, de los proyectos web.

Más información aquí, donde derivan a su vez a la WAI o al W3C: http://accesibilidadweb.dlsi.ua.es/?menu=definicion

Resumiendo, que sí que es muy importante la Accesibilidad Web, el diseño sensible al dispositivo y diseñar tu web pensando en los usuarios que nos visitan desde un móvil. Pensemos en que los robots de Google, o de cualquier otro buscador, necesitan que tu web sea accesible. Estos robots son entes ciegos, algunos tienen serias limitaciones de software, quizá no pueden ejecutar ciertas tecnologías como Javascript. Algo parecido a como puede pasar con los visitantes de un móvil de gama baja, con ordenadores antiguos, o con usuarios con velocidades de conexión lentas.

Muchas de estas restricciones las tenemos en los dispositivos móviles. Y si a esto le sumamos que cada día más personas andamos movilizados, ya tenemos un cóctel explosivo si es que todavía no nos hemos esforzado en esto.

Estado actual de las visitas desde móvil

No lo digo yo, sino que los creadores de la web, la WAI o el W3C llevan tiempo previniendo. Sino que Google lleva tiempo también dándole cada vez más importancia. Dejo aquí un par de ejemplos de cómo van aumentando las visitas desde dispositivos móviles. Primero mes a mes en un proyecto, quizá es por el verano que la gente usa más el móvil..

Usuarios por dispositivo mes a mes

Aquí es donde tuve más curiosidad. ¿Sólo será por el verano? Así que miré que pasaba con respecto al año pasado..

Usuarios por dispositivo mes a mes año pasado

Es un poco alarmante cómo van creciendo las visitas desde móvil, aunque ya ha sido anunciado a voces. Menos mal que tenemos el proyecto hecho con un diseño con Bootstrap 😉 A partir de aquí lo siguiente es ya pensar en que todos los visitantes son dispositivos móviles y exprimir nuestro proyecto haciendo los ajustes necesarios. Hazlo que seguro que merece la pena..

Haciendo unos ajustes en Bootstrap con SASS y LESS

Después de toda la teoría, más de un buen maquetador me había recomendado usar SASS y LESS. Así que ya voy a ir al grano para presentar estas tecnologías y cómo configurar un entorno de trabajo con Atom Editor y así ser más productivos en nuestro desarrollo mobile-first.

SASS y LESS son preprocesadores de hojas de estilo. Con estas tecnologías podemos simplificar la construcción de hojas de estilo CSS. Así, podemos añadir variables, funciones, anidar selectores de estilos.. siendo más productivos y teniendo un proyecto más mantenible a la larga. La idea es construir unos pocos ficheros, que se procesan, y generan el estilo resultante.

En Atom Editor tenemos dos auto-compiladores que funcionan muy bien, comprobado 😉 son el llamado sass-autocompile y el less-autocompile. No hay más que ir a la sección de instalación de paquetes de nuestro Atom Editor, buscar e instalar.

Atom Editor SASS autocompiling

Como se puede ver en la imagen, se puede descargar una versión de Bootstrap preparada para usar SASS. Todos los ficheros tienen la extensión .scss porque son de SASS. Así que con un fichero styles.scss podemos reprocesar nuestro Bootstap para modificar el thema propio. En el momento en que se graba el fichero styles.scss, Atom Editor detectará que es un fichero .scss que procesar, y automáticamente generará el fichero styles.min.css listo para incluir en el HTML. En el fichero styles.scss de SASS, lo que tenemos es que, se modifican algunas cosas de los estilos de Bootstrap y a su vez se importan. Es decir, que todos los estilos estarán incluidos en una sola hoja de estilos, y finalmente el navegador sólo tendrá que descargarse un único fichero .css con todo unificado y comprimido.

Lo mismo funciona para LESS, es la misma idea, aunque la sintaxis es distinta. Algunos recomiendan SASS para los principiantes, pero realmente con la documentación a mano no veo ningún inconveniente a trabajar con LESS.

Unos enlaces relacionados

No debería de dejar enlaces, porque puede que te vayas de la web. Pero el objetivo de este post es echar un cable, así que ahí van xD

http://getbootstrap.com/
http://sass-lang.com/
http://lesscss.org/
https://atom.io/
https://atom.io/packages/sass-autocompile
https://atom.io/packages/less-autocompile

Si estás empezando un nuevo proyecto, te pueden ser interesantes un par de webs con temas desarrollados en Bootstrap:

https://bootswatch.com/
https://startbootstrap.com/

Terminando

Poder definir variables, anidar estilos, etc.. le da mucha potencia a la maquetación. Si a esto le añadimos lo que comentaba al principio, pensando en los dispositivos móviles, podemos ajustar nuestra plantilla, para que sea lo más accesible desde cualquier tipo de dispositivo..


Magento: sacar el ciclo de ventas con un script de PHP

2017-06-24 - Categorías: Magento
Magento logo money

He recibido una consulta sobre cómo sacar el ciclo de ventas de Magento. Ya respondí, pero los cálculos no me salen exactos. Así que jugando, jugando.. he tratado de encontrar cómo Magento calcula el ciclo de ventas que vemos en el panel de control.

Como no me daba exacto, he recorrido después las facturas, que tampoco me daba exacto. Y después añadí el recorrido de los abonos. Con y sin impuestos, tampoco me daba la misma cifra. Balanceando facturas con abonos, con y sin impuestos, que es lo correctamente contable tampoco me salía la misma cifra, aunque se iba acercando.. Conclusión, que en una tarde recorriendo los pedidos, facturas y abonos, no salen los mismos cálculos que te muestra Magento en el panel de control. Pero aquí dejo la información para el que le pueda servir 😉 de todas formas, contablemente, lo correcto son contabilizar las facturas y abonos.

Continuar leyendo..

© 2021 JnjSite.com - MIT license

Sitio hecho con WordPress, diseño y programación del tema por Jnj.