__author__ = 'kaare_000'
import networkx as nx
import random as r

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

def bfs2(dict, start, finish):
    current= start
    nodes = [current]
    j=1
    visited = [current]
    while(finish != current):
        current = nodes[0]
        visited.append(nodes[0])
        setvisited = set(visited)
        for i in range(len(dict[current])):
            if dict[current][i] not in setvisited:
                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]

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

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

def main(n, probability, seed):
    start = 0
    finish = 22
    G = nx.fast_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)

def printing():
    for i in range(5,10):
        n = 2**i
        prob = 0.3
        print('N = ', n,'\nProbability = ', prob)
        main(n, prob, '142845IAPB')
        print()

printing()