Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

Files in the same folder ------------------------ Depending on which implementat

ID: 3756546 • Letter: F

Question


Files in the same folder ------------------------ Depending on which implementation you use for part 1, you may need to include other files in the same folder.
Imports ------- Depending on which implementation you use for part 1, you may need to include additional import statement(s).
Part 1 ------ This week's example files include 2 different implementations of this function. Choose one and copy that implementation here.
Part 2 ------ The courses and their prerequisites are shown in a comment. The courses are each named with a single capital letter.
Part 3 ------ The courses and their prerequisites are shown in a comment.
Part 4 ------ Use an appropriate graph iterator.
Part 5 ------ Use an appropriate graph iterator.
Part 6 ------ If you used the stack-based implementation of the topologicalSort() function, it can produce a different, correct ordering for each run of your program.
The following are some of the possible correct orderings: B A C E D F G H A C E B D F G H A B C E D F G H A B C D F E G H B A C D F E G H
~~~~~~~~~~~~~~~~~~
# This program exercises graphs.
# Replace any "<your code>" comments with your own code statement(s) # to accomplish the specified task. # Do not change any other code.
# The following files must be in the same folder: # abstractcollection.py # graph.py
from graph import LinkedDirectedGraph
# Part 1: # Complete the following function: def topologicalSort(graph): # <your code>
graph = LinkedDirectedGraph()
# The graph represents the following course prerequisites: # A requires nothing # B requires nothing # C requires A # D requires A, B, and C # E requires C # F requires B and D # G requires E and F # H requires C, F, and G
# Part 2: # Add the vertices: # <your code>
# Part 3: # Add the edges: # <your code>
print("Graph:") print(graph) print()
print("Courses:") # Part 4: # Display each vertex on a separate line: # <your code> print()
print("Prerequisites:") # Part 5: # Display each edge on a separate line: # <your code> print()
print("One possible order to take the courses:") # Part 6: # Display the courses in prerequisite (topological) order: # <your code> print()
~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0    def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1
~~~~~~~~~~~~~~~
""" File: graph.py Copyright 2015 by Ken Lambert
Adds the in, +, ==, and clone operations to support graph-specific behavior. """
from abstractcollection import AbstractCollection
class LinkedEdge(object):    # An edge has a source vertex, a destination vertex, # a weight, and a mark attribute.
def __init__(self, fromVertex, toVertex, weight = None):    self._vertex1 = fromVertex self._vertex2 = toVertex self._weight = weight self._mark = False    def clearMark(self): """Clears the mark on the edge.""" self._mark = False    def __eq__(self, other): """Two edges are equal if they connect the same vertices.""" if self is other: return True if type(self) != type(other): return False return self._vertex1 == other._vertex1 and self._vertex2 == other._vertex2
def getFromVertex(self): # Derrf Seitz 12/17/2015 """Returns the edge's origin vertex.""" return self._vertex1    def getOtherVertex(self, thisVertex): """Returns the vertex opposite thisVertex.""" if thisVertex == None or thisVertex == self._vertex2: return self._vertex1 else: return self._vertex2
def getToVertex(self): """Returns the edge's destination vertex.""" return self._vertex2    def getWeight(self): """Returns the edge's weight.""" return self._weight    def isMarked(self): """Returns True if the edge is marked or False otherwise.""" return self._mark    def setMark(self): """Sets the mark on the edge.""" self._mark = True    def setWeight(self, weight): """Sets the weight on the edge to weight.""" self._weight = weight       def __str__(self): """Returns the string representation of the edge.""" return str(self._vertex1) + ">" + str(self._vertex2) + ":" + str(self._weight)
class LinkedVertex(object):
# A vertex has a label, a list of incident edges, # and a mark attribute.
def __init__(self, label): self._label = label self._edgeList = list() self._mark = False
def clearMark(self): """Clears the mark on the vertex.""" self._mark = False;    def getLabel(self): """Returns the label of the vertex.""" return self._label    def isMarked(self): """Returns True if the vertex is marked or False otherwise.""" return self._mark    def setLabel(self, label, g): """Sets the vertex's label to label.""" g._vertices.pop(self._label, None) g._vertices[label] = self self._label = label
def setMark(self): """Sets the mark on the vertex.""" self._mark = True    def __str__(self): """Returns the string representation of the vertex.""" return str(self._label)
def __eq__(self, other): """Two vertices are equal if they have the same labels.""" if self is other: return True if type(self) != type(other): return False return self.getLabel() == other.getLabel()    def __hash__(self): # Derrf Seitz 12/16/2015 """Hash method for a vertex.""" return hash(self._label)
# Methods used by LinkedGraph    def addEdgeTo(self, toVertex, weight): """Connects the vertices with an edge.""" edge = LinkedEdge(self, toVertex, weight) self._edgeList.append(edge)    def getEdgeTo(self, toVertex): """Returns the connecting edge if it exists, or None otherwise.""" edge = LinkedEdge(self, toVertex) try: return self._edgeList[self._edgeList.index(edge)] except: return None
def incidentEdges(self): """Returns the incident edges of this vertex.""" return iter(self._edgeList)    def neighboringVertices(self): """Returns the neighboring vertices of this vertex.""" vertices = list() for edge in self._edgeList: vertices.append(edge.getOtherVertex(self)) return iter(vertices)    def removeEdgeTo(self, toVertex): """Returns True if the edge exists and is removed, or False otherwise.""" edge = LinkedEdge(self, toVertex) if edge in self._edgeList: self._edgeList.remove(edge) return True else: return False

class LinkedDirectedGraph(AbstractCollection):
# A graph has a count of vertices, a count of edges, # and a dictionary of label/vertex pairs.
def __init__(self, sourceCollection = None): self._edgeCount = 0 self._vertices = {} AbstractCollection.__init__(self, sourceCollection)    # in, ==, +, and clone operations
def __contains__(self, item): """Returns True if item is a label in a vertex, or False otherwise.""" for vertex in self: if vertex.getLabel() == item: return True return False
def clone(self): """Returns an exact copy of self, including vertex labels, edges connecting vertices, and edge weights.""" newGraph = type(self)(map(lambda vertex: vertex.getLabel(), self)) for vertex in self: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __add__(self, other): """Returns a new collection consisting of the items in self and other. This will be a graph with the contents of the operand graphs as separate components. Precondition: the labels in the two graph operands are disjoint. Raises: AttributeError if the labels in the two operand graphs are not disjoint.""" newGraph = self.clone() for vertex in other: newGraph.add(vertex.getLabel()) for vertex in other: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __eq__(self, other): """Returns True if self and other are identical, or True if self and other are of the same type, have the same number of vertices, and these vertices are connected in the same manner (including same labels and edge weights).""" # Check simple criteria first if self is other: return True if type(self) != type(other): return False if len(self) != len(other): return False for vertex in self: # All vertex labels must match if not vertex.getLabel() in other: print("Mismatched vertices") return False # Vertices with the same labels must have the same # incident edges otherVertex = other.getVertex(vertex.getLabel()) selfEdges = list(vertex.incidentEdges()) otherEdges = list(otherVertex.incidentEdges()) if len(selfEdges) != len(otherEdges): return False for edge in selfEdges: found = False for otherEdge in otherEdges: if edge == otherEdge and edge.getWeight() == otherEdge.getWeight(): found = True break if not found: return False return True
# Methods for clearing, marks, sizes, string rep
def clear(self): """Clears the graph.""" self._size = 0 self._edgeCount = 0 self._vertices = {}
def clearEdgeMarks(self): """Clears all the edge marks.""" for edge in self.edges(): edge.clearMark()    def clearVertexMarks(self): """Clears all the vertex marks.""" for vertex in self.vertices(): vertex.clearMark()    def sizeEdges(self): """Returns the number of edges.""" return self._edgeCount    def sizeVertices(self): """Returns the number of vertices.""" return len(self)    def __str__(self): """Returns the string representation of the graph.""" result = str(len(self)) + " Vertices: " for vertex in self._vertices: result += " " + str(vertex) result += " "; result += str(self.sizeEdges()) + " Edges: " for edge in self.edges(): result += " " + str(edge) return result
def add(self, label): """For compatibility with other collections.""" self.addVertex(label)
# Vertex related methods    def addVertex(self, label): """Precondition: a vertex with label must not already be in the graph. Raises: AttibuteError if a vertex with label is already in the graph.""" if self.containsVertex(label): raise AttributeError("Label " + str(label) + " already in graph.""") self._vertices[label] = LinkedVertex(label) self._size += 1    def containsVertex (self, label): return label in self._vertices    def getVertex(self, label): """Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" if not self.containsVertex(label): raise AttributeError("Label " + str(label) + " not in graph.""") return self._vertices[label]    def removeVertex(self, label): """Returns True if the vertex was removed, or False otherwise.""" removedVertex = self._vertices.pop(label, None) if removedVertex is None: return False    # Examine all other vertices to remove edges # directed at the removed vertex for vertex in self.vertices(): if vertex.removeEdgeTo(removedVertex): self._edgeCount -= 1
# Examine all edges from the removed vertex to others for edge in removedVertex.incidentEdges(): self._edgeCount -= 1 self._size -= 1 return True    # Methods related to edges
def addEdge(self, fromLabel, toLabel, weight): """Connects the vertices with an edge with the given weight. Preconditions: vertices with fromLabel and toLabel must already be in the graph. The vertices must not already be connected by an edge. Raises: AttibuteError if the vertices are not already in the graph or they are already connected.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel) if self.getEdge(fromLabel, toLabel): raise AttributeError("An edge already connects " + str(fromLabel) + " and " + str(toLabel)) fromVertex.addEdgeTo(toVertex, weight) self._edgeCount += 1    def containsEdge(self, fromLabel, toLabel): """Returns True if an edge connects the vertices, or False otherwise.""" return self.getEdge(fromLabel, toLabel) != None    def getEdge(self, fromLabel, toLabel): """Returns the edge connecting the two vertices, or None if no edge exists. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    return fromVertex.getEdgeTo(toVertex)    def removeEdge (self, fromLabel, toLabel): """Returns True if the edge was removed, or False otherwise. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    edgeRemovedFlg = fromVertex.removeEdgeTo(toVertex) if edgeRemovedFlg: self._edgeCount -= 1 return edgeRemovedFlg
# Iterators    def __iter__(self): """Supports iteration over a view of self (the vertices).""" return self.vertices()
def edges(self): """Supports iteration over the edges in the graph.""" result = list() for vertex in self.vertices(): result += list(vertex.incidentEdges()) return iter(result)    def vertices(self): """Supports iteration over the vertices in the graph.""" return iter(self._vertices.values())
def incidentEdges(self, label): """Supports iteration over the incident edges of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).incidentEdges()    def neighboringVertices(self, label): """Supports iteration over the neighboring vertices of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).neighboringVertices()    ~~~~~~~~~~~~~~~~~
Output
Graph: 8 Vertices: H A B C E D F G 12 Edges: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
Courses: H A B C E D F G
Prerequisites: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
One possible order to take the courses: B A C E D F G H
Files in the same folder ------------------------ Depending on which implementation you use for part 1, you may need to include other files in the same folder.
Imports ------- Depending on which implementation you use for part 1, you may need to include additional import statement(s).
Part 1 ------ This week's example files include 2 different implementations of this function. Choose one and copy that implementation here.
Part 2 ------ The courses and their prerequisites are shown in a comment. The courses are each named with a single capital letter.
Part 3 ------ The courses and their prerequisites are shown in a comment.
Part 4 ------ Use an appropriate graph iterator.
Part 5 ------ Use an appropriate graph iterator.
Part 6 ------ If you used the stack-based implementation of the topologicalSort() function, it can produce a different, correct ordering for each run of your program.
The following are some of the possible correct orderings: B A C E D F G H A C E B D F G H A B C E D F G H A B C D F E G H B A C D F E G H
~~~~~~~~~~~~~~~~~~
# This program exercises graphs.
# Replace any "<your code>" comments with your own code statement(s) # to accomplish the specified task. # Do not change any other code.
# The following files must be in the same folder: # abstractcollection.py # graph.py
from graph import LinkedDirectedGraph
# Part 1: # Complete the following function: def topologicalSort(graph): # <your code>
graph = LinkedDirectedGraph()
# The graph represents the following course prerequisites: # A requires nothing # B requires nothing # C requires A # D requires A, B, and C # E requires C # F requires B and D # G requires E and F # H requires C, F, and G
# Part 2: # Add the vertices: # <your code>
# Part 3: # Add the edges: # <your code>
print("Graph:") print(graph) print()
print("Courses:") # Part 4: # Display each vertex on a separate line: # <your code> print()
print("Prerequisites:") # Part 5: # Display each edge on a separate line: # <your code> print()
print("One possible order to take the courses:") # Part 6: # Display the courses in prerequisite (topological) order: # <your code> print()
~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0    def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1
~~~~~~~~~~~~~~~
""" File: graph.py Copyright 2015 by Ken Lambert
Adds the in, +, ==, and clone operations to support graph-specific behavior. """
from abstractcollection import AbstractCollection
class LinkedEdge(object):    # An edge has a source vertex, a destination vertex, # a weight, and a mark attribute.
def __init__(self, fromVertex, toVertex, weight = None):    self._vertex1 = fromVertex self._vertex2 = toVertex self._weight = weight self._mark = False    def clearMark(self): """Clears the mark on the edge.""" self._mark = False    def __eq__(self, other): """Two edges are equal if they connect the same vertices.""" if self is other: return True if type(self) != type(other): return False return self._vertex1 == other._vertex1 and self._vertex2 == other._vertex2
def getFromVertex(self): # Derrf Seitz 12/17/2015 """Returns the edge's origin vertex.""" return self._vertex1    def getOtherVertex(self, thisVertex): """Returns the vertex opposite thisVertex.""" if thisVertex == None or thisVertex == self._vertex2: return self._vertex1 else: return self._vertex2
def getToVertex(self): """Returns the edge's destination vertex.""" return self._vertex2    def getWeight(self): """Returns the edge's weight.""" return self._weight    def isMarked(self): """Returns True if the edge is marked or False otherwise.""" return self._mark    def setMark(self): """Sets the mark on the edge.""" self._mark = True    def setWeight(self, weight): """Sets the weight on the edge to weight.""" self._weight = weight       def __str__(self): """Returns the string representation of the edge.""" return str(self._vertex1) + ">" + str(self._vertex2) + ":" + str(self._weight)
class LinkedVertex(object):
# A vertex has a label, a list of incident edges, # and a mark attribute.
def __init__(self, label): self._label = label self._edgeList = list() self._mark = False
def clearMark(self): """Clears the mark on the vertex.""" self._mark = False;    def getLabel(self): """Returns the label of the vertex.""" return self._label    def isMarked(self): """Returns True if the vertex is marked or False otherwise.""" return self._mark    def setLabel(self, label, g): """Sets the vertex's label to label.""" g._vertices.pop(self._label, None) g._vertices[label] = self self._label = label
def setMark(self): """Sets the mark on the vertex.""" self._mark = True    def __str__(self): """Returns the string representation of the vertex.""" return str(self._label)
def __eq__(self, other): """Two vertices are equal if they have the same labels.""" if self is other: return True if type(self) != type(other): return False return self.getLabel() == other.getLabel()    def __hash__(self): # Derrf Seitz 12/16/2015 """Hash method for a vertex.""" return hash(self._label)
# Methods used by LinkedGraph    def addEdgeTo(self, toVertex, weight): """Connects the vertices with an edge.""" edge = LinkedEdge(self, toVertex, weight) self._edgeList.append(edge)    def getEdgeTo(self, toVertex): """Returns the connecting edge if it exists, or None otherwise.""" edge = LinkedEdge(self, toVertex) try: return self._edgeList[self._edgeList.index(edge)] except: return None
def incidentEdges(self): """Returns the incident edges of this vertex.""" return iter(self._edgeList)    def neighboringVertices(self): """Returns the neighboring vertices of this vertex.""" vertices = list() for edge in self._edgeList: vertices.append(edge.getOtherVertex(self)) return iter(vertices)    def removeEdgeTo(self, toVertex): """Returns True if the edge exists and is removed, or False otherwise.""" edge = LinkedEdge(self, toVertex) if edge in self._edgeList: self._edgeList.remove(edge) return True else: return False

class LinkedDirectedGraph(AbstractCollection):
# A graph has a count of vertices, a count of edges, # and a dictionary of label/vertex pairs.
def __init__(self, sourceCollection = None): self._edgeCount = 0 self._vertices = {} AbstractCollection.__init__(self, sourceCollection)    # in, ==, +, and clone operations
def __contains__(self, item): """Returns True if item is a label in a vertex, or False otherwise.""" for vertex in self: if vertex.getLabel() == item: return True return False
def clone(self): """Returns an exact copy of self, including vertex labels, edges connecting vertices, and edge weights.""" newGraph = type(self)(map(lambda vertex: vertex.getLabel(), self)) for vertex in self: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __add__(self, other): """Returns a new collection consisting of the items in self and other. This will be a graph with the contents of the operand graphs as separate components. Precondition: the labels in the two graph operands are disjoint. Raises: AttributeError if the labels in the two operand graphs are not disjoint.""" newGraph = self.clone() for vertex in other: newGraph.add(vertex.getLabel()) for vertex in other: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __eq__(self, other): """Returns True if self and other are identical, or True if self and other are of the same type, have the same number of vertices, and these vertices are connected in the same manner (including same labels and edge weights).""" # Check simple criteria first if self is other: return True if type(self) != type(other): return False if len(self) != len(other): return False for vertex in self: # All vertex labels must match if not vertex.getLabel() in other: print("Mismatched vertices") return False # Vertices with the same labels must have the same # incident edges otherVertex = other.getVertex(vertex.getLabel()) selfEdges = list(vertex.incidentEdges()) otherEdges = list(otherVertex.incidentEdges()) if len(selfEdges) != len(otherEdges): return False for edge in selfEdges: found = False for otherEdge in otherEdges: if edge == otherEdge and edge.getWeight() == otherEdge.getWeight(): found = True break if not found: return False return True
# Methods for clearing, marks, sizes, string rep
def clear(self): """Clears the graph.""" self._size = 0 self._edgeCount = 0 self._vertices = {}
def clearEdgeMarks(self): """Clears all the edge marks.""" for edge in self.edges(): edge.clearMark()    def clearVertexMarks(self): """Clears all the vertex marks.""" for vertex in self.vertices(): vertex.clearMark()    def sizeEdges(self): """Returns the number of edges.""" return self._edgeCount    def sizeVertices(self): """Returns the number of vertices.""" return len(self)    def __str__(self): """Returns the string representation of the graph.""" result = str(len(self)) + " Vertices: " for vertex in self._vertices: result += " " + str(vertex) result += " "; result += str(self.sizeEdges()) + " Edges: " for edge in self.edges(): result += " " + str(edge) return result
def add(self, label): """For compatibility with other collections.""" self.addVertex(label)
# Vertex related methods    def addVertex(self, label): """Precondition: a vertex with label must not already be in the graph. Raises: AttibuteError if a vertex with label is already in the graph.""" if self.containsVertex(label): raise AttributeError("Label " + str(label) + " already in graph.""") self._vertices[label] = LinkedVertex(label) self._size += 1    def containsVertex (self, label): return label in self._vertices    def getVertex(self, label): """Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" if not self.containsVertex(label): raise AttributeError("Label " + str(label) + " not in graph.""") return self._vertices[label]    def removeVertex(self, label): """Returns True if the vertex was removed, or False otherwise.""" removedVertex = self._vertices.pop(label, None) if removedVertex is None: return False    # Examine all other vertices to remove edges # directed at the removed vertex for vertex in self.vertices(): if vertex.removeEdgeTo(removedVertex): self._edgeCount -= 1
# Examine all edges from the removed vertex to others for edge in removedVertex.incidentEdges(): self._edgeCount -= 1 self._size -= 1 return True    # Methods related to edges
def addEdge(self, fromLabel, toLabel, weight): """Connects the vertices with an edge with the given weight. Preconditions: vertices with fromLabel and toLabel must already be in the graph. The vertices must not already be connected by an edge. Raises: AttibuteError if the vertices are not already in the graph or they are already connected.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel) if self.getEdge(fromLabel, toLabel): raise AttributeError("An edge already connects " + str(fromLabel) + " and " + str(toLabel)) fromVertex.addEdgeTo(toVertex, weight) self._edgeCount += 1    def containsEdge(self, fromLabel, toLabel): """Returns True if an edge connects the vertices, or False otherwise.""" return self.getEdge(fromLabel, toLabel) != None    def getEdge(self, fromLabel, toLabel): """Returns the edge connecting the two vertices, or None if no edge exists. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    return fromVertex.getEdgeTo(toVertex)    def removeEdge (self, fromLabel, toLabel): """Returns True if the edge was removed, or False otherwise. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    edgeRemovedFlg = fromVertex.removeEdgeTo(toVertex) if edgeRemovedFlg: self._edgeCount -= 1 return edgeRemovedFlg
# Iterators    def __iter__(self): """Supports iteration over a view of self (the vertices).""" return self.vertices()
def edges(self): """Supports iteration over the edges in the graph.""" result = list() for vertex in self.vertices(): result += list(vertex.incidentEdges()) return iter(result)    def vertices(self): """Supports iteration over the vertices in the graph.""" return iter(self._vertices.values())
def incidentEdges(self, label): """Supports iteration over the incident edges of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).incidentEdges()    def neighboringVertices(self, label): """Supports iteration over the neighboring vertices of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).neighboringVertices()    ~~~~~~~~~~~~~~~~~
Output
Graph: 8 Vertices: H A B C E D F G 12 Edges: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
Courses: H A B C E D F G
Prerequisites: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
One possible order to take the courses: B A C E D F G H
Files in the same folder ------------------------ Depending on which implementation you use for part 1, you may need to include other files in the same folder.
Imports ------- Depending on which implementation you use for part 1, you may need to include additional import statement(s).
Part 1 ------ This week's example files include 2 different implementations of this function. Choose one and copy that implementation here.
Part 2 ------ The courses and their prerequisites are shown in a comment. The courses are each named with a single capital letter.
Part 3 ------ The courses and their prerequisites are shown in a comment.
Part 4 ------ Use an appropriate graph iterator.
Part 5 ------ Use an appropriate graph iterator.
Part 6 ------ If you used the stack-based implementation of the topologicalSort() function, it can produce a different, correct ordering for each run of your program.
The following are some of the possible correct orderings: B A C E D F G H A C E B D F G H A B C E D F G H A B C D F E G H B A C D F E G H
~~~~~~~~~~~~~~~~~~
# This program exercises graphs.
# Replace any "<your code>" comments with your own code statement(s) # to accomplish the specified task. # Do not change any other code.
# The following files must be in the same folder: # abstractcollection.py # graph.py
from graph import LinkedDirectedGraph
# Part 1: # Complete the following function: def topologicalSort(graph): # <your code>
graph = LinkedDirectedGraph()
# The graph represents the following course prerequisites: # A requires nothing # B requires nothing # C requires A # D requires A, B, and C # E requires C # F requires B and D # G requires E and F # H requires C, F, and G
# Part 2: # Add the vertices: # <your code>
# Part 3: # Add the edges: # <your code>
print("Graph:") print(graph) print()
print("Courses:") # Part 4: # Display each vertex on a separate line: # <your code> print()
print("Prerequisites:") # Part 5: # Display each edge on a separate line: # <your code> print()
print("One possible order to take the courses:") # Part 6: # Display the courses in prerequisite (topological) order: # <your code> print()
~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0    def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1
~~~~~~~~~~~~~~~
""" File: graph.py Copyright 2015 by Ken Lambert
Adds the in, +, ==, and clone operations to support graph-specific behavior. """
from abstractcollection import AbstractCollection
class LinkedEdge(object):    # An edge has a source vertex, a destination vertex, # a weight, and a mark attribute.
def __init__(self, fromVertex, toVertex, weight = None):    self._vertex1 = fromVertex self._vertex2 = toVertex self._weight = weight self._mark = False    def clearMark(self): """Clears the mark on the edge.""" self._mark = False    def __eq__(self, other): """Two edges are equal if they connect the same vertices.""" if self is other: return True if type(self) != type(other): return False return self._vertex1 == other._vertex1 and self._vertex2 == other._vertex2
def getFromVertex(self): # Derrf Seitz 12/17/2015 """Returns the edge's origin vertex.""" return self._vertex1    def getOtherVertex(self, thisVertex): """Returns the vertex opposite thisVertex.""" if thisVertex == None or thisVertex == self._vertex2: return self._vertex1 else: return self._vertex2
def getToVertex(self): """Returns the edge's destination vertex.""" return self._vertex2    def getWeight(self): """Returns the edge's weight.""" return self._weight    def isMarked(self): """Returns True if the edge is marked or False otherwise.""" return self._mark    def setMark(self): """Sets the mark on the edge.""" self._mark = True    def setWeight(self, weight): """Sets the weight on the edge to weight.""" self._weight = weight       def __str__(self): """Returns the string representation of the edge.""" return str(self._vertex1) + ">" + str(self._vertex2) + ":" + str(self._weight)
class LinkedVertex(object):
# A vertex has a label, a list of incident edges, # and a mark attribute.
def __init__(self, label): self._label = label self._edgeList = list() self._mark = False
def clearMark(self): """Clears the mark on the vertex.""" self._mark = False;    def getLabel(self): """Returns the label of the vertex.""" return self._label    def isMarked(self): """Returns True if the vertex is marked or False otherwise.""" return self._mark    def setLabel(self, label, g): """Sets the vertex's label to label.""" g._vertices.pop(self._label, None) g._vertices[label] = self self._label = label
def setMark(self): """Sets the mark on the vertex.""" self._mark = True    def __str__(self): """Returns the string representation of the vertex.""" return str(self._label)
def __eq__(self, other): """Two vertices are equal if they have the same labels.""" if self is other: return True if type(self) != type(other): return False return self.getLabel() == other.getLabel()    def __hash__(self): # Derrf Seitz 12/16/2015 """Hash method for a vertex.""" return hash(self._label)
# Methods used by LinkedGraph    def addEdgeTo(self, toVertex, weight): """Connects the vertices with an edge.""" edge = LinkedEdge(self, toVertex, weight) self._edgeList.append(edge)    def getEdgeTo(self, toVertex): """Returns the connecting edge if it exists, or None otherwise.""" edge = LinkedEdge(self, toVertex) try: return self._edgeList[self._edgeList.index(edge)] except: return None
def incidentEdges(self): """Returns the incident edges of this vertex.""" return iter(self._edgeList)    def neighboringVertices(self): """Returns the neighboring vertices of this vertex.""" vertices = list() for edge in self._edgeList: vertices.append(edge.getOtherVertex(self)) return iter(vertices)    def removeEdgeTo(self, toVertex): """Returns True if the edge exists and is removed, or False otherwise.""" edge = LinkedEdge(self, toVertex) if edge in self._edgeList: self._edgeList.remove(edge) return True else: return False

class LinkedDirectedGraph(AbstractCollection):
# A graph has a count of vertices, a count of edges, # and a dictionary of label/vertex pairs.
def __init__(self, sourceCollection = None): self._edgeCount = 0 self._vertices = {} AbstractCollection.__init__(self, sourceCollection)    # in, ==, +, and clone operations
def __contains__(self, item): """Returns True if item is a label in a vertex, or False otherwise.""" for vertex in self: if vertex.getLabel() == item: return True return False
def clone(self): """Returns an exact copy of self, including vertex labels, edges connecting vertices, and edge weights.""" newGraph = type(self)(map(lambda vertex: vertex.getLabel(), self)) for vertex in self: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __add__(self, other): """Returns a new collection consisting of the items in self and other. This will be a graph with the contents of the operand graphs as separate components. Precondition: the labels in the two graph operands are disjoint. Raises: AttributeError if the labels in the two operand graphs are not disjoint.""" newGraph = self.clone() for vertex in other: newGraph.add(vertex.getLabel()) for vertex in other: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __eq__(self, other): """Returns True if self and other are identical, or True if self and other are of the same type, have the same number of vertices, and these vertices are connected in the same manner (including same labels and edge weights).""" # Check simple criteria first if self is other: return True if type(self) != type(other): return False if len(self) != len(other): return False for vertex in self: # All vertex labels must match if not vertex.getLabel() in other: print("Mismatched vertices") return False # Vertices with the same labels must have the same # incident edges otherVertex = other.getVertex(vertex.getLabel()) selfEdges = list(vertex.incidentEdges()) otherEdges = list(otherVertex.incidentEdges()) if len(selfEdges) != len(otherEdges): return False for edge in selfEdges: found = False for otherEdge in otherEdges: if edge == otherEdge and edge.getWeight() == otherEdge.getWeight(): found = True break if not found: return False return True
# Methods for clearing, marks, sizes, string rep
def clear(self): """Clears the graph.""" self._size = 0 self._edgeCount = 0 self._vertices = {}
def clearEdgeMarks(self): """Clears all the edge marks.""" for edge in self.edges(): edge.clearMark()    def clearVertexMarks(self): """Clears all the vertex marks.""" for vertex in self.vertices(): vertex.clearMark()    def sizeEdges(self): """Returns the number of edges.""" return self._edgeCount    def sizeVertices(self): """Returns the number of vertices.""" return len(self)    def __str__(self): """Returns the string representation of the graph.""" result = str(len(self)) + " Vertices: " for vertex in self._vertices: result += " " + str(vertex) result += " "; result += str(self.sizeEdges()) + " Edges: " for edge in self.edges(): result += " " + str(edge) return result
def add(self, label): """For compatibility with other collections.""" self.addVertex(label)
# Vertex related methods    def addVertex(self, label): """Precondition: a vertex with label must not already be in the graph. Raises: AttibuteError if a vertex with label is already in the graph.""" if self.containsVertex(label): raise AttributeError("Label " + str(label) + " already in graph.""") self._vertices[label] = LinkedVertex(label) self._size += 1    def containsVertex (self, label): return label in self._vertices    def getVertex(self, label): """Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" if not self.containsVertex(label): raise AttributeError("Label " + str(label) + " not in graph.""") return self._vertices[label]    def removeVertex(self, label): """Returns True if the vertex was removed, or False otherwise.""" removedVertex = self._vertices.pop(label, None) if removedVertex is None: return False    # Examine all other vertices to remove edges # directed at the removed vertex for vertex in self.vertices(): if vertex.removeEdgeTo(removedVertex): self._edgeCount -= 1
# Examine all edges from the removed vertex to others for edge in removedVertex.incidentEdges(): self._edgeCount -= 1 self._size -= 1 return True    # Methods related to edges
def addEdge(self, fromLabel, toLabel, weight): """Connects the vertices with an edge with the given weight. Preconditions: vertices with fromLabel and toLabel must already be in the graph. The vertices must not already be connected by an edge. Raises: AttibuteError if the vertices are not already in the graph or they are already connected.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel) if self.getEdge(fromLabel, toLabel): raise AttributeError("An edge already connects " + str(fromLabel) + " and " + str(toLabel)) fromVertex.addEdgeTo(toVertex, weight) self._edgeCount += 1    def containsEdge(self, fromLabel, toLabel): """Returns True if an edge connects the vertices, or False otherwise.""" return self.getEdge(fromLabel, toLabel) != None    def getEdge(self, fromLabel, toLabel): """Returns the edge connecting the two vertices, or None if no edge exists. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    return fromVertex.getEdgeTo(toVertex)    def removeEdge (self, fromLabel, toLabel): """Returns True if the edge was removed, or False otherwise. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    edgeRemovedFlg = fromVertex.removeEdgeTo(toVertex) if edgeRemovedFlg: self._edgeCount -= 1 return edgeRemovedFlg
# Iterators    def __iter__(self): """Supports iteration over a view of self (the vertices).""" return self.vertices()
def edges(self): """Supports iteration over the edges in the graph.""" result = list() for vertex in self.vertices(): result += list(vertex.incidentEdges()) return iter(result)    def vertices(self): """Supports iteration over the vertices in the graph.""" return iter(self._vertices.values())
def incidentEdges(self, label): """Supports iteration over the incident edges of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).incidentEdges()    def neighboringVertices(self, label): """Supports iteration over the neighboring vertices of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).neighboringVertices()    ~~~~~~~~~~~~~~~~~
Output
Graph: 8 Vertices: H A B C E D F G 12 Edges: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
Courses: H A B C E D F G
Prerequisites: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
One possible order to take the courses: B A C E D F G H
Files in the same folder ------------------------ Depending on which implementation you use for part 1, you may need to include other files in the same folder.
Imports ------- Depending on which implementation you use for part 1, you may need to include additional import statement(s).
Part 1 ------ This week's example files include 2 different implementations of this function. Choose one and copy that implementation here.
Part 2 ------ The courses and their prerequisites are shown in a comment. The courses are each named with a single capital letter.
Part 3 ------ The courses and their prerequisites are shown in a comment.
Part 4 ------ Use an appropriate graph iterator.
Part 5 ------ Use an appropriate graph iterator.
Part 6 ------ If you used the stack-based implementation of the topologicalSort() function, it can produce a different, correct ordering for each run of your program.
The following are some of the possible correct orderings: B A C E D F G H A C E B D F G H A B C E D F G H A B C D F E G H B A C D F E G H
~~~~~~~~~~~~~~~~~~
# This program exercises graphs.
# Replace any "<your code>" comments with your own code statement(s) # to accomplish the specified task. # Do not change any other code.
# The following files must be in the same folder: # abstractcollection.py # graph.py
from graph import LinkedDirectedGraph
# Part 1: # Complete the following function: def topologicalSort(graph): # <your code>
graph = LinkedDirectedGraph()
# The graph represents the following course prerequisites: # A requires nothing # B requires nothing # C requires A # D requires A, B, and C # E requires C # F requires B and D # G requires E and F # H requires C, F, and G
# Part 2: # Add the vertices: # <your code>
# Part 3: # Add the edges: # <your code>
print("Graph:") print(graph) print()
print("Courses:") # Part 4: # Display each vertex on a separate line: # <your code> print()
print("Prerequisites:") # Part 5: # Display each edge on a separate line: # <your code> print()
print("One possible order to take the courses:") # Part 6: # Display the courses in prerequisite (topological) order: # <your code> print() # This program exercises graphs.
# Replace any "<your code>" comments with your own code statement(s) # to accomplish the specified task. # Do not change any other code.
# The following files must be in the same folder: # abstractcollection.py # graph.py
from graph import LinkedDirectedGraph
# Part 1: # Complete the following function: def topologicalSort(graph): # <your code>
graph = LinkedDirectedGraph()
# The graph represents the following course prerequisites: # A requires nothing # B requires nothing # C requires A # D requires A, B, and C # E requires C # F requires B and D # G requires E and F # H requires C, F, and G
# Part 2: # Add the vertices: # <your code>
# Part 3: # Add the edges: # <your code>
print("Graph:") print(graph) print()
print("Courses:") # Part 4: # Display each vertex on a separate line: # <your code> print()
print("Prerequisites:") # Part 5: # Display each edge on a separate line: # <your code> print()
print("One possible order to take the courses:") # Part 6: # Display the courses in prerequisite (topological) order: # <your code> print()
~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0    def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1 """ File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0    def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1
~~~~~~~~~~~~~~~
""" File: graph.py Copyright 2015 by Ken Lambert
Adds the in, +, ==, and clone operations to support graph-specific behavior. """
from abstractcollection import AbstractCollection
class LinkedEdge(object):    # An edge has a source vertex, a destination vertex, # a weight, and a mark attribute.
def __init__(self, fromVertex, toVertex, weight = None):    self._vertex1 = fromVertex self._vertex2 = toVertex self._weight = weight self._mark = False    def clearMark(self): """Clears the mark on the edge.""" self._mark = False    def __eq__(self, other): """Two edges are equal if they connect the same vertices.""" if self is other: return True if type(self) != type(other): return False return self._vertex1 == other._vertex1 and self._vertex2 == other._vertex2
def getFromVertex(self): # Derrf Seitz 12/17/2015 """Returns the edge's origin vertex.""" return self._vertex1    def getOtherVertex(self, thisVertex): """Returns the vertex opposite thisVertex.""" if thisVertex == None or thisVertex == self._vertex2: return self._vertex1 else: return self._vertex2
def getToVertex(self): """Returns the edge's destination vertex.""" return self._vertex2    def getWeight(self): """Returns the edge's weight.""" return self._weight    def isMarked(self): """Returns True if the edge is marked or False otherwise.""" return self._mark    def setMark(self): """Sets the mark on the edge.""" self._mark = True    def setWeight(self, weight): """Sets the weight on the edge to weight.""" self._weight = weight       def __str__(self): """Returns the string representation of the edge.""" return str(self._vertex1) + ">" + str(self._vertex2) + ":" + str(self._weight)
class LinkedVertex(object):
# A vertex has a label, a list of incident edges, # and a mark attribute.
def __init__(self, label): self._label = label self._edgeList = list() self._mark = False
def clearMark(self): """Clears the mark on the vertex.""" self._mark = False;    def getLabel(self): """Returns the label of the vertex.""" return self._label    def isMarked(self): """Returns True if the vertex is marked or False otherwise.""" return self._mark    def setLabel(self, label, g): """Sets the vertex's label to label.""" g._vertices.pop(self._label, None) g._vertices[label] = self self._label = label
def setMark(self): """Sets the mark on the vertex.""" self._mark = True    def __str__(self): """Returns the string representation of the vertex.""" return str(self._label)
def __eq__(self, other): """Two vertices are equal if they have the same labels.""" if self is other: return True if type(self) != type(other): return False return self.getLabel() == other.getLabel()    def __hash__(self): # Derrf Seitz 12/16/2015 """Hash method for a vertex.""" return hash(self._label)
# Methods used by LinkedGraph    def addEdgeTo(self, toVertex, weight): """Connects the vertices with an edge.""" edge = LinkedEdge(self, toVertex, weight) self._edgeList.append(edge)    def getEdgeTo(self, toVertex): """Returns the connecting edge if it exists, or None otherwise.""" edge = LinkedEdge(self, toVertex) try: return self._edgeList[self._edgeList.index(edge)] except: return None
def incidentEdges(self): """Returns the incident edges of this vertex.""" return iter(self._edgeList)    def neighboringVertices(self): """Returns the neighboring vertices of this vertex.""" vertices = list() for edge in self._edgeList: vertices.append(edge.getOtherVertex(self)) return iter(vertices)    def removeEdgeTo(self, toVertex): """Returns True if the edge exists and is removed, or False otherwise.""" edge = LinkedEdge(self, toVertex) if edge in self._edgeList: self._edgeList.remove(edge) return True else: return False

class LinkedDirectedGraph(AbstractCollection):
# A graph has a count of vertices, a count of edges, # and a dictionary of label/vertex pairs.
def __init__(self, sourceCollection = None): self._edgeCount = 0 self._vertices = {} AbstractCollection.__init__(self, sourceCollection)    # in, ==, +, and clone operations
def __contains__(self, item): """Returns True if item is a label in a vertex, or False otherwise.""" for vertex in self: if vertex.getLabel() == item: return True return False
def clone(self): """Returns an exact copy of self, including vertex labels, edges connecting vertices, and edge weights.""" newGraph = type(self)(map(lambda vertex: vertex.getLabel(), self)) for vertex in self: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __add__(self, other): """Returns a new collection consisting of the items in self and other. This will be a graph with the contents of the operand graphs as separate components. Precondition: the labels in the two graph operands are disjoint. Raises: AttributeError if the labels in the two operand graphs are not disjoint.""" newGraph = self.clone() for vertex in other: newGraph.add(vertex.getLabel()) for vertex in other: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __eq__(self, other): """Returns True if self and other are identical, or True if self and other are of the same type, have the same number of vertices, and these vertices are connected in the same manner (including same labels and edge weights).""" # Check simple criteria first if self is other: return True if type(self) != type(other): return False if len(self) != len(other): return False for vertex in self: # All vertex labels must match if not vertex.getLabel() in other: print("Mismatched vertices") return False # Vertices with the same labels must have the same # incident edges otherVertex = other.getVertex(vertex.getLabel()) selfEdges = list(vertex.incidentEdges()) otherEdges = list(otherVertex.incidentEdges()) if len(selfEdges) != len(otherEdges): return False for edge in selfEdges: found = False for otherEdge in otherEdges: if edge == otherEdge and edge.getWeight() == otherEdge.getWeight(): found = True break if not found: return False return True
# Methods for clearing, marks, sizes, string rep
def clear(self): """Clears the graph.""" self._size = 0 self._edgeCount = 0 self._vertices = {}
def clearEdgeMarks(self): """Clears all the edge marks.""" for edge in self.edges(): edge.clearMark()    def clearVertexMarks(self): """Clears all the vertex marks.""" for vertex in self.vertices(): vertex.clearMark()    def sizeEdges(self): """Returns the number of edges.""" return self._edgeCount    def sizeVertices(self): """Returns the number of vertices.""" return len(self)    def __str__(self): """Returns the string representation of the graph.""" result = str(len(self)) + " Vertices: " for vertex in self._vertices: result += " " + str(vertex) result += " "; result += str(self.sizeEdges()) + " Edges: " for edge in self.edges(): result += " " + str(edge) return result
def add(self, label): """For compatibility with other collections.""" self.addVertex(label)
# Vertex related methods    def addVertex(self, label): """Precondition: a vertex with label must not already be in the graph. Raises: AttibuteError if a vertex with label is already in the graph.""" if self.containsVertex(label): raise AttributeError("Label " + str(label) + " already in graph.""") self._vertices[label] = LinkedVertex(label) self._size += 1    def containsVertex (self, label): return label in self._vertices    def getVertex(self, label): """Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" if not self.containsVertex(label): raise AttributeError("Label " + str(label) + " not in graph.""") return self._vertices[label]    def removeVertex(self, label): """Returns True if the vertex was removed, or False otherwise.""" removedVertex = self._vertices.pop(label, None) if removedVertex is None: return False    # Examine all other vertices to remove edges # directed at the removed vertex for vertex in self.vertices(): if vertex.removeEdgeTo(removedVertex): self._edgeCount -= 1
# Examine all edges from the removed vertex to others for edge in removedVertex.incidentEdges(): self._edgeCount -= 1 self._size -= 1 return True    # Methods related to edges
def addEdge(self, fromLabel, toLabel, weight): """Connects the vertices with an edge with the given weight. Preconditions: vertices with fromLabel and toLabel must already be in the graph. The vertices must not already be connected by an edge. Raises: AttibuteError if the vertices are not already in the graph or they are already connected.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel) if self.getEdge(fromLabel, toLabel): raise AttributeError("An edge already connects " + str(fromLabel) + " and " + str(toLabel)) fromVertex.addEdgeTo(toVertex, weight) self._edgeCount += 1    def containsEdge(self, fromLabel, toLabel): """Returns True if an edge connects the vertices, or False otherwise.""" return self.getEdge(fromLabel, toLabel) != None    def getEdge(self, fromLabel, toLabel): """Returns the edge connecting the two vertices, or None if no edge exists. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    return fromVertex.getEdgeTo(toVertex)    def removeEdge (self, fromLabel, toLabel): """Returns True if the edge was removed, or False otherwise. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    edgeRemovedFlg = fromVertex.removeEdgeTo(toVertex) if edgeRemovedFlg: self._edgeCount -= 1 return edgeRemovedFlg
# Iterators    def __iter__(self): """Supports iteration over a view of self (the vertices).""" return self.vertices()
def edges(self): """Supports iteration over the edges in the graph.""" result = list() for vertex in self.vertices(): result += list(vertex.incidentEdges()) return iter(result)    def vertices(self): """Supports iteration over the vertices in the graph.""" return iter(self._vertices.values())
def incidentEdges(self, label): """Supports iteration over the incident edges of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).incidentEdges()    def neighboringVertices(self, label): """Supports iteration over the neighboring vertices of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).neighboringVertices()    """ File: graph.py Copyright 2015 by Ken Lambert
Adds the in, +, ==, and clone operations to support graph-specific behavior. """
from abstractcollection import AbstractCollection
class LinkedEdge(object):    # An edge has a source vertex, a destination vertex, # a weight, and a mark attribute.
def __init__(self, fromVertex, toVertex, weight = None):    self._vertex1 = fromVertex self._vertex2 = toVertex self._weight = weight self._mark = False    def clearMark(self): """Clears the mark on the edge.""" self._mark = False    def __eq__(self, other): """Two edges are equal if they connect the same vertices.""" if self is other: return True if type(self) != type(other): return False return self._vertex1 == other._vertex1 and self._vertex2 == other._vertex2
def getFromVertex(self): # Derrf Seitz 12/17/2015 """Returns the edge's origin vertex.""" return self._vertex1    def getOtherVertex(self, thisVertex): """Returns the vertex opposite thisVertex.""" if thisVertex == None or thisVertex == self._vertex2: return self._vertex1 else: return self._vertex2
def getToVertex(self): """Returns the edge's destination vertex.""" return self._vertex2    def getWeight(self): """Returns the edge's weight.""" return self._weight    def isMarked(self): """Returns True if the edge is marked or False otherwise.""" return self._mark    def setMark(self): """Sets the mark on the edge.""" self._mark = True    def setWeight(self, weight): """Sets the weight on the edge to weight.""" self._weight = weight       def __str__(self): """Returns the string representation of the edge.""" return str(self._vertex1) + ">" + str(self._vertex2) + ":" + str(self._weight)
class LinkedVertex(object):
# A vertex has a label, a list of incident edges, # and a mark attribute.
def __init__(self, label): self._label = label self._edgeList = list() self._mark = False
def clearMark(self): """Clears the mark on the vertex.""" self._mark = False;    def getLabel(self): """Returns the label of the vertex.""" return self._label    def isMarked(self): """Returns True if the vertex is marked or False otherwise.""" return self._mark    def setLabel(self, label, g): """Sets the vertex's label to label.""" g._vertices.pop(self._label, None) g._vertices[label] = self self._label = label
def setMark(self): """Sets the mark on the vertex.""" self._mark = True    def __str__(self): """Returns the string representation of the vertex.""" return str(self._label)
def __eq__(self, other): """Two vertices are equal if they have the same labels.""" if self is other: return True if type(self) != type(other): return False return self.getLabel() == other.getLabel()    def __hash__(self): # Derrf Seitz 12/16/2015 """Hash method for a vertex.""" return hash(self._label)
# Methods used by LinkedGraph    def addEdgeTo(self, toVertex, weight): """Connects the vertices with an edge.""" edge = LinkedEdge(self, toVertex, weight) self._edgeList.append(edge)    def getEdgeTo(self, toVertex): """Returns the connecting edge if it exists, or None otherwise.""" edge = LinkedEdge(self, toVertex) try: return self._edgeList[self._edgeList.index(edge)] except: return None
def incidentEdges(self): """Returns the incident edges of this vertex.""" return iter(self._edgeList)    def neighboringVertices(self): """Returns the neighboring vertices of this vertex.""" vertices = list() for edge in self._edgeList: vertices.append(edge.getOtherVertex(self)) return iter(vertices)    def removeEdgeTo(self, toVertex): """Returns True if the edge exists and is removed, or False otherwise.""" edge = LinkedEdge(self, toVertex) if edge in self._edgeList: self._edgeList.remove(edge) return True else: return False

class LinkedDirectedGraph(AbstractCollection):
# A graph has a count of vertices, a count of edges, # and a dictionary of label/vertex pairs.
def __init__(self, sourceCollection = None): self._edgeCount = 0 self._vertices = {} AbstractCollection.__init__(self, sourceCollection)    # in, ==, +, and clone operations
def __contains__(self, item): """Returns True if item is a label in a vertex, or False otherwise.""" for vertex in self: if vertex.getLabel() == item: return True return False
def clone(self): """Returns an exact copy of self, including vertex labels, edges connecting vertices, and edge weights.""" newGraph = type(self)(map(lambda vertex: vertex.getLabel(), self)) for vertex in self: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __add__(self, other): """Returns a new collection consisting of the items in self and other. This will be a graph with the contents of the operand graphs as separate components. Precondition: the labels in the two graph operands are disjoint. Raises: AttributeError if the labels in the two operand graphs are not disjoint.""" newGraph = self.clone() for vertex in other: newGraph.add(vertex.getLabel()) for vertex in other: for neighbor in vertex.neighboringVertices(): edge = vertex.getEdgeTo(neighbor) newGraph.addEdge(vertex.getLabel(), neighbor.getLabel(), edge.getWeight()) return newGraph
def __eq__(self, other): """Returns True if self and other are identical, or True if self and other are of the same type, have the same number of vertices, and these vertices are connected in the same manner (including same labels and edge weights).""" # Check simple criteria first if self is other: return True if type(self) != type(other): return False if len(self) != len(other): return False for vertex in self: # All vertex labels must match if not vertex.getLabel() in other: print("Mismatched vertices") return False # Vertices with the same labels must have the same # incident edges otherVertex = other.getVertex(vertex.getLabel()) selfEdges = list(vertex.incidentEdges()) otherEdges = list(otherVertex.incidentEdges()) if len(selfEdges) != len(otherEdges): return False for edge in selfEdges: found = False for otherEdge in otherEdges: if edge == otherEdge and edge.getWeight() == otherEdge.getWeight(): found = True break if not found: return False return True
# Methods for clearing, marks, sizes, string rep
def clear(self): """Clears the graph.""" self._size = 0 self._edgeCount = 0 self._vertices = {}
def clearEdgeMarks(self): """Clears all the edge marks.""" for edge in self.edges(): edge.clearMark()    def clearVertexMarks(self): """Clears all the vertex marks.""" for vertex in self.vertices(): vertex.clearMark()    def sizeEdges(self): """Returns the number of edges.""" return self._edgeCount    def sizeVertices(self): """Returns the number of vertices.""" return len(self)    def __str__(self): """Returns the string representation of the graph.""" result = str(len(self)) + " Vertices: " for vertex in self._vertices: result += " " + str(vertex) result += " "; result += str(self.sizeEdges()) + " Edges: " for edge in self.edges(): result += " " + str(edge) return result
def add(self, label): """For compatibility with other collections.""" self.addVertex(label)
# Vertex related methods    def addVertex(self, label): """Precondition: a vertex with label must not already be in the graph. Raises: AttibuteError if a vertex with label is already in the graph.""" if self.containsVertex(label): raise AttributeError("Label " + str(label) + " already in graph.""") self._vertices[label] = LinkedVertex(label) self._size += 1    def containsVertex (self, label): return label in self._vertices    def getVertex(self, label): """Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" if not self.containsVertex(label): raise AttributeError("Label " + str(label) + " not in graph.""") return self._vertices[label]    def removeVertex(self, label): """Returns True if the vertex was removed, or False otherwise.""" removedVertex = self._vertices.pop(label, None) if removedVertex is None: return False    # Examine all other vertices to remove edges # directed at the removed vertex for vertex in self.vertices(): if vertex.removeEdgeTo(removedVertex): self._edgeCount -= 1
# Examine all edges from the removed vertex to others for edge in removedVertex.incidentEdges(): self._edgeCount -= 1 self._size -= 1 return True    # Methods related to edges
def addEdge(self, fromLabel, toLabel, weight): """Connects the vertices with an edge with the given weight. Preconditions: vertices with fromLabel and toLabel must already be in the graph. The vertices must not already be connected by an edge. Raises: AttibuteError if the vertices are not already in the graph or they are already connected.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel) if self.getEdge(fromLabel, toLabel): raise AttributeError("An edge already connects " + str(fromLabel) + " and " + str(toLabel)) fromVertex.addEdgeTo(toVertex, weight) self._edgeCount += 1    def containsEdge(self, fromLabel, toLabel): """Returns True if an edge connects the vertices, or False otherwise.""" return self.getEdge(fromLabel, toLabel) != None    def getEdge(self, fromLabel, toLabel): """Returns the edge connecting the two vertices, or None if no edge exists. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    return fromVertex.getEdgeTo(toVertex)    def removeEdge (self, fromLabel, toLabel): """Returns True if the edge was removed, or False otherwise. Precondition: vertices with fromLabel and toLabel must already be in the graph. Raises: AttibuteError if the vertices are not already in the graph.""" fromVertex = self.getVertex(fromLabel)    toVertex = self.getVertex(toLabel)    edgeRemovedFlg = fromVertex.removeEdgeTo(toVertex) if edgeRemovedFlg: self._edgeCount -= 1 return edgeRemovedFlg
# Iterators    def __iter__(self): """Supports iteration over a view of self (the vertices).""" return self.vertices()
def edges(self): """Supports iteration over the edges in the graph.""" result = list() for vertex in self.vertices(): result += list(vertex.incidentEdges()) return iter(result)    def vertices(self): """Supports iteration over the vertices in the graph.""" return iter(self._vertices.values())
def incidentEdges(self, label): """Supports iteration over the incident edges of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).incidentEdges()    def neighboringVertices(self, label): """Supports iteration over the neighboring vertices of the given verrtex. Precondition: a vertex with label must already be in the graph. Raises: AttibuteError if a vertex with label is not already in the graph.""" return self.getVertex(label).neighboringVertices()    ~~~~~~~~~~~~~~~~~
Output
Graph: 8 Vertices: H A B C E D F G 12 Edges: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
Courses: H A B C E D F G
Prerequisites: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
One possible order to take the courses: B A C E D F G H Graph: 8 Vertices: H A B C E D F G 12 Edges: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
Courses: H A B C E D F G
Prerequisites: A>C:0 A>D:0 B>D:0 B>F:0 C>D:0 C>E:0 C>H:0 E>G:0 D>F:0 F>G:0 F>H:0 G>H:0
One possible order to take the courses: B A C E D F G H

Explanation / Answer

# Replace any "<your code>" comments with your own code statement(s)

# to accomplish the specified task.

# Do not change any other code.

# The following files must be in the same folder:

# abstractcollection.py

# graph.py

from graph import LinkedDirectedGraph

# Part 1:

# Complete the following function:

def topologicalSort(graph):

# <your code>

graph = LinkedDirectedGraph()

# The graph represents the following course prerequisites:

# A requires nothing

# B requires nothing

# C requires A

# D requires A, B, and C

# E requires C

# F requires B and D

# G requires E and F

# H requires C, F, and G

# Part 2:

# Add the vertices:

# <your code>

# Part 3:

# Add the edges:

# <your code>

print("Graph:")

print(graph)

print()

print("Courses:")

# Part 4:

# Display each vertex on a separate line:

# <your code>

print()

print("Prerequisites:")

# Part 5:

# Display each edge on a separate line:

# <your code>

print()

print("One possible order to take the courses:")

# Part 6:

# Display the courses in prerequisite (topological) order:

# <your code>

print()

~~~~~~~~~~~~~~~

"""

File: abstractcollection.py

Copyright 2015 by Ken Lambert

"""

class AbstractCollection(object):

"""An abstract collection implementation."""

# Constructor

def __init__(self, sourceCollection = None):

"""Sets the initial state of self, which includes the

contents of sourceCollection, if it's present."""

self._size = 0

self._modCount = 0

if sourceCollection:

for item in sourceCollection:

self.add(item)

# Accessor methods

def isEmpty(self):

"""Returns True if len(self) == 0, or False otherwise."""

return len(self) == 0

  

def __len__(self):

"""Returns the number of items in self."""

return self._size

def __str__(self):

"""Returns the string representation of self, using []

as delimiters."""

return "[" + ", ".join(map(str, self)) + "]"

def __eq__(self, other):

"""Returns True if self equals other,

or False otherwise.

Compares pairs of items in the two sequences

generated by the iterators on self and other."""

if self is other: return True

if type(self) != type(other) or

len(self) != len(other):

return False

otherIter = iter(other)

for item in self:

if item != next(otherIter):

return False

return True

def __add__(self, other):

"""Returns a new collection containing the contents

of self and other."""

result = type(self)(self)

for item in other:

result.add(item)

return result

def count(self, item):

"""Returns the number of instance of item in self."""

counter = 0

for nextItem in self:

if item == nextItem: counter += 1

return counter

# These methods track and update the modCount, which is used to

# prevent mutations within the context of an iterator (for loop)

def getModCount(self):

"""Returns the number of modifications to the collection."""

return self._modCount

def incModCount(self):

"""Increments the number of modifications to the collection."""

self._modCount += 1

~~~~~~~~~~~~~~~

"""

File: graph.py

Copyright 2015 by Ken Lambert

Adds the in, +, ==, and clone operations to support graph-specific behavior.

"""

from abstractcollection import AbstractCollection

class LinkedEdge(object):

  

# An edge has a source vertex, a destination vertex,

# a weight, and a mark attribute.

def __init__(self, fromVertex, toVertex, weight = None):   

self._vertex1 = fromVertex

self._vertex2 = toVertex

self._weight = weight

self._mark = False

  

def clearMark(self):

"""Clears the mark on the edge."""

self._mark = False

  

def __eq__(self, other):

"""Two edges are equal if they connect

the same vertices."""

if self is other: return True

if type(self) != type(other):

return False

return self._vertex1 == other._vertex1 and

self._vertex2 == other._vertex2

def getFromVertex(self): # Derrf Seitz 12/17/2015

"""Returns the edge's origin vertex."""

return self._vertex1

  

def getOtherVertex(self, thisVertex):

"""Returns the vertex opposite thisVertex."""

if thisVertex == None or thisVertex == self._vertex2:

return self._vertex1

else:

return self._vertex2

def getToVertex(self):

"""Returns the edge's destination vertex."""

return self._vertex2

  

def getWeight(self):

"""Returns the edge's weight."""

return self._weight

  

def isMarked(self):

"""Returns True if the edge is marked

or False otherwise."""

return self._mark

  

def setMark(self):

"""Sets the mark on the edge."""

self._mark = True

  

def setWeight(self, weight):

"""Sets the weight on the edge to weight."""

self._weight = weight   

  

def __str__(self):

"""Returns the string representation of the edge."""

return str(self._vertex1) + ">" +

str(self._vertex2) + ":" +

str(self._weight)

class LinkedVertex(object):

# A vertex has a label, a list of incident edges,

# and a mark attribute.

def __init__(self, label):

self._label = label

self._edgeList = list()

self._mark = False

def clearMark(self):

"""Clears the mark on the vertex."""

self._mark = False;

  

def getLabel(self):

"""Returns the label of the vertex."""

return self._label

  

def isMarked(self):

"""Returns True if the vertex is marked

or False otherwise."""

return self._mark

  

def setLabel(self, label, g):

"""Sets the vertex's label to label."""

g._vertices.pop(self._label, None)

g._vertices[label] = self

self._label = label

def setMark(self):

"""Sets the mark on the vertex."""

self._mark = True

  

def __str__(self):

"""Returns the string representation of the vertex."""

return str(self._label)

def __eq__(self, other):

"""Two vertices are equal if they have

the same labels."""

if self is other: return True

if type(self) != type(other): return False

return self.getLabel() == other.getLabel()

  

def __hash__(self): # Derrf Seitz 12/16/2015

"""Hash method for a vertex."""

return hash(self._label)

# Methods used by LinkedGraph

  

def addEdgeTo(self, toVertex, weight):

"""Connects the vertices with an edge."""

edge = LinkedEdge(self, toVertex, weight)

self._edgeList.append(edge)

  

def getEdgeTo(self, toVertex):

"""Returns the connecting edge if it exists, or

None otherwise."""

edge = LinkedEdge(self, toVertex)

try:

return self._edgeList[self._edgeList.index(edge)]

except:

return None

def incidentEdges(self):

"""Returns the incident edges of this vertex."""

return iter(self._edgeList)

  

def neighboringVertices(self):

"""Returns the neighboring vertices of this vertex."""

vertices = list()

for edge in self._edgeList:

vertices.append(edge.getOtherVertex(self))

return iter(vertices)

  

def removeEdgeTo(self, toVertex):

"""Returns True if the edge exists and is removed,

or False otherwise."""

edge = LinkedEdge(self, toVertex)

if edge in self._edgeList:

self._edgeList.remove(edge)

return True

else:

return False

class LinkedDirectedGraph(AbstractCollection):

# A graph has a count of vertices, a count of edges,

# and a dictionary of label/vertex pairs.

def __init__(self, sourceCollection = None):

self._edgeCount = 0

self._vertices = {}

AbstractCollection.__init__(self, sourceCollection)

  

# in, ==, +, and clone operations

def __contains__(self, item):

"""Returns True if item is a label in a vertex,

or False otherwise."""

for vertex in self:

if vertex.getLabel() == item:

return True

return False

def clone(self):

"""Returns an exact copy of self, including vertex labels,

edges connecting vertices, and edge weights."""

newGraph = type(self)(map(lambda vertex: vertex.getLabel(), self))

for vertex in self:

for neighbor in vertex.neighboringVertices():

edge = vertex.getEdgeTo(neighbor)

newGraph.addEdge(vertex.getLabel(),

neighbor.getLabel(),

edge.getWeight())

return newGraph

def __add__(self, other):

"""Returns a new collection consisting of the

items in self and other. This will be a graph with

the contents of the operand graphs as separate components.

Precondition: the labels in the two graph operands are disjoint.

Raises: AttributeError if the labels in the two operand graphs

are not disjoint."""

newGraph = self.clone()

for vertex in other:

newGraph.add(vertex.getLabel())

for vertex in other:

for neighbor in vertex.neighboringVertices():

edge = vertex.getEdgeTo(neighbor)

newGraph.addEdge(vertex.getLabel(),

neighbor.getLabel(),

edge.getWeight())

return newGraph

def __eq__(self, other):

"""Returns True if self and other are identical, or

True if self and other are of the same type, have the

same number of vertices, and these vertices are connected

in the same manner (including same labels and edge weights)."""

# Check simple criteria first

if self is other: return True

if type(self) != type(other): return False

if len(self) != len(other): return False

for vertex in self:

# All vertex labels must match

if not vertex.getLabel() in other:

print("Mismatched vertices")

return False

# Vertices with the same labels must have the same

# incident edges

otherVertex = other.getVertex(vertex.getLabel())

selfEdges = list(vertex.incidentEdges())

otherEdges = list(otherVertex.incidentEdges())

if len(selfEdges) != len(otherEdges):

return False

for edge in selfEdges:

found = False

for otherEdge in otherEdges:

if edge == otherEdge and

edge.getWeight() == otherEdge.getWeight():

found = True

break

if not found: return False

return True

# Methods for clearing, marks, sizes, string rep

def clear(self):

"""Clears the graph."""

self._size = 0

self._edgeCount = 0

self._vertices = {}

def clearEdgeMarks(self):

"""Clears all the edge marks."""

for edge in self.edges():

edge.clearMark()

  

def clearVertexMarks(self):

"""Clears all the vertex marks."""

for vertex in self.vertices():

vertex.clearMark()

  

def sizeEdges(self):

"""Returns the number of edges."""

return self._edgeCount

  

def sizeVertices(self):

"""Returns the number of vertices."""

return len(self)

  

def __str__(self):

"""Returns the string representation of the graph."""

result = str(len(self)) + " Vertices: "

for vertex in self._vertices:

result += " " + str(vertex)

result += " ";

result += str(self.sizeEdges()) + " Edges: "

for edge in self.edges():

result += " " + str(edge)

return result

def add(self, label):

"""For compatibility with other collections."""

self.addVertex(label)

# Vertex related methods

  

def addVertex(self, label):

"""Precondition: a vertex with label must not

already be in the graph.

Raises: AttibuteError if a vertex with label

is already in the graph."""

if self.containsVertex(label):

raise AttributeError("Label " + str(label) + " already in graph.""")

self._vertices[label] = LinkedVertex(label)

self._size += 1

  

def containsVertex (self, label):

return label in self._vertices

  

def getVertex(self, label):

"""Precondition: a vertex with label must already be in the graph.

Raises: AttibuteError if a vertex with label is not already in the graph."""

if not self.containsVertex(label):

raise AttributeError("Label " + str(label) + " not in graph.""")

return self._vertices[label]

  

def removeVertex(self, label):

"""Returns True if the vertex was removed, or False otherwise."""

removedVertex = self._vertices.pop(label, None)

if removedVertex is None:

return False

  

# Examine all other vertices to remove edges

# directed at the removed vertex

for vertex in self.vertices():

if vertex.removeEdgeTo(removedVertex):

self._edgeCount -= 1

# Examine all edges from the removed vertex to others

for edge in removedVertex.incidentEdges():

self._edgeCount -= 1

self._size -= 1

return True

  

# Methods related to edges

def addEdge(self, fromLabel, toLabel, weight):

"""Connects the vertices with an edge with the given weight.

Preconditions: vertices with fromLabel and toLabel must

already be in the graph.

The vertices must not already be connected by an edge.

Raises: AttibuteError if the vertices

are not already in the graph or they are already connected."""

fromVertex = self.getVertex(fromLabel)   

toVertex = self.getVertex(toLabel)

if self.getEdge(fromLabel, toLabel):

raise AttributeError("An edge already connects " +

str(fromLabel) + " and " +

str(toLabel))

fromVertex.addEdgeTo(toVertex, weight)

self._edgeCount += 1

  

def containsEdge(self, fromLabel, toLabel):

"""Returns True if an edge connects the vertices,

or False otherwise."""

return self.getEdge(fromLabel, toLabel) != None

  

def getEdge(self, fromLabel, toLabel):

"""Returns the edge connecting the two vertices, or None if

no edge exists.

Precondition: vertices with fromLabel and toLabel must

already be in the graph.

Raises: AttibuteError if the vertices

are not already in the graph."""

fromVertex = self.getVertex(fromLabel)   

toVertex = self.getVertex(toLabel)   

return fromVertex.getEdgeTo(toVertex)

  

def removeEdge (self, fromLabel, toLabel):

"""Returns True if the edge was removed, or False otherwise.

Precondition: vertices with fromLabel and toLabel must

already be in the graph.

Raises: AttibuteError if the vertices

are not already in the graph."""

fromVertex = self.getVertex(fromLabel)   

toVertex = self.getVertex(toLabel)   

edgeRemovedFlg = fromVertex.removeEdgeTo(toVertex)

if edgeRemovedFlg:

self._edgeCount -= 1

return edgeRemovedFlg

# Iterators

  

def __iter__(self):

"""Supports iteration over a view of self (the vertices)."""

return self.vertices()

def edges(self):

"""Supports iteration over the edges in the graph."""

result = list()

for vertex in self.vertices():

result += list(vertex.incidentEdges())

return iter(result)

  

def vertices(self):

"""Supports iteration over the vertices in the graph."""

return iter(self._vertices.values())

def incidentEdges(self, label):

"""Supports iteration over the incident edges of the

given verrtex.

Precondition: a vertex with label must already be in the graph.

Raises: AttibuteError if a vertex with label is not already in the graph."""

return self.getVertex(label).incidentEdges()

  

def neighboringVertices(self, label):

"""Supports iteration over the neighboring vertices of the

given verrtex.

Precondition: a vertex with label must already be in the graph.

Raises: AttibuteError if a vertex with label is not already in the graph."""

return self.getVertex(label).neighboringVertices()

Related Questions

Filer Manufacturing has 6300000 shares of common stock outstanding. The current
Question #2739887
Filer Manufacturing has 6300000 shares of common stock outstanding. The current
Question #2806546
Filer Manufacturing has 7 million shares of common stock outstanding. The curren
Question #2623842
Filer Manufacturing has 7 million shares of common stock outstanding. The curren
Question #2640111
Filer Manufacturing has 7 million shares of common stock outstanding. The curren
Question #2736456
Filer Manufacturing has 7 million shares of common stock outstanding. The curren
Question #2761662
Filer Manufacturing has 7.3 million shares of common stock outstanding. The curr
Question #2645561
Filer Manufacturing has 7.3 million shares of common stock outstanding. The curr
Question #2661123
Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
Chat Now And Get Quote

Navigate

Previous
Files https://carrington.instructure.com/courses/8999/files/folder/Case%20Study\
Next
Files need: list.h: http://pastebin.com/rFP7CMhE ll_tst.c: http://pastebin.com/u

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.