information_diffusion.py

import networkx as nx

def diffuse_information(G: nx.MultiGraph, seed: list, case='best_case'):       
    informed_nodes = {n: None for n in seed}
    needs_update = True

    while needs_update:
        needs_update = False
        for u, v, dt in G.edges(nbunch=informed_nodes, data='diffusion_time'):
            if u in informed_nodes:
                if informed_nodes[u] == None or dt[case] > informed_nodes[u]:
                    if v not in informed_nodes:
                        informed_nodes[v] = dt[case]
                        needs_update = True
                    else:
                        if informed_nodes[v] != None and dt[case] < informed_nodes[v]:
                            informed_nodes[v] = dt[case]
                            needs_update = True

            if v in informed_nodes:
                if informed_nodes[v] == None or dt[case] > informed_nodes[v]:
                    if u not in informed_nodes:
                        informed_nodes[u] = dt[case]
                        needs_update = True
                    else:
                        if informed_nodes[u] != None and dt[case] < informed_nodes[u]:
                            informed_nodes[u] = dt[case]
                            needs_update = True
    return informed_nodes

G_1 = nx.MultiGraph()

G_1.add_edge('a', 'b', diffusion_time={'best_case': 1})
G_1.add_edge('a', 'b', diffusion_time={'best_case': 2})
G_1.add_edge('a', 'c', diffusion_time={'best_case': 5})
G_1.add_edge('a', 'd', diffusion_time={'best_case': 1})
G_1.add_edge('b', 'c', diffusion_time={'best_case': 2})

diffuse_information(G_1, ['a']) # returns {'a': None, 'b': 1, 'c': 2, 'd': 1}

G_2 = nx.MultiGraph()

G_2.add_edge('a', 'b', diffusion_time={'best_case': 9})
G_2.add_edge('b', 'c', diffusion_time={'best_case': 5})
G_2.add_edge('a', 'd', diffusion_time={'best_case': 1})
G_2.add_edge('d', 'b', diffusion_time={'best_case': 2})
G_2.add_edge('d', 'e', diffusion_time={'best_case': 222})

diffuse_information(G_2, ['a']) # returns {'a': None, 'b': 2, 'd': 1, 'e': 222, 'c': 5}
diffuse_information(G_2, ['a', 'e']) # returns {'a': None, 'e': None, 'b': 2, 'd': 1, 'c': 5}