CPS420

W2025 Assignment

Euler Circuits

Due: March 23

Team Work

You do not have to be in the same teams as for Lab6!

Assignment Summary

Just like for lab 6, your code will be automatically tested and graded on the moons. You are also provided grading functionality in the main class of the program.

Your code will only be graded on the moons and not on any other platforms, and it must pass the grading tests on the moons in order to receive a grade.

For this reason, you are encouraged to do your entire development on the moons: like for lab6, you will not be writing large quantities of code (our solution adds 30 lines of code to the Euler class, in addition to the lab6 code that added about 15 lines to the Graph class) A sophisticated development environment is not required for this amount of coding. Also the testing infrastructure is already set up on the moons.

However, the coding in this assignment is more challenging than in lab6 and this is why the assignment is worth more, and you are given more time to do it.

Assignment Description

Introduction

Be sure to finish Lab6 before starting this assignment to familiarize yourselves with the Graph and Walk APIs, java development process on the moons, and the provided testing infrastructure and process which are all used in both.

Preparation on the moons

1. Create a directory where you will do your development (e.g. cps420A) and copy all the files handed out into it:

     mkdir cps420A
     cp ~cps420/public_html/doc/Now/A/Handouts/* cps420A
     cd cps420A
     chmod u+x test
   

2. Replace Graph.java in that directory by the one you developed in Lab6 to implement the isConnected method. This method will be needed to implement your assignment. Note that when this assignment was posted on the evening of March 3 to 4, the Graph.java handout for lab6 was replaced by the handout in the assignment directory. If you developped your lab6 solution earlier, you will need to add some functionality to it for this assignment. See D2L announcement on this matter.

Handouts

• Test.java is the main program you can use to test your code. Just as for lab6, this is the java file that you will run in java. Also, like lab6, this is a grading program, which tests both the correctness and the efficiency of your code. All tests, and in particular the efficiency tests, are designed to be run on the moons. If you wish, you can modify Test.java during your development to support your own testing, but be aware that the grading will be performed using our own Test.java.

• Graph.java is the same file handed out in lab 6 that defines the class Graph. You should use your modified version where you have implemented the isConnected method. However, we will be testing your assignment with our own solution for this class, and you do not need to resubmit this class.

• Walk.java is the same file handed out in lab 6. It defines a class of Walk objects that you will use to store the walks you are building. The testing functionality assumes that when a Eulerian circuit is found, it is returned as a Walk object. You should not change anything in this class.

• Euler.java is the only java file that you will work on. This is the file that you will submit for your assignment and the only work that will be graded.

• makefile and test are used to compile and test your work as explained in the Compiling and Testing section of Lab6. The assignment has its own Tests folder.

Programming

• The only public interface of the Euler class is the class method findEuler which is defined as:

  public static Walk findEuler(Graph graph)
  

  This method is used by the Test program, and its signature and return type should not be modified.

• As you can see in the code, the class has four static variables that are accessible to all static methods in the class:
  • The graph passed as a parameter to findEuler is stored in a static Graph variable called g
  • The number of vertices in g is stored in a static int variable called totalV
  • The number of edges in g is stored in a static int variable called totalE
  • The Eulerian circuit being built is stored in the static Walk variable called Eulerian
  Making these variables static avoids repeatedly passing them as parameters in recursive function calls.

• For the assignment, you should implement findEuler using a brute force backtracking algorithm. A brute force algorithm to find a Eulerian circuit in a graph G tries all possible walks in a methodical way to see if one yields a Euler circuit, and returns the first one it finds, or null if none can be found.

  The Euler.java handout proposes breaking down this process as follows:

  • findEuler first checks whether the graph g can have a Euler circuit,
  • if that is the case, findEuler calls a recursive backtracking buildEuler helper function to find an actual Euler circuit in g.

  Here is the outline of a suggested backtracking algorithm to find a Euler circuit:

  1. Visit the first vertex and add it to the circuit
  2. For each newly added vertex in the circuit, try visiting each of its unvisited adjacent vertices one by one, each time trying to complete the Eulerian circuit, until you find one that works. If none works, remove the newly added vertex from the circuit.
  3. Use recursion to implement this process.

  The handout proposes a specific method signature for the buildEuler helper function, but because this helper function is a private method, you do not need to implement your recursive helper function as suggested if you prefer a different approach.

• To compile your code, simply type

    make
  

• To test your code, simply type

    ./test
  

The test script simply runs the main program which is located in the Test class. This Test class provides all the testing facilities that you will need to test your work. The main function uses test cases that are stored in the Tests folder to calculate your assignment grade.

If you are struggling to pass the provided tests, you are encouraged to supplement this testing with your own files, and you can certainly modify Test.java to do so, but keep in mind that we will be using our own Test.java for grading, and not yours.

Note that the last five tests will load test your program. If you are finding that your program is slowing down on larger graphs, and possibly crashing, you will need to make your algorithm more efficient.

Once your code is running smoothly, you are ready to submit the assignment as explained in the Submission section below.

Do not wait until the last minute to start this assignment and test it on the moons as you may run into unexpected last minute problems! As mentioned above, your program must work on the moons in order to get a grade.

As for lab6, do not wait until the last minute to test your code on the moons as you may run into unexpected last minute problems! As mentioned above, your program must work on the moons in order to get a grade.

References and links

• Lecture section 2.2A for paths and circuits, 2.2B for Eulerian circuits, and 2.3 for the adjacency matrix representation of graphs..
• Textbook chapter 10.1 and 10.2
• javadoc is the javadoc documentation for the assignment.
• Handouts contains the java classes used in this assignment, makefile to compile your program and test script to test it.
• Tests folder contains the tests used to grade your assignment on the moons.

Assignment Submission

1. One member of your team should submit the work electronically on the scs moons as follows:

   submit-cps420 Euler.java
   

   Do not change the names of this file as this could make the automated grading fail, resulting in a grade of 0.

2. You will also need to declare your teams on D2L and tell us where to find your assignment on the moons so that we can grade it and provide you with feedback on your grade in D2L. To so so, please follow the instructions for D2L Submissions.

   The two submission folders are called "Assignment - Individual submissions" and "Assignment - Group submissions". The relevant self enrolment groups if you are submitting as a team all have "A" as a prefix.