#!/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…