import networkx as nx
from collections import deque

def afegir_aresta(g, ni, nd, codi_mis, h, m) :
    g.add_edge(ni, nd, codi = codi_mis, hora = h, minut = m)

def crear_MultiDiGraf(nodes, arestes):
    g = nx.MultiDiGraph()
    g.add_nodes_from(nodes)
    for e in arestes:
        ni, nd, codi_mis, h, m = e
        afegir_aresta(g, ni, nd, codi_mis, h, m)
    return g

def filtrar_MultiDiGraf_1(g):
    l =[]
    for n in g:
        if g.in_degree(n) > g.out_degree(n) :
            l.append(n)
    l.sort()
    return l

def filtrar_MultiDiGraf_2(g):
    lc = list(filter(lambda n: g.in_degree(n) > g.out_degree(n), g.nodes()))
    return sorted(lc)

# tria la funcio
filtrar_MultiDiGraf = filtrar_MultiDiGraf_1
#filtrar_MultiDiGraf = filtrar_MultiDiGraf_2

def temps_anterior(h1, m1, h2, m2) :
    return h1 < h2 or (h1 == h2 and m1 <m2)

def primer_enviament_1(g, node, codi) :
    hora_min = 24
    minut_min = 0
    receptor = ''
    for d in g[node]: 
        for i in g[node][d]:
            codiaresta = g[node][d][i]['codi']
            if codiaresta == codi: 
                hora, minut = g[node][d][i]['hora'], g[node][d][i]['minut']
                if temps_anterior(hora, minut, hora_min, minut_min):
                    hora_min, minut_min, receptor =  hora, minut, d
    if receptor !='':
        return True, hora_min, minut_min, receptor
    else:
        return False, 0, 0 , ''

def primer_enviament_2(g, node, codi) :
    hora_min, minut_min = 24, 0
    receptor = ''
    for a in g.out_edges(node, data=True):
        codiaresta = a[2]['codi']
        if codiaresta == codi:
            destí = a[1]
            hora, minut = a[2]['hora'], a[2]['minut']
            if temps_anterior(hora, minut, hora_min, minut_min):
                hora_min, minut_min, receptor =  hora, minut, destí
    if receptor !='':
        return True, hora_min, minut_min, receptor
    else:
        return False, 0, 0 , ''

def primer_enviament_3(g, persona, codi):
    # iterador sobre totes les arestes que arriben a la persona, incloent les etiquetes
    it1 = g.out_edges([persona], data=True)
    # ens quedem només amb els mails del codi indicat
    it2 = filter(lambda x: x[2]['codi'] == codi, it1)
    # ens quedem amb l'hora, el minut i l'emissor del mail
    it3 = map(lambda x: (x[2]['hora'], x[2]['minut'], x[1]), it2)
    # trobem el d'hora mínima;
    # si l'iterador és buit, ret serà el valor per defecte
    ret = min(it3, default=(0, 0, ''))
    # retornem True o False més les dades del mínim
    return (ret[2]!='',) + ret

# tria la funcio
# primer_enviament = primer_enviament_1
# primer_enviament = primer_enviament_2
primer_enviament = primer_enviament_3

def primera_recepcio_1(g, node, codi):
    hora_min = 24
    minut_min = 0
    emissor = ''
    for d in g.predecessors(node): 
        for i in g[d][node]:
            codiaresta = g[d][node][i]['codi']
            if codiaresta == codi: 
                hora, minut = g[d][node][i]['hora'], g[d][node][i]['minut']
                if temps_anterior(hora, minut, hora_min, minut_min):
                    hora_min, minut_min, emissor =  hora, minut, d
    if emissor !='':
        return True, hora_min, minut_min, emissor
    else:
        return False, 0, 0 , ''

def primera_recepcio_2(g, persona, codi):
    # iterador sobre totes les arestes que arriben a la persona, incloent les etiquetes
    it1 = g.in_edges([persona], data=True)
    # ens quedem només amb els mails del codi indicat
    it2 = filter(lambda x: x[2]['codi'] == codi, it1)
    # ens quedem amb l'hora, el minut i l'emissor del mail
    it3 = map(lambda x: (x[2]['hora'], x[2]['minut'], x[0]), it2)
    # trobem el d'hora mínima;
    # si l'iterador és buit, ret serà el valor per defecte
    ret = min(it3, default=(0, 0, ''))
    # retornem True o False més les dades del mínim
    return (ret[2]!='',) + ret
    
# tria la funcio
primera_recepcio = primera_recepcio_1    
#primera_recepcio = primera_recepcio_2    

def origen_missatge_1(g, node, codi):

    ha_enviat, hora_e, minut_e, receptor =  primer_enviament(g, node, codi)
    if not ha_enviat:
        return False
    ha_rebut, hora_r, minut_r, emissor  =  primera_recepcio(g, node, codi)
    if not ha_rebut:
        return True
    return temps_anterior(hora_e, minut_e, hora_r, minut_r)

def origen_missatge_2(g, cl, c):
    """
    Retorna True si cl ha enviat un missatge de codi c i 
    o bé no ha rebut cap missatge de codi c 
    o bé si l'ha rebut ha estat després del 1r enviament
    """
    be, he, me, re = primer_enviament(g, cl, c)
    br, hr, mr, rr = primera_recepcio(g, cl, c)
    return be and (not br or he*60+me < hr*60+mr)

# tria la funcio
origen_missatge = origen_missatge_1
#origen_missatge = origen_missatge_2
 
def recorregut_MultiDiGraf_1(g, cl):
    """
    Utilitzant descendants
    """
    return sorted(nx.descendants(g, cl))

def recorregut_MultiDiGraf_2(g, cl):
    """
    A partir dels nodes de l'arbre dfs en preordre
    """
    ng = nx.dfs_tree(g, cl)
    cjt = set(ng.nodes) -  {cl}
    return sorted(cjt)

# tria la solució que vols provar
recorregut_MultiDiGraf = recorregut_MultiDiGraf_2

def recorregut_missatge_MultiDiGraf_1(g, cl, c):
    """
    obtenir l'arbre dfs amb l'arrel cl
    i filtrar els nodes tals qu els arriba una aresta amb codi = c
    """
    s = set()
    for n2 in nx.descendants(g, cl):
        for n1 in g.pred[n2]:
            for i in g[n1][n2]:
                if g[n1][n2][i]['codi'] == c:
                    s.add(n2)
    return sorted(s)
 
def recorregut_missatge_MultiDiGraf_2(g, client, codi):
    """
    crear un nou graf que contingui només les arestes amb codi = codi
    sobre aquest nou graf, calcular el resultat cridant a la funció
    recorregut_MultiDiGraf
    """
    h = nx.MultiDiGraph()
    for a, b in g.edges():
        for i in range(len (g[a][b])):
            if g[a][b][i]['codi'] == codi:
                hora = g[a][b][i]['hora']
                minut = g[a][b][i]['minut']
                afegir_aresta(h, a, b, codi, hora, minut)
    return recorregut_MultiDiGraf(h, client)

def recorregut_missatge_MultiDiGraf_3(g, node, codi):
    """
    Recorregut en amplada, filtrant les arestes de codi donat
    i desant nodes visitats i nodes per visitar en llistes
    """
    lnodes = [node]
    visitats = [node]
    while len(lnodes) != 0:
        origen = lnodes.pop()
        for desti in g.successors(origen):
            for i in g[origen][desti]:
                if g[origen][desti][i]['codi'] == codi:
                    if desti not in visitats:
                        visitats.append(desti)
                        lnodes.append(desti)
    visitats.remove(node)
    visitats.sort()
    return visitats

def recorregut_missatge_MultiDiGraf_4(g, node, codi):
    """
    Com 2 però utilitzant el mètode edge_subgraph
    """
    totes_arestes = g.edges(data='codi', keys=True)
    arestes = filter(lambda x: x[3] == codi, totes_arestes)
    sg = g.edge_subgraph(map(lambda x: (x[0], x[1], x[2]), arestes))
    return recorregut_MultiDiGraf(sg, node)

# tria la solució que vols provar
recorregut_missatge_MultiDiGraf = recorregut_missatge_MultiDiGraf_4