__author__ = 'kaare_000'
import matplotlib.pyplot as plt
import networkx as nx
import random as r

def bfs(dict, start, finish):
    print(dict)
    current= start
    nodes = [current]
    j=1
    while(finish != current):
        current = nodes[0]
        for i in range(len(dict[current])):
            nodes.append(dict[current][i])
        current = nodes[j]
        j += 1
        nodes.pop(0)
    print('Ilma mäluta = ',j)



def bfs2(dict, start, finish):
    current= start
    nodes = []
    nodes.append(current)
    j=1
    visited = []
    while(finish not in set(visited)):
        current = nodes[0]
        visited = list(visited)
        visited.append(nodes[0])
        visited = set(visited)
        for i in range(len(dict[current])):
            if dict[current][i] not in visited:
                nodes.append(dict[current][i])
        j += 1
        nodes.pop(0)

    print('Mäluga, külastatud tipud = ', j)

def bfs3(dict, start, finish):
    current= start
    nodes = [current]
    j=1
    seen = [current]
    for i in range(len(dict[current])):
        seen.append(dict[current][i])
    while(finish not in seen):
        for i in range(len(dict[current])):
            if dict[current][i] not in set(seen):
                seen.append(dict[current][i])
            else:
                nodes.append(dict[current][i])
        nodes.pop(0)
        current = nodes[j]
        j += 1

    print('Mäluga, nähtud tipud = ', j)

def main(n, probability, seed):
    start = r.randint(0,n)
    finish = r.randint(0,n)
    G = nx.gnp_random_graph(n,probability,seed=seed)
    dict = nx.to_dict_of_lists(G)

    bfs(dict, start, finish)
    bfs2(dict, start, finish)
    bfs3(dict, start, finish)

#main(512, r.choice([0.2,0.3,0.4,0.5]), '142845IAP')

def printing():
    for i in range(4,10):
        n = 2**i
        prob = r.choice([0.3])
        print('N = ', n,'\nProbability = ', prob)
        main(n, prob, '142845iapb')
        print()

printing()