Graph class

The Graph Abstract Data Type describes a strategy for using Vertex objects to describe a Graph.

The Graph class describes the nodes in the graph. Its ADT includes:

• Graph() - creates a new empty graph
• addVertex(newVertex) - adds a new Vertex object to the Graph
• add_edge(fromVertex, toVertex) - creates a new edge connecting two vertices
• add_edge(fromVertex, toVertex, weight) - creates a new edge with a weight
• getVertex(vertexKey) - returns the Vertex object identified by vertexKey.
• getVertices() - returns a list of all vertices in the Graph
• in - returns True in expressions of the form vertex in graph

In this Python implementation, the dictionary in the Graph class includes a series of values that are mapped to the keys of Vertex objects.

Use the following code as a template for writing the Graph class.

class Graph(object):
    """Describes the Graph class, which is primarily a dictionary  
    mapping vertex names to Vertex objects, along with a few methods 
    that can be used to manipulate them.
    """
    def __init__(self):
        """Initializes an empty dictionary of Vertex objects
        """

    def add_vertex(self, key):
        """Creates a new "key-value" dictionary entry with the string "key"
        key as the dictionary key, and the Vertex object itself as the value. 
        Returns the new vertex as a result.
        """

    def get_vertex(self, key):
        """Looks for the key in the dictionary of Vertex objects, and 
        returns the Vertex if found. Otherwise, returns None.
        """

    def __contains__(self, key):
        """This 'dunder' expression is written so we can use Python's "in" 
        operation: If the parameter 'key' is in the dictionary of vertices,
        the value of "key in my_graph" will be True, otherwise False.
        """


    def add_edge(self, from_vertex, to_vertex, weight=0):
        """Adds an edge connecting two vertices (specified by key parameters)
        by modifying those vertex objects. Note that the weight can be 
        specified as well, but if one isn't specified, the value of weight 
        will be the default value of 0.
        """

    def get_vertices(self):
        """Returns a list of the Vertex keys"""

    def __iter__(self):
        """Another 'dunder' expression that allows us to iterate through
        the list of vertices.
        Example use:
        for vert in graph:  # Python understands this now!
            print(v)
        """
        return iter(self.vertex_dict.values())

Check your Graph class by running these commands on it:

g = Graph()
for i in range(6):
    g.add_vertex(i)  # Create vertexes and add to the graph
# Add a series of edges between the vertices
g.add_edge(0,1,5)
g.add_edge(0,5,2)
g.add_edge(1,2,4)
g.add_edge(2,3,9)
g.add_edge(3,4,7)
g.add_edge(3,5,3)
g.add_edge(4,0,1)
g.add_edge(5,4,8)
g.add_edge(5,2,1)
# Display all the vertices (possible because `iter` is defined)
for vertex in g:
    print(vertex)
for vertex1 in g:
   for vertex2 in vertex1.getConnections():
       print("( %s , %s )" % (vertex1.get_id(), vertex2.get_id()))