12 mar. 2017

Estructura de datos en python (Grafos)

Continuando con la serie de artículos sobre estructuras de datos en python. En este caso se tocará el tema de grafos con dos ejemplos, uno con listas y otro con matrices.

Los artículos anteriores son:

Este artículo se basa en los códigos en github Grafos con listas adyacentes y Grafos con matriz adyacente y del vídeo en youtube Grafos en Python.

De ejemplo de grafo se usará un modelo de procesos de colas, a continuación la imagen:


A continuación el código manejando el grafo como una lista:


#!/usr/bin/env python



class Vertice(object):

 def __init__(self, n):

  #Se define el nombre del vertice y la lista de vecinos

  self.nombre = n

  self.vecinos = list()

 

 def agregarVecino(self, v):

  if v not in self.vecinos:

   self.vecinos.append(v)

   self.vecinos.sort()







class Grafo(object):

 #Se crea un diccionario de vertices.

 vertices = {}

 

 def agregarVertice(self, vertice):

  #Se pregunta si vertice es una instancia de Vertice y si el nombre no esta en la lista de vertices.

  #Si se cumple se agrega el vertice al diccionario de vertices.

  if isinstance(vertice, Vertice) and vertice.nombre not in self.vertices:

   self.vertices[vertice.nombre] = vertice

   return True

  else:

   return False

 

 def agregarBorde(self, u, v):

  #Si u y v estan en vertices. se agregan como vecinos.

  if u in self.vertices and v in self.vertices:

   self.vertices[u].agregarVecino(v)

   self.vertices[v].agregarVecino(u)

   return True

  else:

   return False

   

 def printGrafo(self):

  #Se muestra el grafo.

  for key in sorted(list(self.vertices.keys())):

   print(key + str(self.vertices[key].vecinos))



if __name__ == '__main__':

 g = Grafo()

 cinco = Vertice('5')

 tres = Vertice('3')

 cuatro = Vertice('4')

 uno = Vertice('1')

 dos = Vertice('2')

 for i in range(ord('1'), ord('6')):

  g.agregarVertice(Vertice(chr(i)))



 bordes = ['53','54','31','35','41','42','45','12','13','14','21','24']

 for borde in bordes:

  g.agregarBorde(borde[:1],borde[1:])



 g.printGrafo()

Al ejecutar el script se tiene:
python grafo-listas.py
1['2', '3', '4']
2['1', '4']
3['1', '5']
4['1', '2', '5']
5['3', '4']


Como se ve, los vertices relacionados, el 1 se conecta con 2,3 y 4, el 2 con 1 y 4, el 3 con 1 y 5, el 4 con 1,2 y 5; y el 5 con 3 y 4.

El siguiente código muestra otra manera de crear el grafo, en este caso se puede manejar el peso de los bordes (aunque no se usa en el ejemplo).  A continuación el código:


#!/usr/bin/env python3



#Se importa nuevas caracteristicas de print

from __future__ import print_function





#Se crea la clace vertice que solo tiene como argumento su nombre.

class Vertice(object):

 def __init__(self, n):

  self.nombre = n





#Se crea la clase grafo con vertices e indices de bordes como diccionarios

#y bordes como una lista.

class Grafo(object):

 vertices = {}

 bordes = []

 indices_bordes = {}





 def agregarVertice(self,vertice):

  #Si vertice es una instancia de su clase y su nombre no esta en el 

  #diccionario de vertices se agrega.

  if isinstance(vertice, Vertice) and vertice.nombre not in self.vertices:

   self.vertices[vertice.nombre] = vertice

   #Se recorre los bordes y se agregan.

   for fila in self.bordes:

    fila.append(0)

   self.bordes.append([0] * (len(self.bordes)+1))

   self.indices_bordes[vertice.nombre] = len(self.indices_bordes)

   return True

  else:

   return False



 def agregarBorde(self,u,v, peso=1):

  #Se agrega el borde.

  if u in self.vertices and v in self.vertices:

   self.bordes[self.indices_bordes[u]][self.indices_bordes[v]] = peso

   self.bordes[self.indices_bordes[v]][self.indices_bordes[u]] = peso

   return True

  else:

   return False





 def printGrafo(self):

  #Se muestra el grafo

  for v, i in sorted(self.indices_bordes.items()):

   print(v + ' ', end='')

   for j in range(len(self.bordes)):

    print(self.bordes[i][j], end='')

   print(' ')    





if __name__ == '__main__':

 g = Grafo()

 cinco = Vertice('5')

 tres = Vertice('3')

 cuatro = Vertice('4')

 uno = Vertice('1')

 dos = Vertice('2')

 for i in range(ord('1'), ord('6')):

  g.agregarVertice(Vertice(chr(i)))



 bordes = ['53','54','31','35','41','42','45','12','13','14','21','24']

 for borde in bordes:

  g.agregarBorde(borde[:1],borde[1:])



 g.p

rintGrafo()





Al ejecutar el script se tiene lo siguiente:
python grafo-matrix-adyacente.py 
1 01110 
2 10010 
3 10001 
4 11001 
5 00110 

Como en el caso anterior, el vertice 1 se conecta con 2,3 y 4, el vertice 2 se conecta con 1 y 4, el vertice 3 conecta a 1 y 5, el vertice 4 conecta a 1,2 y 5; y el vertice 5 conecta con 3 y 4.



Se tienen dos formas de representar un grafo, puede usar el que prefiera, dependiendo de la complejida, si se necesita manejar pesos, la opción es el de la matriz.


11 mar. 2017

Estructura de datos en Python (Lista Enlazada)

Continuando con la serie de estructuras de datos, en el artículo anterior se trato de la estructura de datos Nodo, en este artículo se usará el Nodo por medio de composición en la lista enlazada.

Este artículo se basa del tutorial en youtube llamado Python:Linked Lists donde pasan el enlace al código en github.

La lista enlazada se basa en el Nodo, como recordarán el Nodo tiene el dato y lo que apunta al próximo nodo.  En el caso de la lista enlazada contendrá lo siguiente:

  • Argumentos:
    • Nodo: Al crear la lista enlazada se crea un Nodo sin datos y que apunte a None.
    • primero: variable privada que apunta al primer nodo.
    • ultimo: variable privada que apunta al último nodo.
    • tamagno: variable privada que lleva la cantidad de nodos que maneja la lista.
  • Métodos:
    • obtenerTamagno: Devuelve el tamaño de la lista.
    • add: Agrega un nodo a la lista enlazada.
    • remove: Remueve un nodo de la lista enlazada.
    • find:Busca un dato en la lista, devuelve el dato o False.


El código de la lista enlazada se muestra a continuación:


#!/usr/bin/env python3

#Se importa Nodo de nodos.

from nodos import Nodo









class ListaEnlazada(object):

    def __init__(self,primero = Nodo(None,None)):

        """Se asigna como Nodo inicial a primero y ultimo por que apuntan al mismo nodo

        y se define el tamagno de la lista en cero"""

        self.__primero = primero 

        self.__ultimo = self.__primero

        self.__tamagno = 0





    def obtenerTamagno(self):

        """Devuelve el tamagno de la lista"""

        return self.__tamagno



    def add(self,d):

        """Agrega un nodo a la lista enlazada"""

        #Se crea una instancia de nodo donde se le pasa el dato d y se coloca

        #como proximo nodo el primer nodo.

        nodoNuevo = Nodo(d,self.__primero)

        #El primer nodo apunta al nodo nuevo y se incrementa el tamagno.

        self.__primero = nodoNuevo

        self.__tamagno += 1





    def remove(self,d):

        """Se elimina el nodo que tenga el dato d"""

        #Al nodo actual se le asigna el primer nodo

        nodoActual = self.__primero

        #Y al nodo anterior se le asigna None.

        nodoAnterior = None



        #Mientras exista el nodo actual-

        while nodoActual:

            #Si el dato de nodo actual es igual al dato que se esta buscando.

            if nodoActual.dato == d:

                #Si existe nodo anterior

                if nodoAnterior:

                    #Se asigna  al apuntador proximo del nodo anterior el proximo de nodo actual

                    nodoAnterior.proximo = nodoActual.proximo

                else

                    #A primero se le asigna el apuntador al proximo nodo del nodo actual

                    self.__primero = nodoActual.proximo

                #En cualquiera de los dos casos se decrementa el tamagno de la lista.

                self.__tamagno -= 1

                #Devuelve True por que se elimino.

                return True

            else:

                #Se asigna al nodo anterior el nodo actual

                nodoAnterior = nodoActual

                #Se asigna al nodo actual, el nodo proximo del nodo actual

                nodoActual = nodoActual.proximo





    def find(self,d):

        """Se busca d en la lista enlazada, si existe devuelve d, si no devuelve None"""

        #a nodo actual se le asigna el primer nodo.

        nodoActual = self.__primero

        #Mientras exista el nodo actual.

        while nodoActual:

            #Si el dato de nodo actual es igual a d, devuelve d

            if nodoActual.dato == d:

                return d

            else:

                #Si no, el nodo actual apunta al proximo nodo.

                nodoActual = nodoActual.proximo

        #Si no se encuentra devuelve None.

        return None 







if __name__ == '__main__':

    miLista = ListaEnlazada()

    miLista.add(1)

    miLista.add(8)

    miLista.add(12)

    print("size: {0}".format(miLista.obtenerTamagno()))

    print (miLista.find(8))

    miLista.remove(8)

    print("size: {0}".format(miLista.obtenerTamagno()))

    print(miLista.remove(12))

    print("size:{0} ".format(miLista.obtenerTamagno()))

    print(miLista.find(5))



Al ejecutar el script se tiene lo siguiente:

python listas.py 
size: 3
8
size: 2
True
size: 1
None


Como se puede ver se agregan 3 elementos a la lista, luego se muestra el tamaño de la lista, se va eliminando cada elemento de la lista, donde se muestra el tamagno de la lista mientras se va eliminando elementos, y por último se busca el valor de 5 en la lista donde devuelve None.