Programming#8: Euler circuit programming assignment: Due: Friday, May 23.

• Understand the Euler circuit problem: See the slide set in this zip file for more details and an interesting application of the Euler circuit. An Euler circuit for a graph G is a path represented as a sequence of vertices that starts and ends in the same vertex and traverse each edges in G exactly once. Not every graph has an Euler circuit in it. A graph G has an Euler circuit in it if and only if G is a connected graph and each vertex in G has an even degree (i.e an even number of edges incident on it). Given a graph G, the task of the Euler circuit problem is to determine whether G has an Eluer circuit in it and if it does provide one Euler circuit as a solution.

• Understand the scheme used to encode the information of a graph as a text file: See this text file encoding a butter-fly-shape graph of 5 vertices and 6 edges. In this assignment, we can encode the information of a graph in a text file in the following way: (i) the total number of vertices is recorded as the sole number in the first line of the file, and (ii) for each vertex in the graph, there is a separate line in the file in the format: v: u₁ u₂ … u_n where v is the name of the vertex, the colon is used as a separator, and u₁ u₂ … u_n is the list of the names of the neighboring vertices of v.

• Download the basic code framework: Download this new zip file (with the sample executable updated May 12, Monday) to examine the basic code framework folder, a sample executable EulerCircuit.exe, and sample graphs such as graph1.txt, graph2.txt, graph3.txt, and biolaGraph.txt in it.

• Understand the data structures for storing the information of a graph: In the code framework, when an object of the EulerSolver class (see the declaration of the class in EulerSolver.h and the implementation of the class in EulerSolver.cpp) reads the information of a graph from a text file, it stores the information in its private data members in the following way: (i) the number of the vertices and the number of the edges in the graph are stored in NumOfVertices and NumOfEdges respectively, (ii) for the information of the vertices in the graph, vector<Vertex> Vertices stores the names of the vertices as a vector of Vertex (i.e. string) and each vertex is represented by its name as a string, and (iii) map< Vertex, AdjacencyVector > MapOfAdjacentVertices stores the information of the edges in the graph so that for each vertex v you can find the neighbors of v (those connected to v by the existing edges in the graph) stored in MapOfAdjacentVertices[v] as a vector of Vertex (i.e. string). Note that you can determine whether there are any edges currently incident on v by checking whether MapOfAdjacentVertices[v].size()is greater than 0.

• Run the sample executable to find Euler circuits: Run EulerCircuit.exe (generated from a finished version of the code framework) and use it to find Euler circuits for graphs encoded in graph1.txt, graph2.txt, graph3.txt, biolaGraph.txt, or other text files containing graphs of interest to you. EulerCircuit.exe works by having an EulerSolver object in the main function to repeatedly invoke the GetOneEulerCircuit(char * fileName, Circuit &eulerCircuit) method to read in a graph from a file with a file name provided by the user, store the graph information in the private data members of the EulerSolver object, and invoke the GetOneEulerCircuit(Circuit & eulerCircuit) method to determine whether there is an Euler circuit in the graph, and store a solution in eulerCircuit for display if it does exist.

• Understand the algorithm used to find an Euler circuit: To find an Euler circuit, the GetOneEulerCircuit(char * fileName, Circuit &eulerCircuit) method starts by invoking the GetOneExhaustiveCircuitAtThisVertex(Circuit &resultCircuit, Vertex startingVertex) to find a circuit starting and ending in the first vertex of the graph. (It is very important to note that when GetOneExhaustiveCircuitAtThisVertex will return true if and only if it does find one such circuit, and it removes from the graph those edges used in the circuit and update NumOfEdges accordingly.) If such circuit doses exist, GetOneEulerCircuit uses it as the initial circuit solution; otherwise, the graph does not have an Euler circuit. GetOneEulerCircuit then repeatedly checks whether there are vertices on the current circuit solution with some remaining edges incident on them. Whenever there is such a vertex, GetOneEulerCircuit calls GetOneExhaustiveCircuitAtThisVertex to find a new circuit starting and ending in that vertex, and then call StitchNewCircuitIntoCurrentlCircuit to stitch the new circuit into the current circuit solution. This process is repeated until no vertices on the current circuit solution still have edges incident on them. (Note that the graph does not have an Euler circuit if GetOneExhaustiveCircuitAtThisVertex can not find a circuit at any point when it is invoked in the process above.) At that point, the current circuit is an Euler circuit if all edges have been used and deleted. Otherwise, the graph is not a connected graph and there is no Euler circuit.

• Add your own code to complete the implementation in the code framework: Study the code framework and finish the implementation of the GetOneEulerCircuit(Circuit & eulerCircuit) method and the StitchNewCircuitIntoCurrentlCircuit(Circuit & newCircuit, Circuit & currentCircuit) method of the Euler solver class in EulerSolver.cpp to make it fully functional.

• Extensively testing your program: try at least graph1.txt, graph2.txt, graph3.txt, and biolaGraph.txt to make sure your program can correctly determine whether there is an Euller circuit in a given graph and if so it can correctly find an Euler circuit.