graph = { "a" : {"c"},
          "b" : {"c", "e"},
          "c" : {"a", "b", "d", "e"},
          "d" : {"c"},
          "e" : {"c", "b"},
          "f" : {}
        }

# The keys of the dictionary above are the nodes of our graph. The corresponding values are sets with the nodes, which are connected by an edge. 
# A set is better than a list or a tuple, because this way, we can have only one edge between two nodes. There is no simpler and more elegant way
# to represent a graph.
# An edge can also be ideally implemented as a set with two elements, i.e. the end nodes. This is ideal for undirected graphs. 
# For directed graphs we would prefer lists or tuples to implement edges.

# A simple Python graph class, demonstrating the essential facts and functionalities of graphs.

class Graph(object):

    def __init__(self, graph_dict=None):
        # initializes a graph object. If no dictionary or None is given, an empty dictionary will be used.
        if graph_dict == None:
            graph_dict = {}
        self._graph_dict = graph_dict

# returns a list of all the edges of a vertice.

    def edges(self, vertice):
        return self._graph_dict[vertice]

# returns the vertices of a graph as a set.

    def all_vertices(self):
        return set(self._graph_dict.keys())

# returns the edges of a graph.

    def all_edges(self):
        return self.__generate_edges()

# If the vertex "vertex" is not in self._graph_dict, a key "vertex" with an empty list as a value is added to the dictionary.
# Otherwise nothing has to be done.

    def add_vertex(self, vertex):
        if vertex not in self._graph_dict:
            self._graph_dict[vertex] = []

# assumes that edge is of type set, tuple or list; between two vertices can be multiple edges!

    def add_edge(self, edge):
        edge = set(edge)
        vertex1, vertex2 = tuple(edge)
        for x, y in [(vertex1, vertex2), (vertex2, vertex1)]:
            if x in self._graph_dict:
                self._graph_dict[x].add(y)   #as soon as the value is a list, this fails, i.e. when the vertex has just been added in line 31.
                print(type(self._graph_dict[x]))
            else:
                self._graph_dict[x] = [y]   # once a new pair is added with x as key, line 40 fails, too.

    def __generate_edges(self):

        # A static method generating the edges of the graph "graph". Edges are represented as sets with one (a loop back to the vertex) or two vertices.
        edges = []
        for vertex in self._graph_dict:
            for neighbour in self._graph_dict[vertex]:
                if {neighbour, vertex} not in edges:
                    edges.append({vertex, neighbour})
        return edges

    def __iter__(self):
        self._iter_obj = iter(self._graph_dict)
        return self._iter_obj

    def __next__(self):
        # allows us to iterate over the vertices.
        return next(self._iter_obj)

    def __str__(self):
        res = "vertices: "
        for k in self._graph_dict:
            res += str(k) + " "
        res += "\nedges: "
        for edge in self.__generate_edges():
            res += str(edge) + " "
        return res

g = {"a": {"d"},
     "b": {"c"},
     "c": {"b", "c", "d", "e"},
     "d": {"a", "c"},
     "e": {"c"},
     "f": {}
     }

graph = Graph(g)

for vertice in graph:
    print(f"Edges of vertice {vertice}: ", graph.edges(vertice))

graph.add_edge({"ab", "fg"})
graph.add_edge({"xyz", "bla"})
# graph.add_edge({"a", "z"})    # here the error in line 40 above gets revealed. 

print("")
print("Vertices of graph:")
print(graph.all_vertices())

print("Edges of graph:")
print(graph.all_edges())

print("Add vertex:")
graph.add_vertex("z")

print("Add an edge:")
graph.add_edge({"a", "d"})

print("Vertices of graph:")
print(graph.all_vertices())

print("Edges of graph:")
print(graph.all_edges())

print('Adding an edge {"x","y"} with new vertices:')
graph.add_edge({"x","y"})

print("Vertices of graph:")

print(graph.all_vertices())

print("Edges of graph:")

print(graph.all_edges())

j = {"ab", "fg"}
vertex1, vertex2 = tuple(j)
for x, y in [(vertex1, vertex2), (vertex2, vertex1)]:
    print(x,y)

l = {"a", "z"}
vertex1, vertex2 = tuple(l)
for x, y in [(vertex1, vertex2), (vertex2, vertex1)]:
    print(x,y)

# We will design a new class Graph2 now, which inherits from our previously defined graph Graph and we add the following methods to it:
# vertex_degree, find_isolated_vertices, delta, degree_sequence.


class Graph2(Graph):
    
    def vertex_degree(self, vertex):
# The degree of a vertex is the number of edges connecting it, i.e. the number of adjacent vertices. Loops are counted double, i.e. every
# occurence of vertex in the list of adjacent vertices.
        degree =  len(self._graph_dict[vertex]) 
        if vertex in self._graph_dict[vertex]:
            degree += 1
        return degree

    def find_isolated_vertices(self):
        """ returns a list of isolated vertices. """
        graph = self._graph_dict
        isolated = []
        for vertex in graph:
            print(isolated, vertex)
            if not graph[vertex]:
                isolated += [vertex]
        return isolated
        
    def Delta(self):
        """ the maximum degree of the vertices """
        max = 0
        for vertex in self._graph_dict:
            vertex_degree = self.vertex_degree(vertex)
            if vertex_degree > max:
                max = vertex_degree
        return max
    
    def degree_sequence(self):
        """ calculates the degree sequence """
        seq = []
        for vertex in self._graph_dict:
            seq.append(self.vertex_degree(vertex))
        seq.sort(reverse=True)
        return tuple(seq)