<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Class Session 4 Exercise
Step1:  Now, define a function that returns the index numbers of the neighbors of a vertex i, when the 
graph is stored in adjacency matrix format.  So your function will accept as an input a NxN numpy matrix.
Step2:  Define a function that enumerates the neighbors of a vertex i, when the 
graph is stored in adjacency list format (a list of lists)
Step3:  Define a function that enumerates the neighbors of a vertex i, when the 
graph is stored in edge-list format (a numpy array of length-two-lists).  Use numpy.where and numpy.unique
Step4:  This next function is the simulation funtion.  "n" is the number of vertices.
It returns a length-three list containing the average running time for enumerating the neighbor vertices of a vertex in the graph.
Step5:  A simulation with 1000 vertices clearly shows that adjacency list is fastest
Step6:  We see the expected behavior, with the running time for the adjacency-matrix and edge-list formats going up when we increase "n", but there is hardly any change in the running time for the graph stored in adjacency list format
<ASSISTANT_TASK:>
Python Code:
import numpy as np
import igraph
import timeit
import itertools
Explanation: Class Session 4 Exercise:
Comparing asymptotic running time for enumerating neighbors of all vertices in a graph
We will measure the running time for enumerating the neighbor vertices for three different data structures for representing an undirected graph:
    adjacency matrix
    adjacency list
    edge list
Let's assume that each vertex is labeled with a unique integer number.  So if there are N vertices, the vertices are labeled 0, 2, 3, 4, ..., N-1.
First, we will import all of the Python modules that we will need for this exercise:
note how we assign a short name, "np" to the numpy module. This will save typing.
End of explanation
def enumerate_matrix(gmat, i):
Explanation: Now, define a function that returns the index numbers of the neighbors of a vertex i, when the 
graph is stored in adjacency matrix format.  So your function will accept as an input a NxN numpy matrix.
End of explanation
def enumerate_adj_list(adj_list, i):
Explanation: Define a function that enumerates the neighbors of a vertex i, when the 
graph is stored in adjacency list format (a list of lists):
End of explanation
def enumerate_edge_list(edge_list, i):
Explanation: Define a function that enumerates the neighbors of a vertex i, when the 
graph is stored in edge-list format (a numpy array of length-two-lists).  Use numpy.where and numpy.unique
End of explanation
def do_sim(n):
    retlist = []
    
    nrep = 10
    nsubrep = 10
    
    # this is (sort of) a Python way of doing the R function "replicate":
    for _ in itertools.repeat(None, nrep):
        
        # make a random undirected graph with fixed (average) vertex degree = 5
        g = igraph.Graph.Barabasi(n, 5)
        
        # get the graph in three different representations
        g_matrix = np.matrix(g.get_adjacency().data)
        g_adj_list = g.get_adjlist()
        g_edge_list = np.array(g.get_edgelist())
    
        start_time = timeit.default_timer()
    
        for _ in itertools.repeat(None, nsubrep):
            for i in range(0, n):
                enumerate_matrix(g_matrix, i)
    
        matrix_elapsed = timeit.default_timer() - start_time
        
        start_time = timeit.default_timer()
        
        for _ in itertools.repeat(None, nsubrep):
             for i in range(0, n):
                enumerate_adj_list(g_adj_list, i)        
        
        adjlist_elapsed = timeit.default_timer() - start_time
        
        start_time = timeit.default_timer()
        
        for _ in itertools.repeat(None, nsubrep):
             for i in range(0, n):
                enumerate_edge_list(g_edge_list, i)        
        
        edgelist_elapsed = timeit.default_timer() - start_time
        
        retlist.append([matrix_elapsed, adjlist_elapsed, edgelist_elapsed])
        # average over replicates and then
        # divide by n so that the running time results are on a per-vertex basis
    return np.mean(np.array(retlist), axis=0)/n
Explanation: This next function is the simulation funtion.  "n" is the number of vertices.
It returns a length-three list containing the average running time for enumerating the neighbor vertices of a vertex in the graph.
End of explanation
do_sim(1000)*1000
Explanation: A simulation with 1000 vertices clearly shows that adjacency list is fastest:
(I multiply by 1000 just so the results are in ms.)
End of explanation
do_sim(2000)*1000
Explanation: We see the expected behavior, with the running time for the adjacency-matrix and edge-list formats going up when we increase "n", but there is hardly any change in the running time for the graph stored in adjacency list format:
End of explanation
<END_TASK>