#!/usr/bin/python
#-*- coding: utf-8 -*-
from collections import deque
import pygraphviz as pgv

"""
    'graph_gen.py' by Édouard Lumet <edouard.lumet@etu.enseeiht.fr> 1A APP IR @ N7
    With this program you can generate cyclic or complete graph and then you can either
    remove one vertex or run BFS or run Dijkstra.
"""

## VARS ##

GRAPH = {}
VISITED = {}
WEIGHT = {}
BFS_TREE = pgv.AGraph()
#DIJKSTRA = []
TYPE = ""
CHOICE = 9

## FUNCTIONS ##

# This function generates a cycle graph
def cycle():
    """
        Call this function to generate a cycle graph.
        It will be in the GRAPH dictionnary.
    """
    global TYPE
    print("This is a cycle graph.")
    i = 1 # You SHOULD NOT modify it
    while i <= VERTEX:
        VISITED[i] = False
        if i == 1:
            GRAPH[i] = [VERTEX, i+1]
        elif i == VERTEX:
            GRAPH[i] = [i-1, 1]
        else:
            GRAPH[i] = [i-1, i+1]
        i += 1
    TYPE = "cy"
    return GRAPH

# This function generates a complete graph
def complete():
    """
        Call this function to generate a complete graph.
        It will be in the GRAPH dictionnary.
    """
    global TYPE
    print("This is a complete graph.")
    adjlist = []
    i = 1 # You SHOULD NOT change it
    k = 1 # You SHOULD NOT change it
    while i <= VERTEX:
        VISITED[i] = False
        adjlist.append(i)
        i += 1
    while k <= VERTEX:
        adjlist_temp = list(adjlist)
        adjlist_temp.remove(k)
        GRAPH[k] = adjlist_temp
        k += 1
    TYPE = "co"
    return GRAPH

# This function removes a vertex from the current generated graph
def remove(vertex):
    """
        Call this function with the numerous of a vertex to remove
        this vertex of the graph you generated.
    """
    if TYPE == "cy":
        del VISITED[vertex]
        if vertex == 1:
            GRAPH[GRAPH.keys()[-1]][1] = vertex+1
            GRAPH[vertex+1][0] = GRAPH.keys()[-1]
        elif vertex == GRAPH.keys()[-1]:
            GRAPH[vertex-1][1] = 1
            GRAPH[1][0] = vertex-1
        else:
            GRAPH[vertex-1][1] = vertex+1
            GRAPH[vertex+1][0] = vertex-1
        del GRAPH[vertex]
    else:
        del GRAPH[vertex]
        for i in GRAPH:
            GRAPH[i].remove(vertex)
    return GRAPH

# This function runs BFS on a graph
def bfs(vertex):
    """
        Call this function with the numerous of a vertex to run BFS algorithm
        on the graph you generated from this vertex.
    """
    queue = deque([]) # LIFO, see line 3
    queue.append(vertex)
    VISITED[vertex] = True
    while queue != deque([]):
        vertex = queue.popleft()
        BFS_TREE.add_node(vertex)
        for neighbor in GRAPH[vertex]:
            if not VISITED[neighbor]:
                queue.append(neighbor)
                VISITED[neighbor] = True
    return BFS_TREE

# This function runs Dijkstra on a graph
def dijkstra(vertex):
    """
        Call this function with the numerous of a vertex to run Dijkstra's algorithm
        on the graph from this vertex.
    """
    return 0

# This function reset vars used to build graph and tree
def clear():
    """ Call this function to reset the graph you generated. """
    global GRAPH
    global VISITED
    global BFS_TREE
    GRAPH = {}
    VISITED = {}
    BFS_TREE = pgv.AGraph()

# This function prints graphs in a prettier way than simple dictionnary printing
def print_graph(graph):
    """
        Call this function with a graph to print it in a prettier way
        than simple dictionnary printing as it is implemented like that.
    """
    graphpgv = pgv.AGraph()
    for key, value in graph.items():
        print("{} : {}".format(key, value))
        graphpgv.add_edge(key, value[0])
        graphpgv.add_edge(key, value[1])
    graphpgv.write('graph.dot')
    graphpgv.layout('dot')
    graphpgv.draw('graph.png')
    graphpgv.draw


# This function prints trees
def print_tree(tree):
    """ Call this function with a tree to print it. """
    tree.write('BFS_tree.dot')
    tree.layout('dot')
    tree.draw('BFS_tree.png')
    tree.close()

## MAIN ##

while CHOICE != 0:
    # Menu (exit when 0 is typed by user)
    print("What do you want to do ?")
    print("\t1- Cycle graph")
    print("\t2- Complete graph")
    print("\t3- Remove vertex")
    print("\t4- Run BFS")
    #print("\t5- Run Dijkstra")
    print("\t6- Print current graph")
    print("\t7- Clear current graph")
    print("\t0- Quit")
    CHOICE = int(input("Type your choice (1,2,3,4,6,7,0) : "))
    while CHOICE < 1 and CHOICE > 7 and CHOICE == 5:
        CHOICE = int(input("Type your choice (1,2,3,4,6,7,0) : "))

    if CHOICE == 1:
        # Generate ycle graph
        VERTEX = int(input("Type a number of verteces (>2) : "))
        while VERTEX < 2:
            # Avoid an invalid number of verteces for a 
            VERTEX = int(input("Type a number of verteces (>2) : "))
        print_graph(cycle())
    elif CHOICE == 2:
        # Generate complete graph
        VERTEX = int(input("Type a number of verteces (>0) : "))
        while VERTEX < 1:
            VERTEX = int(input("Type a number of verteces (>0) : "))
        print_graph(complete())
    elif CHOICE == 3:
        # Remove one vertex
        VERTEX = int(input("Type the numerous of the vertex you want to remove : "))
        while VERTEX < 1 and VERTEX > GRAPH.keys()[-1]:
            VERTEX = int(input("Type the numerous of the vertex you want to remove : "))
        print_graph(remove(VERTEX))
    elif CHOICE == 4:
        # Run BFS
        VERTEX = int(input("Type the numerous of the source vertex to run BFS : "))
        while VERTEX < 1 and VERTEX > GRAPH.keys()[-1]:
            VERTEX = int(input("Type the numerous of the source vertex to run BFS : "))
        print_tree(bfs(VERTEX))
    #elif CHOICE == 5:
    #    # Run Dijkstra
    #    VERTEX = int(input("Type the numerous of the source vertex to run Dijkstra : "))
    #    print_tree(dijkstra(VERTEX))
    elif CHOICE == 6:
        # Print current graph
        print_graph(GRAPH)
    elif CHOICE == 7:
        # Clear current graph
        clear()
exit()