Complementos I Práctica Lab 1

#! /usr/bin/python

# 1ra Practica Laboratorio
# Complementos Matematicos I
# Consigna: Implementar los siguientes metodos
# Team Tutturu: Tomas Fernandez De Luco, Sebastian Moline, Gianni Weinand

import sys

def lee_grafo_stdin():
    '''
   Lee un grafo desde entrada estandar y devuelve su representacion como lista.
   Ejemplo Entrada:
       3
       A
       B
       C
       A B
       B C
       C B
   Ejemplo retorno:
       (['A','B','C'],[('A','B'),('B','C'),('C','B')])
   '''
    V = []
    E = []
    cant_nodos = int(raw_input())
    contador = 0
    for line in sys.stdin:
        contador = contador + 1
        if(contador <= cant_nodos):
            V.append(line[:-1])
        else:
            pepe = line.split()
            E.append((pepe[0],pepe[1]))

    return (V,E)



def lee_grafo_archivo(file_path):
    '''
   Lee un grafo desde un archivo y devuelve su representacion como lista.
   Ejemplo Entrada:
       3
       A
       B
       C
       A B
       B C
       C B
   Ejemplo retorno:
       (['A','B','C'],[('A','B'),('B','C'),('C','B')])
   '''
    V = []
    E = []
    with open(file_path, "r") as f:
        cant_nodos = int(f.readline())
        for i in range(cant_nodos):
            V.append(f.readline()[:-1])
        for line in f:
            pepe = line.split()
            E.append((pepe[0], pepe[1]))
    return (V,E)



def imprime_grafo_lista(grafo):
    '''
   Muestra por pantalla un grafo. El argumento esta en formato de lista.
   '''
    print("Vertices:")
    for x in grafo[0]:
        print x

    print("Aristas:")
    for (a,b) in grafo[1]:
        print(a + " " + b)



def lista_a_incidencia_dicc(grafo_lista):
    '''
   Transforma un grafo representado por listas a su representacion
   en matriz de incidencia.
    '''
    #Creamos un diccionario de pares nodo:indice
    indiceNodo = {}
    for (i,v) in enumerate(grafo_lista[0]):
        indiceNodo[v] = i

    #Creamos una matriz cuadrada de |V|*|E| y la llenamos de ceros.
    matriz = [[0 for x in range(len(grafo_lista[1]))] for y in range(len(grafo_lista[0]))]
    for (x,(a,b)) in enumerate(grafo_lista[1]):
        #Sumamos 1 en el lugar que corresponde a la fila de a y la columna de (a,b)
        matriz[indiceNodo[a]][x] += 1
        #Sumamos 1 en el lugar que corresponde a la fila de b y la columna de (a,b)
        matriz[indiceNodo[b]][x] += 1

    return (grafo_lista[0], matriz)

def lista_a_incidencia(grafo_lista):
    '''
   Transforma un grafo representado por listas a su representacion
   en matriz de incidencia.
   '''

    matriz = [[0 for x in range(len(grafo_lista[1]))] for y in range(len(grafo_lista[0]))]
    for (n,(a,b)) in enumerate(grafo_lista[1]):
        for x in range(len(grafo_lista[0])):
            if a == grafo_lista[0][x]:
                indiceA = x
                break
        for x in range(len(grafo_lista[0])):
            if b == grafo_lista[0][x]:
                indiceB = x
                break

        matriz[indiceA][n] += 1
        matriz[indiceB][n] += 1

    return (grafo_lista[0], matriz)


def incidencia_a_lista(grafo_incidencia):
    '''
   Transforma un grafo representado por una matriz de incidencia a su
   representacion por listas.
   '''
    V = grafo_incidencia[0]
    E = []

    #Recorremos las filas con y
    for y in range(len(V)):
        #verticeA y verticeB son los indices de los vertices en los que incide una arista.
        verticeA = verticeB = -1
        #Recorremos la fila y con x.
        for x in range(len(grafo_incidencia[1][y])):
            #Si vale 2, la arista es un bucle.
            if grafo_incidencia[1][y][x] == 2:
                verticeA = y
                verticeB = y
                break
            #Si vale 1, es una arista normal.
            if grafo_incidencia[1][y][x] == 1:
                #Si aun no asignamos verticeA, lo hacemos ahora.
                if verticeA == -1:
                    verticeA = y
                #Si ya lo asignamos, queda por asignar verticeB.
                else:
                    verticeB = y
                    break
        #Agregamos la arista a la lista, recordando que verticeA y verticeB son indices de V.
        E.append((V[verticeA],V[verticeB]))
    return (V,E)



def imprime_grafo_incidencia(grafo_incidencia):
    '''
   Muestra por pantalla un grafo.
   El argumento esta en formato de matriz de incidencia.
   '''
    print("Vertices:")
    for x in grafo_incidencia[0]:
        print x

    print("Matriz de incidencia:")
    for x in grafo_incidencia[1]:
        print x


def lista_a_adyacencia_dicc(grafo_lista):
    '''
   Transforma un grafo representado por listas a su representacion
   en matriz de adyacencia.
   '''
    #Creamos un diccionario de pares nodo:indice
    indiceNodo = {}
    for (i,v) in enumerate(grafo_lista[0]):
        indiceNodo[v] = i

    #Creamos una matriz de |V|*|V| y la llenamos de ceros.
    matriz = [[0 for x in range(len(grafo_lista[0]))] for y in range(len(grafo_lista[0]))]
    #Recorremos las aristas.
    for (a,b) in grafo_lista[1]:
        #En los lugares correspondientes al par de nodos, sumamos 1 por cada arista.
        matriz[indiceNodo[a]][indiceNodo[b]] += 1
        matriz[indiceNodo[b]][indiceNodo[a]] += 1

    return (grafo_lista[0], matriz)

def lista_a_adyacencia(grafo_lista):
    '''
   Transforma un grafo representado por listas a su representacion
   en matriz de adyacencia.
   '''
    matriz = [[0 for x in range(len(grafo_lista[0]))] for y in range(len(grafo_lista[0]))]
    for(a,b) in grafo_lista[1]:
        for x in range(len(grafo_lista[0])):
            if a == grafo_lista[0][x]:
                indiceA = x
                break

        for x in range(len(grafo_lista[0])):
            if b == grafo_lista[0][x]:
                indiceB = x
                break
        matriz[indiceA][indiceB] += 1
        matriz[indiceB][indiceA] += 1

    return (grafo_lista[0], matriz)



def adyacencia_a_lista(grafo_adyacencia):
    '''
   Transforma un grafo representado una matriz de adyacencia a su
   representacion por listas.
   '''
    V = grafo_adyacencia[0]
    E = []
    #Con y recorremos las filas de la matriz de adyacencia.
    for y in range(len(grafo_adyacencia[1])):
        #Comenzamos desde y para no repetir aristas.
        for x in range(y,len(grafo_adyacencia[1])):
            #Si x==y, estamos en un bucle y cada arista aumenta el valor en la matriz en 2.
            if x == y:
                step = 2
            #Si no, hay tantas aristas como el valor de la matriz.
            else:
                step = 1
            #Contando las aristas como corresponde, las agregamos a la lista.
            for i in range(0, grafo_adyacencia[1][y][x], step):
                #La arista es la tupla de nodos en las posiciones y, x de V.
                E.append((V[y], V[x]))
    return (V,E)

def imprime_grafo_adyacencia(grafo_adyacencia):
    '''
   Muestra por pantalla un grafo.
   El argumento esta en formato de matriz de adyacencia.
   '''
    print("Vertices:")
    for x in grafo_adyacencia[0]:
        print x

    print("Matriz de adyacencia:")
    for x in grafo_adyacencia[1]:
        print x


#################### FIN EJERCICIO PRACTICA ####################
grafo_adyacencia1 = (
    ['A', 'B', 'C', 'D'],
    [[0, 1, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0],]
)

grafo_adyacencia2 = (
    ['A', 'B', 'C', 'D'],
    [[0, 2, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0],]
)

def lee_entrada_1():
    count = 0
    for line in sys.stdin:
        count = count + 1
        print 'Linea: [{0}]'.format(line)
    print 'leidas {0} lineas'.format(count)


def lee_entrada_2():
    count = 0
    try:
        while True:
            line = raw_input()
            count = count + 1
            print 'Linea: [{0}]'.format(line)
    except EOFError:
        pass

    print 'leidas {0} lineas'.format(count)


def lee_archivo(file_path):
    print 'leyendo archivo: {0}'.format(file_path)
    count = 0

    with open(file_path, 'r') as f:
        first_line = f.readline()
        print 'primer linea: [{}]'.format(first_line)
        for line in f:
            count = count + 1
            #print 'Linea: [{0}]'.format(line)
    print 'leidas {0} lineas'.format(count)


def main():
    grafo = lee_grafo_archivo(sys.argv[1])
    imprime_grafo_lista(grafo)
    print
    imprime_grafo_adyacencia(lista_a_adyacencia(grafo))
    imprime_grafo_lista(adyacencia_a_lista(lista_a_adyacencia(grafo)))
    print
    imprime_grafo_incidencia(lista_a_incidencia(grafo))
    imprime_grafo_lista(incidencia_a_lista(lista_a_incidencia(grafo)))
    #~ # Para leer desde un archivo
    #    if (len(sys.argv) < 2):
    #        print 'ERROR. Argumento (file) faltante'
    #        return
    #    lee_archivo(sys.argv[1])


if __name__ == '__main__':
    main()