I need to write python code that solves the following problem. An Erds–Rényi ran
ID: 3669062 • Letter: I
Question
I need to write python code that solves the following problem.
An Erds–Rényi random graph G(n,p) is generated by two parameters n: the number of vertices. p: a number in [0,1], which is the probability that each of the n(n+1)/2 edges is independently included in the graph. You can check wiki for more details. Problems Generating a random graph. Write a function to generate a random graph given n and p. Input: an integer n>1 and p in [0,1] Output: an undirected graph G. You can use whatever format to store the graph (e.g. adjacent list). Hint: Initiate G to be an empty graph. For each
i<j, generate a random number q between 0 and 1. If q<p then add the edge (i,j) to G (if you are using adjacent list then this involves updating the lists of both i and j). In Python, you can generate a random number in [0,1] using random.random() after importing random.
Computing the size of the largest connected component. Given a graph G and a threshold t, write a function to test whether G contains a connected component of t vertices or more.
Input: a graph G and and a number t
Output: 1 if G contains a connected componnet of t vertices or more. 0 otherwise.
Hint: One solution is the following. For each vertex, you can compute the number of vertices in its connected component by BFS or DFS. Then, the function returns 1 if there exists a vertex whose connected component has at least t vertices. There are much faster ways to do this using BFS or DFS.
Testing your algorithm on randomly generated graphs.
Let n = 40.
For each c in [0.1,1.9] with step 0.1, let p=c/n, generate 500 random graphs G(n,p) using your function for step 1.
Use your function for step 2 to calculate the percentage of graphs (out of the 500 graphs with the same c) whose largest connected componenet has at least t=n^{2/3}=40^{2/3}vertices.
Record the total running time of your program.
Output: a graph where the x-axis is c and the y-axis is the percentage. See an example below for n=30.
Hint: The total number of graphs you should generate is 500*19---there are 19 different c's and for each c you should generate 500 graphs. Note that the percentage is calculated for each c.
Explanation / Answer
class Node(object):
def __init__(self, index, neighbors):
self.index = index
# A set of indices (integers, not Nodes)
self.neighbors = set(neighbors)
def add_neighbor(self, neighbor):
self.neighbors.add(neighbor)
class Component(object):
def __init__(self, nodes):
self.nodes = nodes
self.adjacent_nodes = set()
for node in nodes:
self.adjacent_nodes.add(node.index)
self.adjacent_nodes.update(node.neighbors)
def size(self):
return len(self.nodes)
def node_indices(self):
return set(node.index for node in self.nodes)
def is_saturated(self):
return self.node_indices == self.adjacent_nodes
def add_node(self, node):
self.nodes.append(node)
self.adjacent_nodes.update(node.neighbors)
adj_matrix = [[0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
matrix_size = len(adj_matrix)
nodes = {}
for index in range(matrix_size):
neighbors = [neighbor for neighbor, value in enumerate(adj_matrix[index])
if value == 1]
nodes[index] = Node(index, neighbors)
components = []
index, node = nodes.popitem()
component = Component([node])
while nodes:
if not component.is_saturated:
missing_node_index = component.adjacent_nodes.difference(component.node_indices).pop()
missing_node = nodes.pop(missing_node_index)
component.add_node(missing_node)
else:
components.append(component)
index, node = nodes.popitem()
component = Component([node])
components.append(component)
print max([component.size for component in components])