Description
Complete HW5 by implementing the circular puzzle in a Graph ADT.
- Write a function list_to_graph(L) that converts the list defining the circular tiles into the Graph ADT definitions (a set of vertices and a set of edges) that can be entered into a Graph ADT. Each tile will be a vertex. The first tile will be tile 1, not tile 0. The weight of each tile provides the definition for two edges. Paste that function under this line.
def list_to_graph(L):
vertices = set(range(1, len(L) + 1))
edges = set()
for i in range(len(L)):
weight = L[i]
next_index = (i + weight) % len(L)
edges.add((i + 1, next_index + 1, weight))
edges.add((next_index + 1, i + 1, weight))
return vertices, edges
- Instantiate a Graph with the circular tile definition created above.
- Determine if a path exists between the first and last tile.
- See if you can implement the Graph ADT further to determine the shortest path from the first tile to the last tile.
- See if you can further expand the Graph ADT to determine all
Submit
- This Word document with your list_to_graph(L) function embedded.
- A py file which contains all the code for your implementation and how you entered each puzzle to find if there is a path.
