(Actualización de este post: http://micaminomaster.com.co/grafo-algoritmo/libreria-grafos-dinamicos/)

Me gustaría compartirles un módulo que realicé en Python 3.5 acerca de Grafos. Durante las siguientes semanas voy a trabajar bastante con esta herramienta y sería de gran ayuda un módulo que me ayude a administrar todas estas tareas.

Debido a que voy a trabajar con algoritmos, no puedo usar la herramienta networkx de Python. Solo utilizo su herramienta gráfica la cual es muy potente.

Utilizo el módulo numpy como excelente herramienta para manejar las estructuras de datos de matrices.

El módulo está disponible en mi repositorio público: https://github.com/arturoverbel/graph_python.

Módulo de características de un Grafo

Las características más importantes como son el manejo de nodo y de los arcos, debe ser lo más básico de este módulo. La siguiente clase abarca estos aspectos:

import numpy as np


class Graph:
    source = []
    target = []
    weight = []
    vertex = []

    undirected = 0

    def __init__(self, source=[], target=[], weight=[], directed=True):
        self.source = np.array(source)
        self.target = np.array(target)
        self.weight = np.array(weight)
        self.directed = directed

        self.set_vertex()

    def print_r(self):
        print("Source: ", self.source)
        print("Target: ", self.target)
        print("Weight: ", self.weight)
        print("Vertex: ", self.vertex)

    def set_vertex(self):
        vertex = np.unique(self.source)
        vertex2 = np.unique(self.target)
        self.vertex = np.unique(np.concatenate([vertex, vertex2]))
        return self.vertex

    def get_weight(self, n1, n2):
        return self.weight[np.logical_and(self.source == n1, self.target == n2)]

    def export(self):
        array_export = [(int(self.source[i]), int(self.target[i]), self.weight[i]) for i in range(self.source.size)]
        return array_export

En esta clase se definen los nodos fuentes y nodos destinos junto con su peso, las funciones son:

print_r( ): Imprime los valores de nodos fuentes, nodos destino, pesos de cada arco y nos los nodos como tal (vertex)
set_vertex( ): Dependiendo de los nodos fuentes y destino, realiza una lista de los nodos existentes del grafo, importantes para usarlo en los algoritmos.
get_weight(n1, n2): Dado dos nodos encontrar el peso de su arco.
export( ): Exportar todos los datos de arco en una matriz

La clase principal, de la cual hereda la anterior es la siguiente:

from _graph.GraphAPSP import GraphAPSP
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np


class GraphPro(GraphAPSP):

    def __init__(self, source=[], target=[], weight=[], directed=True):
        GraphAPSP.__init__(self, source, target, weight, directed)

    @staticmethod
    def creategraph(total_nodes, pro_edges, weights, directed=True):

        source = np.array([])
        target = np.array([])
        weight = np.array([])

        for i in range(total_nodes):
            for k in range(i+1, total_nodes):
                if k == i:
                    continue

                p = 1 - pro_edges
                has_edge = np.random.choice(2, 1, p=[p, pro_edges])[0]

                if not has_edge:
                    continue

                probabilities = np.zeros(len(weights))
                probabilities = probabilities + (1 / len(weights))
                w = np.random.choice(weights, 1, p=probabilities)[0]

                source = np.append(source, i)
                target = np.append(target, k)
                weight = np.append(weight, w)

                if not directed:
                    source = np.append(source, k)
                    target = np.append(target, i)
                    weight = np.append(weight, w)

        return GraphPro(source, target, weight)

    def draw(self, with_weight=True):
        Gr = nx.DiGraph()
        Gr.add_weighted_edges_from(self.export())
        pos = nx.spring_layout(Gr)
        list_edges = list(Gr.edges())
        last = ()

        if self.last_vertex_modified.size > 0:
            last = (int(self.last_vertex_modified[0]), int(self.last_vertex_modified[1]) )
            list_edges.remove(last)

        nx.draw(Gr, pos=pos, with_labels=True, edgelist=list_edges, node_size=600)

        if with_weight:
            edge_labels = dict([((u, v,), d['weight']) for u, v, d in Gr.edges(data=True)])
            nx.draw_networkx_edge_labels(Gr, pos=pos, edgelist=list_edges, edge_labels=edge_labels)

        if len(last) > 0:
            nx.draw_networkx_edges(Gr, pos=pos, edgelist=[last], width=2.0, edge_color='b')

        plt.axis('off')
        plt.show()

Este módulo genera grafos aleatoriamente pasando datos como el número de nodos, la probabilidad de que exista un arco y los pesos que pueda tener, además de si es un grafo dirigido. Tiene además una función para dibujar el grafo. El atributo de self.last_vertex_modified lo veremos más adelante.

Hasta aquí podemos mostrar una apariencia de un grafo generado con este módulo:

from _graph.GraphPro import GraphPro as g
import os

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

weights = [1, 2, 3, 4, 5]
graph = g.creategraph(6, .75, weights, directed=False)

graph.print_r()
graph.draw()

El resultado:

Figura 1. Imagen generada con el módulo de grafos aleatorios

El resultado en consola es:

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

Este es otro ejemplo solamente cambiando el número de nodos de 6 a 20, con la siguiente linea de código:

from _graph.GraphPro import GraphPro as g
import os

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

weights = [1, 2, 3, 4, 5]
graph = g.creategraph(20, .4, weights, directed=False)

graph.print_r()
graph.draw(with_weight=False)

El resultado:

Figura 2. Creación de grafo aleatorio con 20 nodos y una propabilidad de arco de 40%

Módulo de Grafo dinámicos

Tenemos la clase DynamicGraph con propiedades de un grafo dinámico. En este caso sol otenemos cuatro funciones.

import numpy as np
from _graph.Graph import Graph


class DynamicGraph(Graph):
    def __init__(self, source=[], target=[], weight=[], directed=True):
        Graph.__init__(self, source, target, weight, directed)
        self.last_vertex_modified = np.array([])

    def dynamic_decreasing_random_vertex(self):

        count_max = 100
        flag = 0
        while True:
            source = np.random.choice(self.vertex, 1)[0]
            choisen = self.target[source == self.source]
            if choisen.size != 0:
                target = np.random.choice(choisen, 1)[0]
                break
            flag = flag + 1
            if flag >= count_max:
                return -2

        return self.dynamic_decreasing_vertex(source, target)

    def dynamic_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)

        self.last_vertex_modified = returned

        return returned

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

        count_max = 100
        flag = 0
        while True:
            source = np.random.choice(self.vertex, 1)[0]
            index_for_target = np.invert(np.logical_or(np.in1d(self.vertex, self.target[source == self.source]), self.vertex == source))

            choisen = self.vertex[index_for_target]
            if choisen.size != 0:
                target = np.random.choice(choisen, 1)[0]
                break
            flag = flag + 1
            if flag >= count_max:
                return -2

        w = np.random.choice(weights)
        return self.dynamic_incremental_vertex(source, target, w)

    def dynamic_incremental_vertex(self, source, target, weight=1):

        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)

        self.last_vertex_modified = returned

        return returned

dynamic_incremental_vertex( source, target, weight=1): Agrega un nuevo arco al grafo dado un nodo fuente y destino con un peso específico.
dynamic_incremental_random_vertex( weights=[*] ): Agrega un nuevo arco con fuente y destino aleatorios, el peso también es aleatorio y puede ser especificado el conjunto
dynamic_decreasing_vertex( source, target): Elimina un arco existente del grafo dado un nodo fuente y destino.
dynamic_decreasing_random_vertex( weights=[*] ): Elimina un arco con fuente y destino aleatorios dentro del grafo.

Las dos funciones que realizan el proceso de actualización del arco en el grafo, tambén actualiza un atributo llamado self.last_vertex_modified para identificar en la instancia el último elemento modificado. Esto lo usamos al momento de dibujar un grafo. Veamoslo en acción con el siguiente código:

from _graph.GraphPro import GraphPro as g
import os

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

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

print("-------Incremental-----")
data = graph.dynamic_incremental_random_vertex(weights)
graph.print_r()

graph.draw()
print()
print("------------------------")

En el código generamos aleatoriamente un grafo de seis nodos, con una probabilidad de arco de 75% y unos pesos específicos. Utillizamos la función que agrega un nuevo arco aleatoriamente. Tenemos el siguiente resultado:

Figura 3. Grafo dinámico creciente por arco, generado aleatoriamente

Como se puede observar en la figura, el arco agregado es (3, 1) con peso de 2.0, el resultado por consola es:

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

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

------------------------

Conclusiones

Con esto, tenemos todo lo necesario para trabajar con los grafos, ahora solo queda aplicar los algoritmos correspondientes. El código final está disponible en https://github.com/arturoverbel/graph_python. Utilizando Python 3.5

Mi Camino Master

Mi experiencia y mis pensamientos acerca de mis estudios de Maestría en Ciencias de la Información y las Comunicaciones

Todo para trabajar con grafos en Python

Módulo de características de un Grafo

Módulo de Grafo dinámicos

Conclusiones

Arturo Verbel De Leon

Comentarios Cancel reply

Lo más visto

Sígueme

Lo más visto

Últimas entradas

Sígueme