implementation of problem C

probC.py

import random
from collections import defaultdict
from datetime import datetime
from math import log, ceil


class Graph:

    def __init__(self, nb_vertex, nb_max_edge_per_node):
        self.graph = defaultdict(list)
        self.nb_vertex = nb_vertex
        for i in range(nb_vertex):
            self.graph[i] = []

        self.nb_max_edge_per_node = nb_max_edge_per_node
        self.nb_connected_vertex = 0
        self.create_connect()
        self.node_has_transmit = [False] * nb_vertex
    
    #creating a random graph with nb_vertex
    def create_connect(self):
        for i in range(self.nb_vertex):
            nb_connections = len(self.graph[i])
            not_k_connected_node = self.get_not_k_connected_node(i)
            if self.nb_max_edge_per_node - nb_connections <= len(not_k_connected_node):
                k_edges = random.sample(not_k_connected_node, self.nb_max_edge_per_node - nb_connections)
                for k_edge in k_edges:
                    self.addEdge(i, k_edge)

        # count unconnected nodes to take them into account
        count_unconnected = 0
        for i in range(self.nb_vertex):
            if len(self.graph[i]) != k:
                count_unconnected += 1

        self.nb_connected_vertex = self.nb_vertex - count_unconnected
    
    #Utility function to get the nodes that have less than nb_max_edge_per_node neighbors
    def get_not_k_connected_node(self, source):
        not_k_connected_node = []
        for node, neighbors in self.graph.items():
            if len(neighbors) < self.nb_max_edge_per_node and node != source:
                not_k_connected_node.append(node)
        return not_k_connected_node
    
    
    def addEdge(self, src, dest):
        self.graph[src].append(dest)
        self.graph[dest].append(src)
    
    #Determines if all the computers had broadcasted their message
    def is_all_sent(self, debug=False, nb_iteration=0):
        count_sent = 0
        for sent in self.node_has_transmit:
            count_sent += (1 if sent else 0)
        if debug:
            print(count_sent, ' out', self.nb_connected_vertex, 'in  iteration', nb_iteration)
        return count_sent == self.nb_connected_vertex
    
    #doing the N round
    def do_N_round(self, c=5):
        self.node_has_transmit = [False] * self.nb_vertex
        nb_round = ceil(c * log(self.nb_vertex) * self.nb_max_edge_per_node)
        for i in range(nb_round):
            if self.is_all_sent():
                self.is_all_sent(debug=True, nb_iteration=i + 1)
                return True
            self.do_round()

        return self.is_all_sent(debug=True, nb_iteration=c)
    
    #single round function
    def do_round(self):
        chance_is_active = 1 / self.nb_max_edge_per_node

        # Activate nodes with a chance of 1/k or not
        active_nodes = [False] * self.nb_vertex
        for i in range(self.nb_vertex):
            if random.random() <= chance_is_active:
                active_nodes[i] = True

        # For each node check if it has transmited the message or not
        for i in range(self.nb_vertex):
            if len(self.graph[i]) == self.nb_max_edge_per_node and self.is_transmitable(i, active_nodes):
                self.node_has_transmit[i] = True

        # print('nb_sent', self.is_all_sent())
    
    #Utility function to check if a node can receive a message
    def is_transmitable(self, source, active_nodes):
        count_active_nodes = 0
        for neighbors in self.graph[source]:
            if active_nodes[neighbors]:
                count_active_nodes += 1
        return (count_active_nodes == 1)
    
    #Applicating the boss algorithm several times to check the accuracy of his method with c large enough
    def benchmark(self, c=5, nbSimulation=100):
        random.seed(datetime.now())
        count_success = 0
        for _ in range(nbSimulation):
            count_success += 1 if self.do_N_round(c=c) else 0
        print('number of sucess', count_success, ' out of ', nbSimulation, ' percentage ',
              (count_success / nbSimulation) * 100)


if __name__ == '__main__':
    random.seed(datetime.now())
    N = 2000
    k = 10
    graph = Graph(N, k)
    graph.benchmark()