Question

Below is the Graph file that needs to be modified(using Python3) :

Attached is a simplified undirected Graph ADT class partially implemented using the Edge List structure. Complete the implementation of the incomplete methods using associated comments to guide you. In the 'main method' area of the code, an empty graph is created, and vertices and edges are inserted to form the following graph. When you are sure your methods are working, implement the DFS algorithm and run it on the graph, printing out the resulting sequence of edges (i.e., the DISCOVERY edges). Also print whether the graph is connected, based on the results of your traversal algorithms. You test the code using other graph examples if it is needed. There are a total of 9 sub questions to be completed in the code.

#!/usr/bin/python3

# Simple Vertex class
class Vertex:
""" Lightweight vertex structure for a graph.
Vertices can have the following labels:
UNEXPLORED
VISITED
Assuming the element of a vertex is string type
"""
__slots__ = '_element', '_label'

def __init__(self, element, label="UNEXPLORED"):
""" Constructor. """
self._element = element
self._label = label

def element(self):
""" Return element associated with this vertex. """
return 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 "(%s, %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','_element', '_label'

def __init__(self, u, v, element = None,label = "UNEXPLORED"):
""" Constructor. Note that u and v are Vertex objects. """
self._origin = u
self._destination = v
self._element = element
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. """
return (self._origin, self._destination)

def isIncident(self, v):
""" Return True if vertex v is incident upon this edge, else False. """
return v == self._origin or v == self._destination

def isEndponts(self, u, v):
""" Return True if both vertics u and v are incident upon this edge, else False. """
return self.isIncident(u) and self.isIncident(v)
  
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 "(%s, %s, %s)" % (self._origin._element,self._destination._element,self._label)

class Graph:
""" Partial Graph ADT represented by an edge list structure."""
  
#---- Graph implementation -------------------------
__slots__ = '_edges', '_vertices'

def __init__(self):
self._edges = []
self._vertices = []

#-- Public methods
def edges(self):
""" Return all edges of the graph. """
# ... Implement this (1)
return [] #replace to your one code

def edgeCount(self):
""" Return the number of edges in the graph. """
# ... Implement this (2)
return [] #replace to your one code

def vertices(self):
""" Return all vertices of the graph. """
# ... Implement this (3)
return [] #replace to your one code

def vertexCount(self):
""" Return the number of vertices in the graph. """
# ... Implement this (4)
return [] #replace to your one code

def getEdge(self, v1, v2):
""" Return the edge with vertices v1 to v2, or None if not adjacent. """
# ... Implement this (5)
return None #replace to your one code

def getVertexByValue(self, e):
""" Return the vertex that has element of value e. """
# ... Implement this (6)
return None #replace to your one code
def incidentEdges(self, v):
""" Return a collection of all edges that are incident to vertex v in the graph. """
# ... Implement this (7)
return [] #replace to your one code

def print(self):
""" Print the edge list with the format:
"""
print("Edge List:" )
for e in self.edges():
print(e)
print()

def insert_vertex(self, x=None):
"""Insert and return a new Vertex with element x."""
v = Vertex(x)
self._vertices.append(v)
return v
  
def insert_edge(self, u, v, x=None):
"""Insert and return a new Edge from u to v with auxiliary element x.

Raise a ValueError if u and v are not vertices of the graph.
Raise a ValueError if u and v are already adjacent.
"""
if self.getEdge(u, v) is not None: # includes error checking
raise ValueError('u and v are already adjacent')
e = Edge(u, v, x)
self._edges.append(e)
  
def DFS(g):
# Implement the depth-first search algorithm from the class notes.
# Collect the discovered edges that form the DFS tree of 'g' and return the collection
# ... Implement this (8)
return [] #replace to your one code

#-- Main method
v_elements = ["A","B","C","D","E"]
g = Graph()
for v in range(5):
g.insert_vertex(v_elements[v])
  
g.insert_edge(g.getVertexByValue("A"),g.getVertexByValue("B"))
g.insert_edge(g.getVertexByValue("A"),g.getVertexByValue("C"))
g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("C"))
g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("D"))
g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("E"))
g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("D"))
g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("E"))

# 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 (9)
print("Graph is connected:", False) #replace to your one code

Answer 1

PYTHON CODE:

#!/usr/bin/python3

# Simple Vertex class
class Vertex:
""" Lightweight vertex structure for a graph.
Vertices can have the following labels:
UNEXPLORED
VISITED
Assuming the element of a vertex is string type
"""
__slots__ = '_element', '_label'
  
def __init__(self, element, label="UNEXPLORED"):
""" Constructor. """
self._element = element
self._label = label
  
def element(self):
""" Return element associated with this vertex. """
return 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 "(%s, %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','_element', '_label'
  
def __init__(self, u, v, element = None,label = "UNEXPLORED"):
""" Constructor. Note that u and v are Vertex objects. """
self._origin = u
self._destination = v
self._element = element
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. """
return (self._origin, self._destination)
  
def isIncident(self, v):
""" Return True if vertex v is incident upon this edge, else False. """
return v == self._origin or v == self._destination
  
def isEndponts(self, u, v):
""" Return True if both vertics u and v are incident upon this edge, else False. """
return self.isIncident(u) and self.isIncident(v)
  
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 "(%s, %s, %s)" % (self._origin._element,self._destination._element,self._label)

class Graph:
""" Partial Graph ADT represented by an edge list structure."""
  
#---- Graph implementation -------------------------
__slots__ = '_edges', '_vertices'
  
def __init__(self):
self._edges = []
self._vertices = []
  
#-- Public methods
def edges(self):
""" Return all edges of the graph. """
# ... Implement this (1)
#return [] #replace to your one code
return self._edges
  
def edgeCount(self):
""" Return the number of edges in the graph. """
# ... Implement this (2)
#return [] #replace to your one code
return len(self._edges)
  
def vertices(self):
""" Return all vertices of the graph. """
# ... Implement this (3)
#return [] #replace to your one code
return self._vertices
  
def vertexCount(self):
""" Return the number of vertices in the graph. """
# ... Implement this (4)
#return [] #replace to your one code
return len(self._vertices)
  
def getEdge(self, v1, v2):
""" Return the edge with vertices v1 to v2, or None if not adjacent. """
# ... Implement this (5)
#return None #replace to your one code
for EDGE in self._edges:
if EDGE.isEndponts(v1,v2):
return EDGE
return None
  
def getVertexByValue(self, e):
""" Return the vertex that has element of value e. """
# ... Implement this (6)
for VERTEX in self._vertices:
if VERTEX.element()==e:
return VERTEX
return None
#replace to your one code
  
def incidentEdges(self, v):
""" Return a collection of all edges that are incident to vertex v in the graph. """
# ... Implement this (7)
INCI_EDGES=[]
for EDGES in self._edges:
if(EDGES.isIncident(v)):
INCI_EDGES.append(EDGES)
return INCI_EDGES #replace to your one code
  
def print(self):
""" Print the edge list with the format:
"""
print("Edge List:" )
for e in self.edges():
print(e)
print()
  
def insert_vertex(self, x=None):
"""Insert and return a new Vertex with element x."""
v = Vertex(x)
self._vertices.append(v)
return v
  
def insert_edge(self, u, v, x=None):
"""Insert and return a new Edge from u to v with auxiliary element x.
  
Raise a ValueError if u and v are not vertices of the graph.
Raise a ValueError if u and v are already adjacent.
"""
if self.getEdge(u, v) is not None: # includes error checking
raise ValueError('u and v are already adjacent')
e = Edge(u, v, x)
self._edges.append(e)

def DFS_utility(g,v):
v.setLabel("VISITED")
for edge in g.incidentEdges(v):
if (edge.getLabel()=="UNEXPLORED"):
next_vert=edge.opposite(v)
if(next_vert.getLabel()=="UNEXPLORED"):
edge.setLabel("DISCOVERY")
DFS_utility(g,next_vert)
else:
edge.setLabel("BACK")
  
def DFS(g):
# Implement the depth-first search algorithm from the class notes.
# Collect the discovered edges that form the DFS tree of 'g' and return the collection
# ... Implement this (8)
v=g.vertices()[0];
DFS_utility(g,v);
Discovery_edge_list=[]
for edge in g.edges():
if(edge.getLabel()=="DISCOVERY"):
Discovery_edge_list.append(edge);
return Discovery_edge_list
#return [] #replace to your one code

#-- Main method
v_elements = ["A","B","C","D","E"]
g = Graph()
for v in range(5):
g.insert_vertex(v_elements[v])
  
g.insert_edge(g.getVertexByValue("A"),g.getVertexByValue("B"))
g.insert_edge(g.getVertexByValue("A"),g.getVertexByValue("C"))
g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("C"))
g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("D"))
g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("E"))
g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("D"))
g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("E"))

# 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 (9)
isconnec=True
for vert in g.vertices():
if(vert.getLabel()=="UNEXPLORED"):
isconnec=False
print("Graph is connected:", isconnec) #replace to your one code

CODE SNAPSHOT:

1 #!/usr/bin/python3 3 # Simple Vertex class 4. class Vertex: "" Lightweight vertex structure for a graph. Vertices can have the following labels: UNEXPLORED VISITED Assuming the element of a vertex is string type slots_= ' element', 'label' def init (self, element, label="UNEXPLORED"): """ Constructor. """ self._element = element self._label = label def element(self): " Return element associated with this vertex. " return 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 " Set 30 31 def str_(self): " Used when printing this object. *** return "%s, %s)" % (self._element, self._label) 32 33 34 # Simple Edge class 35 - class Edge: " Lightweight edge structure for a graph. 36

35 - class Edge: " Lightweight edge structure for a graph. 37 Edges can have the following labels: UNEXPLORED DISCOVERY BACK 38 _slots _ = '_origin', '_destination', '_element', '_label' def init (self, u, v, element = None, label = "UNEXPLORED"): "" Constructor. Note that u and v are Vertex objects." self. origin = u self. destination = v self._element = element 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. "" return (self._origin, self._destination) def isIncident(self, v): " Return True if vertex v is incident upon this edge, else False. " return v == self. origin or v == self._destination 67 - def isEndponts(self, u, v): "" Return True if both vertics u and v are incident upon this edge, else false. "" return self.isIncident(u) and self.isIncident (v)

64 return selt.isIncident u) and self.isIncident v 70 71 72 73 74 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 75 79 80 81 def _str__(self): "" Used when printing this object. *** return "%s, %s, %s)" % (self._origin._element, self._destination._element, self._label) 82 83. class Graph: 84 "" Partial Graph ADT represented by an edge list structure."" #---- Graph implementation -- _slots_= '_edges', '_vertices def init__(self): self._edges = [] self._vertices = [] #-- Public methods def edges(self): " Return all edges of the graph." # ... Implement this (1) #return [] #replace to your one code return self._edges 96 99 100 101 102 def edgeCount(self): " " Return the number of edges in the graph."" # ... Implement this (2) #return [] #replace to your one code return len(self._edges) 103 104 105

105 106 107 108 def vertices(self): " Return all vertices of the graph. """ # ... Implement this (3) #return [] #replace to your one code return self. vertices 109 110 111 112 113 114 def vertexCount(self): """ Return the number of vertices in the graph. "" # ... Implement this (4) #return [] #replace to your one code return len(self._vertices) 115 116 117 118 119 120 121 122 123 def getEdge(self, v1, v2): " " Return the edge with vertices vi to v2, or None if not adjacent." # ... Implement this (5) #return None #replace to your one code for EDGE in self._edges: _ if EDGE.isEndponts(v1,v2); return EDGE return None 124 125 126 127 128 129 130 131 def getVertexByValue(self, e): """ Return the vertex that has element of value e. "" # ... Implement this (6) for VERTEX in self._vertices: if VERTEX.element()==e: return VERTEX return None #replace to your one code 132 133 134 135 136 137 138 def incidentEdges(self, v): " " Return a collection of all edges that are incident to vertex v in the graph. # ... Implement this (7) INCI EDGES=[] for EDGES in self._edges: 1/CDccc icIncidonta. 139 140

151 156 140 for EDGES in self._edges: 141 if(EDGES.isIncident(v)): 142 INCI_EDGES. append(EDGES) 143 return INCI_EDGES #replace to your one code 144 145 - def print(self): 146 "" Print the edge list with the format: 147 148 print("Edge List:" ) 149 for e in self.edges(): 150 print(e) print() 152 153 def insert_vertex(self, x=None): 154 """Insert and return a new Vertex with element x."" 155 V = Vertex(x) self._vertices.append(v) 157 return v 158 159- def insert_edge(self, u, v, x=None): 160 ""Insert and return a new Edge from u to v with auxiliary element x. 161 162 Raise a ValueError if u and v are not vertices of the graph. 163 Raise a ValueError if u and v are already adjacent. 164 165 if self.getEdge(u, v) is not None: # includes error checking 166 raise ValueError('u and v are already adjacent'), 167 e = Edge(u, v, x) 168 self._edges.append(e) 169 170 def DFS_utility (gv): 171 v.setLabel("VISITED") 172 for edge in g.incidentEdges(v): 173 if (edge.getLabel()=="UNEXPLORED"): 174 next_vert=edge.opposite(v) 175 if(next_vert.getLabel()=="UNEXPLORED"):

174 179 Search algorithm from the otasg nanalo return th 183 next_vert=edge.opposite(v) 175 if(next_vert.getLabel() == "UNEXPLORED"): 176 edge.setLabel("DISCOVERY") 177 DFS_utility(g, next_vert) 178 else: edge.setLabel("BACK") 180 181 - def DFS(g): 182 # Implement the depth-first search algorithm from the class notes. # Collect the discovered edges that form the DFS tree of 'g' and return the collection # ... Implement this (8) v=g.vertices()[]; 186 DFS_utility(g,v); Discovery_edge_list=[] 188- for edge in g.edges(): 189 if(edge.getLabel()=="DISCOVERY"); 190 Discovery edge_list.append(edge); return Discovery edge list #return [] #replace to your one code 193 184 185 187 191 192 194 195 #-- Main method 196 v_elements = ["A", "B","c","D", "E"] 197 g = Graph() 198 for v in range(5): 199 g.insert vertex(v_elements[v]) 200 201 g.insert_edge(g.getVertexByValue("A"),g.getVertexByValue("B") 202 g.insert_edge(g.getVertexByValue("A"),g.getVertexByValue("C") 203 g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("C") 204 g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("D")) 205 g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("E") 206 g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("D")) 207 g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("E")) 208 209 # Print all edges

203 g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("C")) 204 g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("D")) 205 g.insert_edge(g.getVertexByValue("B"),g.getVertexByValue("E")) 206 g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("D")) 207 g.insert_edge(g.getVertexByValue("C"),g.getVertexByValue("E")) 208 209 # Print all edges 210 print("Edges:", g.edgeCount()); 211 for e in g.edges(): 212 print(e) 213 print() 214 215 # Print all vertices 216 print("vertices:", g.vertexCount()) 217 for v in g.vertices(): 218 print(v) 219 print() 220 221 # Print the actual graph (in matrix form) 222 g.print() 223 print() 224 225 # Call DFS on g, to get the discovery edges 226 discovery = DFS (8) 227 print("DFS edges:") 228 for e in discovery: 229 print(e) 230 print() 231 232 # Determine whether the graph is connected 233 #... Implement this (9) 234 isconnec=True 235» for vert in g.vertices(): 236 if(vert.getLabel()=="UNEXPLORED"): 237 D isconnec=False 238 print("Graph is connected:", isconnec) #replace to your one code

OUTPUT SNAPSHOT:

Edges: 7 (A, B, UNEXPLORED) (A, C, UNEXPLORED) (B, C, UNEXPLORED) (B, D, UNEXPLORED) (B, E, UNEXPLORED) (C, D, UNEXPLORED) (C, E, UNEXPLORED) Vertices: 5 (A, UNEXPLORED) (B, UNEXPLORED) (C, UNEXPLORED) (D, UNEXPLORED) (E, UNEXPLORED) Edge List: (A, B, UNEXPLORED) (A, C, UNEXPLORED) (B, C, UNEXPLORED) (B, D, UNEXPLORED) (B, E, UNEXPLORED) (C, D, UNEXPLORED) (C, E, UNEXPLORED) DFS edges: (A, B, DISCOVERY) (B, C, DISCOVERY) (C, D, DISCOVERY) (C, E, DISCOVERY) Graph is connected: True ...Program finished with exit code o Press ENTER to exit console.