you just need to complete the part which says solution

in this you will write 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

PLEASE USE PYTHON TO WRITE THE "def findEuler(self)" and " def tryVisiting(self, vertex, unvisitedEs, walk)"

here is 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: 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 = 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]) if i= 0 and sourceV = 0 and destV  
 ----------------------------------------------------------------------------
 
and here is 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   #### 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  #### 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