#!/usr/bin/python3

# Simple Vertex class

class Vertex:

“”” Lightweight vertex structure for a graph.

Vertices can have the following labels:

UNEXPLORED

VISITED

Note that in our simple implementation, the elements arealways

integers in the range [0 .. MatrixSize – 1], so we can use themdirectly

as indices into the AM.

“””

__slots__ = ‘_element’, ‘_label’

def __init__(self, element, label=”UNEXPLORED”):

“”” Constructor. “””

self._element = int(element)

self._label = label

def element(self):

“”” Return element associated with this vertex. “””

return int(self._element)

def getLabel(self):

“”” Get label assigned to this vertex. “””

return self._label

def setLabel(self, label):

“”” Set label after the vertex has been created. “””

self._label = label

def __str__(self):

“”” Used when printing this object. “””

return “(%2d, %s)” % (self._element,self._label)

# Simple Edge class

class Edge:

“”” Lightweight edge structure for a graph.

Edges can have the following labels:

UNEXPLORED

DISCOVERY

BACK

“””

__slots__ = ‘_origin’, ‘_destination’, ‘_label’

def __init__(self, u, v, label=”UNEXPLORED”):

“”” Constructor. Note that u and v are Vertex objects. “””

self._origin = u

self._destination = v

self._label = label

def getLabel(self):

“”” Get label assigned to this edge. “””

return self._label

def setLabel(self, label):

“”” Set label after the edge has been created. “””

self._label = label

def endpoints(self):

“”” Return (u,v) tuple for source and destination vertices.”””

# … Implement this

return ()

def isIncident(self, v):

“”” Return True if vertex v is incident upon this edge, else False.”””

# … Implement this

return False

def opposite(self, v):

“”” Return the vertex that is opposite v on this edge. “””

if not isinstance(v, Vertex):

raise TypeError(‘v must be a Vertex’)

if v not in [self._destination, self._origin]:

raise ValueError(‘v not incident to edge’)

return self._destination if v is self._origin else self._origin

def __str__(self):

“”” Used when printing this object. “””

return “(%2d, %2d, %s)” %(self._origin._element,self._destination._element,self._label)

class AMGraph:

“”” Partial Graph ADT represented by an adjacency matrix.

From this point on, the term ‘adjacency matrix’ is denoted’AM’.

The AM will store ‘Edge’ objects at each position containing anedge,

otherwise a ‘None’ will be stored in that position. “””

#————————- Graph implementation————————-

# ‘_matrix’ is a 2D array representing the AM

__slots__ = ‘_matrix’, ‘_edges’, ‘_vertices’

#– c’tor

def __init__(self, edgeCollection, vertexCollection):

# We keep a collection of edges and vertices *only* for use withthe

# accessor methods for those objects; all other methods MUST usethe AM directly

self._edges = edgeCollection

self._vertices = vertexCollection

# Parse the edge collection, and insert the edges into the

# appropriate place in the AM (remember to insert ‘None’ at theappropriate

# locations too, and to take ‘mirroring’ into account)

# … Implement this: Create AM, and fill it as required

return

#– Public methods

def edges(self):

“”” Return a set of all edges of the graph. “””

# … Implement this

return []

def edgeCount(self):

“”” Return the number of edges in the graph. “””

# … Implement this

return 0

def vertices(self):

“”” Return a set of all vertices of the graph. “””

# … Implement this

return []

def vertexCount(self):

“”” Return the number of vertices in the graph. “””

# … Implement this

return 0

def getEdge(self, v1, v2):

“”” Return the edge from v1 to v2, or None if not adjacent.”””

# … Implement this

return None

def incidentEdges(self, v):

“”” Return a collection of all edges incident to vertex v in thegraph. “””

# … Implement this

return []

def print(self):

“”” Print the square matrix for this graph.

Make sure to properly show the rows and columns,

as well as labelling.

The output should be neatly aligned in columns.

If an AM entry contains an edge, output in the format (u,v).

Otherwise, output a string such as ‘[NONE]’

See the assignment for a sample of the required output.

“””

# … Implement this

return

def DFS(g):

# Implement the depth-first search algorithm from the classnotes.

# Collect the edges that form the DFS tree of ‘g’ and return thecollection.

# … Implement this

return []

#– Main method

vertices = []

for i in range(13):

vertices.append(Vertex(i))

# Create edge objects corresponding to the graph given in thequestion,

# and add them to the collection; note that an edge object isformed from

# two Vertex objects

# … Implement this, using the vertices from the list above

edges = []

g = AMGraph(edges, vertices)

# Print all edges

print(“Edges:”, g.edgeCount())

for e in g.edges():

print(e)

print()

# Print all vertices

print(“Vertices:”, g.vertexCount())

for v in g.vertices():

print(v)

print()

# Print the actual graph (in matrix form)

g.print()

print()

# Call DFS on g, to get the discovery edges

discovery = DFS(g)

print(“DFS edges:”)

for e in discovery:

print(e)

print()

# Determine whether the graph is connected

# … Implement this, using the DFS traversal results

print(“Graph is connected:”, False)

*********I POSTED 2 QUESTION THE FIRST ONE IS THE QUESTION ANDTHE SECOND ONE IS THE TO BE COMPLETED CODE GIVEN WITH THEASSIGNMENT****

## Expert Answer

Answer to #!/usr/bin/python3 # Simple Vertex class class Vertex: “”” Lightweight vertex structure for a graph. Vertices can have t…