In this practice Question, it will help you understand writing a backtracking algorithm to find an Euler circuit in a graph if one exists or to identify when there isn't one. As you know, there are simple ways of determining whether a given graph has an Euler circuit, and this should be checked before starting to find an actual Euler circuit.

A backtracking algorithm to build an Euler circuit is a recursive algorithm which tries in a systematic way all the possible ways of building a circuit and stops when it manages to build one. More precisely, it can be described as a recursive function which tries to visit the "next" available vertex (i.e. one which is joined to the current vertex by an unvisited edge) until an Euler circuit is found. Visiting the next vertex consists of:

1. Adding the vertex to the circuit
2. Trying to visit each of its available adjacent vertices one by one, each time trying to complete a Euler circuit, until you find one that works, in which case the circuit has been built. An "available adjacent vertex" is one which shares a still unvisited adjacent edge with the vertex being visited.
3. If it was not possible to visit an available adjacent vertex, then the visit of the original vertex failed, and it should be removed from the circuit.

This algorithm is expressed recursively and is also best implemented recursively. If coded carefully, this is not a large function.

The main code: Graph.py

from Walk import Walk import sys import random import copy sys.setrecursionlimit(100000) class Graph: """ Graph objects can be used to work with undirected graphs. They are internally represented using adjacency matrices. DO NOT MODIFY THIS CLASS EXCEPT TO ADD CODE FOR FINDING EULER CIRCUITS """ DIRECTED = True UNDIRECTED = False seeded = False  @classmethod def fromFile(cls, filename): """ Instantiates list of Graphs read from a file. The file has the following format: Each graph starts on a new line which contains two elements: - "D" or "U" to specify whether the graph is directed or undirected - The number of vertices in that graph Followed by one line for each row of the adjacency matrix of the graph: in each row the elements are separated by blanks. Note: When it encounters problems with the data, fromFile stops reading the file and returns the correct information read up to that point. Parameters: str filename: name of file containing graphs Returns a list of Graphs described in the file. """ f = open(filename, "r") graphList = [] with f as lines: row = 0 for line in lines: if row == 0: entries = line.split() if len(entries) != 2: print("Error: First line of graph must have format 'D'|'U' TotalVertices") break if entries[0]=='U': directed = Graph.UNDIRECTED else: directed = Graph.DIRECTED vertices = int(entries[1]) edges = [] row += 1 elif row <= vertices: newrow = [int(i) for i in line.split()] if len(newrow) != vertices: print("Error: invalid number of entries in row ", row) break edges.append(newrow) row += 1 elif row > vertices: graphList.append(Graph(directed, vertices, edges)) row = 0 f.close() return graphList  @classmethod def newRandomSimple(cls, seed, vertices, density): """ Instantiates new simple Graph randomly as specified by parameters. The graph is undirected without loops or parallel edges. Parameters: int seed: seed for random number generator int vertices: number of vertices in the Graph int density: the odds that there will be an edge between any two distinct vertices are 1/density Returns a new graph to specifications or None if they can't be met. """ if vertices <= 0: print("Error: Number of vertices must be positive") return None if density <= 1: print("Error: density must be greater than 1") return None # Seed the random number generator once if not Graph.seeded: random.seed(a=seed) Graph.seeded = True # Create array of 0 edges edges = [] for i in range(vertices): edges.append(list([0]*vertices)) # Populate non-diagonal cells of matrix for i in range(vertices): for j in range(i+1,vertices): if random.randint(0, density-1) == density-1: edges[i][j] = 1 edges[j][i] = edges[i][j] return Graph(Graph.UNDIRECTED, vertices, edges) def __init__(self, directed, vertices, edges): """Creates a new Graph from an adjacency matrix Parameters: Boolean directed: Graph.DIRECTED or Graph.UNDIRECTED int vertices: number of vertices in the Graph List edges: adjacency matrix of the edges Notes: - This constructor is not intended to be used directly. The two class methods fromFile and newRandomSimple should be used instead. - Nevertheless, if incorrect data is received, the graph information will be rejected and an empty graph will be returned. """ self.inputMistakes = False self.directed = directed if vertices <= 0: print("Error: Number of vertices must be positive") return # Total number of vertices and edges. self.totalV = vertices self.totalE = 0 # Adjacency matrix of graph. # edges[x][y] is the number of edges from vertex x to vertex y. self.edges = edges # Used by graph visitors to keep track of visited vertices. self.visitedV = [None]*vertices # Used by graph visitors to keep track of visited edges. self.visitedE = [] # Used by graph visitors to keep track of unvisited edges # as an alternative to using visitedE. self.unvisitedE = [] for i in range(vertices): self.visitedE.append(list([None]*vertices)) self.unvisitedE.append(list([None]*vertices)) self.clearVisited() # Read adjacency matrix for i in range(vertices): for j in range(vertices): if edges[i][j] < 0: print("Error: Number of edges cannot be negative") self.inputMistakes = True elif directed or j >= i: self.totalE += edges[i][j] # Verify that adjacency matrix is symmetric when graph is undirected if not directed: for i in range(vertices): for j in range(i+1, vertices): if edges[i][j] != edges[j][i]: print("Error: adjacency matrix is not symmetric") self.inputMistakes = True if self.inputMistakes: self.totalV = 0 def clearVisited(self): """Resets visitedV, visitedE, and unvisitedE matrices for a new visitation.""" for i in range(self.totalV): self.visitedV[i] = False for j in range(self.totalV): self.visitedE[i][j] = 0 self.unvisitedE[i][j] = self.edges[i][j] def __str__(self): """Returns a String representation of the graph which is a 2-D representation of the adjacency matrix of that graph.""" res = "" for i in range(self.totalV): for j in range(self.totalV-1): res += str(self.edges[i][j]) res += " " res += str(self.edges[i][self.totalV-1]) res += " " return res def totalVertices(self): """Returns the number of vertices in the graph.""" return self.totalV def totalEdges(self): """Returns the number of edges in the graph.""" return self.totalE def getEdges(self): """Returns a deep copy of the adjacency matrix of the graph.""" return copy.deepcopy(self.edges) def getEdgeCount(self, sourceV, destV): """ Counts number of edges between two vertices Parameters: int sourceV: sourve vertex int destV: destination vertex Returns the number of edges from sourceV to destV """ if sourceV >= 0 and sourceV < self.totalV and destV >= 0 and destV < self.totalV: return self.edges[sourceV][destV] else: return 0 def isConnected(self): """Returns True iff graph is connected.""" self.clearVisited() self.DFSvisit(0) for i in range(self.totalV): if not self.visitedV[i]: return False return True def DFSvisit(self, vertex): """ Conducts a Depth First Search visit of the unvisited vertices. Ties between vertices are broken in numeric order. Parameters: int vertex: starting vertex for the DFS visit Side Effect: visitedV is updated to reflect which vertices are visited. """ self.visitedV[vertex] = True for i in range(self.totalV): if self.edges[vertex][i] != 0 and not self.visitedV[i]: self.DFSvisit(i) ################ Solution ########################## def findEuler(self): """ Returns: an Euler circuit for the graph if one exists, or None if none exists. """ return None def tryVisiting(self, vertex, unvisitedEs, walk): """ Recursive backtracking algorithm tries visiting adjacent unvisited edges one by one building an Euler circuit along the way. Parameters: int vertex: vertex being currently visited int unvisitedEs: total number of unvisited edges so far Walk walk: Euler walk built so far Returns: True iff an Euler circuit has been found and False otherwise """ return False 

These are the Functions to be Edited only these functions:

################ Solution ########################## def findEuler(self): """ Returns: an Euler circuit for the graph if one exists, or None if none exists. """ return None def tryVisiting(self, vertex, unvisitedEs, walk): """ Recursive backtracking algorithm tries visiting adjacent unvisited edges one by one building an Euler circuit along the way. Parameters: int vertex: vertex being currently visited int unvisitedEs: total number of unvisited edges so far Walk walk: Euler walk built so far Returns: True iff an Euler circuit has been found and False otherwise """ return False 

You use this used as a helper: Walk.py

 class Walk: """ Walk objects can be used to build walks from Graphs. A Walk is simply a list of vertices in the order in which they occur in the walk. The edges are not listed. Note: this class does not verify the validity of the walk, i.e. it does not verify whether there are valid edges between two adjacent vertices in the walk. DO NOT MODIFY THIS CLASS """ NOVERTEX = -1 def __init__(self, maxVertices): """ Creates a new empty Walk. Parameters: int maxVertices: The maximum number of vertices in the Walk. """ # Maximum possible length of Walk, including last edge returning to first vertex. self.maxV = maxVertices # Actual length of Walk, including last edge returning to first vertex. self.totalV = 0 # The vertices are listed in their order of traversal. self.vertices = [] for i in range(maxVertices): self.vertices.append(0) def __str__(self): """Returns a String representation of the Walk which is simply a list of vertices separated by blanks.""" if self.totalV == 0: return "" res = "" for i in range(self.totalV-1): res += str(self.vertices[i]) res += " " res+= str(self.vertices[self.totalV-1]) return res def isEmpty(self): """Returns True iff the walk has no vertices.""" return self.totalV == 0 def isTrivial(self): """Returns True iff the walk is a single vertex.""" return self.totalV == 1 def isCircuit(self): """Returns True iff the walk is a non-empty circuit.""" if self.totalV == 0: return False return self.vertices[0] == self.vertices[self.totalV-1] def __len__(self): """Returns the number of edges in the Walk. Note: an empty Walk and a Walk with a single vertex both have length 0. """ return self.length() def length(self): """Returns the number of edges in the Walk. Note: an empty Walk and a Walk with a single vertex both have length 0. """ if self.totalV == 0: return 0 return self.totalV - 1 def totalVertices(self): """Returns the number of vertices in the Walk.""" return self.totalV def getVertex(self, n): """Returns the nth vertex in the Walk or Walk.NOVERTEX if there is no such vertex. Parameters: int n: position of vertex to be returned. Counting starts at 0. """ if 0 <= n and n < self.totalV: return self.vertices[n] else: return NOVERTEX def getVertices(self): """ Returns a copy of the list of vertices in the Walk. """ return self.vertices.copy() def addVertex(self, vertex): """Adds another vertex to the end of the Walk if possible. Parameters: vertex: vertex to be added Returns True iff the vertex could be added, i.e maxVertices was not reached """ if self.totalV == self.maxV: return False self.vertices[self.totalV] = vertex self.totalV += 1 return True def removeLastVertex(self): """Removes the last vertex added to Walk if possible. Returns True iff the last vertex could be removed, i.e Walk was not empty """ if self.totalV == 0: return False self.totalV -= 1 self.vertices[self.totalV] = 0 return True 

And this is what you use to Test it: Test.py

from Graph import Graph from Walk import Walk def main(): """ Main test program calculates score for program. It first tests the getEuler method on graphs in test files. Then tests it on randomly generated undirected simple graphs. """ dirPath = "./tests/" score = 0 # Run test files to check correctness print(" ======================= TEST CORRECTNESS ======================= ") print(" ------- There are no Euler circuits in the first two tests ----- ") score += 4 - testInput(dirPath + "disconnected", 0) print("Score so far: " + str(score)) score += 5 - testInput(dirPath + "noEuler", 0) print("Score so far: " + str(score)) print(" ------- From now on all test graphs have Euler circuits ------- ") score += testInput(dirPath + "small", 6) print("Score so far: " + str(score)) score += testInput(dirPath + "medium", 5) print("Score so far: " + str(score)) score += testInput(dirPath + "large", 6) print("Score so far: " + str(score)) score += 4*testInput(dirPath + "verylarge", 1) print("Correctness score: " + str(score) + " out of 30.") # Test very large graphs print(" ======================= TEST EFFICIENCY ======================= ") score += 2*testInput(dirPath + "huge1", 1) print("Score so far: " + str(score) + " out of 40.") score += 2*testInput(dirPath + "huge2", 1) print("Score so far: " + str(score) + " out of 40.") score += 2*testInput(dirPath + "huge3", 1) print("Score so far: " + str(score) + " out of 40.") score += 2*testInput(dirPath + "huge4", 1) print("Score so far: " + str(score) + " out of 40.") score += 2*testInput(dirPath + "huge5", 1) print("Final score: " + str(score) + " out of 40.") def testInput(filename, expected): """ Reads graphs from a file and tests the getEuler method on these graphs. Parameters: str filename: path of file int expected: number of graphs in file which have an Euler circult Returns the number of valid Euler circuits for the graphs in the file. """ print(" ------- Test " + filename +" ------- ") found = 0 graphList = Graph.fromFile(filename) for graph in graphList: found += testOnGraph(graph) print(" Euler circuits expected: " + str(expected) + ", found: " + str(found)) return found def testOnGraph(graph): """ Tests the getEuler method for a graph. Prints the results. Parameters: Graph graph: graph on which the getEuler method will be tested Returns 1 if a valid Euler circuit has been found and 0 otherwise """ print("Graph has " + str(graph.totalVertices()) + " vertices, and " + str(graph.totalEdges()) + " edges."); circuit = graph.findEuler() if(circuit is None): print("Graph has no Euler Circuit") return 0 elif (isValidEuler(graph,circuit)): print("Valid Euler Circuit") return 1 else: print("Invalid Euler Circuit") return 0 def isValidEuler(graph, circuit): """ Verifies whether a walk is a valid Euler circuit for a graph. Parameters: Graph graph: original graph Walk circuit: potential Euler circuit for graph Returns True iff circuit is a valid Euler circuit for graph. """ # First check if the path is a circuit if not circuit.isCircuit(): print("Error: Path returned is not a circuit") return False # Then check if the circuit has the correct number of edges circuitLength = circuit.length() totalEdges = graph.totalEdges() if circuitLength < totalEdges: print("Error: Some edges have not been visited") return False if circuitLength > totalEdges: print("Error: Too many edges in circuit") return False # Now traverse the circuit to verify that it is a correct Euler circuit for this graph edges = graph.getEdges() path = circuit.getVertices() v1 = path[0] for i in range(1,circuitLength): v2 = path[i] if edges[v1][v2] == 0: print("Error: The graph does not have enough edges between " + str(v1) + " and" + str(v2) + " to support the circuit found.") return False edges[v1][v2]-=1 edges[v2][v1]-=1 v1 = v2 return True # calls main program if __name__ == '__main__': main() 

This is a preparation question for my upcoming midterm; please help me understand by filling in those functions to complete this question.