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

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


def bfs2(G, start, finish):
    dict = nx.to_dict_of_lists(G)
    current= start
    nodes = [current]
    j=0
    visited = [current]
    while(finish not in set(visited)):
        for i in range(len(dict[current])):
            nodes.append(dict[current][i])
        visited.append(current)
        nodes.pop(0)
        current = nodes[j+1]
        j += 1
    print('Mäluga, külastatud tipud = ', j)

def bfs3(G, start, finish):
    dict = nx.to_dict_of_lists(G)
    current= start
    nodes = [current]
    j=0
    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+1]
        j += 1

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

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

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

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

def printing():
    for i in range(1,7):
        n = i*100
        prob = r.choice([0.2,0.3,0.4,0.5])
        print('N = ', n,'\nProbability = ', prob)
        main(n, prob, '142845IAPB')
        print()

printing()