Livre Ali en python: Sec.2 à 5 Graph (préparation)

Préparation: Mise en place de différents graphiques

Implémenté dans le dictionnaire python (correspond à l'implémentation dans la liste adjacente)

Recevez les informations de chaque arête à partir de l'entrée standard et mettez à jour le dictionnaire.

Dans le graphe orienté, {node1: node2} exprime le bord de node1 → node2. Le graphe non orienté est représenté par {node1: node2, node2: node1} du graphe orienté. Dans le cas de la pondération, il s'agit de {node1: [node2, weight]}.

import copy
def join_dic(a, b):
    for i in b:
        if (i in a):
            if type(a[i]) != list:
                a[i] = [a[i],b[i]]
                a[i] = list(set(a[i]))
                if len(a[i]) ==1:
                    a[i] = a[i][0]
            elif not (b[i] in a[i]):
                a[i].append(b[i])
        else:
            a[i] = b[i]

    return a

def d_to_ud(a):
    output = copy.deepcopy(a)
    for i in a:
        nodes = a[i]
        if type(nodes) ==int:
            join_dic(output,{nodes:i})
        else:
            for j in nodes:
                join_dic(output,{j:i})
    return output


graph = {}
while 1:
    edge = input()
    if edge  == "":
        break
    edge = list(map(int,edge.split()))
    dic = {edge[0]:edge[1]}
    graph = join_dic(graph,dic)

print(graph)

print(d_to_ud(graph))
    
def join_weighted_graph(a, b):
    ## a = {from:[to, weight]}

    for i in b:
    
        if i in a:
          if type(a[i][0]) == list:
            a[i].append(b[i])
          else:
            a[i] = [a[i],b[i]]
        else:
          a[i] = b[i]

    return a


def d_to_ud_weighted(a):
    output = copy.deepcopy(a)
    for i in a:

        if type(a[i][0]) == list:

            for j in a[i]:

               node = j[0]
               weight = j[1]

               new_edge = {node:[i,weight]}

               join_weighted_graph(output,new_edge)

        else:
            join_weighted_graph(output,{a[i][0]:[i,a[i][1]]})
    return output


graph = {}    
while 1:
    edge = input()
    if edge == "":
        break
    edge = list(map(int,edge.split()))

    graph = join_weighted_graph(graph, {edge[0]:[edge[1],edge[2]]})

print(graph)

print(d_to_ud_weighted(graph))

Postscript)

première moitié: contribution

0 1
1 2
2 0

production

{0: 1, 1: 2, 2: 0}
{0: [1, 2], 1: [0, 2], 2: [0, 1]}

Seconde moitié:

contribution

1 2 3
1 4 2
2 4 -1
2 3 4
3 4 5

production

{1: [[2, 3], [4, 2]], 2: [[4, -1], [3, 4]], 3: [4, 5]}
{1: [[2, 3], [4, 2]], 2: [[4, -1], [3, 4], [1, 3]], 3: [[4, 5], [2, 4]], 4: [[1, 2], [2, -1], [3, 5]]}

Addendum 2) Utilisez autopep8 pour être conforme à pep8

import copy


def join_dic(a, b):
    for i in b:
        if (i in a):
            if type(a[i]) != list:
                a[i] = [a[i], b[i]]
                a[i] = list(set(a[i]))
                if len(a[i]) == 1:
                    a[i] = a[i][0]
            elif not (b[i] in a[i]):
                a[i].append(b[i])
        else:
            a[i] = b[i]

    return a


def d_to_ud(a):
    output = copy.deepcopy(a)
    for i in a:
        nodes = a[i]
        if type(nodes) == int:
            join_dic(output, {nodes: i})
        else:
            for j in nodes:
                join_dic(output, {j: i})
    return output


graph = {}
while 1:
    edge = input()
    if edge == "":
        break
    edge = list(map(int, edge.split()))
    dic = {edge[0]: edge[1]}
    graph = join_dic(graph, dic)

print(graph)

print(d_to_ud(graph))


def join_weighted_graph(a, b):
    # a = {from:[to, weight]}

    for i in b:

        if i in a:
            if type(a[i][0]) == list:
                a[i].append(b[i])
            else:
                a[i] = [a[i], b[i]]
        else:
            a[i] = b[i]

    return a


def d_to_ud_weighted(a):
    output = copy.deepcopy(a)
    for i in a:

        if type(a[i][0]) == list:

            for j in a[i]:

                node = j[0]
                weight = j[1]

                new_edge = {node: [i, weight]}

                join_weighted_graph(output, new_edge)

        else:
            join_weighted_graph(output, {a[i][0]: [i, a[i][1]]})
    return output


graph = {}
while 1:
    edge = input()
    if edge == "":
        break
    edge = list(map(int, edge.split()))

    graph = join_weighted_graph(graph, {edge[0]: [edge[1], edge[2]]})

print(graph)

print(d_to_ud_weighted(graph))