import networkx as nx

def fusiona_zones1(gm, z1, z2, z3):
    for n in list(gm.neighbors(z1)) + list(gm.neighbors(z2)):
        gm.add_edge(z3, n)
    gm.remove_node(z1)
    gm.remove_node(z2)

    
def fusiona_zones2(gm, z1, z2, z3):
    v1 = set(gm[z1])
    v2 = set(gm[z2])
    v3 = (v1 | v2) - set([z1, z2]) # conjunt de veïns, exceptuant els dos nodes fusionats
    gm.remove_node(z1)
    gm.remove_node(z2)
    gm.add_node(z3)
    for vei in v3:
        gm.add_edge(z3, vei)

        
# tria la solució que vulguis
fusiona_zones = fusiona_zones1


def zones_de_pas1(gm, za, zb):
    if nx.has_path(gm, za, zb):
        zdp = set(g.nodes()) - set([za, zb])
        for path in nx.all_simple_paths(gm, za, zb):
            zdp = zdp & set(path)
        return zdp
    else:
        return {'IMPOSSIBLE'}


def zones_de_pas2(gm, za, zb):
    try:
        path = nx.shortest_path(gm, za, zb)
    except nx.exception.NetworkXNoPath:
        return {'IMPOSSIBLE'}
    zdp = set()
    for node in path[1:-1]:
        g2 = gm.copy()
        g2.remove_node(node)
        if not nx.has_path(g2, za, zb):
            zdp.add(node)
    return zdp


# tria la solució que vulguis         
zones_de_pas = zones_de_pas1