#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Aug 28 14:40:14 2019

@author: phjo
"""

from stack import stack, queue

from random import randrange

g1 = [[1, 2], [6], [3, 4], [], [7, 8], [1], [], [], [6]]
g2 = [[1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], \
      [3, 7], [4, 6, 8], [5, 7]]

def aleatoire(n, a):
    """ crée un graphe orienté aléatoire à n noeuds et a arêtes """
    G = [[] for i in range(n)]
    for i in range(a):
        s, d = randrange(n), randrange(n)
        while s == d or d in G[s]: # une boucle infinie n'est pas impossible !
            s, d = randrange(n), randrange(n)
        G[s].append(d)
    return G
    
    

def bfs(G, node):
    L = []
    visited = {node}
    Q = queue()
    Q.enqueue(node)
    while not Q.isEmpty():
        print(Q.items)
        n = Q.dequeue()
        L.append(n)
        for w in G[n]:
            if w not in visited:
                Q.enqueue(w)
                visited.add(w)
    return L
            

def stackTraversal(G, node):
    L = []
    visited = {node}
    S = stack()
    S.push(node)
    while not S.isEmpty():
        n = S.pop()
        L.append(n)
        for w in G[n]:
            if w not in visited:
                S.push(w)
                visited.add(w)
    return L

def dfs(G, node):
    L = []
    visited = set()
    S = stack()
    S.push(node)
    while not S.isEmpty():
        n = S.pop()
        if n not in visited:
            visited.add(n)
            L.append(n)
            for w in G[n]:
                S.push(w)
    return L

def dfsAutre(G, node):
    L = [node]
    visited = {node}
    S = stack()
    S.push(node)
    while not S.isEmpty():
        n = S.peek()
        nextNode = False
        i = 0
        while not nextNode and i < len(G[n]):
            if G[n][i] not in visited:
                nextNode = True
            else:
                i += 1
        if nextNode:
            S.push(G[n][i])
            visited.add(G[n][i])
            L.append(G[n][i])
        else:
            S.pop()
    return L
                
# parcours en profondeur : version récursive (voir chapitre II)
def recdfs(G, node, visited = None):
    if visited == None:
        visited = {node}
    else:
        visited.add(node)
    L = [node]
    for w in G[node]:
        if w not in visited:
            L += recdfs(G, w, visited)
    return L
    
    

from time import time

def mesure(f, G, node):
    t1 = time()
    f(G, node)
    return time() - t1