Learn

We will create a custom Hamiltonian class responsible for traversing a graph to determine if a Hamiltonian path or cycle exists.

When defining our Hamiltonian class, we should define the following within the constructor. Let’s connect each of these defined class members back to our bus route graph to see why we should define these components.

  • vertices: a list of the vertices in the graph.
    • In our bus route graph, we need to know what students need to be picked up.
  • adj_matrix: the adjacency matrix.
    • We need to know which roads connect to each house to see the possible route options.
  • start: the index of the starting vertex of the graph.
    • We need to know where the bus departs from (this location is also our final end point for a Hamiltonian cycle). In this case, the bus departs from the school and should end up back at the school.
  • path: a list of the path vertices’ indexes we have currently traversed (this list will be modified as we backtrack throughout the graph to find different paths).
    • As the bus moves to each student’s house, we add each student vertex to the possible path.
  • visited_vertices: a list to indicate if each vertex has been visited. Since a Hamiltonian path and cycle must visit each vertex only, this will help us keep track of which vertex has been visited. If a vertex has been visited, it should be assigned the value of 1 and 0 otherwise. At the start, all vertices should have a 0 value in this list.
    • We only want to visit each student’s house once and need to keep track if the student has been picked up yet or not.
  • hpaths: a list containing all Hamiltonian paths in this graph. If empty, none exist.
    • If we’ve found an eligible path where each student has been visited once, we keep track of that path here.
  • cycles: a list containing all Hamiltonian cycles in this graph. If empty, none exist.
    • If we find an eligible path where each student has been visited once and end up back at the school, we keep track of that path here.

Before we start traversing the path, in our traverse() method, we should:

  • First, add our start vertex index to the path list since it is the start of our path
  • Call the recursive search() function, that we will implement in the next exercise.

Instructions

1.

Review the Hamiltonian constructor to see what class members are defined that will be used later in the implementation.

Click Run to move onto the next checkpoint!

2.

Using the above implementation details, add the appropriate code below each commented line within the Hamiltonian class traverse() method.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?