Complementos I Práctica Lab 3

#! /usr/bin/python
# -*- coding: utf-8 -*-
from practica2 import *

# 3ra Practica Laboratorio
# Complementos Matematicos I
# Consigna: Implementar los siguientes metodos


'''
Recordatorio:
- Un camino/ciclo es Euleriano si contiene exactamente 1 vez
a cada arista del grafo
- Un camino/ciclo es Hamiltoniano si contiene exactamente 1 vez
a cada vértice del grafo
'''


#Falta armar los TypeError y ver de hacer más lindo el código.


def check_is_hamiltonian_trail(graph, path):
    """Comprueba si una lista de aristas constituye un camino hamiltoniano
    en un grafo.

    Args:
        graph (grafo): Grafo en formato de listas.
                       Ej: (['a', 'b', 'c'], [('a', 'b'), ('b', 'c')])

        path (lista de aristas): posible camino
                                 Ej: [('a', 'b'), ('b', 'c')]

    Returns:
        boolean: path es camino hamiltoniano en graph

    Raises:
        TypeError: Cuando el tipo de un argumento es inválido
    """
    if len(path) == 0:
        if len(graph[0]) == 0:
            return True
        return False

    for prueba in path:
        flag = 0
        for arista in graph[1]:
            if prueba == arista:
                flag = 1
                break
        if flag == 0:
            return False


    usosDeVertices = [0 for x in range(len(graph[0]))]
    for (indice, vert) in enumerate(graph[0]):
        if vert == path[0][0]:
            usosDeVertices[indice] += 1
            break

    for arista in path:
        for (indice, vert) in enumerate(graph[0]):
            if vert == arista[1]:
                usosDeVertices[indice] += 1
                break

    for contador in usosDeVertices:
        if contador != 1:
            return False

    return True


def check_is_hamiltonian_circuit(graph, path):
    """Comprueba si una lista de aristas constituye un ciclo hamiltoniano
    en un grafo.

    Args:
        graph (grafo): Grafo en formato de listas.
                       Ej: (['a', 'b', 'c'], [('a', 'b'), ('b', 'c')])

        path (lista de aristas): posible ciclo
                                 Ej: [('a', 'b'), ('b', 'c')]

    Returns:
        boolean: path es ciclo hamiltoniano en graph

    Raises:
        TypeError: Cuando el tipo de un argumento es inválido
    """
    if len(path) == 0:
        if len(graph[0]) == 0:
            return True
        return False

    for prueba in path:
        flag = 0
        for arista in graph[1]:
            if prueba == arista:
                flag = 1
                break
        if flag == 0:
            return False


    usosDeVertices = [0 for x in range(len(graph[0]))]
    for (indice, vert) in enumerate(graph[0]):
        if vert == path[0][0]:
            usosDeVertices[indice] += 1
            break

    for arista in path:
        for (indice, vert) in enumerate(graph[0]):
            if vert == arista[1]:
                usosDeVertices[indice] += 1
                break

    for (indice, contador) in enumerate(usosDeVertices):
        if graph[0][indice] == path[0][0]:
            if contador != 2:
                return False
        else:
            if contador != 1:
                return False

    return True


def check_is_eulerian_trail(graph, path):
    """Comprueba si una lista de aristas constituye un camino euleriano
    en un grafo.

    Args:
        graph (grafo): Grafo en formato de listas.
                       Ej: (['a', 'b', 'c'], [('a', 'b'), ('b', 'c')])

        path (lista de aristas): posible camino
                                 Ej: [('a', 'b'), ('b', 'c')]

    Returns:
        boolean: path es camino euleriano en graph

    Raises:
        TypeError: Cuando el tipo de un argumento es inválido
    """
    if len(path) == 0:
        if len(graph[0]) == 0:
            return True
        return False

    usosDeVertices = [0 for x in range(len(graph[0]))]
    usosDeAristas = [0 for x in range(len(graph[1]))]
    for (numero, prueba) in enumerate(path):
        if (numero != len(path) - 1) and path[numero][1] !=  path[numero + 1][0]:
            return False
        flag = 0
        for (indice, arista) in enumerate(graph[1]):
            if prueba == arista:
                flag = 1
                usosDeAristas[indice] += 1
                break

        for (indice, vertice) in enumerate(graph[0]):
            if vertice == prueba[0]:
                usosDeVertices[indice] += 1
            if vertice == prueba[1]:
                usosDeVertices[indice] += 1

        if flag == 0:
            return False

    for contador in usosDeVertices:
        if contador == 0:
            return False

    for contador in usosDeAristas:
        if contador != 1:
            return False

    return True


def check_is_eulerian_circuit(graph, path):
    """Comprueba si una lista de aristas constituye un ciclo euleriano
    en un grafo.

    Args:
        graph (grafo): Grafo en formato de listas.
                       Ej: (['a', 'b', 'c'], [('a', 'b'), ('b', 'c')])

        path (lista de aristas): posible ciclo
                                 Ej: [('a', 'b'), ('b', 'c')]

    Returns:
        boolean: path es ciclo euleriano en graph

    Raises:
        TypeError: Cuando el tipo de un argumento es inválido
    """
    if check_is_eulerian_trail(graph, path) and (len(path) == 0 or path[0][0] == path[len(path)-1][1]):
        return True
    return False


def graph_has_eulerian_circuit(graph):
    """Comprueba si un grafo no dirigido tiene un circuito euleriano.

    Args:
        graph (grafo): Grafo en formato de listas.
                       Ej: (['a', 'b', 'c'], [('a', 'b'), ('b', 'c')])

    Returns:
        boolean: graph tiene un circuito euleriano

    Raises:
        TypeError: Cuando el tipo del argumento es inválido
    """
    if len(componentes_conexas(graph)) > 1:
        return False

    gradosDeVertices = [0 for x in range(len(graph[0]))]

    for (vert1, vert2) in graph[1]:
        for (indice, vertice) in enumerate(graph[0]):
            if vertice == vert1:
                gradosDeVertices[indice] += 1
            if vertice == vert2:
                gradosDeVertices[indice] += 1

    for grado in gradosDeVertices:
        if grado % 2 == 1:
            return False

    return True


def estan_conectados(graph, vertA, vertB):
    for (indice, arista) in enumerate(graph[1]):
        if (arista[0] == vertA and arista[1] == vertB) or (arista[0] == vertB and arista[1] == vertA):
            return indice
    return -1

def verticeQueNoEs (vertice, arista):
    if vertice == arista[0]:
        return arista[1]
    return arista[0]

def find_eulerian_circuit(graph):
    """Obtiene un circuito euleriano en un grafo no dirigido, si es posible

    Args:
        graph (grafo): Grafo en formato de listas.
                       Ej: (['a', 'b', 'c'], [('a', 'b'), ('b', 'c')])

    Returns:
        path (lista de aristas): circuito euleriano, si existe
        None: si no existe un circuito euleriano

    Raises:
        TypeError: Cuando el tipo del argumento es inválido
    """
    if len(componentes_conexas(graph)) > 1:
        return None

    aristasRestantes = graph[1]
    verticeInicial = graph[0][0]
    verticeActual = graph[0][0]
    camino = []

    while aristasRestantes != []:
        print camino
        posiblesAristas = []
        for vertice in graph[0]:
            conexion = estan_conectados( (graph[0], aristasRestantes), verticeActual, vertice)
            if conexion != -1:
                compConexasActuales = len(componentes_conexas((graph[0], aristasRestantes)))
                compConexasNuevas = len(componentes_conexas((graph[0], aristasRestantes[:conexion] + aristasRestantes[conexion+1:])))
                if compConexasNuevas > compConexasActuales :
                    puente = True
                else:
                    puente = False

                posiblesAristas = posiblesAristas + [(aristasRestantes[conexion], conexion, puente)]


        if posiblesAristas == []:
            break
        else:
            flag = 0
            for opcion in posiblesAristas:
                if opcion[2] == False:
                    flag = 1
                    verticeActual = verticeQueNoEs(verticeActual, opcion[0])
                    camino = camino + [opcion[0]]
                    aristasRestantes = aristasRestantes[:opcion[1]] + aristasRestantes[opcion[1]+1:]
                    break

            if flag == 0:
                verticeActual = verticeQueNoEs(verticeActual, posiblesAristas[0][0])
                camino = camino + [posiblesAristas[0][0]]
                aristasRestantes = aristasRestantes[:posiblesAristas[0][1]] + aristasRestantes[posiblesAristas[0][1]+1:]



    if len(camino) == len(graph[1]) and verticeActual == verticeInicial:
        return camino

    return None


def main():
    grafo = (['A'] , [('A','A')])
    print(find_eulerian_circuit(grafo))
    print()
    print()
    grafo = (['A','B','C','D'], [('A','A'),('A','B'),('B','C'),('C','D'),('D','A'),('B','D'),('A','C'),('A','D'),('B','C')])
    print(find_eulerian_circuit(grafo))
    print()
    print()
    grafo = (['A','B','C','D','E','F','G'], [('A','D'),('A','B'),('B','C'),('D','C'),('E','C'),('G','C'),('E','F'),('G','F')] )
    print(find_eulerian_circuit(grafo))
    print()
    print()

if __name__ == '__main__':
    main()