2

Tengo un árbol de búsqueda, pero estoy intentando mostrar la solución gráficamente dibujando el árbol en python, intente usando networkx pero no eh podido darle forma, como podría lograr esto?

Agregue mas info:

** Nota: estoy nuevo en Python y no conosco tanto el lenguaje.**

import networkx as nx
import matplotlib.pyplot as plt

g = nx.DiGraph()

Lado1 = "Izquierdo"
Lado2 = "Derecho"

start = {"Granjero":Lado1, "Lobo":Lado1, "Cabra":Lado1, "Col":Lado1}
meta = {"Granjero":Lado2, "Lobo":Lado2, "Cabra":Lado2, "Col":Lado2}
items = start.keys()
Cola = []
notrepet = []
path = []
Grafo = []
Cola_n = []
path.append(start)
notrepet.append(start)
Cola.append(start)



def validar_estado(estado):
    if estado["Lobo"] == estado["Cabra"] and estado["Lobo"] != estado["Granjero"]:
        return False
    elif estado["Cabra"] == estado["Col"] and estado["Col"] != estado["Granjero"]:
        return False
    else:
        return True


def Generar_estados(estado_actual):
    Lista_estados_Generados = []
    Estado_Nuevo = dict(estado_actual)

    if Estado_Nuevo["Granjero"] == Lado2:  # si esta en el lado derecho
        Estado_Nuevo["Granjero"] = Lado1  # lo pasamos al lado izquierdo
        if validar_estado(Estado_Nuevo) and Estado_Nuevo not in notrepet:
            Lista_estados_Generados.append(dict(Estado_Nuevo)) #si el granjero regresa soloa la otra orilla
            notrepet.append(dict(Estado_Nuevo))
        for k, v in Estado_Nuevo.items():
            if k != "Granjero":
                if v == Lado2: #si estan en lado derecho 
                    Estado_Nuevo[k] = Lado1  #lo pasamos al lado izquierdo
                    if validar_estado(Estado_Nuevo) and Estado_Nuevo not in notrepet:
                        Lista_estados_Generados.append(dict(Estado_Nuevo))
                        notrepet.append(dict(Estado_Nuevo))
                    Estado_Nuevo[k] = Lado2 # Reestablecemos el estado para posteriores estados
    else: 
        Estado_Nuevo["Granjero"] = Lado2
        for k, v in Estado_Nuevo.items():
            if k != "Granjero":
                if v == Lado1:
                    Estado_Nuevo[k] = Lado2
                    if validar_estado(Estado_Nuevo) and Estado_Nuevo not in notrepet:
                        Lista_estados_Generados.append(dict(Estado_Nuevo))
                        notrepet.append(dict(Estado_Nuevo))
                    Estado_Nuevo[k] = Lado1
    return Lista_estados_Generados

print(start)
while Cola:
    nodo = Cola.pop(0)
    Cola_n.append(nodo)
    if nodo != meta: #si aun no encontramos la solucion
        temp_list = Generar_estados(nodo)[:]
        Grafo.append(list(temp_list))
        print("Genera", temp_list)
        Cola.extend(temp_list.copy())      
    elif nodo == meta:
        print("Termina......")
        break 

en las lista Cola_n guardo todos los nodos que se craron y en la lista Grafo guardo lista de los nodos que genero cada uno de los nodos guardados en Cola_n

Entonces con esa relacion intento dibujar un arbol que tenga una forma parecida a esta:

introducir la descripción de la imagen aquí

1
  • 1
    Ya te imaginarás que es prácticamente imposible responder tu pregunta con la información que das. ¿Cómo tienes almacenado el árbol? ¿Qué tipo de estructura es (diccionario, lista de listas, objetos...)? ¿Cómo quieres representarlo? (dar un ejemplo dibujado "a mano" de cómo debería verse) ¿Qué has conseguido hasta ahora? (ejemplo de código networkx y resultado producido) En todo caso, para árboles igual te es más útil usar graphviz (hay un paquete para manejarlo desde python también)
    – abulafia
    Commented el 9 nov. 2018 a las 7:43

4 respuestas 4

2

A ver si lo entendí correctamente. Una vez tu programa ha terminado de ejecutarse, la variable Grafo contiene una lista de listas, etc. Al final, los elementos de las listas más internas son diccionarios. Así (omito parte):

[[{'Cabra': 'Derecho',
   'Col': 'Izquierdo',
   'Granjero': 'Derecho',
   'Lobo': 'Izquierdo'}],
 [{'Cabra': 'Derecho',
   'Col': 'Izquierdo',
   'Granjero': 'Izquierdo',
   'Lobo': 'Izquierdo'}],
 [{'Cabra': 'Derecho',
   'Col': 'Izquierdo',
   'Granjero': 'Derecho',
   'Lobo': 'Derecho'},
...
 [{'Cabra': 'Izquierdo',
   'Col': 'Derecho',
   'Granjero': 'Izquierdo',
   'Lobo': 'Derecho'}],
 [{'Cabra': 'Derecho',
   'Col': 'Derecho',
   'Granjero': 'Derecho',
   'Lobo': 'Derecho'}]]

Entiendo que esta estructura de datos es el "árbol" que quieres representar. Los nodos de ese árbol son estados por los que va pasando el "rompecabezas". Por tanto en cada uno de los nodos hay un diccionario que representa el estado.

A la hora de representar gráficamente el árbol, habrá que mostrar dentro de cada nodo del mismo el diccionario en cuestión, en lugar de un número que no nos diría gran cosa. La figura resultante va a ser un poco grande...

Se me ocurre que la forma más sencilla de lograr esa figura es usar graphviz, e ir construyendo el objeto que hay que pasarle a graphviz mientras vamos recorriendo el árbol en profundidad.

Para que el siguiente código funcione necesitas tener instalado el programa graphviz (si estás en un Ubuntu puedes usar sudo apt install graphviz, si estás en Windows deberás mirar cómo instalarlo en la página de graphviz). Además necesitas la biblioteca grapvhiz para python (pip install graphviz).

import graphviz
from pprint import pformat

n = 0
def recorre_en_profundidad(nodo, anterior, dot):
  global n
  if type(nodo) == dict:
      # pprint(nodo, width=20)
      n+=1
      dot.node(str(n), pformat(nodo, width=20))
      return n
  else:
    for rama in nodo:
      hijo = recorre_en_profundidad(rama, n, dot)
      if anterior:
        dot.edge(str(anterior), str(hijo))

dot = graphviz.Digraph(comment='Arbol de decisión')
recorre_en_profundidad(Grafo, None, dot)
dot.render()

Eso generará un pdf que contendrá el siguiente gráfico:

Resultado

Pero desconozco si es esto lo que buscabas. Por otra parte, en tu estructura de datos aparece en alguna de las ramas una lista vacía, que mi código ha ignorado. No sé cómo debería representarse en el árbol.

Actualización

Otra posibilidad para tener un grafo más compacto es cambiar lo que muestra el interior de cada nodo. En lugar de volcar el diccionario, podemos crear una cadena de este estilo, por ejemplo: "Lo,Co || Gr,Ca" que representa que el lobo y la col están a la izquierda, mientras que el granjero y la cabra están a la derecha.

Si escribimos una función que genere ese tipo de representación dado el diccionario:

def estado(d):
  izdo = []
  dcho = []
  for k,v in d.items():
    if v=="Derecho":
      dcho.append(k[:2])
    else:
      izdo.append(k[:2])
  return " || ".join([",".join(izdo), ",".join(dcho)])

Podemos usarla en la función que crea el grafico, en vez de pformat(), así:

n = 0
def recorre_en_profundidad(nodo, anterior, dot):
  global n
  if type(nodo) == dict:
      # pprint(nodo, width=20)
      n+=1
      print(estado(nodo))
      dot.node(str(n), estado(nodo))
      return n
  else:
    for rama in nodo:
      hijo = recorre_en_profundidad(rama, n, dot)
      if anterior:
        dot.edge(str(anterior), str(hijo))

El grafico que sale ahora es:

Resultado

Tengo la impresión de que, aunque el grafo representa el resultado de tu algoritmo, no está bien. No veo cómo un estado puede evolucionar a otro según lo que ahí aparece. Creo que tu algoritmo genera un árbol de decisión incorrecto, pero al menos esta representación gráfica puede ayudarte a depurarlo.

Actualización adicional

(y con esta ya paro, lo prometo :-))

Para máxima diversión, puedes cambiar la función estado() por esta otra:

def estado(d):
  icons = {"Lobo": "🐺", "Cabra": "🐐", "Col": "🍀", "Granjero": "👴"}
  izdo = []
  dcho = []
  for k,v in d.items():
    if v=="Derecho":
      dcho.append(icons[k])
    else:
      izdo.append(icons[k])
  return " || ".join(["".join(izdo), "".join(dcho)])

Y entonces el grafo resultante, cuando lo visualizas en un Jupyter Notebook sería así (el aspecto de los emoji puede variar según el operativo):

Arbol con emoji

Por desgracia, dot.render() genera un pdf que no muestra los iconos, pues la fuente que usa no tiene los caracteres Unicode apropiados.

2
  • Muchas gracias si es lo que buscaba hacer, y ya aprovechando me podrías explicar las funciones de "Estado" y de búsqueda, mas que nada los métodos que usaste para generar el grafo, estoy comenzando en python y no conozco esa librería . Si tienes razón hay un error en el resultado, gracias por el ese dato también. Por cierto pobre la función de estado, pero me quedan igual todos al lado derecho Commented el 10 nov. 2018 a las 4:04
  • PD: ya funciono la funcion "estado":p Commented el 10 nov. 2018 a las 4:15
2

Con la ayuda abulafia puede hacer lo que buscaba, el algoritmo funciona bien, solo que no guardaba bien el árbol y ni el recorrido, pero ya esta corregido o al menos ya logre que funcionara como buscaba.

Para la búsqueda en anchura y profundidad hice esto, espero que a alguien mas le sea útil al menos como idea.

import graphviz
import os
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin'
import Drawpy
n = 0

side1 = "left"
side2 = "right"

start = {"farmer":side1, "wolf":side1, "goat":side1, "cabbage":side1}
meta = {"farmer":side2, "wolf":side2, "goat":side2, "cabbage":side2}

_Queue =[]
notrepet =[]
_patch  = []

notrepet.append(start)
_Queue.append(start)


def validate_state(state):
    if state["wolf"] == state["goat"] and state["wolf"] != state["farmer"]:
        return False
    elif state["goat"] == state["cabbage"] and state["cabbage"] != state["farmer"]:
        return False
    else:
        return True

def Generar_states(state_actual, _patch ,dot):
    global n
    list_state = []
    new_state = dict(state_actual)
    _nodes = [w[0] for w in _patch.copy()] # se supone que obtengo todas las llaves de los dict
    if state_actual not in _nodes: #si aun no se ah creado el nodo para ese estado
        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 0)
    if state_actual["farmer"] == side2:  
        new_state["farmer"] = side1  
        if validate_state(new_state) and new_state not in notrepet:
            list_state.append(dict(new_state)) 
            notrepet.append(dict(new_state))
            n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)

        for k, v in new_state.items():
            if k != "farmer":
                if v == side2: 
                    new_state[k] = side1  
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side2 
    else: 
        new_state["farmer"] = side2
        for k, v in new_state.items():
            if k != "farmer":
                if v == side1:
                    new_state[k] = side2
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side1
    return list_state

#Tipo: (0) en profundidad (1) anchura, (2)profundidad limitada
def algoritmo(tipo, _patch, dot):
    while _Queue:
        if tipo == 0:
            node = _Queue.pop() #en profundidad
        elif tipo == 1:
            node = _Queue.pop(0) # anchura

        if node != meta: 
            temp_list = Generar_states(node, _patch, dot)[:]
            print("Generate", temp_list)
            _Queue.extend(temp_list.copy())      
        elif node == meta:
            print("End......")
            break 



dot = graphviz.Digraph(comment='Arbol de decisión')
algoritmo(0, _patch, dot) #LLAMAMO EL METEDO PRINCIPAL. 
dot.render()

La funcion

Make_node() es esta

def Make_Node(state1, state2, id_node, _patch, dot, hijo_padre):
    if hijo_padre == 0: # si el nodo es padre
        id_node += 1
        _patch.append((dict(state1), id_node)) #vamos guardando el nodo y sus id's
        dot.node(str(id_node), estado(dict(state1)))
    elif hijo_padre == 1: #si se trata de un nodo hijo debe creear
        id_node +=1
        _patch.append((dict(state2), id_node))
        dot.node(str(id_node), estado(dict(state2)))
        dot.edge(str([ w[1] for w in _patch if w[0] == state1].pop()), str(id_node))

    return id_node, _patch, dot

Es muy probable que se puede hacer de mejor manera y seguramente tenga varios detalles, me escudo en que aun soy nuevo en la programación y soy mas nuevo aun en python :p

0
def crea(n):
    matriz=[]
    for i in range (n+1):
        matriz.append([0]*(2*n+1))
    return matriz

def poneuno(m):
    mitad=n*2//2
    for i in range(len(m)):
            m[i][mitad+i]=1
            m[i][mitad-i]=1

    return m

def ordena(m):
    n = len(m)
    for i in range(n):
        for j in range(0,2*n-1):
            if m[i][j]==0:
                m[i][j]=""
            print('{:>4}'.format(m[i][j]), end= '')
        print()

def llena(m):
    for i in range(len(m)):
        if i>1:
            for j in range(0,len(m)*2-2):
                m[i][j]=m[i-1][j-1]+m[i-1][j+1]

    return m

n=int(input("n: "))
matriz=crea(n)

matriz=poneuno(matriz) matriz=llena(matriz) ordena(matriz)

"""trianulo recursivo"""

def f1(n):              # Imprime n-1 blancos.
    if (n > 0):
        print('{:3}'.format(' '), end='')
        f1(n-1)

def f2(i, n):               # Imprime secuencia ascendente.
    if (i <= n):
        print('{:3}'.format(i), end='')
        f2(i + 1, n)

def f3(i):                  # Imprime secuencia descendente.
    if (i >= 1):
        print('{:3}'.format(i), end='')
        f3(i - 1)

def piramide(fila, n):
    f1(n - fila)            # Imprime n – 1 blancos
    f2(1, fila)         # Imprime secuencia ascendente
    f3(fila - 1)            # Imprime secuencia descencente
    print()
    if (fila <  n  ):
        piramide(fila + 1, n)       # imprime n filas .


def r1(n,i):
    if i<n and i>0:
        print(n,end="")
        r1(n,i-1)

def r2(i,n):
    if (i <= n)and i>0:
        print('{:3}'.format(i), end='')
        f2(i - 1, n)

def rombo(fila,n):
    r1(n,n)
    r2(n,n)
1
-1
import os

class node():
    def __init__(self, dato):
        self.left = None
        self.right = None
        self.dato = dato

class arbol():
    def __init__(self):
        self.root = None

    def insert(self, a, dato):
        if a == None:
            a = node(dato)
        else:
            d = a.dato
            if dato < d:
                a.left = self.insert(a.left, dato)
            else:
                a.right = self.insert(a.right, dato)
        return a

    def inorder(self, a):
        if a == None:
            return None
        else:
            self.inorder(a.left)
            print(a.dato)
            self.inorder(a.right)

    def preorder(self, a):
        if a == None:
            return None
        else:
            print(a.dato)
            self.preorder(a.left)
            self.preorder(a.right)

    def postorder(self, a):
        if a == None:
            return None
        else:
            self.postorder(a.left)
            self.postorder(a.right)
            print(a.dato)

    def buscar(self, dato, a):
        if a == None:
            return None
        else:
            if dato == a.dato:
                return a.dato
            else:
                if dato < a.dato:
                    return self.buscar(dato, a.left)
                else:
                    return self.buscar(dato, a.right)

tree = arbol()

while True:
    os.system("cls")
    print("Arbol ABB")
    opc = input("\n1.-Insertar nodo \n2.-Inorden \n3.-Preorden \n4.-Postorden \n5.-Buscar \n6.-Salir \n\nElige una opcion -> ")

    if opc == '1':
        nodo = input("\nIngresa el nodo -> ")
        if nodo.isdigit():
            nodo = int(nodo)
            tree.root = tree.insert(tree.root, nodo)
        else:
            print("\nIngresa solo digitos...")
    elif opc == '2':
        if tree.root == None:
            print("Vacio")
        else:
            tree.inorder(tree.root)
    elif opc == '3':
        if tree.root == None:
            print("Vacio")
        else:
            tree.preorder(tree.root)
    elif opc == '4':
        if tree.root == None:
            print("Vacio")
        else:
            tree.postorder(tree.root)
    elif opc == '5':
        nodo = input("\nIngresa el nodo a buscar -> ")
        if nodo.isdigit():
            nodo = int(nodo)
            if tree.buscar(nodo, tree.root) == None:
                print("\nNodo no encontrado...")
            else:
                print("\nNodo encontrado -> ",tree.buscar(nodo, tree.root), " si existe...")
        else:
            print("\nIngresa solo digitos...")        
    elif opc == '6':
        print("\nElegiste salir...\n")
        os.system("pause")
        break
    else:
        print("\nElige una opcion correcta...")
    print()
    os.system("pause")

print()

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.