import networkx as nx
def check(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
def draw(graph):
g = nx.DiGraph(graph)
nx.draw(g, with_labels=True, node_size=1000, node_color='#cfc8f4', arrowsize=40)
Draw the graph (on paper) that has the following list of edges: [[1, 2], [1, 0], [2, 0]]
.
What is the adjacency dictionary of this graph?
{0: [], 1: [2, 3], 2: [0]}
Draw the graph (on paper) that has the following adjacency dict: {0: [1, 2, 3], 1: [2], 2: [], 3: []}
What is the list of edges of this graph?
[0, 1], [0, 2], [0, 3], [1, 2]
The cycle graph is a graph on n
nodes which looks like this:
Write a function that takes a parameter n
and returns the cycle graph on n
nodes as an edge list.
def cycle_graph(n):
pass
Write a function that takes a parameter n
and returns the cycle graph on n
nodes as an adjacency dictionary.
def cycle_graph_list(n):
pass
The complete graph is a graph where all nodes are connected.
Write a function that takes a parameter n
and returns the complete graph on n
nodes as an edge list OR adjacency dictionary (you can choose).
def complete_graph(n):
pass
Write a function that takes a list of edges, and converts it into an adjacency dictionary.
Write a function that takes an adjacency dictionary, and converts it into a list of edges.
You can use the draw
function (defined at the beginning of the sheet) to draw a graph. This may help you test your code. Two examples:
g = [[1, 2], [1, 0], [2, 0]]
draw(g)
g = {0: [1, 2, 3], 1: [2]}
draw(g)
You are given a graph and two vertices. Check if they are neigbours. Recall that two vertices are neighbors if they are connected by an edge.
For example, for G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}, x = 2, y = 5
it should return True
def neighbours(G, x, y):
# Complete the function. G is a graph adjacency list, x and y are numbers of vertices
return
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 2
y = 5
check(neighbours(G, x, y), expected=True)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 5
y = 2
check(neighbours(G, x, y), expected=True)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 3
y = 2
check(neighbours(G, x, y), expected=False)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 0
y = 4
check(neighbours(G, x, y), expected=False)
G = {0:[1,3], 1:[], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 0
y = 2
check(neighbours(G, x, y), expected=False)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 2
y = 2
check(neighbours(G, x, y), expected=False)
You are given a graph and two vertices. Check if they are distance two apart. For example, on the picture below vertices 1 and 2 are distance two apart while 3 and 4 are not and 4 and 5 are not because they are neighbours.
For example, we need to solve this problem to find out whether people $x$ and $y$ have mutual friends.
For example, for G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}, x = 2, y = 3
it should return True
.
Be sure you have checked all the corner cases
def almost_neighbours(G, x, y):
# Complete the function. G is a graph adjacency list, x and y are numbers of vertices
pass
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 2
y = 5
check(almost_neighbours(G, x, y), expected=False)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 3
y = 2
check(almost_neighbours(G, x, y), expected=True)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 0
y = 4
check(almost_neighbours(G, x, y), expected=True)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 1
y = 5
check(almost_neighbours(G, x, y), expected=False)
G = {0:[1,3], 1:[], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 0
y = 2
check(almost_neighbours(G, x, y), expected=False)
G = {0:[1,2,3], 1:[0], 2:[0,4,5], 3:[0], 4:[2,5], 5:[2,4]}
x = 2
y = 2
check(almost_neighbours(G, x, y), expected=False)
Function should return the value False, it is returning the value True Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!