# Module 11 extra problems

# Part 1 - Warm up questions

# make sure you understand the strength and weaknesses of each graph implementation

# trace bfs and dfs on different graphs



# Part 2 - Extra Practice


# Question 1
# Draw the graphs that correspond to the following implementations (and
# convert them to the other formats as well). 
# (a) Edge list: [ [0,1],[0,7],[0,2],[0,5], [0,6], [4,6], [4,7], [3,4], [3,5] ]
# (b) Adjacency List: { 0:[1,5], 1:[0,2,3], 2:[1,4], 3:[1,4], 4:[2,3], 5:[0,6], 6:[5,7,8], 7:[6], 8:[6] }
# (c) Adjacency Matrix: [ [0,1,1,1,0], [1,0,1,1,0], [1,1,0,0,1], [1,1,0,0,0], [0,0,1,0,0] ]

# Question 2
# We studied three graph representation formats in Module 11: 
# * edge list
# * adjacency lists using a dictionary
# * adjacency matrix
# Write functions that convert from one format to another
# (a) edge list to adjacency list
# (b) edge list to adjacency matrix
# (c) adjacency list to edge list
# (d) adjacency list to adjacency matrix
# (e) adjacency matrix to edge list
# (f) adjacency matrix to adjacency list

# Question 3
# (a) Find breadth-first search order traversals for the graphs in Question 1
# (b) Find depth-first search order traversals for the graphs in Question 1

# Question 4
# Write a function is_connected that consumes a graph G, and produces True
# if G is connected, and False otherwise. Assume G is represented using an
# adjacency list representation. 

# Question 5 (this was an assignment question in a previous term)
# A bipartite graph is a graph whose vertices can be divided into two non-intersecting 
# sets (say U and V) such that every edge in the graph connects a vertex in U to a vertex in V. 
# A graph colouring involves assigning different colours to vertices of a graph so that no 
# two adjacent vertices have the same colour. A bipartite graph can be coloured using 
# exactly two colours.              
#
# Complete the Python function is_bipartite, which consumes graph, a non-empty dictionary 
# corresponding to an adjacency list representation of a connected graph containing at 
# least two vertices, and reurns True if graph is bipartite, and False if it is not. 
# You may assume that each neighbour list in the dictionary contains at least one vertex, 
# and contains no duplicates. It is not guaranteed to be in increasing order, however.
#
# One way to determine if a connected graph is bipartite is by attempting to colour it 
# using only two colours. This can be done using a variation on the breadth-first search 
# traversal implemented in class.  
# * Choose any vertex in the graph as a starting point, v
# * Initialize Q = [v]
# * Create a dictionary colours, and set colours[v] to 0 (use 0 for one colour, and 1 for the other)
# * While Q is not empty:
#	Remove Q[0] and call it v
#	For each neighbour of v:
#	    If neighbour is not in colours, add it to colours with the opposite colour of v 
#              (since they cannot be the same colour), and append the neighbour to Q
# 	    If neighbour had previously been coloured the same colour as v, there is a problem 
#              (v and its neighbours cannot be the same colour). 
#              The 2-colouring is not possible. Return False
#   	    If neighbour has previously been coloured the opposite colour of v, then leave 
#              it that colour (but don't add neighbour to Q since it has already been examined)
# * Once Q is empty, it means that all vertices were assigned one of the two colours and there 
#     were no problems. Therefore, the graph is 2-colourable, i.e. it is bipartite. Return  True.

# Question 6: 
# Write a function, connected-pieces, that consumes a graph, G, (represented using an 
# adjaccency matrix) and returns a list (in any order) of the connected pieces in G.
# Each connected piece is presented by a list of vertices (in any order) for that piece.

# Question 7:
# Rewrite bfs assuming G is represented by an adjacency matrix rather than an
# adjacency list. 

# Question 8:
# Rewrite dfs assuming G is represented by an adjacency matrix rather than an
# adjacency list.