import networkx as nx
import itertools

def crea_graf(nomf):
    g = nx.Graph()
    with open(nomf, 'r') as f:
        nnodes = int(f.readline())
        for i in range(nnodes):
            nom, nservei, ntemps = f.readline().split(', ')
            g.add_node(nom, servei = nservei, temps = int(ntemps))
        for linia in f:
            node1, node2, t = linia.strip().split(', ')
            g.add_edge(node1, node2, temps =int(t))
    return g

def subgraf_serveis_tipus_1(g, tipus):
    # subgraf amb els serveis d'un tipus determinat
    lnodes = []
    for node in g:
        if g.nodes[node]['servei'] == tipus:
            lnodes.append(node)
    sg = g.subgraph(lnodes)
    return sg

def subgraf_serveis_tipus_2(g, tipus):
    itnodes = map(lambda x: x[0], filter(lambda x: x[1]==tipus, g.nodes(data='servei')))
    sg = g.subgraph(itnodes)
    return sg

# tria l'opció
#subgraf_serveis_tipus = subgraf_serveis_tipus_1
subgraf_serveis_tipus = subgraf_serveis_tipus_2

def temps_serveis_1(g):
    tnodes = 0
    for node in g:
        tnodes = tnodes + g.nodes[node]['temps']
    return tnodes

def temps_serveis_2(g):
    return sum(map(lambda x: g.nodes[x]['temps'], g.nodes()))

# tria l'opció
#temps_serveis = temps_serveis_1
temps_serveis = temps_serveis_2

def temps_despl_cami_1(g, cami):
    t = 0
    ant = cami[0]
    for node in cami[1:]:
        t = t + g[ant][node]['temps']
        ant = node
    return t

def temps_despl_cami_2(g, cami):
    tdespl = 0
    for i in range(len(cami)-1):
        tdespl = tdespl + g[cami[i]][cami[i+1]]['temps']
    return tdespl

def temps_despl_cami_3(g, cami):
    arestes_cami = zip(cami, cami[1:])
    return sum(map(lambda x: g[x[0]][x[1]]['temps'] , arestes_cami))


# tria l'opció
#temps_despl_cami = temps_despl_cami_1
#temps_despl_cami = temps_despl_cami_2
temps_despl_cami = temps_despl_cami_3

"""
camí més rapid al graf g entre n1 i n2 que passa per tots els nodes de g
i temps per fer aquest cami
"""
def cami_mes_rapid_1(g, n1, n2):
    # tots els camins entre n1 i n2
    camins = nx.all_simple_paths(g, n1, n2)
    # selecció dels camins que passen per tots els nodes
    camins_valids = filter(lambda x: len(x)==g.order(), camins)
    cmin = next(camins_valids)
    tmin = temps_despl_cami(g, cmin) 
    for cami in camins_valids:
        t = temps_despl_cami(g, cami) 
        if t < tmin :
            tmin = t
            cmin = cami
    return cmin, tmin

def cami_mes_rapid_2(g, n1, n2):
    # tots els camins entre n1 i n2, ordenats de més a menys curt
    # considerant l'atribut temps de les arestes de g
    camins = nx.shortest_simple_paths(g, n1, n2, weight = 'temps')
    # selecció dels camins que passen per tots els nodes
    camins_valids = filter(lambda x: len(x)==g.order(), camins)
    cmin = next(camins_valids)
    tmin = temps_despl_cami(g, cmin) 
    return cmin, tmin

#tria l'opció
#cami_mes_rapid = cami_mes_rapid_1
cami_mes_rapid = cami_mes_rapid_2

def serveis(g, tipus, n1, n2):
    sg = subgraf_serveis_tipus(g, tipus)
    tnodes = temps_serveis(sg)
    cami_min, tmin = cami_mes_rapid(sg, n1, n2)
    return cami_min, tnodes+tmin