Grafos

Durante los próximos meses voy a estar trabajando mucho con grafos en python. Exactamente con los problemas de caminos más cortos de los pares (APSP) en grafos dinámicos.

Los grafos dinámicos son aquellos grafos que con el tiempo pueden variar su número de vértices, arcos y/o pesos de arcos. Estos pueden crecer o decrecer, por tal motivo pueden a ver muchos tipos de grafos dinámicos dependiendo de cómo se comporten sus componentes. Expliequemos mejor estos componentes:

• Vértices o nodos: Son objetos indivisible y sin propiedades y es la unidad fundamental de la que está formados los grafos.
• Arcos o aristas: Son pares ordenados de un conjunto de vértices (se le conoce aristas si el grafo es no dirigido y arcos si es un grafo dirigido)
• Peso de arco: es un número de los reales que le da valor a un arco.

Imagen 1. Ejemplo de un grafo

En la imagen 1 podemos describir sus componentes:

• Vértices:
• Arcos: , , ,

Grafos Dinámicos

Cuando en un grafo varían sus atributos tanto de vértices, como arcos y/o pesos, entonces los denominamos con grafos dinámicos. Estos se categorizan dependiendo de qué y cómo cambian con el tiempo. Por ejemplo si un grafo aumenta su número de arcos, podemos llamarlo grafos crecientes en arcos, un ejemplo son las redes sociales o rutas de transporte.

La mayoría de los algoritmos existentes que atacan estos problemas, no están dirigidos a grafos completamente dinámicos (full dinamic graph), más bien a grafos crecientes o decrecientes en vértices, arcos y/o pesos.

Pruebas para grafos dinámicos

Los siguientes códigos que se muestran en esta entrada es una continuación de la entra anterior http://micaminomaster.com.co/grafo-algoritmo/dijkstra-floyd-warshall-python/.

Datos aleatorios

Para generar grafos aleatorios comenzemos en realizar una función que permita generar resultados en función de unas probabilidades, tenemos el siguiente iPython Notebook:

Este archivo puede ser encontrado en el github: https://github.com/arturoverbel/python_notebooks/blob/master/Function%20probability.ipynb. A tener en cuenta:

• Este script está realizado en Python 2.7
• Se utiliza la librería Numpy de Python

Este script da arroja como resultados aleatoriamente de un grupo de datos dependiendo de unas probabilidades. En el primer script se muestra función probability la cual recibe dos parámetros. Datos que se seleccionarán aleatoriamente y la probabilidad de cada uno. En el ejemplo los datos son con probabilidad respectivamente.  En el script siguiente se realiza una prueba más elaborada. Pasando los mismos datos diez mil veces. El resultado es muy parecido a las probabilidades de cada datos. Las cuáles son , las cuales son muy parecidos a las probabilidades que se pasaron de .

Creador de grafos

Ya teniendo nuestra función aleatorio, ahora procedemos a la creación de grafos aleatorios:

El código público  se puede encontrar en: https://github.com/arturoverbel/python_notebooks/blob/master/function_create_graph.ipynb .

Establecer dinamismo por vértice

Para hacerlos dinámicos por vértice basta con agregar o quitar un vértice de un grafo aleatoriamente. Para esto le pasamos a la función que nos defina qué comportamiento usar (incremental o decreciente). Esta vez se presentará el código sin notebook. Solo la sección de la clase general.

Nuestra clase Graph Pro tiene que ejecutarse de la siguiente forma:

import graphpro as g
import os

os.system('clear')
print("<------------------------>")
print("Test Create\n")

weights = [1, 2, 3, 4, 5]
graph = g.GraphPro.creategraph(5, .65, weights)
graph.print_r()

print("------------------------")
data = graph.set_dynamic_vertex('incremental', weights)
print(data)
graph.print_r()
print("------------------------")
data = graph.set_dynamic_vertex('decreasing')
print(data)


graph.print_r()

print("------------------------")

Las líneas marcadas indican las nuevas funciones que implementaremos. Primero realizaremos las funciones de incrementar y decrecer por arco, pasando un nodo fuente y un nodo destino.

Decrecer un grafo por un arco

def decreasing_vertex(self, source, target):

    index = np.where(np.logical_and(self.source == source, self.target == target))[0][0]
    returned = np.array([])

    self.source = np.delete(self.source, index)
    returned = np.append(returned, source)

    self.target = np.delete(self.target, index)
    returned = np.append(returned, target)

    self.weight = np.delete(self.weight, index)

    return returned

Esta función devolverá el arco insertado junto con su peso correspondiente.

Incrementar un grafo por un arco

def incremental_vertex(self, source, target, weight):

    returned = np.array([])

    self.source = np.append(self.source, source)
    returned = np.append(returned, source)

    self.target = np.append(self.target, target)
    returned = np.append(returned, target)

    self.weight = np.append(self.weight, weight)
    returned = np.append(returned, weight)

    return returned

Grafo dinámico aleatorio

def set_dynamic_vertex(self, behavior, weights=[1, 2, 3, 4, 5, 6, 7, 8, 9]):

    returned = 0
    found_set = False

    for source in self.vertex:
        for target in self.vertex:
            if source == target:
                continue

            p = GraphPro.probability([0, 1], [0.5, 0.5])
            if p == 0:
                continue

            index = np.where(np.logical_and(self.source == source, self.target == target))

            if index[0].size == 0 and (behavior == 'incremental' or behavior == 'full'):
                probabilities = np.zeros(len(weights))
                probabilities = probabilities + (1 / len(weights))
                w = GraphPro.probability(weights, probabilities)

                returned = self.incremental_vertex(source, target, w)
                found_set = True

            elif index[0].size > 0 and (behavior == 'decreasing' or behavior == 'full'):
                returned = self.decreasing_vertex(source, target)
                found_set = True

            if found_set:
                break
        if found_set:
            break

    if found_set is False:
        return self.set_dynamic_vertex(behavior, weights)

    return returned

Esta función realiza un recorrido de los vértices hasta que resulte un cambio en el grafo. Recibe un parámetro behavior sobre el comportamiento del grafo (incremental o decreciente). De esta manera al ejecutar el primer código tenemos como resultados diferentes impresiones, por ejemplo:

<------------------------>
Test Create

Source:  [ 0.  0.  1.  1.  1.  2.  2.  3.  3.  3.  4.  4.  4.  4.]
Target:  [ 3.  4.  2.  3.  4.  0.  1.  1.  2.  4.  0.  1.  2.  3.]
Weight:  [ 5.  4.  1.  4.  5.  3.  5.  2.  3.  3.  1.  3.  1.  3.]
Vertex:  [ 0.  1.  2.  3.  4.]
------------------------
[ 3.  0.  3.]
Source:  [ 0.  0.  1.  1.  1.  2.  2.  3.  3.  3.  4.  4.  4.  4.  3.]
Target:  [ 3.  4.  2.  3.  4.  0.  1.  1.  2.  4.  0.  1.  2.  3.  0.]
Weight:  [ 5.  4.  1.  4.  5.  3.  5.  2.  3.  3.  1.  3.  1.  3.  3.]
Vertex:  [ 0.  1.  2.  3.  4.]
------------------------
[ 0.  4.]
Source:  [ 0.  1.  1.  1.  2.  2.  3.  3.  3.  4.  4.  4.  4.  3.]
Target:  [ 3.  2.  3.  4.  0.  1.  1.  2.  4.  0.  1.  2.  3.  0.]
Weight:  [ 5.  1.  4.  5.  3.  5.  2.  3.  3.  1.  3.  1.  3.  3.]
Vertex:  [ 0.  1.  2.  3.  4.]
------------------------

En la primera salida tenemos el grafo generado aleatoriamente. En la segunda el mismo grafo despúes de una inserción, en este caso el arco insertado es . En la tercera, el mismo grafo después de un decrecimiento por arco, el arco removido fue . De esta manera tenemos nuestro grafo dinámico aleatorio.

El código se encuentra disponible en https://github.com/arturoverbel/graph_python.