class Vertice(object):
    
    def __init__(self, n):
    #Se define el nombre del vertice y la lista de vecinos
        self.nombre = n
        self.vecinos = list()
        self.visitado = False
        self.padre = None
        self.nivel = -1

    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 = {}
    bordes = []
    indicearitas = {}

    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
            #Se recorre los bordes y se agregan.
            for fila in self.bordes:
                fila.append(0)
            self.bordes.append([0] * (len(self.bordes)+1))
            self.indicearitas[vertice.nombre] = len(self.indicearitas)
            return True
        else:
            return False


    def agregarBorde(self, u, v, peso=1):
    #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)
            self.bordes[self.indicearitas[u]][self.indicearitas[v]] = peso
            self.bordes[self.indicearitas[v]][self.indicearitas[u]] = peso
            return True
        else:
            return False

    def dfs (self, dato):
        if dato in self.vertices:
            self.vertices[dato].visitado = True
            for nodo in self.vertices[dato].vecinos:
                if self.vertices[nodo].visitado == False:
                    self.vertices[nodo].padre = dato
                    print ('\n' + str (nodo))
                    self.dfs(nodo)
    
    def bfs (self, dato):
        if dato in self.vertices:
            cola = [dato]
            self.vertices[dato].visitado = True
            self.vertices[dato].nivel = 0
            print ('\n' + str (dato))
            while (len(cola)>0):
                act = cola [0]
                cola = cola[1:]
                for v in self.vertices[act].vecinos:
                    if self.vertices[v].visitado == False:
                        cola.append(v)
                        self.vertices[v].visitado = True
                        self.vertices[v].nivel = self.vertices[act].nivel = 1
                        print ('\n' + str (v))

    def reiniciarvaldfs(self, dato):
        if dato in self.vertices:
            self.vertices[dato].visitado = False
            for nodo in self.vertices[dato].vecinos:
                if self.vertices[nodo].visitado == True:
                    self.vertices[nodo].padre = None
                    self.dfs(nodo)

    def reiniciarvalbfs(self, dato):
        if dato in self.vertices:
            cola = [dato]
            self.vertices[dato].visitado = False
            self.vertices[dato].nivel = -1
            while (len(cola)>0):
                act = cola [0]
                cola = cola[1:]
                for v in self.vertices[act].vecinos:
                    if self.vertices[v].visitado == True:
                        cola.append(v)
                        self.vertices[v].visitado = False
                        self.vertices[v].nivel = self.vertices[act].nivel = -1
    
    def printGrafo(self):
        #Se muestra el grafo.
        print('\n Grafo y sus relaciones:')
        for key in sorted(list(self.vertices.keys())):
            print(key + str(self.vertices[key].vecinos))

    def printmatriz(self):
        #Se muestra la matriz
        print('\n Matriz de Adyacencia:')
        for v, i in sorted(self.indicearitas.items()):
            print(v + ' ', end='')
            for j in range(len(self.bordes)):
                print(self.bordes[i][j], end='')
            print(' ')  


def opciones():
    print('''
*************************************************
*       Selecciona una opción del menu          *
*       ------------------------------          *
*  1. Agregar Vertices                          *
*  2. Crear relaciones                          *
*  3. Mostar Grafo                              *
*  4. Mostrar Matriz Adyacencia                 *
*  5. Mostrar recorrido DFS                     *
*  6. Mostrar recorrido BFS                     *
*  7. Salir                                     *
*************************************************
    ''')